CF 1287 div 2問題解

前言
昨夜CF div 2を打って、点数を上げることを考えます.しかし、脳がオンラインになっていないので、BCの問題はすべて掛けて、Aの2つだけです.この恥をかくためにこの編を特筆する.
すべての問題:https://codeforces.com/contest/1287/problems
A. Angry Students
問題:https://codeforces.com/contest/1287/problem/A問題解:一度直接スキャンして、記録(A)の後で一番長い部分(P)を記録すればいいです.時間複雑度:(O(n)).コード:略
B. Hyperset
問題:https://codeforces.com/contest/1287/problem/B題名:任意のペアのカードに対して、それらとグループを構成できるカードが唯一であることがわかります.暴力はすべてのカードペアを列挙し、mapに情報を格納し、直接検索すればよい.時間複雑度:O((n^2)klogn)コード:

#include
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
typedef long long ll;
#define I inline void
#define IN inline int
#define C(x,y) memset(x,y,sizeof(x))
#define STS system("pause")
templateI read(D &res){
    res=0;register D g=1;register char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')g=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        res=(res<<3)+(res<<1)+(ch^48);
        ch=getchar();
    }
    res*=g;
}
mapmp;
string s;
char c[2020][110],t[110];
int n,m;
ll ans;
I Match(int x,int y){
    F(i,1,m){
        if(c[x][i]==c[y][i])t[i]=c[x][i];
        else {
            if(c[x][i]=='S'&&c[y][i]=='E')t[i]='T';
            else if(c[x][i]=='S'&&c[y][i]=='T')t[i]='E';
            else if(c[x][i]=='E'&&c[y][i]=='S')t[i]='T';
            else if(c[x][i]=='E'&&c[y][i]=='T')t[i]='S';
            else if(c[x][i]=='T'&&c[y][i]=='S')t[i]='E';
            else t[i]='S';
        }
    }
    s.clear();s.append(t+1);
}
int main(){
    //cin>>t+1;s.append(t+1);
    //F(i,0,s.size()-1)cout<>c[i]+1;
    F(i,1,n-1){
        F(j,i+1,n){
            Match(i,j);
            if(!mp.count(s))continue;
            ans+=mp[s];
        }
        s.clear();s.append(c[i]+1);mp.insert(make_pair(s,1));
    }
    cout<

C. Garland
問題:https://codeforces.com/contest/1287/problem/C标题:DPを考える.(f[i][j][k][0/1])が前(i)ビットを考慮したことを示すと、すでに0の場所に(j)個の偶数が置かれ、(k)個の奇数の最小代価が置かれている.遷移方程式は,現在のビットが0であるかどうかで議論すればよい.時間の複雑さ:O((n^3))これは本題(私は料理が多すぎる)を通じて、どのように最適化するかを考えるのに十分です.(i)が決定された場合、(j+k)は一定値です.だから(j,k)を変数に押し込むことができます.時間複雑度:O((n^2))コード:

#include
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
typedef long long ll;
#define I inline void
#define IN inline int
#define C(x,y) memset(x,y,sizeof(x))
#define STS system("pause")
I read(int &res){
    res=0;re g=1;register char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')g=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        res=(res<<3)+(res<<1)+(ch^48);
        ch=getchar();
    }
    res*=g;
}
int n,m,a[110],v[110],s[110],f[110][110][2],A,B;
int main(){
    read(n);
    F(i,1,n){
        read(a[i]);s[i]=s[i-1];
        if(!a[i])a[i]=-1,s[i]++;
        else v[a[i]]=1,a[i]&=1;
    }
    F(i,1,n){
        if(!v[i]){
            if(i&1)B++;else A++;
        }
    }
//  F(i,1,n)cout<B)continue;
if(j)f[1][j][0]=min(f[0][j-1][0],f[0][j-1][1]);
f[1][j][1]=min(f[0][j][0],f[0][j][1]);
}
}
F(i,2,n){
if(a[i]!=-1){
F(j,0,min(s[i],A))if(s[i]-j<=B)f[i][j][a[i]]=min(f[i-1][j][0]+a[i],f[i-1][j][1]+(a[i]^1));
continue;
}
F(j,0,min(s[i],A)){
if(s[i]-j>B)continue;
if(j)f[i][j][0]=min(f[i-1][j-1][0],f[i-1][j-1][1]+1);
f[i][j][1]=min(f[i-1][j][0]+1,f[i-1][j][1]);
}
}
//F(i,1,n)F(j,0,min(s[i],A))cout<

