由难到易为：L，E，D
L. 8-bit Zoom
暴力模拟即可
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 60;
int n, Z;
string str[MAXN];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t--)
{
cin >> n >> Z;
for(int i = 0; i < n; ++i)
cin >> str[i];
if((n * Z )% 100 == 0)
{
if(Z == 100)
{
for(int i = 0; i < n; ++i)
cout << str[i] << '\n';
}
else if(Z == 200)
{
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
cout << str[i][j] << str[i][j];
cout << '\n';
for(int j = 0; j < n; ++j)
cout << str[i][j] << str[i][j];
cout << '\n';
}
}
else if(Z == 150)
{
if(n % 2 == 0)
{
bool flag = true;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; j += 2)
if(str[i][j] != str[i][j+1])
{
flag = false;
break;
}
}
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; j += 2)
if(str[j][i] != str[j+1][i])
{
flag = false;
break;
}
}
if(flag)
{
char mp[100][100];
for(int i=0,x=0;i<n;i+=2,x++)
{
for(int j=0,y=0;j<n;j+=2,y++)
{
mp[x][y]=str[i][j];
}
}
for(int i=0;i<n/2;i++)
{
for(int j=0;j<n/2;j++)
{
cout<<mp[i][j]<<mp[i][j]<<mp[i][j];
}
cout<<"\n";
for(int j=0;j<n/2;j++)
{
cout<<mp[i][j]<<mp[i][j]<<mp[i][j];
}
cout<<"\n";
for(int j=0;j<n/2;j++)
{
cout<<mp[i][j]<<mp[i][j]<<mp[i][j];
}
cout<<"\n";
}
}
else
{
cout<<"error\n";
}
}
else
{
cout << "error\n";
}
}
else if(Z == 125)
{
if(n % 4 == 0)
{
bool flag = true;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; j += 4)
if(str[i][j] != str[i][j+1] || str[i][j+1] != str[i][j+2] || str[i][j+2] != str[i][j+3])
{
flag = false;
break;
}
}
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; j += 4)
if(str[j][i] != str[j+1][i] || str[j+1][i] != str[j+2][i] || str[j+2][i] != str[j+3][i])
{
flag = false;
break;
}
}
if(flag)
{
char mp[100][100];
for(int i=0,x=0;i<n;i+=4,x++)
{
for(int j=0,y=0;j<n;j+=4,y++)
{
mp[x][y]=str[i][j];
}
}
for(int i=0;i<n/4;i++)
{
for(int j=0;j<n/4;j++)
{
cout<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j];
}
cout<<"\n";
for(int j=0;j<n/4;j++)
{
cout<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j];
}
cout<<"\n";
for(int j=0;j<n/4;j++)
{
cout<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j];
}
cout<<"\n";
for(int j=0;j<n/4;j++)
{
cout<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j];
}
cout<<"\n";
for(int j=0;j<n/4;j++)
{
cout<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j];
}
cout<<"\n";
}
}
else
{
cout<<"error\n";
}
}
else
{
cout << "error\n";
}
}
else if(Z == 175)
{
if(n % 4 == 0)
{
bool flag = true;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; j += 4)
if(str[i][j] != str[i][j+1] || str[i][j+1] != str[i][j+2] || str[i][j+2] != str[i][j+3])
{
flag = false;
break;
}
}
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; j += 4)
if(str[j][i] != str[j+1][i] || str[j+1][i] != str[j+2][i] || str[j+2][i] != str[j+3][i])
{
flag = false;
break;
}
}
if(flag)
{
char mp[100][100];
for(int i=0,x=0;i<n;i+=4,x++)
{
for(int j=0,y=0;j<n;j+=4,y++)
{
mp[x][y]=str[i][j];
}
}
for(int i=0;i<n/4;i++)
{
for(int j=0;j<n/4;j++)
{
cout<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j];
}
cout<<"\n";
for(int j=0;j<n/4;j++)
{
cout<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j];
}
cout<<"\n";
for(int j=0;j<n/4;j++)
{
cout<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j];
}
cout<<"\n";
for(int j=0;j<n/4;j++)
{
cout<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j];
}
cout<<"\n";
for(int j=0;j<n/4;j++)
{
cout<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j];
}
cout<<"\n";
for(int j=0;j<n/4;j++)
{
cout<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j];
}
cout<<"\n";
for(int j=0;j<n/4;j++)
{
cout<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j]<<mp[i][j];
}
cout<<"\n";
}
}
else
{
cout<<"error\n";
}
}
else
{
cout << "error\n";
}
}
}
else
{
cout << "error\n";
}
}
return 0;
}
|
E. Out of Control
定义 为以 结尾的串在
时对答案的贡献，考虑如何状态转移，显然当原序列中小于等于 的数的数量大于 时，，
状态转移的过程可以看作对题目的模拟：
若当前串结尾为小于
的数，则可以添加 使其成为以 结尾的串，若当前串恰好以 结尾，只要小于等于
的数还有剩余即可直接放在串的末尾使其仍以 结尾。同时，以 结尾的串长度最多不超过原序列中小于等于
的数的数量，因此该情况下直接使
即可
由于我们只需要各个数之间的大小关系，因此使用离散化解决范围过大的问题，之后的状态转移使用前缀和维护即可把空间压到
。整体时间复杂度为
官方题解说的分治FFT有空再写（
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e3+10;
const ll MOD = 1e9 + 7;
ll T;
ll n,m;
ll a[N],t[N];
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
t[i]=a[i];
}
sort(t+1,t+n+1);
m=unique(t+1,t+n+1)-t-1;
vector<ll>b(m+1);
vector<ll>dp(m+1);
for(int i=1;i<=n;i++)
{
a[i]=lower_bound(t+1,t+m+1,a[i])-t;
b[a[i]]++;
}
for(int i=1;i<=m;i++)
{
dp[i]=1;
b[i]+=b[i-1];
}
for(int i=1;i<=n;i++)
{
ll cnt = 0,pre_sum = 0;
for(int j=1;j<=m;j++)
{
pre_sum += dp[j];
pre_sum %= MOD;
cnt += dp[j];
cnt %= MOD;
if(b[j] > i)
{
dp[j] = pre_sum;
}else
{
dp[j] = 0;
}
}
cout << cnt << '\n';
}
}
return 0;
}
|
D. Chaos Begin
标程凸包的证明没看懂，写暴力过了。
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
| #include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> Point;
const int N = 50010;
Point po[N << 1];
vector<Point>ans;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
map<Point,int>cnt;
for(int i = 1;i <= n * 2;++i)
{
cin >> po[i].x >> po[i].y;
cnt[po[i]]++;
}
map<Point,int>pos;
ans.clear();
sort(po + 1,po + 1 + n * 2);
for(int i = 1;i <= 2 * n;++i)
{
pos[po[i]] = i;
}
for(int i = 1;i <= n;++i)
{
int dx = po[i + 1].x - po[1].x;
int dy = po[i + 1].y - po[1].y;
map<Point,int>vis;
vis[po[1]] += 1;
vis[po[i + 1]] += 1;
for(int j = 2;j <= 2 * n;++j)
{
if(vis[po[j]] == cnt[po[j]])
{
if(j != 2 * n)
{
continue;
}else
{
ans.push_back(Point{dx,dy});
ans.push_back(Point{-dx,-dy});
}
}
Point tmp = Point{po[j].x + dx,po[j].y + dy};
vis[po[j]]++;
if(pos.count(tmp))
{
if(vis[tmp] < cnt[tmp])
{
vis[tmp]++;
}else
{
break;
}
}else
{
break;
}
}
}
sort(ans.begin(),ans.end());
int k = unique(ans.begin(),ans.end()) - ans.begin();
cout << k << '\n';
for(int i = 0;i < k;++i)
{
cout << ans[i].x << ' ' << ans[i].y << '\n';
}
}
}
|
剩下的题有空再补（逃