Codeforces Round #650 (Div. 3) (D 思维 E 思维 F1 dp F2 dp)ccsudeer-

题目链接

D. Task On The Board

题意:给你一个s串，要求你选取m个字符出来构成t串，t串中有b数组，b[i]的定义是   要求构造的t串 满足给定b数组的数值。题目保证一定有解

做法：从b[i]为0的地方开始放 s串中 最大的 字符 ，接着其他位置的 b[i]相应的减去，又一轮找等于0的位置，赋第二大字符，依次类推即可。

 #include<bits/stdc++.h> using namespace std; const int N=60; char s[N],t[N]; int b[N],vs[30],vis[N],m,n; void init() {     memset(vs,0,sizeof(vs));     memset(vis,0,sizeof(vis));     memset(b,0,sizeof(b)); } void solve() {     init();     scanf("%s",s+1);     n=strlen(s+1);     for(int i=1;i<=n;++i) vs[s[i]-'a'+1]++;      scanf("%d",&m);     for(int i=1;i<=m;++i) scanf("%d",&b[i]);     int tot=0;     int pre=26;     //puts("***");     while(tot<m){         vector<int>G;         for(int i=1;i<=m;++i){             if(vis[i]) continue;             if(!b[i]) G.push_back(i);//找到 b[i]==0的下标         }         for(;pre;--pre){//找到一个字母去填             if(vs
>=G.size()){                 for(int v:G) {                     t[v]=pre-1+'a';                     vis[v]=1;                 }                 vs
-=G.size();                 tot+=G.size();                 pre--;                 break;             }         }        // printf("G.size():%dn",G.size());          for(int i=1;i<=m;++i){             if(vis[i]) continue;             //printf("i:%d n",i);             for(int v:G){                 b[i]-=abs(v-i);             }         }         //for(int i=1;i<=m;++i) printf("%d ",b[i]);      }     for(int i=1;i<=m;++i) printf("%c",t[i]);     puts("");  } int main() {     int _;scanf("%d",&_);while(_--) solve(); } 

E. Necklace Assembly

题意：给你n个字符，要你选取一些字符 构造最长的字符 使得 字符顺时针（往后移）动k位后依然是 原来的字符串。

做法：枚举长度，建图跑连通块，判断一下是否有  相同数量的字符  能填满该连通块即可。

 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1005 #define inf 1e9 #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) using namespace std;  inline ll read() {  ll x=0,w=1; char c=getchar();  while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}  while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}  return w==1?x:-x; } const int N=3e3+10; int vs[30],n,k,vs1[30],X[N],vis[N]; vector<int>G[N]; char s[N]; int bfs(int u) {     int ans=0;     queue<int>que;     que.push(u);     vis[u]=1;     while(que.size()){         int now=que.front();que.pop();         ans++;         for(int v:G[now]){             if(vis[v]) continue;             vis[v]=1;             que.push(v);         }     }     return ans; } void solve() {     memset(vs,0,sizeof(vs));     n=read(),k=read();      scanf("%s",s+1);     rep(i,1,n) vs[s[i]-'a'+1]++;      sort(vs+1,vs+1+26);     int ans=0;     for(int i=1;i<=n;++i){         for(int j=1;j<=i;++j){             int nx=(j+k)%i;             if(nx==0) nx=i; //            if(i==5){ //                printf("j:%d nx:%dn",j,nx); //            }             G[j].push_back(nx);             G[nx].push_back(j);         }          int len=0;         for(int j=1;j<=i;++j) vis[j]=0;         for(int j=1;j<=i;++j){             if(!vis[j]){                 //if(i==5) printf("j:%dn",j);                 X[++len]=bfs(j);             }         }         sort(X+1,X+1+len); //        if(i==5){ //            printf("i:%d len:%dn",i,len); // //            for(int i=1;i<=len;++i) printf("%d ",X[i]); //            puts(""); //        }           for(int j=1;j<=26;++j) vs1[j]=vs[j];           int j=1,id=1;         while(id<=26&&j<=len){             if(vs1[id]>=X[j]) vs1[id]-=X[j],++j;             else ++id;         }         if(j>len) ans=max(ans,i);          for(int j=1;j<=i;++j) vis[j]=0,G[j].clear();     }     printf("%dn",ans);   }      int main() {     int _=read();while(_--)     {         solve();     } } /* 5 5 4 ababa */ 

F1. Flying Sort (Easy Version)

题意：给定n个不同的数，每次可选择一个数，移到最头  或移到最尾，求最少的操作次数，使得数组非递减。

 

做法：找最大的 不变的连续的子序列，n-mx即可。

 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back #define mk make_pair const int N = 2e5+10; const int mod = 1e9+7;  int t, n, a[N], b[N], dp[N], vis[N];  int main(){  cin >> t;  while(t--){   cin >> n;   for(int i = 1; i <= n; i++){    cin >> a[i];    dp[i] = 1;    b[i] = a[i];    vis[i] = 0;   }    sort(b+1, b+n+1);   int len = unique(b+1, b+n+1) - b - 1;    for(int i = 1; i <= n; i++)         a[i] = lower_bound(b+1, b+1+len, a[i]) - b;     for(int i = 1; i <= n; i++){    if(vis[a[i]-1]) dp[i] = dp[vis[a[i]-1]] + 1;    vis[a[i]] = i;   }    int l = 0;   for(int i = 1; i <= n; i++) l = max(l,dp[i]);   cout << n-l << "n";  }  return 0; } 

F2. Flying Sort (Hard Version)

做法：这题跟F1的却别是，n大了  数是可以重复的。

题意：dp做法，参考来自：博客

 #include<bits/stdc++.h> using namespace std; const int N=2e5+10; int a[N],n,X[N],len,dp[N][3],num[N],fi[N],pos[N],last[N]; void solve() {     scanf("%d",&n);     len=0;     for(int i=1;i<=n;++i) {scanf("%d",&a[i]);X[++len]=a[i];}       sort(X+1,X+1+len);     len=unique(X+1,X+1+len)-X-1;     //for(int i=1;i<=n;++i) a[i]=lower_bound(X+1,X+1+len,a[i])-X;      for(int i=1;i<=n;++i){         dp[i][0]=dp[i][1]=dp[i][2]=num[i]=pos[i]=fi[i]=0;     }      for(int i=1;i<=n;++i){         a[i]=lower_bound(X+1,X+1+len,a[i])-X;         if(!fi[a[i]]){             fi[a[i]]=i,pos[a[i]]=i;         }         last[a[i]]=i;         ++num[a[i]];     }      int mx=0;     for(int i=1;i<=n;++i){         dp[i][0]=dp[pos[a[i]]][0]+1;         dp[i][1]=max({dp[pos[a[i]]][1],dp[pos[a[i]-1]][0],dp[pos[a[i]-1]][2]})+1;         if(i==last[a[i]]){             dp[i][2]=dp[fi[a[i]]][1]+num[a[i]]-1;         }         mx=max({mx,dp[i][0],dp[i][1],dp[i][2]});         pos[a[i]]=i;     }      printf("%dn",n-mx);  } int main() {     int _;scanf("%d",&_);while(_--) solve(); }