NOIP 2014 整理

Day 1

生活大爆炸版石头剪刀布

描述

石头剪刀布是常见的猜拳游戏:石头胜剪刀,剪刀胜布,布胜石头。如果两个人出拳一样,则不分胜负。在《生活大爆炸》第二季第 8 集中出现了一种石头剪刀布的升级版游戏。

升级版游戏在传统的石头剪刀布游戏的基础上,增加了两个新手势:
斯波克:《星际迷航》主角之一。
蜥蜴人:《星际迷航》中的反面角色。
这五种手势的胜负关系如表一所示,表中列出的是甲对乙的游戏结果。

现在,小 A 和小 B 尝试玩这种升级版的猜拳游戏。已知他们的出拳都是有周期性规律的,但周期长度不一定等。例如:如果小 A 以“石头-布-石头-剪刀-蜥蜴人-斯波克”长度为 $6$ 的周期出拳,那么他的出拳序列就是“石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-……”;
而如果小 B 以“剪刀-石头-布-斯波克-蜥蜴人”长度为 $5$ 的周期出拳,那么他出拳的序列就是“剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-……”
已知小 A 和小 B 一共进行 $N$ 次猜拳。每一次赢的人得 $1$ 分,输的得 $0$ 分;平局两人都
得 $0$ 分。现请你统计 $N$ 次猜拳结束之后两人的得分。

$0 < N \leq 200, 0 < NA \leq 200, 0 < NB \leq 200$

分析

模拟题。

可以先 $\Theta(n)$ 预先处理处每一个人第 $i$ 次的决策,放在 $a[], b[]$ 中,然后再 $\Theta(n)$ 计算结果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//  Created by ZJYelizaveta on Friday, September 22, 2017 AM09:22:06 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 200 + 3;
const int INF = 0x3f3f3f3f;
const int win[5][5] = {
{0, -1, 1, 1, -1},
{1, 0, -1, 1, -1},
{-1, 1, 0, -1, 1},
{-1, -1, 1, 0, 1},
{1, 1, -1, -1 ,0}
};
int n, s1, s2;
int r1[MAX_N], r2[MAX_N];
int a[MAX_N], b[MAX_N];


int main()
{
n = readIn<int>(), s1 = readIn<int>(), s2 = readIn<int>();
for (int i = 0; i < s1; ++i) r1[i] = readIn<int>();
for (int i = 0; i < s2; ++i) r2[i] = readIn<int>();

int cnt1 = n / s1, cnt2 = n / s2;
for (int i = 0; i < cnt1 * s1; ++i) a[i] = r1[i % s1];
for (int i = cnt1 * s1; i < n; ++i) a[i] = r1[i % s1];
for (int i = 0; i < cnt2 * s2; ++i) b[i] = r2[i % s2];
for (int i = cnt2 * s2; i < n; ++i) b[i] = r2[i % s2]; //
// for (int i = 0; i < n; ++i) printf("%d ", a[i]); printf("\n");
// for (int i = 0; i < n; ++i) printf("%d ", b[i]); printf("\n");

int ans1 = 0, ans2 = 0;
for (int i = 0; i < n; ++i) {
// printf("%d %d\n", a[i], b[i]);
if (win[a[i]][b[i]] == 0) continue;
else if (win[a[i]][b[i]] == 1) ++ans1;
else ++ans2;
}
printf("%d %d\n", ans1, ans2);
return 0;
}

联合权值

描述

无向连通图 G 有 $n$ 个点,$n-1$ 条边。点从 $1$ 到 $n$ 依次编号,编号为 $i$ 的点的权值为 $W_{i}$ ,每条边的长度均为 $1$。图上两点 $(u, v)$ 的距离定义为 $u$ 点到 $v$ 点的最短距离。对于图 G 上的点对 $(u, v)$ ,若它们的距离为 $2$ ,则它们之间会产生 $W _{u} \times W_{v} $ 的联合权值。
请问图 G 上所有可产生联合权值的有序点对中,联合权值最大的是多少?所有联合权值之和是多少?

$1 < n \leq 200000, 0 < W_{i} \leq 10000$

分析

