啊人生第一次打多校被虐
紧随yql的脚步做题。
1001：
可以发现我们平时表示的数都是$x*log_{10}{10}$，所以类似于做一个换底公式就可以了。
-1是一个烟雾弹，因为小学生都知道2^n不可能是整十的数。
#include<bits/stdc++.h> #define N 100005 using namespace std; double x,y; int m; int main(){ int cnt=0; while(scanf("%d",&m)==1){ x=(double)m; x*=log10(2); printf("Case #%d: %d ",++cnt,(int)x); } }
1002：
这题先把字符串拆成26进制，然后贪心做就可以了。
#include<bits/stdc++.h> const int N=1e6+10; const int M=1e5+9; const int yql=1e9+7; using namespace std; int f[26][N],p[N],vis[200],n; char s[N],ss[N]; inline bool cmp(int a,int b){ for(int i=M;i>=0;i--)if(f[a][i]!=f[b][i])return f[a][i]>f[b][i]; return a<b; } int main(){ int cas=0; while(scanf("%d",&n)==1){ memset(f,0,sizeof(f));memset(vis,1,sizeof(vis)); for(int i=1;i<=n;i++){ scanf("%s",ss);int len=strlen(ss); for(int j=0;j<len;j++)f[ss[j]-'a'][len-j-1]++; if(len>1)vis[ss[0]-'a']=0; } for(int i=0;i<26;i++){ for(int j=0;j<M;j++){ f[i][j+1]+=f[i][j]/26; f[i][j]%=26; } p[i]=i; } sort(p,p+26,cmp);int r=25; while(!vis[p[r]])r--; int tmp=p[r]; for(int i=r;i<25;i++)p[i]+=p[i+1]; int ans=0;p[25]=tmp;int sum=0; for(int i=0;i<26;i++){ int val=25-i,sum=0; for(int j=M-1;j>=0;j--){ sum=(1LL*sum*26+f[p[i]][j])%yql; f[p[i]][j]=0; } ans+=1LL*val*sum%yql; if(ans>=yql)ans-=yql; } printf("Case #%d: %d ",++cas,ans); } }
1003：
有点像雅礼集训的某道题，洛谷以前某模拟赛原题。
如果是洛谷做法是点分治带log，肯定要被卡常
然后有神奇的On做法一遍dfs统计答案
可以看成是矩形面积并，这就类似与那道雅礼题了，就可以树状数组维护一维就可以了。
也是一个log，但是常数优越。
#include<bits/stdc++.h> const int N=200010; using namespace std; typedef long long ll; struct Edge{int u,v,next;}G[N<<1]; int tot=0,head[N],a[N],d[N],lpos[N],rpos[N],cnt=0,q[N],fa[N],n; int c[N*5]; ll w[N],ans; inline int lowbit(int x){return x&(-x);} inline void addedge(int u,int v){ G[++tot].u=u;G[tot].v=v;G[tot].next=head[u];head[u]=tot; G[++tot].u=v;G[tot].v=u;G[tot].next=head[v];head[v]=tot; } bool cmp(int x,int y){ if(a[x]==a[y])return d[x]>d[y]; return a[x]<a[y]; } inline void add(int x,int val){ if(!x)return; for(int i=lpos[x];i<=n;i+=lowbit(i))c[i]+=val; } inline int ask(int x){ int ans=0; for(int i=x;i;i-=lowbit(i))ans+=c[i]; return ans; } void dfs(int u,int f){ lpos[u]=++cnt; for(int i=head[u];i;i=G[i].next){ int v=G[i].v;if(v==f)continue; fa[v]=u;d[v]=d[u]+1; dfs(v,u); } rpos[u]=cnt; } inline int size(int x){return ask(rpos[x])-ask(lpos[x]-1);} inline void solve(int l,int r,int val){ ans+=w[n]; for(int i=l;i<=r;i++){ int u=q[i]; for(int i=head[u];i;i=G[i].next){ int v=G[i].v;if(v==fa[u]||a[v]==val)continue; ans-=w[size(v)]; } add(fa[u],-size(u)); } if(a[1]!=val)ans-=w[size(1)]; for(int i=r;i>=l;i--){ int u=q[i]; add(fa[u],size(u)); } } inline int read(){ int f=1,x=0;char ch; do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9'); do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9'); return f*x; } int main(){ int cas=0; for(int i=1;i<N;i++)w[i]=1LL*i*i; while(scanf("%d",&n)==1){ for(int i=1;i<=n;i++)a[i]=read(); ans=0;cnt=0;tot=0;memset(head,0,sizeof(head)); for(int i=1;i<n;i++){ int u=read(),v=read(); addedge(u,v); } for(int i=1;i<=n;i++)q[i]=i,c[i]=0; dfs(1,0); sort(q+1,q+n+1,cmp); for(int i=1;i<=n;i++)add(i,1); int j=0; for(int i=1;i<=n;i=j){ for(j=i;j<=n&&a[q[i]]==a[q[j]];j++);solve(i,j-1,a[q[i]]); } ans-=n;ans>>=1; printf("Case #%d: %I64d ",++cas,ans); } }
1006：
找循环节，先确定一个出现次数以及因数
然后在另一个里面找
具体可以参考题解公式。
#include<bits/stdc++.h> const int N=1000010; const int yql=1e9+7; using namespace std; int n,m,cnt,cas,a[N],b[N],c[N],vis[N]; inline int read(){ int f=1,x=0;char ch; do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9'); do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9'); return f*x; } inline void dfsa(int u){ if(vis[u])return;vis[u]=1;++cnt; if(!vis[a[u]])dfsa(a[u]); } inline void dfsb(int u){ if(vis[u])return;vis[u]=1;++cnt; if(!vis[b[u]])dfsb(b[u]); } int main(){ while(scanf("%d%d",&n,&m)==2){ memset(vis,0,sizeof(vis));memset(c,0,sizeof(c)); for(int i=0;i<n;i++)a[i]=read();for(int i=0;i<m;i++)b[i]=read(); for(int i=0;i<m;i++)if(!vis[i]){ cnt=0;dfsb(i);c[cnt]++; } for(int i=1;i<=m;i++)c[i]=1LL*i*c[i]%yql; int lim=max(n,m); for(int i=lim;i;i--)for(int j=i+i;j<=lim;j+=i)c[j]=(c[j]+c[i])%yql; for(int i=0;i<=n;i++)vis[i]=0;int ans=1; for(int i=0;i<n;i++)if(!vis[i]){ cnt=0;dfsa(i);ans=1LL*ans*c[cnt]%yql; } printf("Case #%d: %d ",++cas,ans); } }
1011：
找规律。
#include<bits/stdc++.h> typedef long long ll; using namespace std; ll m;int cnt,n; int main(){ while(scanf("%d%lld",&n,&m)==2){ printf("Case #%d: ",++cnt); if(m<=n){printf("%lld ",m);continue;} m-=n;m=(m-1)%(n*2-2)+1; if(m<=n-1){printf("%lld ",m);continue;} m-=n-1; if(m<=n-2){printf("%lld ",m);continue;} else printf("%d ",n); } }
以上是考场完成的……
剩下的能补几题是几题吧。