A - Toy Train

很顯然，一個站有多少個糖，那么就要從這個點運多少次。設第i個點有\(a_i\)個糖，那么就要轉\(a_i-1\)圈，然后再走一段。很顯然最后一段越小越好。

然后枚舉起點后，每個點的答案就是起點到他的距離加上再走的距離。然后取個max就好了。

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<cctype> #define qmin(x,y) (x=min(x,y)) #define qmax(x,y) (x=max(x,y)) #define vi vector<int> #define vit vector<int>::iterator #define pir pair<int,int> #define fr first #define sc second #define mp(x,y) make_pair(x,y) using namespace std;inline char gc() { // static char buf[100000],*p1,*p2; // return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;return getchar(); }template<class T> int read(T &ans) {ans=0;char ch=gc();T f=1;while(!isdigit(ch)) {if(ch==EOF) return -1;if(ch=='-') f=-1;ch=gc();}while(isdigit(ch))ans=ans*10+ch-'0',ch=gc();ans*=f;return 1; }template<class T1,class T2> int read(T1 &a,T2 &b) {return read(a)!=EOF&&read(b)!=EOF?2:EOF; }template<class T1,class T2,class T3> int read(T1 &a,T2 &b,T3 &c) {return read(a,b)!=EOF&&read(c)!=EOF?3:EOF; }typedef long long ll; const int Maxn=1100000; const ll inf=0x3f3f3f3f3f3f3f3fll;int n,m,a[Maxn],b[Maxn],x,y;signed main() { // freopen("test.in","r",stdin);read(n,m);memset(b,0x3f,sizeof(b));for(int i=1;i<=m;i++) {read(x,y);a[x]++;if(y>x) qmin(b[x],y-x);else qmin(b[x],y+n-x);}for(int i=1;i<=n;i++) if(!a[i]) b[i]=0;for(int i=1;i<=n;i++) {int ans=0;for(int j=1;j<=n;j++) {int temp;if(j>=i) temp=j-i;else temp=j+n-i;temp+=(a[j]-1)*n+b[j];qmax(ans,temp);}printf("%d ",ans);}return 0; }

B - Wrong Answer

厚顏無恥地求一波贊

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<cctype> #define qmin(x,y) (x=min(x,y)) #define qmax(x,y) (x=max(x,y)) #define vi vector<int> #define vit vector<int>::iterator #define pir pair<int,int> #define fr first #define sc second #define mp(x,y) make_pair(x,y) using namespace std;inline char gc() { // static char buf[100000],*p1,*p2; // return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;return getchar(); }template<class T> int read(T &ans) {ans=0;char ch=gc();T f=1;while(!isdigit(ch)) {if(ch==EOF) return -1;if(ch=='-') f=-1;ch=gc();}while(isdigit(ch))ans=ans*10+ch-'0',ch=gc();ans*=f;return 1; }template<class T1,class T2> int read(T1 &a,T2 &b) {return read(a)!=EOF&&read(b)!=EOF?2:EOF; }template<class T1,class T2,class T3> int read(T1 &a,T2 &b,T3 &c) {return read(a,b)!=EOF&&read(c)!=EOF?3:EOF; }typedef long long ll; const int Maxn=1100000; const ll inf=0x3f3f3f3f3f3f3f3fll;int k;signed main() { // freopen("test.in","r",stdin);read(k);int temp=1999-k%1999;puts("2000");for(int i=1;i<=1998;i++) printf("0 ");printf("%d ",-temp);printf("%d\n",(k+temp)/1999+temp);return 0; }

C - Morse Code