D. Numbers on Tree
問題:https://codeforces.com/contest/1287/problem/D問題解:下から上へ問題を解決することを考える.操作のたびに、現在のノードのサブツリー内の点の値をスタックに追加し、境界位置を見つけて現在のノードの(a[i])に値を割り当て、その後の対応点の値+1を与えることができます.しかし、1回の操作では、このような加算操作が前のサブツリー内の点のサイズ関係を変更する可能性があるため、これは間違っています.この問題を避ける方法を考える.解があれば,すべての点の(a[i])が異なるように,必ずスキームが存在することを証明できる.そのため、前回のスタックの最大値を記録して、次回はすべての点の値にこの最大値を加えてからスタックに入ることができます.時間複雑度:O((n^2)logn)コード:

#include
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
typedef long long ll;
#define I inline void
#define IN inline int
#define C(x,y) memset(x,y,sizeof(x))
#define STS system("pause")
I read(int &res){
    res=0;re g=1;register char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')g=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        res=(res<<3)+(res<<1)+(ch^48);
        ch=getchar();
    }
    res*=g;
}
typedef pairpii;
priority_queueq;
vectore[2020];
int n,m,root,tot,bas,dep[2020],fa[2020],c[2020],w[2020];
pii b[2020];
I D_1(int x,int d){
    dep[x]=d;q.emplace(make_pair(d,x));
    for(auto p:e[x])D_1(p,d+1);
}
I D_2(int x){
    w[x]+=bas;
    b[++tot]=make_pair(w[x],x);
    for(auto p:e[x])D_2(p);
}
int main(){
    read(n);
    F(i,1,n)read(fa[i]),read(c[i]);
    F(i,1,n)if(!fa[i])root=i;else e[fa[i]].emplace_back(i);
    D_1(root,1);
    while(!q.empty()){
        m=q.top().second;q.pop();tot=bas=0;
        for(auto p:e[m]){
            D_2(p);sort(b+1,b+1+tot);bas=b[tot].first;
        }
        if(tot

E Madhouse
問題:https://codeforces.com/contest/1287/problem/D问题解:まず简単版を考えます.([1,n])および([1,n−1])について尋ねることができる.1回目のクエリは2回目よりも多くの(n)個の列を発見し、この(n)個の列はちょうどこの列の(n)個の接尾辞の乱順バージョンである.この(n)個の列を見つけて、列全体を復元します.総シリアル数:O((n^2))困難版では,同じ手法を用いて,([1,n/2])の部分のシリアルを先に求めることができる.それから([1,n])という部分を尋ねます.(f[i][x])は、今回の問い合わせのすべての長さiの列において、文字(x)の出現回数を表す.(f[i+1][x]-f[i][x])の意味を考えると、これが原列([i+1,n-i])という区間内の文字(x)の出現回数であることがわかります.前半を求めたので,後半は逆順列挙(i)で個々に求めることができる.合計シリアル数:O(0.75*(n^2))コード:

#include
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
typedef long long ll;
#define I inline void
#define IN inline int
#define C(x,y) memset(x,y,sizeof(x))
#define STS system("pause")
templateI read(D &res){
    res=0;register D g=1;register char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')g=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        res=(res<<3)+(res<<1)+(ch^48);
        ch=getchar();
    }
    res*=g;
}
mapmp;
struct P{
    string a;
    friend bool operator > (P x,P y){
        return x.a.size()==y.a.size()?x.a.compare(y.a)>0:x.a.size()>y.a.size();
    }
}p;
priority_queue
,greater
 >q;
char c[110],ans[110];
string s;
int n,m,cnt[30],now[30],f[110][30];
namespace solve1{
    I solve(int x){
        if(x==1){
            cout<>c+1;ans[1]=c[1];return;
        }
        cout<>c+1;m=strlen(c+1);sort(c+1,c+1+m);p.a.clear();p.a.append(c+1);q.emplace(p);
        }
        cout<>c+1;m=strlen(c+1);sort(c+1,c+1+m);s.clear();s.append(c+1);mp[s]++;
        }
        C(cnt,0);m=0;
        while(!q.empty()){
            s=q.top().a;q.pop();//cout<cnt[i]){ans[++m]=i+'a'-1;cnt[i]++;break;}
        }
        reverse(ans+1,ans+1+x);
    }
};
namespace solve2{
    I solve(){
        cout<>1){
            cin>>c+1;m=strlen(c+1);
            F(j,1,m)f[m][c[j]-'a'+1]++;
        }
        re l,r;
        FOR(i,(n-1)>>1,0){
            l=i+1;r=n-i;
            C(cnt,0);
            F(j,l,r-1)cnt[ans[j]-'a'+1]++;
            F(j,1,26)if(f[i+1][j]-f[i][j]>cnt[j]){ans[r]=j+'a'-1;break;}
        }
        cout<>c+1;cout<