既然只要求图 G 上的点对 $(u, v)$ ,它们的距离为 $2$ 便可以计算联合权值,那么我们不妨枚举每一个点为中点时,与之相连的距离为 $1$ 的点中,权值最大和次大的点并记下来,然后比较联合权值的大小。

至于求所有的联合权值之和,那么就准备一个 $sum[]$ 数组,记录每一个点与之相连且距离为 $1$ 的所有的点的权值之和,然后逐点记录贡献。

具体细节看代码qwq

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//  Created by ZJYelizaveta on Friday, September 22, 2017 AM09:53:42 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 200000 + 3;
const int INF = 0x3f3f3f3f;
const int MOD = 10007;
int n;
vector<int> G[MAX_N];
ll w[MAX_N], sum[MAX_N];
pair<ll, ll> p;
ll ans, maxVal;

inline void solve() {
ans = 0, maxVal = 0;
memset(sum, 0, sizeof sum);
for (register int u = 1; u <= n; ++u) {
p.first = 0, p.second = 0;
for (register int i = 0; i < (int)G[u].size(); ++i) {
int v = G[u][i];
sum[u] += w[v];
if (p.first <= w[v]) p.second = p.first, p.first = w[v];
else if (p.first > w[v] && p.second < w[v]) p.second = w[v];
}
maxVal = max(maxVal, p.first * p.second);
for (register int i = 0; i < (int)G[u].size(); ++i) {
int v = G[u][i];
ans = ans + w[v] * (sum[u] - w[v]);
ans = (ans % MOD + MOD) % MOD;
}
}
// for (register int i = 1; i <= n; ++i) printf("%lld\n", sum[i]);
}

int main()
{
n = readIn<int>();
for (register int i = 0; i <= n; ++i) G[i].clear();
for (register int i = 1; i <= n - 1; ++i) {
int u = readIn<int>(), v = readIn<int>();
G[u].push_back(v), G[v].push_back(u);
}
for (register int i = 1; i <= n; ++i) w[i] = readIn<int>();

solve();
printf("%lld %lld\n", maxVal, ans);
return 0;
}

飞扬的小鸟

描述

Flappy Bird 是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度,让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话,便宣告失败。
为了简化问题,我们对游戏规则进行了简化和改编:

  1. 游戏界面是一个长为 $n$ ,高为 $m$ 的二维平面,其中有 $k$ 个管道(忽略管道的宽度)。
  2. 小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发,到达游戏界面最右边时,游戏完成。
  3. 小鸟每个单位时间沿横坐标方向右移的距离为 $1$ ,竖直移动的距离由玩家控制。如
    果点击屏幕,小鸟就会上升一定高度 $X$ ,每个单位时间可以点击多次,效果叠加;如果不点击屏幕,小鸟就会下降一定高度 $Y$。小鸟位于横坐标方向不同位置时,上升的高度 $X$ 和下降的高度 $Y$ 可能互不相同。
  4. 小鸟高度等于 $0$ 或者小鸟碰到管道时,游戏失败。小鸟高度为 $m$ 时,无法再上升。

现在,请你判断是否可以完成游戏。如果可以,输出最少点击屏幕数;否则,输出小鸟
最多可以通过多少个管道缝隙。

$5 \leq n \leq 10000, 5 \leq m \leq 1000, 0 \leq k<n, 0<X<m, 0<Y<m, 0<P<n, 0 \leq L<H ≤m,L +1<H$

分析

搜索 + 剪枝,动态规划 + 优化 这两种方法都是可以过这道题目的。

令 $dp[i][j]$ 为横坐标到 $i$ ,纵坐标到 $j$ 所需的最少点击数。

上升高度因为可以点击多次所以可以看做是做“完全背包”,而下降则相当于做“01 背包”。

这样一来我们有一个很见到的 $\Theta(nm^{2})$ 的转移方程:

这个转移方程每次状态转移的时间复杂度为 $\Theta(m)$ ,那么如何每次状态转移的时间复杂度呢?

考虑“点击 $k - 1$ 次”和“点击 $k$ 次”之间的关联。

如果到达点 $[i, j]$ 最少点击数为 $k$ ,那么也就是说点击 $k - 1$ 可以到达 $[i, j - x[i - 1]]$ 。那么在只考虑上升的情况下,转移方程可以优化为:

