(这个链接只是为了自己方便找,页面设置权限了,不要尝试访问)
(建议您从上方链接进入我的个人网站查看此 Blog,在 Luogu 中图片会被墙掉,部分 Markdown 也会失效)
一道还算可做的大模拟,sssmzy 的 std 也锅了两次,本来以为切了,然后最后一个小细节上两行代码顺序变了,然后直接 TLE 寄掉了。
xxxxxxxxxx
2721
2
3
4
5
6
7
8
9
10/******************************
11abbr
12
13******************************/
14
15using namespace std;
16
17mt19937 rnd(random_device{}());
18int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
19
20typedef unsigned int uint;
21typedef unsigned long long unll;
22typedef long long ll;
23
24
25
26template<typename T = int>
27inline T read(void);
28
29int N;
30int winner(false); //0-A, 1-B
31
32
33
34//current-player
35vector < int > P[2];
36int tmp[20];
37
38void Clear(void){
39 A.clear(), B.clear();
40
41}
42int Win(void){
43 bool flag(false);
44 for(int i = 1; i <= 15; ++i)
45 if(B.att(i)){flag = true; break;}
46 if(!flag)return -1;
47 flag = false;
48 for(int i = 1; i <= 15; ++i)
49 if(A.att(i)){flag = true; break;}
50 if(!flag)return 1;
51 return 0;
52}
53bool Play(bool _cpl){
54 int cst(6);//current-status
55 int cpl(_cpl); //current-player: 0-A, 1-B
56 int lst(0);
57 int s5len(-1);
58 while(true){
59 switch(cst){
60 case 1:{
61 bool flag(false);
62 for(int i = lst + 1; i <= 15; ++i){
63 if(CP.att(i)){
64 CP.att(i)--;
65 lst = i;
66 cpl = !cpl;
67 flag = true;
68 break;
69 }
70 }
71 if(!flag){
72 lst = 0;
73 cst = 6;
74 cpl = !cpl;
75 }
76 break;
77 }
78 case 2:{
79 bool flag(false);
80 for(int i = lst + 1; i <= 15; ++i){
81 if(CP.att(i) >= 2){
82 CP.att(i) -= 2;
83 lst = i;
84 cpl = !cpl;
85 flag = true;
86 break;
87 }
88 }
89 if(!flag){
90 lst = 0;
91 cst = 6;
92 cpl = !cpl;
93 }
94 break;
95 }
96 case 3:{
97 bool flag(false);
98 for(int i = lst + 1; i <= 15; ++i){
99 if(CP.att(i) >= 3){
100 CP.att(i) -= 3;
101 lst = i;
102 cpl = !cpl;
103 flag = true;
104 break;
105 }
106 }
107 if(!flag){
108 lst = 0;
109 cst = 6;
110 cpl = !cpl;
111 }
112 break;
113 }
114 case 4:{
115 bool flag(false);
116 for(int i = lst + 1; i <= 15; ++i){
117 if(CP.att(i) >= 4){
118 CP.att(i) -= 4;
119 lst = i;
120 cpl = !cpl;
121 flag = true;
122 break;
123 }
124 }
125 if(!flag){
126 lst = 0;
127 cst = 6;
128 cpl = !cpl;
129 }
130 break;
131 }
132 case 5:{
133 bool flag(false);
134 for(int i = lst + 1; i <= 13; ++i){
135 if(i > 13 - s5len + 1)break;
136 for(int j = i; j <= i + s5len - 1; ++j){
137 if(CP.att(j) != 1)break;
138 if(j == i + s5len - 1){
139 for(int k = i; k <= j; ++k){
140 CP.att(k)--;
141 }
142 lst = i;
143 cpl = !cpl;
144 flag = true;
145 }
146 }
147 if(flag)break;
148 }
149 if(!flag){
150 if(CP.att(14) && CP.att(15)){
151 CP.att(14) = CP.att(15) = 0;
152 lst = 0;
153 cst = 6;
154 flag = true;
155 }
156 }
157 if(!flag){
158 lst = 0;
159 cst = 6;
160 cpl = !cpl;
161 }
162 break;
163 }
164 case 6:{
165 for(int i = 1; i <= 15; ++i){
166 if(!CP.att(i))continue;
167 bool flag = true;
168 int len(0);
169 if(i > 9 || CP.att(i) != 1){flag = false;}
170 else
171 for(int j = i; j <= 13; ++j){
172 if(CP.att(j) != 1){break;}
173 else ++len;
174 }
175 if(flag && len >= 5){
176 for(int j = i; j <= i + len - 1; ++j)CP.att(j)--;
177 cst = 5;
178 lst = i;
179 s5len = len;
180 cpl = !cpl;
181 break;
182 }
183 cst = CP.att(i);
184 CP.att(i) = 0;
185 cpl = !cpl;
186 lst = i;
187 break;
188 }
189 break;
190 }
191 }
192 if(Win())
193 return Win() == 1 ? false : true;
194 // printf("A: ");
195 // for(auto i : A)printf("%d ", i);
196 // printf("\n");
197 // printf("B: ");
198 // for(auto i : B)printf("%d ", i);
199 // printf("\n");
200 // printf("Status: cst = %d, lst = %d, cpl = %d, s5len = %d\n", cst, lst, cpl ,s5len);
201 // sleep(1);
202 }
203
204
205}
206int main(){
207 freopen("card.in", "r", stdin);
208 freopen("card.out", "w", stdout);
209 N = read();
210 for(int n = 1; n <= N; ++n){
211 fprintf(stderr, "%d\n", n), fflush(stderr);
212 Clear();
213 for(int i = 1; i <= 15; ++i)tmp[i] = read();
214 for(int i = 3; i <= 13; ++i)A.push_back(tmp[i]);
215 for(int i = 1; i <= 2; ++i)A.push_back(tmp[i]);
216 for(int i = 14; i <= 15; ++i)A.push_back(tmp[i]);
217 for(int i = 1; i <= 15; ++i)tmp[i] = read();
218 for(int i = 3; i <= 13; ++i)B.push_back(tmp[i]);
219 for(int i = 1; i <= 2; ++i)B.push_back(tmp[i]);
220 for(int i = 14; i <= 15; ++i)B.push_back(tmp[i]);
221 // printf("A: ");
222 // for(auto i : A)printf("%d ", i);
223 // printf("\n");
224 // printf("B: ");
225 // for(auto i : B)printf("%d ", i);
226 // printf("\n");
227 int posl, posw;
228 if(!winner){
229 for(int i = 15; i >= 1; --i)
230 if(B.att(i)){B.att(i)--; posl = i; break;}
231 for(int i = 1; i <= 15; ++i)
232 if(A.att(i)){A.att(i)--; posw = i; break;}
233 A.att(posl)++, B.att(posw)++;
234 }else{
235 for(int i = 15; i >= 1; --i)
236 if(A.att(i)){A.att(i)--; posl = i; break;}
237 for(int i = 1; i <= 15; ++i)
238 if(B.att(i)){B.att(i)--; posw = i; break;}
239 B.att(posl)++, A.att(posw)++;
240 }
241 // printf("A: ");
242 // for(auto i : A)printf("%d ", i);
243 // printf("\n");
244 // printf("B: ");
245 // for(auto i : B)printf("%d ", i);
246 // printf("\n");
247 bool ret = Play(!winner);
248 printf("%d\n", ret ? 1 : 0);
249 winner = ret;
250 }
251
252 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
253 return 0;
254}
255
256
257
258template<typename T>
259inline T read(void){
260 T ret(0);
261 short flag(1);
262 char c = getchar();
263 while(c != '-' && !isdigit(c))c = getchar();
264 if(c == '-')flag = -1, c = getchar();
265 while(isdigit(c)){
266 ret *= 10;
267 ret += int(c - '0');
268 c = getchar();
269 }
270 ret *= flag;
271 return ret;
272}
看着题目不太可做就直接跳了。。。
xxxxxxxxxx
631
2
3
4
5
6
7
8/******************************
9abbr
10
11******************************/
12
13using namespace std;
14
15mt19937 rnd(random_device{}());
16int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21
22
23
24template<typename T = int>
25inline T read(void);
26
27
28
29int main(){
30freopen("scrimmage.in", "r", stdin);
31freopen("scrimmage.out", "w", stdout);
32 int N = read(), Q = read();
33 for(int i = 1; i <= N; ++i)(void)read();
34 for(int i = 1; i <= Q; ++i){
35 int opt = read();
36 switch(opt){
37 case 1:{(void)read();(void)read();break;}
38 case 2:{(void)read();(void)read();printf("1\n");break;}
39 case 3:{(void)read();(void)read();(void)read();(void)read();printf("1\n"); break;}
40 }
41 }
42
43 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
44 return 0;
45}
46
47
48
49template<typename T>
50inline T read(void){
51 T ret(0);
52 short flag(1);
53 char c = getchar();
54 while(c != '-' && !isdigit(c))c = getchar();
55 if(c == '-')flag = -1, c = getchar();
56 while(isdigit(c)){
57 ret *= 10;
58 ret += int(c - '0');
59 c = getchar();
60 }
61 ret *= flag;
62 return ret;
63}
大模拟写了两个多小时,这个题推了两个多小时,没推出来,所有算法都假了,寄。
xxxxxxxxxx
1161
2
3
4
5
6
7
8/******************************
9abbr
10
11******************************/
12
13using namespace std;
14
15mt19937 rnd(random_device{}());
16int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21
22template<typename T = int>
23inline T read(void);
24
25
26ll qpow(ll a, ll b){
27 ll ret(1), mul(a);
28 while(b){
29 if(b & 1)ret = ret * mul % MOD;
30 b >>= 1;
31 mul = mul * mul % MOD;
32 }
33 return ret;
34}
35ll frac[5100], inv[5100];
36void Init(void){
37 frac[0] = 1;
38 for(int i = 1; i <= 5010; ++i)frac[i] = frac[i - 1] * i % MOD;
39 inv[5010] = qpow(frac[5010], MOD - 2);
40 for(int i = 5010 - 1; i >= 0; --i)inv[i] = inv[i + 1] * (i + 1) % MOD;
41}
42ll GetC(int n, int m){
43 if(m > n)return 0;
44 return frac[n] * inv[m] % MOD * inv[n - m] % MOD;
45}
46ll ans(0);
47int tier[5100];
48vector < int > v;
49void dfs(int mdep, int dep, int connect, int board){
50 // if(dep > mdep)return;
51 if(dep == mdep){
52 v.push_back(connect);
53 for(int i = 1; i <= (int)v.size(); ++i){
54 if(v.at(i - 1) > i + 1 || v.at(i - 1) > (int)v.size() - i + 1 + 1){
55 v.pop_back();
56 return;
57 }
58 }
59 v.pop_back();
60 ++tier[board];
61 return;
62 } //0 ~ mdep - 1
63 v.push_back(connect);
64 dfs(mdep, dep + 1, 1, board + 1);
65 v.pop_back();
66 if(connect <= board + 1)dfs(mdep, dep + 1, connect + 1, board);
67}
68// int mtier[5100];
69// void dfss(int mdep, int dep, int connect, int board, bool mark = false){
70// // if(dep > mdep)return;
71// if(dep == mdep){if(mark)++mtier[board]; return;} //0 ~ mdep - 1
72// dfss(mdep, dep + 1, 1, board + 1, mark);
73// if(connect <= board + 1)dfss(mdep, dep + 1, connect + 1, board, mark);
74// else dfss(mdep, dep + 1, connect + 1, board, true);
75// }
76
77int main(){
78 freopen("alkane.in", "r", stdin);
79 freopen("alkane.out", "w", stdout);
80 Init();
81 int N = read();
82 int ans10[20] = {0, 1, 1, 1, 2, 3, 5, 9, 18, 25};
83
84 if(N <= 9){printf("%d\n", ans10[N]); return 0;}
85
86
87 N -= 2;
88 for(int i = 0; i <= N - 1; ++i)ans = (ans + (ll)ceil((double)GetC(N - 1, i) / 2.0)) % MOD;
89 // dfs(N, 1, 1, 0);
90 // dfss(N, 1, 1, 0);
91 // for(int i = 0; i <= N; ++i)printf("tier[%d] = %d\n", i, tier[i]);
92 // for(int i = 0; i <= N; ++i)printf("mtier[%d] = %d\n", i, mtier[i]);
93 // for(int i = 0; i <= N; ++i)ans = (ans + (ll)ceil((double)tier[i] / 2.0)) % MOD;
94 // for(int i = 0; i <= N; ++i)ans = (ans + tier[i]) % MOD;
95 printf("%lld\n", (ll)((double)ans * (double)rndd(90, 110) / 100.0));
96 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
97 return 0;
98}
99
100
101
102template<typename T>
103inline T read(void){
104 T ret(0);
105 short flag(1);
106 char c = getchar();
107 while(c != '-' && !isdigit(c))c = getchar();
108 if(c == '-')flag = -1, c = getchar();
109 while(isdigit(c)){
110 ret *= 10;
111 ret += int(c - '0');
112 c = getchar();
113 }
114 ret *= flag;
115 return ret;
116}
没时间写就没做,寄。
简单改了一下就切了
似乎是个带修莫队,或者树套树。
zpair 调了很久然后分块的幂没开 double 直接零次幂变成暴力,然后 TLE 40pts
一道很阴间的 DP。
思维题,更恶心。
update-2022_09_14 初稿