首页 > 代码库 > Codeforces Round #422 (Div. 2)
Codeforces Round #422 (Div. 2)
A:
给你两个数 (最小的那个<=12) 问这两个数阶乘的GCD
我都吓傻了
直接fac(min(a,b)) 搞定
//By SiriusRen#include <bits/stdc++.h>using namespace std;int A,B;long long t=1;int main(){ scanf("%d%d",&A,&B); if(A>B)swap(A,B); for(int i=1;i<=A;i++)t=t*i; printf("%I64d\n",t);}
B:
暴力匹配即可
//By SiriusRen#include <bits/stdc++.h>using namespace std;int n,m,ans[2005],ans1=0x3f3f3f3f,ans2;char a[2005],b[2005];int main(){ scanf("%d%d",&n,&m); scanf("%s%s",a+1,b+1); for(int i=1;i<=m-n+1;i++){ int t=0; for(int j=1;j<=n;j++){ if(a[j]!=b[i+j-1])t++; } ans[i]=t; } for(int i=1;i<=m-n+1;i++){ if(ans1>ans[i])ans1=ans[i],ans2=i; }printf("%d\n",ans1); for(int i=1;i<=n;i++)if(a[i]!=b[ans2+i-1])printf("%d ",i);}
C:
我似乎是写麻烦了?
搞了两个vector
vector是按照时间长度塞的
一个按照排序 另一个按照r排序
newr<l或者newl>r中的最小值
搞一个前缀min 一个后缀min
写完调一年
//By SiriusRen#include <bits/stdc++.h>using namespace std;const int N=200050,inf=2e9+1;int n,x,l[N],r[N],c[N],ans=inf;struct Node1{int l,r,c,s;Node1(){}Node1(int L,int R,int C){l=L,r=R,c=C;}};struct Node2{int l,r,c,s;Node2(){}Node2(int L,int R,int C){l=L,r=R,c=C;}};vector<Node1>vecl[N];vector<Node2>vecr[N];bool operator<(Node1 a,Node1 b){if(a.l!=b.l)return a.l<b.l;return a.c<b.c;}bool operator<(Node2 a,Node2 b){if(a.r!=b.r)return a.r<b.r;return a.c<b.c;}int main(){ scanf("%d%d",&n,&x); for(int i=1;i<=n;i++){ scanf("%d%d%d",&l[i],&r[i],&c[i]); vecl[r[i]-l[i]+1].push_back(Node1(l[i],r[i],c[i])); vecr[r[i]-l[i]+1].push_back(Node2(l[i],r[i],c[i])); } for(int i=0;i<=x;i++){ sort(vecl[i].begin(),vecl[i].end()); sort(vecr[i].begin(),vecr[i].end()); int t=vecl[i].size()-1; if(~t)vecl[i][t].s=vecl[i][t].c,vecr[i][0].s=vecr[i][0].c; for(int j=t-1;j>=0;j--)vecl[i][j].s=min(vecl[i][j+1].s,vecl[i][j].c); for(int j=1;j<=t;j++)vecr[i][j].s=min(vecr[i][j-1].s,vecr[i][j].c); } for(int i=1;i<=n;i++){ int len=r[i]-l[i]+1,len2=x-len; if(len2<0)continue; int t1=lower_bound(vecl[len2].begin(),vecl[len2].end(),Node1(r[i]+1,0,0))-vecl[len2].begin(); int t2=upper_bound(vecr[len2].begin(),vecr[len2].end(),Node2(0,l[i]-1,inf))-vecr[len2].begin()-1; if(t1>=0&&t1<vecl[len2].size())ans=min(ans,c[i]+vecl[len2][t1].s); if(t2>=0&&t2<vecr[len2].size())ans=min(ans,c[i]+vecr[len2][t2].s); }printf("%d\n",ans==inf?-1:ans);}
D:
筛出来每个数的最小质因子
质数就是x*(x-1)/2
非质数:f[i]=(1ll*f[mindiv[i]]*i/mindiv[i]+f[i/mindiv[i]])%mod;
//By SiriusRen#include <bits/stdc++.h>using namespace std;const int N=5000500,mod=1000000007;int mindiv[N],prime[N],f[N],t,l,r,tot,ans,temp=1;int main(){ for(int i=2;i<N;i++){ if(!mindiv[i])mindiv[i]=i,prime[++tot]=i,f[i]=1ll*i*(i-1)/2%mod; for(int j=1;j<=tot&&i*prime[j]<N;j++){ mindiv[i*prime[j]]=prime[j]; if(i%prime[j]==0)break; } } scanf("%d%d%d",&t,&l,&r); for(int i=2;i<=r;i++)f[i]=(1ll*f[mindiv[i]]*i/mindiv[i]+f[i/mindiv[i]])%mod; for(int i=l;i<=r;i++){ ans=(ans+1ll*f[i]*temp)%mod,temp=1ll*temp*t%mod; }printf("%d\n",ans);}
E:
f[i][j]表示s串匹配到i 用了j次操作
f[i+1][j]=max(f[i+1][j],f[i][j])
f[i+lcp][j+1]=max(f[i+lcp][j+1],f[i][j]+lcp)
lcp直接后缀数组搞了~
(hash也行)
//By SiriusRen#include <bits/stdc++.h>using namespace std;const int N=400050;int cntA[N],cntB[N],A[N],B[N],sa[N],rk[N],tsa[N],ht[N],lens,lent,n,Log[N],g[N][20],P,f[N][50],ans;char s[N];void SA(){ for(int i=1;i<=n;i++)cntA[s[i]]++; for(int i=1;i<=256;i++)cntA[i]+=cntA[i-1]; for(int i=n;i;i--)sa[cntA[s[i]]--]=i; rk[sa[1]]=1; for(int i=2;i<=n;i++)rk[sa[i]]=rk[sa[i-1]]+(s[sa[i]]!=s[sa[i-1]]); for(int l=1;rk[sa[n]]<n;l<<=1){ memset(cntA,0,sizeof(cntA)); memset(cntB,0,sizeof(cntB)); for(int i=1;i<=n;i++)cntA[A[i]=rk[i]]++,cntB[B[i]=(i+l<=n?rk[i+l]:0)]++; for(int i=1;i<=n;i++)cntA[i]+=cntA[i-1],cntB[i]+=cntB[i-1]; for(int i=n;i;i--)tsa[cntB[B[i]]--]=i; for(int i=n;i;i--)sa[cntA[A[tsa[i]]]--]=tsa[i]; rk[sa[1]]=1; for(int i=2;i<=n;i++)rk[sa[i]]=rk[sa[i-1]]+(A[sa[i]]!=A[sa[i-1]]||B[sa[i]]!=B[sa[i-1]]); } for(int i=1,j=0;i<=n;i++){ j=j?j-1:0; while(s[i+j]==s[sa[rk[i]-1]+j])j++; ht[rk[i]]=j; } for(int i=1;i<=n;i++)g[i][0]=ht[i],Log[i]=Log[i>>1]+1; for(int j=1;j<=19;j++){ for(int i=1;i<=n;i++){ g[i][j]=min(g[i][j-1],g[i+(1<<(j-1))][j-1]); } }}int lcp(int x,int y){ if(x==y)return n-x+1; x=rk[x],y=rk[y]; if(x>y)swap(x,y); x++; int t=Log[y-x+1]; return min(g[x][t],g[y-(1<<t)+1][t]);}int main(){ scanf("%d%s",&lens,s+1); scanf("%d%s",&lent,s+lens+2); Log[0]=-1,s[lens+1]=‘#‘,n=lens+lent+1,SA(); scanf("%d",&P); for(int i=1;i<=lens+1;i++){ for(int j=0;j<=P;j++){ f[i+1][j]=max(f[i+1][j],f[i][j]); if(f[i][j]==lent){puts("YES");return 0;}// if(s[i+1]!=s[lens+1+f[i][j]])continue; int LCP=lcp(i,lens+1+f[i-1][j]+1);// if(LCP)printf("i=%d j=%d LCP=%d\n",i,j,LCP); f[i+LCP][j+1]=max(f[i+LCP][j+1],f[i][j]+LCP); } } puts("NO"); }
F:
DFS一下搞定
//By SiriusRen
#include <bits/stdc++.h>using namespace std;vector<int> G[1001];map<pair<int, int>, int> idx;int N; double t[1001];void dfs(int x, int l){ int d = G[x].size(); double v = l == 0 ? 0 : 1 + t[x],dt = 2. / d; for (int y : G[x]) if (y != l){ v += dt; while (v >= 2) v -= 2; t[y] = v; printf ("1 %d ",idx[{x,y}]); if (v < 1) printf ("%d %d %.12lf\n",x,y,v); else printf ("%d %d %.12lf\n",y,x,v-1); dfs(y,x); }}int main(){ scanf("%d",&N); for (int i=1;i<N;i++){ int x,y; scanf ("%d %d",&x,&y); idx[{x,y}] = idx[{y,x}] = i; G[x].push_back(y),G[y].push_back(x); } printf ("%d\n",N-1); dfs(1,0);}
Codeforces Round #422 (Div. 2)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。