这样我们就可以 $\Theta(1)$ 转移啦qwq

这里要注意一点,就是我们肯定要判断上升和下降是否接触到边界,也就是将边界标记为 $dp[pos][low] = \textrm{INF}, dp[pos][high] = \textrm{INF}$ ,这里把判断要放在最后。因为有一种情况,即点击 $k - 1$ 次会到达管道最下方,但是点击 $k$ 次并不会触碰到管道,因为点击 $k$ 次由点击 $k - 1$ 次转移而来,所以这里将判断放在最后面。

然后上升的时候,因为不管怎么上升最高高度只会为 $m$ 所以这里要拎出来单独计算。

总时间复杂度 $\Theta(nm)$ 。 

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
//  Created by ZJYelizaveta on Wednesday, October 25, 2017 AM10:45:41 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 10000 + 3;
const int MAX_M = 1000 + 3;
const int INF = 0x3f3f3f3f;
int n, m, k;
int x[MAX_N], y[MAX_N];
struct Pipe {
int flag, low, high;
}a[MAX_N];
int dp[MAX_N][MAX_M];
int ans;

int main()
{
n = readIn<int>(), m = readIn<int>(), k = readIn<int>();
for (int i = 0; i < n; ++i) x[i] = readIn<int>(), y[i] = readIn<int>();

for (int i = 1; i <= k; ++i) {
int x = readIn<int>(); a[x].flag = true;
a[x].low = readIn<int>(), a[x].high = readIn<int>();
}

dp[0][0] = INF;
for (int i = 1; i <= n; ++i) {
dp[i][0] = INF;
for (int j = 1; j < m; ++j) {
dp[i][j] = INF;

if (j - x[i - 1] > 0) { // clicks
if (dp[i - 1][j - x[i - 1]] != INF) {
dp[i][j] = min(dp[i][j], dp[i - 1][j - x[i - 1]] + 1);
}
if (dp[i][j - x[i - 1]] != INF) {
dp[i][j] = min(dp[i][j], dp[i][j - x[i - 1]] + 1);
}
}
}

for (int j = 1; j <= m - y[i - 1]; ++j) { // down
if (dp[i - 1][j + y[i - 1]] != INF) dp[i][j] = min(dp[i][j], dp[i - 1][j + y[i - 1]]);
}

dp[i][m] = INF;
for (int j = m - x[i - 1]; j <= m; ++j) { // Edge
if (dp[i - 1][j] != INF) dp[i][m] = min(dp[i][m], dp[i - 1][j] + 1);
if (dp[i][j] != INF) dp[i][m] = min(dp[i][m], dp[i][j] + 1);
}

if (a[i].flag) { // check
for (int j = 1; j <= m; ++j) if (j <= a[i].low || j >= a[i].high) dp[i][j] = INF;
} //
}

ans = INF;
for (int i = 1; i <= m; ++i) ans = min(ans, dp[n][i]);

if (ans != INF) {
printf("1\n%d\n", ans);
}
else {
int pos = -INF;
for (int i = n - 1; i >= 0; --i) {
for (int j = 1; j <= m; ++j) {
if (dp[i][j] != INF) {
pos = i; break;
}
}
if (pos != -INF) break;
}
// printf("%d\n", pos);

int cnt = 0;
for (int i = 1; i <= pos; ++i) if (a[i].flag) ++cnt;

printf("0\n%d\n", cnt);
}
return 0;
}

Day 2

无线网络发射器选址

描述

随着智能手机的日益普及,人们对无线网的需求日益增大。某城市决定对城市内的公共场所覆盖无线网。
假设该城市的布局为由严格平行的 $129$ 条东西向街道和 $129$ 条南北向街道所形成的网格状,并且相邻的平行街道之间的距离都是恒定值 $1$。东西向街道从北到南依次编号为 $0,1,2, \cdots ,128$ ,南北向街道从西到东依次编号为 $0,1,2, \cdots,128$。
东西向街道和南北向街道相交形成路口,规定编号为 $x$ 的南北向街道和编号为 $y$ 的东西向街道形成的路口的坐标是 $(x, y)$。在某些路口存在一定数量的公共场所。
由于政府财政问题,只能安装一个大型无线网络发射器。该无线网络发射器的传播范围是一个以该点为中心,边长为 $2 \times d$ 的正方形。传播范围包括正方形边界。

