首页 > 代码库 > 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)