A
签到
F
找规律，发现(n+2)^2-n^2=4n+4=4(n+1)，于是4个凑一组，按余数进行讨论即可，code略
I
签到
#include<bits/stdc++.h> using namespace std; int n; long long ans; char s[100007]; map<pair<int,int>,int>mp; int main() { int T;scanf("%d",&T); while(T--) { scanf("%d",&n); scanf("%s",s+1); mp.clear(); int x=0,y=0; ans=0; mp[make_pair(0,0)]=1; for(int i=1;i<=n;i++) { if(s[i]==‘U‘)x++;else if(s[i]==‘D‘)x--; else if(s[i]==‘L‘)y++;else y--; ans+=mp[make_pair(x,y)]; ++mp[make_pair(x,y)]; } printf("%lld\n",ans); } }
L
天真的以为2e6能用log过，说白了是自己太天真……
实际上一开始想的思路是正确的但是绕了好大一个弯子。
答案单调不减显而易见，很容易发现每次记录每个模数取模后的最小值，这样大概是一个log……
然后最开始发现的答案大概是n/maxp的结论就可以用了，枚举值即可，复杂度就是O(n)
#include<cstdio> #include<algorithm> const int N=2e6+7,M=2e5+7; typedef unsigned long long ull; int n,m,p[M],a[N]; ull pw[N]; int main() { pw[0]=1;for(int i=1;i<=2e6;i++)pw[i]=pw[i-1]*23333; int T;scanf("%d",&T); while(T--) { ull ans=0,lcm=1; int mx=1; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d",&p[i]); mx=std::max(mx,p[i]); if(lcm<=n)lcm*=p[i]; } for(int i=1;i<mx;i++)a[i]=1; for(int i=mx;i<=n;i++)a[i]=0; for(int v=2,l,r=mx-1;r<=n;v++) { l=r+1; int nr=0; for(int i=1;i<=m;i++)nr=std::max(nr,r/p[i]*p[i]+p[i]-1); if(nr<l)break; for(int i=l;i<=nr&&i<=n;i++)a[i]=v; r=nr; } for(int i=1;i<=n;i++)ans+=a[i]*pw[n-i]; printf("%llu\n",ans); } }
持续更新中……