首先，直接n方DP求每一段能代表的字符串的個數很簡單，然后因為相同的子串只能統計一次答案，那么就用一顆trie樹來存就好了。

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<cctype> #define qmin(x,y) (x=min(x,y)) #define qmax(x,y) (x=max(x,y)) #define vi vector<int> #define vit vector<int>::iterator #define pir pair<int,int> #define fr first #define sc second #define mp(x,y) make_pair(x,y) using namespace std;inline char gc() { // static char buf[100000],*p1,*p2; // return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;return getchar(); }template<class T> int read(T &ans) {ans=0;char ch=gc();T f=1;while(!isdigit(ch)) {if(ch==EOF) return -1;if(ch=='-') f=-1;ch=gc();}while(isdigit(ch))ans=ans*10+ch-'0',ch=gc();ans*=f;return 1; }template<class T1,class T2> int read(T1 &a,T2 &b) {return read(a)!=EOF&&read(b)!=EOF?2:EOF; }template<class T1,class T2,class T3> int read(T1 &a,T2 &b,T3 &c) {return read(a,b)!=EOF&&read(c)!=EOF?3:EOF; }typedef long long ll; const int Maxn=11000000; const int inf=0x3f3f3f3f; const int mod=1000000007;int n,f[5100],a[Maxn],ans,ch[Maxn][2],cnt=1;signed main() { // freopen("test.in","r",stdin);read(n);f[0]=1;for(int i=1;i<=n;i++)read(a[i]);for(int i=1;i<=n;i++) {memset(f,0,sizeof(f));f[i+1]=1;int now=1;for(int j=i;j>=1;j--) {for(int k=1;k<=3;k++) f[j]=(f[j]+f[j+k])%mod;if(j<=i-3) {if(!a[j]) {if(a[j+1]) {if(a[j+2]||!a[j+3]) f[j]=(f[j]+f[j+4])%mod;}else {if(!a[j+2]||!a[j+3]) f[j]=(f[j]+f[j+4])%mod;}}elseif(a[j+3]) {if(!a[j+1]||!a[j+2]) f[j]=(f[j]+f[j+4])%mod;}else if(!a[j+1]||!a[j+2]) f[j]=(f[j]+f[j+4])%mod;}if(!ch[now][a[j]]) {ch[now][a[j]]=++cnt;ans=(ans+f[j])%mod;}now=ch[now][a[j]];}printf("%d\n",ans);}return 0; }

D - Isolation

枚舉右端點，然后把每個數字最后一次出現的位置設為1，倒數第二次出現的位置設為-1，這樣，如果一個后綴和小于等于k，就可以轉移。

然后進行分塊，每一塊記總和和后綴小于等于一個數的dp值的和即可。

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<cctype> #include<cmath> #define qmin(x,y) (x=min(x,y)) #define qmax(x,y) (x=max(x,y)) #define vi vector<int> #define vit vector<int>::iterator #define pir pair<int,int> #define fr first #define sc second #define mp(x,y) make_pair(x,y) using namespace std;inline char gc() { // static char buf[100000],*p1,*p2; // return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;return getchar(); }template<class T> int read(T &ans) {ans=0;char ch=gc();T f=1;while(!isdigit(ch)) {if(ch==EOF) return -1;if(ch=='-') f=-1;ch=gc();}while(isdigit(ch))ans=ans*10+ch-'0',ch=gc();ans*=f;return 1; }template<class T1,class T2> int read(T1 &a,T2 &b) {return read(a)!=EOF&&read(b)!=EOF?2:EOF; }template<class T1,class T2,class T3> int read(T1 &a,T2 &b,T3 &c) {return read(a,b)!=EOF&&read(c)!=EOF?3:EOF; }typedef long long ll; const int Maxn=110000; const int inf=0x3f3f3f3f; const int mod=998244353;int bn[Maxn],bl[Maxn],br[Maxn],f[Maxn],b[Maxn],a[Maxn],in[Maxn],bf[500][1000],n,k,las[Maxn],pre[Maxn];inline int modd(int x) {return x>=mod?x-mod:x; }void update(int x) {memset(bf[x],0,sizeof(bf[0]));bn[x]=0;for(int i=br[x];i>=bl[x];i--) {bf[x][bn[x]+500]=modd(bf[x][bn[x]+500]+f[i]);bn[x]+=b[i];}for(int i=1;i<1000;i++) bf[x][i]=modd(bf[x][i]+bf[x][i-1]); }signed main() { // freopen("test.in","r",stdin);read(n,k);int m=sqrt(n);memset(bl,0x3f,sizeof(bl));memset(las,-1,sizeof(las));memset(pre,-1,sizeof(pre));f[0]=1;for(int i=0;i<=n;i++) {in[i]=i/m;qmin(bl[in[i]],i);qmax(br[in[i]],i);}update(0);for(int i=1;i<=n;i++) {read(a[i]);if(~las[a[i]]) {pre[i]=las[a[i]];b[las[a[i]]]=-1;update(in[las[a[i]]]);if(~pre[las[a[i]]]) {b[pre[las[a[i]]]]=0;update(in[pre[las[a[i]]]]);}}b[i]=1;int now=1;for(int j=i-1;j>=bl[in[i]];j--) {if(now<=k) f[i]=modd(f[i]+f[j]);now+=b[j];}for(int j=in[i]-1;j>=0;j--) {if(k-now+500>0) f[i]=modd(f[i]+bf[j][min(k-now+500,999)]);now+=bn[j];}update(in[i]);las[a[i]]=i;}printf("%d\n",f[n]);return 0; }

轉載于:https://www.cnblogs.com/shanxieng/p/10429233.html

總結

以上是生活随笔為你收集整理的Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 1)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。