现在政府有关部门准备安装一个传播参数为 $d$ 的无线网络发射器,希望你帮助他们在城
市内找出合适的安装地点,使得覆盖的公共场所最多。

$1 \leq d \leq 20, 1 \leq n \leq 20, 0 \leq x \leq 128, 0 \leq y \leq 128, 0 < k \leq 10^{6}$

分析

因为 $0 \leq x \leq 128, 0 \leq y \leq 128$ ,那么我们令 $cnt[i][j]$ 为范围在 $x \leq i, y \leq j$ 的覆盖的公共场所数量。那么我们可以以 $\Theta(128^{2}40^{2})$ 的时间复杂度预处理出来。

然后我们将所有的 $cnt[i][j]$ 放进优先队里来维护,这样队首就是我们所求的最大值。至于方案数量,那么就只需要遍历一遍队列即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//  Created by ZJYelizaveta on Tuesday, October 24, 2017 AM08:52:01 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 128 + 3;
const int INF = 0x3f3f3f3f;
int d, n;
int a[MAX_N][MAX_N];
int sum[MAX_N][MAX_N];
int mx, cnt;

int main()
{
d = readIn<int>(), n = readIn<int>();
// printf("%d %d\n", d, n);
for (int i = 1; i <= n; ++i) {
int x = readIn<int>(), y = readIn<int>(), k = readIn<int>();
a[x][y] = k;
}

priority_queue<int> q;
for (int i = 0; i <= 128; ++i) {
for (int j = 0; j <= 128; ++j) {
for (int l = max(0, i - d); l <= min(128, i + d); ++l) {
for (int r = max(0, j - d); r <= min(128, j + d); ++r) {
sum[i][j] += a[l][r];
}
}
q.push(sum[i][j]);
}
}

mx = q.top();
while (!q.empty()) {
int temp = q.top(); q.pop();
if (temp == mx) ++cnt;
}
printf("%d %d\n", cnt, mx);
return 0;
}

寻找道路

描述

在有向图 G 中,每条边的长度均为 $1$ ,现给定起点和终点,请你在图中找一条从起点到终点的路径,该路径满足以下条件:

  1. 路径上的所有点的出边所指向的点都直接或间接与终点连通。
  2. 在满足条件 1 的情况下使路径最短。

注意:图 G 中可能存在重边和自环,题目保证终点没有出边。
请你输出符合条件的路径的长度。

$0 < n \leq 10000, 0 < m \leq 200000, 0 < x, y, s, t \leq n, x \neq t$

分析

这道题目还是比较简单的。

我们有结论:如果在原图上有点 $u$ 不能走到终点 $t$ ,那么在反图中(即将原图中所有边的方向都取反)我们从终点出发也遍历不到点 $u$ 。

有了这个结论,那么我们可以先预处理处在反图上从终点出发到达不了的点,即从终点开始 dfs,每遍历到一个点,就标记一下。如果 dfs 结束,还有点没有遍历到,那么这个点就是从终点 $t$ 出发走不到的点。我们还要将与这些点相邻的点(能到达且距离为 $1$ 的点)也标记一下。

然后就可以在原图上做 spfa 了,那些被标记的点在做最短路的时候,判断一下使之不能加入队列中即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
//  Created by ZJYelizaveta on Tuesday, October 24, 2017 AM10:47:29 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 10000 + 3;
const int MAX_M = 200000 + 3;
const int INF = 0x3f3f3f3f;
int n, m;
int s, t;
int ans;

vector<int> G[MAX_N];
int vis[MAX_N];
inline void dfs(int u) {
// printf("%d\n", u);
vis[u] = 1;
for (int i = 0; i < (int)G[u].size(); ++i)
if (!vis[G[u][i]]) dfs(G[u][i]);
}

