Codeforces Round#661(Div.3)問題解A,B,C,D

A. Remove Smallest
テーマゲート
Remove Smallest
構想
データ範囲が小さいことに注意して(1≦a i≦100 1≦ai≦100 1≦ai≦100)、入力した配列の中の最小値と最大値を求めて、最小から最大まで1回歩いて、その中の各値がすべてあるかどうかを見て、もしないならばNO、すべてあるならYES
AC Code

#include
#include
#include
#include
using namespace std;
#define INF 0x3f3f3f3f
// #define TDS_ACM_LOCAL
int n, mi, mx, vis[109], a;
void solve(){
    cin>>n;
    mx=0, mi=INF;
    memset(vis, 0, sizeof(vis));
    for(int i=1; i<=n; i++){
        cin>>a;
        vis[a]=1;
        if(a>mx)    mx=a;
        if(a<mi)    mi=a;
    }
    int flag=0;
    for(int i=mi; i<=mx; i++){
        if(vis[i]==0)   {flag=1; break;}
    }
    if(flag)    cout<<"NO"<<endl;
    else    cout<<"YES"<<endl;
    return ;
}   

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

B. Gifts Fixing
テーマゲート
Gifts Fixing
構想
明らかなaとbの配列が最終的にそれぞれの配列の最小値となるので、位置毎の変化回数については容易に得ることができ、aとbの変換はa-であってもb-であってもよいし、同時に2つの自滅であってもよいので、aとbの対応する位置の動作回数は2つのそれぞれの操作回数の中で最大のものであり、そしてすべての操作回数を合計すると最小操作回数となる
AC Code

#include
#include
#include
using namespace std;
#define INF 0x3f3f3f3f
// #define TDS_ACM_LOCAL
const int N=59;
int n, a[N], b[N];
int mia, mib;
long long ans;
void solve(){
    cin>>n;
    ans=0;
    mia=mib=INF;
    for(int i=1; i<=n; i++){
        cin>>a[i];
        if(a[i]<mia)    mia=a[i];
    }
    for(int i=1; i<=n; i++){
        cin>>b[i];
        if(b[i]<mib)    mib=b[i];
    }
    for(int i=1; i<=n; i++){
        ans+=max(a[i]-mia, b[i]-mib);
    }
    cout<<ans<<endl;
    return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

C. Boats Competition
テーマゲート
Boats Competition
テーマの大意
長さnの配列をあげて、中から2つの値を取って、加算する値は等しくなければならなくて、求めた値は最も多い対数に対して
構想
データ範囲が小さい1≦n≦50 1≦n≦50 1≦n≦n≦50であることに注意して、私達は直接S Sの値を列挙することができて、2から2∗n 2*n 2∗n、それから各値に対してそれぞれその中で行ける対数の個数を計算して、最大値を求める
AC Code

#include
#include
#include
using namespace std;
// #define TDS_ACM_LOCAL
const int N=110;
int n, x, a[N], ans, cnt;
void solve(){
    cin>>n;
    memset(a, 0, sizeof(a));
    for(int i=0; i<n; i++)  cin>>x, a[x]++;
    ans=0;
    for(int i=2; i<=2*n; i++){
        cnt=0;
        for(int j=1; j<=i; j++) if(a[i-j])  cnt+=min(a[j], a[i-j]);
        ans=max(ans, cnt/2);    // 2        
    }
    cout<<ans<<endl;
    return ;
}

int main(){
    ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

D. Binary String To Subsequences
テーマゲート
Binary String To Subsequences
テーマの大意
長さnの0と1を含む文字列をあげます.最小の01サブ文字列(0と1が交互に現れる)の個数を求め、位置ごとに0と1が何番目のサブ文字列であるべきかを求めます.
構想
0で終わるサブ文字列と1で終わるサブ文字列を2つのキューでそれぞれ格納できます.コードでidxで表されるサブ文字列の個数1、0で終わるサブ文字列に1を受け取って1になり、1のキュー2に格納し、0を1で終わるサブ文字列に受け取って0になり、0で終わるキュー3、0で終わるサブ文字列がなければ新しい4、1で終わるサブ文字列がない場合は、新しい
AC Code

#include
#include
#include
#include
using namespace std;
// #define TDS_ACM_LOCAL
const int N=2e5 +9;
int n, x, a[N], idx;
string s;
void solve(){   
    cin>>n;
    cin>>s;
    idx=0;
    queue<int> q0, q1;
    for(int i=0; i<n; i++){                 //idx          ，  idx++             
        if(s[i]=='0'){                      
            if(!q1.empty()){                // 0  1          0，  0   
                x=q1.front(); q1.pop();
                a[i]=x;
                q0.push(x);
            }
            else{                           //     1       ，       
                a[i]=++idx;
                q0.push(idx);
            }
        }
        else{
            if(!q0.empty()){                // 1  0          1，  1   
                x=q0.front(); q0.pop();
                a[i]=x;
                q1.push(x);
            }   
            else{                           //     0       ，       
                a[i]=++idx;
                q1.push(idx);
            }
        }
    }
    cout<<idx<<endl;
    for(int i=0; i<n; i++)  cout<<a[i]<<" ";
    cout<<endl;
    return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}