Codeforces Round#531(Div.3)問題解と訓練総括

47635 ワード
cf。
このAはBが読めないわけではありません.Eが書けないので、他の問題は簡単です.開場15分でA問題を落とさず、振り向いてB問題を見て、30分ぐらいで諦めて、読めませんでした.Cの問題を始めて、1発のA、それからDの問題を開いて、貪欲に終わってから急いで問題を出して、少し心配してAができるとは限らなくて、1発のAです.E題は正解を考えて書き始め、20 mins waを2発書き、残り30 minsでFを開き、Fは期限内に書き終わっていない.まとめてみました:1.A,Bの問題が出ないときは、他の問題をやめてもいいです.2.気持ちを落ち着かせなければならない.問題:
A.題意:nを1つあげて、1-nの数を2つに分けて、sum差を最小にして、n 1 e 9.考え方:%4と関係があり、4つの数であれば必ず組み合わせることができ、残りは多く出てきて、もし=1ならば、2は必ず2つの差が0にならない.コード:
#include 
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int main(){
    IO;
    int n;cin>>n;
    if(n%4==0||n%4==3) cout <<0<<'
';
    else cout << 1<< '
';
    return 0;
}

B.題意:n(n 1 e 4)個の数字、k(1 e 4)個の顔料を与え、染色する.同色の数字の重み値が異なり、かつ各顔料を使用したことがあることを要求する.考え方:重複する数字がkを超えているかどうかを判断し、出力を構成する.構造の時に二層を走って、同種の重み値の数に対して、番号によって染色し、番号>=kmodでよい.コード:
#include 
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 5005;
int num[maxn],ans[maxn];
map<int,int>mp;

int main(){
    IO;
    int n,k;cin>>n>>k;vector<int>a(n);forn(i,n)cin>>a[i];
    forn(i,n){
        mp[a[i]]++;
        if(mp[a[i]]>k)return cout << "NO" <<'
',0;
    }
    cout <<"YES"<<'
';
    int cnt = 0;
    for(auto x:mp){
        forn(i,n)if(a[i]==x.first) ans[i] = ++cnt,cnt%=k;
    }
    forn(i,n) cout<< ans[i]<<' ';
    cout <<'
';

    return 0;
}

C題意:AとBはゲームをしていて、Aは1つの数字の重みをxに減らすことができて、Bは1つの数字の重みをyに増やすことができます.1つの数字が<=0であれば、Bはそれを加算することはできません.彼らのラウンドは全部で10^100回あって、あなたにn個の数字を聞いて、Aは最大でどれだけの数字の重み値を減らすことができます<=0.n 100は、数字の重み値が1 e 5を超えない考え方:x>yを思い浮かべると必ずすべての数字を戻すことができ、またAが一度に減らすことができる数字を見ることができる.コード:
#include 
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int main(){
    IO;
    int n,x,y;cin>>n>>x>>y;
    if(x>y) return cout <<n<<'
',0;vector<int>a(n);
    forn(i,n) cin>>a[i];
    int cnt = 0;
    forn(i,n){
        if(a[i]<=x) cnt++;
    }
    cout << (cnt+1)/2<<'
';
    return 0;
}

D.題意:文字列長3 e 5を与え、いずれも012で構成する.毎回1文字を0|1|2に変更することができ、最小操作回数が要求される場合、辞書順が最小の012等数の文字列を構築する.考え方:欲張り.
  • 0個の数が足りない場合は0以外のものを優先的に0
    • に変更する.
  • 個の数が足りない場合は優先的に多めの2を1
    • に変更する.
  • 2個数が足りない場合は逆さまに非2を2
    • に変更する.
  • このとき1つの数が足りなければ0を1コードに変更する:
    • #include 
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int num[4];