int vis1[MAX_N];
inline void prepare() {
// printf("%d\n", t);
memset(vis, 0, sizeof vis);
dfs(t);

memset(vis1, 1, sizeof vis1);
for (int u = 1; u <= n; ++u) if (!vis[u]) {
for (int i = 0; i < (int)G[u].size(); ++i) {
int v = G[u][i];
vis1[v] = 0;
}
}
for (int i = 1; i <= n; ++i) if (!vis1[i]) vis[i] = 0;
}

struct Edge {
int to, next;
}edge[MAX_M];
int head[MAX_N], cnt = 0;
int dist[MAX_N], inq[MAX_N];

inline void addEdge(int from, int to) {
edge[++cnt].to = to; edge[cnt].next = head[from]; head[from] = cnt;
}

inline void spfa() {
queue<int> q;
memset(dist, INF, sizeof dist);
memset(inq, 0, sizeof inq);
q.push(s); inq[s] = 1; dist[s] = 0;

while (!q.empty()) {
int u = q.front(); q.pop();
inq[u] = 0;

for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to;
if (vis[v] && dist[v] > dist[u] + 1) {
dist[v] = dist[u] + 1;
if (!inq[v]) {
inq[v] = 0; q.push(v);
}
}
}
}
if (dist[t] == INF) ans = -1;
else ans = dist[t];
}

inline void solve() {
if (!vis[s]) ans = -1;
else {
ans = 0;
spfa();
}
printf("%d\n", ans);
}

int main()
{
n = readIn<int>(), m = readIn<int>();
for (int i = 1; i <= m; ++i) {
int u = readIn<int>(), v = readIn<int>();
G[v].push_back(u);
addEdge(u, v);
}
s = readIn<int>(), t = readIn<int>();

prepare();
solve();

return 0;
}

解方程

描述

已知多项式方程:

求这个方程在 $[1, m]$ 内的整数解($n$ 和 $m$ 均为正整数)。

$0 < n \leq 100, \left | a_{i} \right | \leq 10^{10000}, a_{n} \neq 0, m \leq 1000000$

分析

感谢出题人,给我这种数学渣渣留了 30 分,[滑稽].jpg

没思路,然后看了一下题解。

首先对于 $50 \%$ 的分数如果考虑暴力的思路,肯定是需要用高精度的,于是换一个思路考虑。

一元高次方程是没有通解的,而且本题系数非常大,显然不是用一个很确切的数学方法来求解。

考虑将方程放在模意义下来考虑,我们令

我们取一个大质数 $p$ ,如果 $f(x) \pmod p = 0$ ,那么 $(f(x) + p) \pmod p = 0$ ,虽然反过来不一定成立,那么这个时候就需要看你的人品了qwq,这样可以水到 70 分,时间复杂度 $\Theta(mnlogn)$ 。

如果计算的时候不想以 $\Theta(nlogn)$ 这样较高的时间复杂度计算 $f(x)$,那么其实我们可以将时间复杂度降至 $\Theta(n)$ 的,我们需要用到 秦九韶算法 ,原理是这样的:

因为 $f(x) \ \% \ p = 0$ ,那么有 $(f(x) + p) \ \% \ p = 0$ ;又因为反过来不一定成立,所以我们不妨多取几个质数来验证,但是这样时间复杂度仍然降不到一个理想的程度。

又因为我们考虑,在模 $p$ 意义下,若 $f(x) \pmod p= 0$ ,则一定有 $f(x+p) \pmod p = 0$ 。反之,若 $f(x) \pmod p\neq 0$ ,则一定有$f(x+p) \pmod p \neq 0$ 。所以我们只需验证 $[1,p)$ 即可。

这样我们取两个较小的质数和一个较大的质数,然后三者同时成立时,此时的 $x​$ 为解之一。

时间复杂度为 $\Theta(mn + MOD1 + MOD2)$ ,看起来有点吓人,但是实际上这个复杂度并不满qwq

代码

$30 \%$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//  Created by ZJYelizaveta on Tuesday, October 24, 2017 PM02:17:24 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.
// 30%

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 100 + 3;
int n, m;
int a[MAX_N];
vector<int> ans;
int cnt;

