2022上海赛（A,E,H)

Dashboard - 2022 Shanghai Collegiate Programming Contest - Codeforces

A. Another A+B Problem

题意：给出一个表达式 xx+xx=xx的格式，然后每个位置有三种字母表示三种状态，G表示这个位置的字母在答案中存在并且位置相同，P表示这个位置的字母在答案中存在但并不在这个位置，B表示这种字符在答案中不存在，或者存在与答案中数目相同的颜色不为B的位置，问有多少不同的答案。

题解: 模拟，如果为G就不管直接加上，如果为P，用一个sum计数器存储一下，表示最少有sum个数要使用掉，并且记录当前位置，保证这个数不能在这个位置出现，如果B，表示这个数不会出现，或者最多出现sum次+G出现的次数，所以按照前面的方式模拟，保证使用次数不超过sum即可，最后判断所有的sum是不是都<=0。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N=2e5+5;
const ll inf=1e18;
ll n,m;
ll dp[N][102];
string s,p;
ll vis[20];
unordered_map<char,ll> sum,mp;
set<string> ans;
vector<ll> q[N];
void dfs(ll th,string l){
  if(th==2){
    dfs(th+1,l+'+');
    return ;
  }
  if(th==5){
    dfs(th+1,l+'=');
    return ;
  }
  if(th==8){
    string x="";
    x+=l[0];x+=l[1];
    string y="";
    y+=l[3];y+=l[4];
    string z="";
    z+=l[6];z+=l[7];
    for(ll i=0;i<=9;i++){//判断所有sum是否都<=0，即是不是把所有的p都使用掉了
      if(sum[i+'0']>0) return;
    }
    if((atoi(x.c_str())+atoi(y.c_str()))==atoi(z.c_str())){//判断这个表达式是否成立
      ans.insert(l);
    } 
    return ;
  }
  if(vis[th]==1){//G直接加上即可
     dfs(th+1,l+s[th]);
     return ;
  }
  for(ll i=0;i<=9;i++){
    char c='0'+i;
    if(mp[c]==-1){//如果i存在某个位置为B并且sum<=0，那么就不能再使用了
      if(sum[c]<=0)
        continue;
    }
    bool flag=0;
    for(ll j=0;j<q[i].size();j++){//找到合法的位置
    if(q[i][j]==th){
      flag=1;
     }
    }
    if(!flag){
    sum[c]--;
    dfs(th+1,l+c);
    sum[c]++;
    }
  }
}
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin>>s>>p;
  for(ll i=0;i<p.size();i++){
    if(p[i]=='G') vis[i]=1;
    else if(p[i]=='P'){
       sum[s[i]]++;
       q[s[i]-'0'].push_back(i);
    }
    else{
      mp[s[i]]=-1;
      q[s[i]-'0'].push_back(i);//注意这里，B的位置也不能走
    }
  }
  dfs(0,"");
  cout<<ans.size()<<endl;
  set<string>::iterator it;
  for(it=ans.begin();it!=ans.end();it++){
    cout<<*it<<endl;
  }
}

 E. Expenditure Reduction

题意: 给出两个字符串a , b，在前面的字符串中找一个字串S，保证S的一个子序列是b，找出最短的S。

题解: dp，dp[i][j]表示在a中（1-i）范围内含有（1-j）的b的子序列的最短字串。

  dp[i][j]=dp[i-1][j]+1 //每一项都是前一项+1

  if(a[i]==b[j]) dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1)//相同情况下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e5+5;
const ll inf=1e18;
ll n,m;
ll dp[N][102];
char p[N],q[N];
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll t;cin>>t;
  while (t--){
    cin>>p+1>>q+1;
    ll len1=strlen(p+1);
    ll len2=strlen(q+1);
    for(ll i=0;i<=len1;i++)
     for(ll j=1;j<=len2;j++){//给每个位置附上一个最大值len1+1;
      dp[i][j]=len1+1;
     }
     dp[0][0]=0;//初始化第一个位置
    for(ll i=1;i<=len1;i++) 
     for(ll j=1;j<=len2;j++){
      dp[i][j]=dp[i-1][j]+1;
      if(p[i]==q[j]){//相同的时候
        dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);
      }
     }
     ll pos=1,ans=len1+1;
     for(ll i=1;i<=len1;i++){//找出最小字串
      if(dp[i][len2]<ans){
        ans=dp[i][len2];pos=i;
      }
     }
     for(ll i=pos-ans+1;i<=pos;i++) cout<<p[i];
     cout<<endl;
  }
}
/*
1
paiiipeaded paed
*/

H. Heirloom Painting

题意: 给一个长度为n的环，每次只能连续选择k个位置，将其涂成相同的颜色，问最少几次能涂成给出字符串的形式，如果不能输出 '-1'

题解: 如果一段连续的颜色相同的方块，他的长度<k,那么它一定会影响到别的方块，如何抵消掉这种影响，就必须保障，有一段连续的，他的长度>=k,这样它可以晚涂，覆盖掉别的方块对它的影响，而又不影响别的位置，所以每段连续的向上除，然后判断有没有>=k的位置。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N=2e5+5;
const ll inf=1e18;
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  ll t;cin>>t;
  while(t--){
    ll n,m,k;cin>>n>>m>>k;
    vector<ll> a(n+1,0);
    bool flag=0;
    for(ll i=1;i<=n;i++){
       cin>>a[i];
    }
    ll sum=0;
    ll ans=0;
    ll la=0;
    ll end=n;
    ll le=1;
    while(a[end]==a[1]&&end!=1){//这个是找出第一个字符的连续长度，因为是环，最后一个字符与第一个可能相同，也要加上去
      le++;
      end--;
    }
    for(ll i=1;i<=end;i++){
      ll j=i+1;
      while(a[j]==a[i]&&j<=end){
        le++;j++;
      }
      ll p=(le+k-1)/k;//求出需要几次
      if(le>=k) flag=1;//判断有没有>=k的片段
      ans+=p;
      la=i;
      le=1;
      i=j-1;
    }
    if(!flag) cout<<"-1"<<endl;
    else cout<<ans<<endl;
  }
}