#2018.05.29 ACM的第一次尝试

news/2023/12/1 4:42:58

菜鸡如我居然也打了（假的）ACM，，在团队里还发挥了不少作用（自己码A了一道dp ~~高兴死了~~）

题就不上了，写一下今天的感受。

这次的题目，看了后脑子里都是能马上想出思路的，但毕竟是ACM，必须A掉题目才能拿分，一开始想到的思路总不会是最优的（T1 T2水一遍就过了完全没有讨论。。），于是团队模式带来的好处就得以体现了。在T3我们花费了大量时间，一道关于数论的题目，判断在b进制下p/q是否为有限小数。

拿到这题我很自觉地转过去看老爹的代码。。。数学我就烂得一比，那天数论也就懵懵懂懂地听了过去然后跟个傻子一样研究学习扩欧（←写了满满一页的笔记和自己的一些想法然而。。。）心想这题就全权交给延恺了，，然后稍微一想，想到了这个和gcd有很大的关系。于是就和延恺开始做这题，思路开始很清晰，但是渐渐地我们发现了很多反例，于是开始调试，于是开始删改。交了一遍第九个点就过不了。最终甚至把代码重写，更换了思路，然后，然后卡了第13个点，于是开始做优化，做优化，做到最后实在是不知道该如何优化了而2个多小时已经过去了，左边的老爹已经A了T1 T2，码了能过样例的T4。当时心态有点崩，只能跳过这题往下面找题做。

看到Elevator的时候想想是能做的，but代码力实在不足，然后我们选择了跳过。

ACM打到后面我们已经失去战斗力了（在一道题上卡死然后整个人都崩了）。于是延恺选择思考H，而我换了个位置改T4。。。T4拿到手可以很直观地看出要写递推，然后就开始想dp方程。给我启示最大的不是我爹的代码而是题目中的‘Pyramid’，于是根据题目的条件画了画图，金字塔的形状，区间dp的想法就产生了。后来调试了一下就A掉了，感觉还是不错的。

然后我们最后的成绩就是这三道题，G是一道LCA表示还根本用不来。至于老师后来讲的最短路，抽屉原理什么的就完全不熟悉了。

T3卡着时间其实思路是没有错的，赛后我们修改了一下在while语句里加了两句话就，，就过了-/\-。。。

诚恳地附上代码吧。

#include<bits/stdc++.h>
using namespace std;
#define ll  long long
ll p,q,b,n;ll gcd(ll x,ll y)
{if(y==0) return x;else return gcd(y,x%y);
}inline ll read()
{ll s=0;bool whs=1;char c=' ';for(;c<'0'||c>'9';c=getchar()) if(c=='-') whs=0;for(;c>='0'&&c<='9';s=s*10-48+c,c=getchar());return whs?s:-s;
}bool Emilia()
{ll o;o=gcd(q,b);while(o>1&&q!=1){ while(q%o==0) q/=o; //比赛中即是少了这两句o=gcd(q,b);}if(q==1) return 0;else return 1;
}int main() 
{n=read();for(int i=1;i<=n;i++){p=read(),q=read(),b=read();ll c=gcd(p,q);p/=c,q/=c;if(p>q) p%=q;if(Emilia()) printf("Infinite\n");else printf("Finite\n");}return 0;
}

我作为一个沙茶，对数论的强大一无所知。代码力奇弱无比只能仰望班上的大神们然后不动声色地靠近。。

这次ACM夺冠的是我们的蒟蒻小分队。实在是太强了。 ~~虽然罚了1500多分，~~A过六道题是真的强，%%%%%%。

沙茶如我得多多努力啊。