博客园挂了，不让粘图。
写的朴素一点。
#1：100+100+25=225
#2：100+70+35=205
#2：100+60+45=205（我）
回到第一机房还算不错的第一仗。
考完之后我以为我AK了然而T2被卡常打成暴力，T3贪心伪证了（虽说是全场最高分）
全程在思考。很好啊。
继续保持。
注意常数，在卡常题上要花些时间优化打法卡常。
T1：Simple
做法比较傻逼。
互质下才好做，所以把nm都干掉gcd，把这样贡献的答案先算上。
我们考虑列出一个表，每n个一行（n<=m）。
这样如果某一个数是m的倍数，那么从这里开始这一列就不会出现坏数了。
那么只要每一列算最早什么时候会出现m的倍数就好了，ex_gcd。
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 #define int long long 5 int gcd(int a,int b){return b?gcd(b,a%b):a;} 6 void ex_gcd(int a,int b,int &x,int &y){ 7 if(!b){x=1;y=0;return;} 8 ex_gcd(b,a%b,x,y); 9 int r=x;x=y;y=r-a/b*y; 10 } 11 main(){//freopen("ex_simple2.in","r",stdin); 12 int t;scanf("%lld",&t); 13 while(t--){ 14 int n,m,q,ans=0,x,y,g; 15 scanf("%lld%lld%lld",&n,&m,&q); 16 if(n>m)n^=m^=n^=m; 17 g=gcd(n,m);ans+=q-q/g; 18 n/=g;m/=g;q/=g; 19 ex_gcd(n,m,x,y);x%=m;//printf("x=%lld\n",x); 20 for(int i=1;i<n;++i)ans+=min(((m-i)*x%m+m)%m,(q-i+n)/n);//,printf("%lld\n",ans); 21 printf("%lld\n",ans); 22 } 23 }
T2：Walk
卡常题。
1000000的w以内最多有240个约数，所以做dp找每个约数的最长链就好了。
1 //1000000以内每个数最多有240个约数，而平均只有14个 2 //注意卡内存:61079552个int 3 #include<cstdio> 4 #include<iostream> 5 #include<unordered_map> 6 using namespace std; 7 int FIR[1000005],L[14000000],TO[14000000],CNT; 8 void add(int a,int d){L[++CNT]=FIR[a];FIR[a]=CNT;TO[CNT]=d;} 9 int fir[400005],l[800005],to[800005],w[800005],cnt; 10 void link(int a,int b,int v){l[++cnt]=fir[a];fir[a]=cnt;to[cnt]=b;w[cnt]=v;} 11 int ans[400005],n; 12 unordered_map<int,int>dp[400005]; 13 int read(){ 14 register int p=0;register char ch=getchar(); 15 while(ch<'0'||ch>'9')ch=getchar(); 16 while(ch>='0'&&ch<='9')p=(p<<3)+(p<<1)+ch-48,ch=getchar(); 17 return p; 18 } 19 void dfs(int p,int fa){ 20 for(int i=fir[p];i;i=l[i])if(to[i]!=fa){ 21 dfs(to[i],p); 22 for(int j=FIR[w[i]];j;j=L[j]){ 23 int x=dp[to[i]][TO[j]],y=dp[p][TO[j]]; 24 ans[x+y+1]=max(ans[x+y+1],TO[j]); 25 dp[p][TO[j]]=max(y,x+1); 26 } 27 dp[to[i]].clear(); 28 } 29 } 30 int main(){//freopen("t2.in","r",stdin);freopen("my.out","w",stdout); 31 n=read();int mx=0; 32 for(int x,y,w,i=1;i<n;++i)x=read(),y=read(),w=read(),link(x,y,w),link(y,x,w),mx=max(mx,w); 33 for(int i=1;i<=mx;++i)for(int j=i;j<=mx;j+=i)add(j,i); 34 dfs(1,0); 35 for(int i=n;i;--i)ans[i]=max(ans[i],ans[i+1]); 36 for(int i=1;i<=n;++i)printf("%d\n",ans[i]); 37 }
然后就T成暴力了。
改为对于每个约数建边，根号硬筛而不是预处理，就A了。
1 #include<cstdio> 2 #include<iostream> 3 #include<vector> 4 using namespace std; 5 vector<int>a[1000004],b[1000005]; 6 int fir[400005],l[800005],to[800005],cnt; 7 void link(int a,int b){l[++cnt]=fir[a];fir[a]=cnt;to[cnt]=b;} 8 int ans[400005],lgst; 9 int read(){ 10 register int p=0;register char ch=getchar(); 11 while(ch<'0'||ch>'9')ch=getchar(); 12 while(ch>='0'&&ch<='9')p=(p<<3)+(p<<1)+ch-48,ch=getchar(); 13 return p; 14 } 15 int dfs(int p,int fa){ 16 int mx=0; 17 for(int i=fir[p];i;i=l[i])if(to[i]!=fa){ 18 int x=dfs(to[i],p)+1; 19 lgst=max(lgst,mx+x);mx=max(mx,x); 20 }fir[p]=0;return mx; 21 } 22 int main(){//freopen("ex_walk2.in","r",stdin);freopen("my.out","w",stdout); 23 register int n=read(); 24 for(int t=1,x,y,w;t<n;++t){ 25 x=read(),y=read(),w=read(); 26 for(int i=1;i*i<=w;++i)if(w%i==0){ 27 a[i].push_back(x),b[i].push_back(y); 28 if(i*i!=w)a[w/i].push_back(x),b[w/i].push_back(y); 29 } 30 } 31 for(int i=1;i<=1000000;++i){ 32 for(int j=0;j<a[i].size();++j)link(a[i][j],b[i][j]),link(b[i][j],a[i][j]); 33 for(int j=0;j<a[i].size();++j)if(fir[a[i][j]])dfs(a[i][j],0); 34 ans[lgst]=max(ans[lgst],i); 35 cnt=lgst=0; 36 } 37 for(int i=n;i;--i)ans[i]=max(ans[i],ans[i+1]); 38 for(int i=1;i<=n;++i)printf("%d\n",ans[i]); 39 }
T3：Travel
思路懂了，还想到了优化。
但是下午就要考试显然没时间改了。