int main()
{
n = readIn<int>(), m = readIn<int>();
for (int i = 1; i <= n + 1; ++i) a[i] = readIn<int>();

for (int x = 1; x <= m; ++x) {
int temp = 0;
for (int i = 1; i <= n + 1; ++i) {
if (i == 1) temp += a[i];
if (i == 2) temp += a[i] * x;
if (i == 3) temp += a[i] * x * x;
}
if (temp == 0) {
++cnt; ans.push_back(x);
}
}

printf("%d\n", cnt);
for (int i = 0; i < ans.size(); ++i) printf("%d\n", ans[i]);
return 0;
}

$70 \%$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
//  Created by ZJYelizaveta on Tuesday, October 24, 2017 PM02:49:31 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.
// 70%

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 100 + 3;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int n, m;
char str[MAX_N];
ll a[MAX_N];
vector<int> ans;
int cnt;

inline ll quickPow(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1) (res *= a) %= MOD;
(a *= a) %= MOD;
b >>= 1;
}
return res;
}

inline ll readStr() {
ll x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = (x * 10 + ch - '0' % MOD + MOD) % MOD; ch = getchar();}
return (x * f % MOD + MOD) % MOD;
}

int main()
{
n = readIn<int>(), m = readIn<int>();
for (int i = 1; i <= n + 1; ++i) a[i] = readStr();

// for (int i = 1; i <= n + 1; ++i) printf("%lld ", a[i]); printf("\n");

for (int x = 1; x <= m; ++x) {
ll temp = 0;
for (int i = 1; i <= n + 1; ++i) {
temp = (temp + a[i] * quickPow(x, i - 1) % MOD + MOD) % MOD;
}
if (temp == 0) {
ans.push_back(x);
++cnt;
}
}

printf("%d\n", cnt);
for (int i = 0; i < ans.size(); ++i) printf("%d\n", ans[i]);

return 0;
}

$100 \%$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//  Created by ZJYelizaveta on Tuesday, October 24, 2017 PM03:18:44 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 100 + 3;
const int MAX_M = 1000000 + 3;
const int MOD1 = 10651;
const int MOD2 = 11677;
const int MOD3 = 11987;
int n, m;
int a[MAX_N][5];
int flag1[MOD1], flag2[MOD2];
vector<int> ans;
int cnt;

inline void readStr(int i) {
char ch; bool flag;
while (!isdigit(ch = getchar()) && ch != '-');
flag = (ch == '-') ? false : true;
a[i][1] = (ch == '-') ? 0 : (ch - '0') % MOD1;
a[i][2] = (ch == '-') ? 0 : (ch - '0') % MOD2;
a[i][3] = (ch == '-') ? 0 : (ch - '0') % MOD3;

while (isdigit(ch = getchar())) {
a[i][1] = (a[i][1] * 10 + ch - '0') % MOD1;
a[i][2] = (a[i][2] * 10 + ch - '0') % MOD2;
a[i][3] = (a[i][3] * 10 + ch - '0') % MOD3;
}
if (flag == false) {
a[i][1] = (MOD1 - a[i][1]) % MOD1;
a[i][2] = (MOD2 - a[i][2]) % MOD2;
a[i][3] = (MOD3 - a[i][3]) % MOD3;
}
}

inline bool calculate(int x, int mod, int flag) {
int res = 0;
for (int i = n; i >= 0; --i) {
res = (1ll * res * x + a[i][flag]) % mod;
}
return res == 0 ? true : false;
}

int main()
{
n = readIn<int>(), m = readIn<int>();
for (int i = 0; i <= n; ++i) readStr(i);

// for (int i = 0; i <= n; ++i) printf("%d %d %d\n", a[i][1], a[i][2], a[i][3]);

for (int i = 0; i < MOD1; ++i) flag1[i] = calculate(i, MOD1, 1);
for (int i = 0; i < MOD2; ++i) flag2[i] = calculate(i, MOD2, 2);

ans.clear();
for (int i = 1; i <= m; ++i) {
int fir = i % MOD1; int sec = i % MOD2;
if (flag1[fir] && flag2[sec] && calculate(i, MOD3, 3)) {
ans.push_back(i); ++cnt;
}
}

printf("%d\n", cnt);
for (int i = 0; i < (int)ans.size(); ++i) printf("%d\n", ans[i]);
return 0;
}
Partager