int main(){
    IO;
    int n;cin>>n;
    string s;cin>>s;
    forn(i,n){
        int x = s[i]-'0';
        num[x]++;
    }
    forn(i,n)if(num[0]<n/3){
        if(num[s[i]-'0']>n/3){
            num[s[i]-'0']--;
            num[0]++;
            s[i] = '0';
        }
    }
    forn(i,n)if(num[1]<n/3){
        if(num[s[i]-'0']>n/3&&s[i]!='0'){
            num[s[i]-'0']--;
            num[1]++;
            s[i] = '1';
        }
    }
    for(int i = n-1;i>=0;i--)if(num[2]<n/3){
        if(num[s[i]-'0']>n/3){
            num[s[i]-'0']--;
            num[2]++;
            s[i] = '2';
        }
    }
    for(int i = n-1;i>=0;i--)if(num[1]<n/3){
        if(num[s[i]-'0']>n/3){
            num[s[i]-'0']--;
            num[1]++;
            s[i] = '1';
        }
    }
    for(auto x:s) cout<<x;
    return 0;
}

    E.題意:2 e 5の長さの配列aに、等大のb配列を構築する.要求満足:1.b0=0 2.bi+1 = bi|| bi+1 = bi +1 3. a配列においてai=ajであればbi=bjである.b配列の構造方法を求めます.考え方:次のビットが+1に変わるか変わらないかであれば,シナリオ数2,できない場合はシナリオ数1である.現在の位置が二重状態であるかどうかを状態配列で構築します.コード:
    #include 
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int maxn = 2e5+5;
const int mod = 998244353;
int pos[maxn];
map<int,int>mp;

int main(){
    IO; 
    int n;cin>>n;
    vector<int>a(n);
    forn(i,n) cin>>a[i];
    forn(i,n){
        if(!mp[a[i]]) mp[a[i]] = i+1;
        else pos[mp[a[i]]-1]--,pos[i]++;
    }
    int cnt = pos[0];ll res = 1;
    for1(i,n-1){
        if(cnt==0) (res *= 2)%=mod; 
        cnt+=pos[i];
    }
    cout <<res<<'
    '    ;





    return 0;
}

    F.題意:行列長n=16,高m=1 e 4をあげます.その中の任意の2行しか交換できないたびに、交換は数回もなく、上から下へ左から右の順に並べられ、任意の隣接数の差が>=kになるようにマトリクスを構築することができます.k最大を求める.構想:n=16、ヒント状圧.もともと16ありました!この状態を2^16回に短縮して01で表す.この問題の違いは首尾を考慮する必要があることだ.コード:
    #include 
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int maxn = 1e4+5;
const int inf = 0x3f3f3f3f;

int a[20][maxn],d[20][20],dd[20][20],dp[16][1<<16][16];
bool vis[16][1<<16][16];

int main(){
    IO;
    int n,m;cin>>n>>m;
    forn(i,n) forn(j,m) cin>>a[i][j];
    forn(i,n){
        forn(j,n){
            int gg = inf;
            forn(k,m){
                gg = min(abs(a[i][k]-a[j][k]),gg);
            }
            d[i][j] = gg;
            gg = inf;
            forn(k,m-1){
                gg = min(abs(a[i][k+1]-a[j][k]),gg);
            }
            dd[i][j] = gg;
        }
    }
    //cerr<
    int ans = 0;
    forn(s,n){
        vis[s][1<<s][s] = 1;
        dp[s][1<<s][s] = inf;
        forn(i,1<<n){
            forn(j,n)if(vis[s][i][j]){
                forn(k,n){
                    int x = 1<<k;
                    if(i&x)continue;
                    //cerr<
                    dp[s][i|x][k] = max(dp[s][i|x][k],min(d[k][j],dp[s][i][j]));
                    vis[s][i|x][k] = 1;
                }
            }
        }
        int gg = 0;
        forn(i,n){
            int x = min(dp[s][(1<<n)-1][i],dd[s][i]);
            gg = max(gg,x);
            //cerr<
        }
        ans = max(ans,gg);
    }
    //forn(i,1<
      //  cout<
    //}
   // cerr<
    cout << ans <<'
    '    ;

    return 0;
}
    ポアソン分布間のKLダイバージェンスのメモ
    片付けるシンプルで汎用的なAjax