2018 ACM-ICPC南京区域赛题解
发布时间
阅读量：
阅读量
解题过程
比赛开始后先处理A题，在处理A题时shl误读题目内容（即对问题理解有偏差），被迫停止。
随后决定用手推的方法处理。
总结出解决A题的方法后编写代码。
当看到E的问题时意识到自己误解了问题描述（即对问题理解存在偏差）。
完成并提交了A题却因为未考虑N等于零的情况（即边界条件）而导致WA+1。
处理完所有A相关的部分之后再次着手编写E的问题分析部分。
接着由lfw负责J题的讨论与进展。
而E的问题无法通过测试用例检验（即程序无法通过样例测试）。
由于调整过程中出现了一些混乱（即出现了一些沟通上的问题）导致无法顺利调试程序。
随后由lw负责撰写J的相关内容，并最终取得了一次性通过的结果（即解决了J问题）。
接着由shl提出I的问题解决方案（即口述了解决方案），而lw和shl共同探讨如何解决G的问题。
在I问题取得进展后决定集中精力解决G问题，并最终确定了解决方案（即找到G的正确解法）。
然后lw转向几何计算这部分工作，在经过反复检查和修正之后成功解决问题（解决了几何计算相关的问题）。
最后由lw负责解决M的问题并取得了成功（解决了M相关的问题），剩余时间不足以进行其他项目的研究工作。
最后罚时很多，因为前期签到题过得太慢，A题40+分钟才过,J题1小时40分钟才过。
题解
A - Adrien and Austin
题解：设有n块石头，编号依次为1至n,两人交替进行游戏,每次玩家必须选取连续编号的1到k块石头,无法操作的一方败北.请问先手是否存在必胜策略？
找规律，首先,n==0时，第一个人必败。k==1时,n为奇数时先手必胜。k>1时,先手必胜.
参考代码：
1 2usingnamespace std;
3longlong LL;
4constint7;
5LL quick_pow(LL a,LL b)
6{
71;
8while(b)
9 {
10if1mod;
11mod;
121;
13 }
14return ans;
15}
16int main()
17{
18int t;
19"%d"t);
20int242);
21while)
22 {
23int n;
24"%d"n);
251;
26mod;
271mod;
282mod;
293mod;
30mod;
31"%lld\n",ans);
32 }
33View Code
B - Tournament
Unsolved.
C - Cherry and Chocolate
Unsolved.
D - Country Meow
队友写的.题解：
参考代码：
1 2#define 3#define 4struct point
5{
6double x,y,z;
7double0double0double0)
8 {
9c;
10 }
11};
12 13int npoint,nouter;
144],res;
15double radius,tmp,ans;
16 17double dist(point p1,point p2)
18{
19doublep2.z;
20returndz);
21}
22 23double dot(point p1,point p2)
24{
25returnp2.z;
26}
27 28void ball()
29{
303double3333],det;
31int i,j;
320;
33switch(nouter)
34 {
35case10break;
36case2:
37012;
38012;
39012;
400]);
41break;
42case3:
43forint02)
44 {
4510].x;
4610].y;
4710].z;
48 }
49forint02)
50forint02)
512;
52forint02)
53dot(q[i],q[i]);
54if00110110eps)
55return;
560011101det;
571100010det;
5800011];
5900011];
6000011];
610]);
62break;
63case4:
64forint03)
65 {
6610].x;
6710].y;
6810].z;
69dot(q[i],q[i]);
70 }
71forint03)
72forint03)
732;
74001122]
75011220]
76022110]
77021120]
78011022]
79001221];
80ifreturn;
81forint03)
82 {
83forint03)
84sol[i];
85001122]
86011220]
87022110]
88021120]
89011022]
90001221det;
91forint03)
922;
93 }
940];
95forint03)
96 {
97L[i];
98L[i];
99L[i];
100 }
1010]);
102 }
103}
104105voidint n)
106{
107 ball();
108if4)
109forint0)
110ifeps)
111 {
112pt[i];
113nouter;
114 minball(i);
115nouter;
116if0)
117 {
118pt[i];
11910sizeofi);
1200Tt;
121 }
122 }
123}
124125double smallest_ball()
126{
1271;
128forint0)
129ifeps)
130 {
1311;
1320pt[i];
133 minball(i);
134 }
135return sqrt(radius);
136}
137138void prework()
139{
140forint0)
141"%lf%lf%lf"pt[i].z);
142}
143144void mainwork()
145{
146smallest_ball();
147}
148149void print()
150{
151"%.5f\n",ans);
152}
153154int main()
155{
156while"%d"npoint))
157 {
158 prework();
159 mainwork();
160 print();
161 }
162return0;
163View Code
E - Eva and Euro coins
题目解析：有两个给定的二进制串（由0和1组成），即每当有连续的k个0时可以将其转换成1s；同样地，在连续出现k个1时也可以将其转换成0s。那么这两个二进制串是否能够通过这种转换规则变得完全相同？
可以利用归约。连续k个0或1可以归约掉。最后判断是否相同即可。
参考代码：
1 2usingnamespace std;
3constint5;
4char s[maxn],t[maxn];
5int2];
6int n,k,tmp;
7voidchar st[])
8{
90sizeof(cnt));
100010;
11forint1i)
12 {
130'0';
14110'0'1111;
15if1k;
16 }
17forint1if0'0'else'0';}
18}
19int main()
20{
21"%d%d"k);
22"%s"1);
23"%s"1);
24 work(s);work(t);
25forint1if"No"return0;}}
26"Yes");
27return0;
28View Code
F - Frank
Unsolved.
G - Pyramid
题解：打表找规律，ans=n(n+1)(n+2)(n+3).
参考代码：
1 2usingnamespace std;
3longlong LL;
4constint7;
5LL quick_pow(LL a,LL b)
6{
71;
8while(b)
9 {
10if1mod;
11mod;
121;
13 }
14return ans;
15}
16int main()
17{
18int t;
19"%d"t);
20int242);
21while)
22 {
23int n;
24"%d"n);
251;
26mod;
271mod;
282mod;
293mod;
30mod;
31"%lld\n",ans);
32 }
33View Code
H - Huge Discount
Unsolved.
I - Magic Potion
队友写的，好像是最大流，题解待更。
参考代码：
1 2usingnamespace std;
3constint1010;
4constint5;
5constint0x3f3f3f3f;
6struct Edge{
7int to,nxt,cap,flow;
8}edge[maxm];
9int tol;
10int head[maxn];
11void init(){
122;
131sizeof(head));
14}
15voidintintintint0){
160;
17;
180;
19;
20}
21int Q[maxn];
22int dep[maxn],cur[maxn],sta[maxn];
23boolintintint n){
24int00;
251sizeof01));
260;
27s;
28whiletail){
29int];
30forint1edge[i].nxt){
31intedge[i].to;
32if1){
331;
34ifreturntrue;
35v;
36 }
37 }
38 }
39returnfalse;
40}
41intintintint n){
42int0;
43while(bfs(s,t,n)){
44forint0head[i];
45int0;
46while1){
47ift){
48intinf;
49forint10)
50 {
51edge[sta[i]].flow);
52 }
53tp;
54forint10){
55tp;
561tp;
57if0i;
58 }
591].to;
60 }
61elseif11dep[edge[cur[u]].to]){
62cur[u];
63edge[cur[u]].to;
64 }
65else{
66while11].to;
67 edge [cur[u]].nxt;
68 }
69 }
70 }
71return maxflow;
72}
73int main()
74{
75 init();
76int n,m,k;
77"%d%d%d"k);
78int ti,mi;
79int05;
80int12;
81forint121);
82forint121);
83 AddEdge(ss,s1,n);
84 AddEdge(ss,s2,k);
85forint1)
86 {
87"%d"ti);
88forint1)
89 {
90"%d"mi);
91221);
92 }
93 }
94forint1)
95 {
9621);
97 }
98int1);
99"%d\n",ans);
100}
101View Code
J - Prime Game
队友写的，题解：
参考代码：
1 2#define 3usingnamespace std;
4 5int n;
6int a[maxl],p[maxl],dy[maxl];
7longlong v[maxl];
8bool no[maxl];
9int f[maxl];
10longlong ans;
1112void shai()
13{
141true;
15int t,j;
16forint2)
17 {
18if0i;
1911];
20while0maxl)
21 {
22p[j];
23true;
24if0)
25break;
26j];
27 }
28 }
29}
3031void prework()
32{
33forint10)
34 f[p[i]].clear();
35forint1)
36 {
37"%d"a[i]);
38int0;
39while1)
40 {
41iflast)
42 f[dy[x]].push_back(i);
43dy[x];
44dy[x];
45 }
46 }
47}
4849void mainwork()
50{
510int l,r,len;
52longlong tmp;
53forint10)
54if0)
55 {
56v[n];
5710f[p[i]].size();
58if01)
5901];
60forint01)
61if11)
62 {
63111;
641];
65 }
66if1n)
671]];
68tmp;
69 }
70}
7172void print()
73{
74"%lld\n",ans);
75}
7677int main()
78{
79 shai();
80forlonglong1)
8112;
82while"%d"n))
83 {
84 prework();
85 mainwork();
86 print();
87 }
88return0;
89View Code
K - Kangaroo Puzzle
随机化。。
1 2usingnamespace std;
3char2525];
4int n,m;
5int main()
6{
7"%d%d"m);
8forint1"%s",s[i]);
90));
10char4'L''R''U''D'};
11forint120"U");
12forint120"R");
13forint120"D"///adsfag14forint120"L");
15forint149920i)
16 {
17int4;
18"%c",str[x]);
19 }
20"");
21return0;
22View Code
L - Lagrange the Chef
Unsolved.
M - Mediocre String Problem
解答：给定两个字符串S₁和S₂，请从S₁中选取长度在l到r之间的任意一个子串，并将该子串与S₂的前缀部分连接在一起形成回文结构，请问有多少种满足条件的组合方式？
我们可以通过选择变量l、x、r以及f来实现对称性设置。具体来说，在满足条件lx与1f对称的前提下，将字符串s1进行反转操作，并应用exkmp算法来判断x到r的部分是否为回文串。接下来，在遍历所有可能的r值时（即从最小到最大的范围），我们可以使用Manacher算法进一步分析s1的结构特点。同时，在这一过程中我们需要将另一个字符串exnext进行反转操作，并维护一个前缀和数组来记录相关信息的变化趋势。
即可。
参考代码：
1 2usingnamespace std;
3longlong ll;
4#define 5constint0x3f3f3f3f;
6constint10;
7char s[maxn],t[maxn];
8int lens,lent;
9int mynext[maxn],extend[maxn];
10ll sum[maxn];
11 12voidcharintint nxt[])
13{
140m;
15int0;
16while11;
171j;
18int1;
19forint2i)
20 {
21int1;
22intk];
23if1L;
24else 25 {
2601);
27while;
28j;
29i;
30 }
31 }
32}
33voidcharintcharintintint extend[])
34{
35 pre_exkmp(x,m,nxt);
36int0;
37whilej;
380j;
39int0;
40forint1i)
41 {
42int1;
43intk];
44if1L;
45else 46 {
4701);
48whilej;
49j;
50i;
51 }
52 }
53}
54char2];
55int1];
56voidcharint le)
57{
58int0;
59'$''#';
60forint0'#';
610;
62int00;
63forint0i)
64 {
6521;
66while;
67ifi;
68 }
69}
70//moban 71 72intint r)
73{
74ifreturn0;
75elseif0return sum[r];
76elsereturn1];
77}
78 79int main()
80{
81"%s%s",s,t);
82strlen(t);
83//len[] 84lens);
85 exkmp(t,lent,s,lens,mynext,extend);
86lens);
8700];
88forint11extend[i];
890;
90forint223i)
91 {
92int1;
93if00continue;
94if1)
95 {
96int22;
97int1;
98int2;
99getsum(l,r);
100 }
101else102 {
103int212;
104int1;
105int2;
106getsum(l,r);
107 }
108 }
109"%lld\n",ans);
110111return0;
112View Code
全部评论 (0)
还没有任何评论哟~