Codeforces Round #612 (Div. 2)

C. Garland

题意：大概就是给你一个n排列，有些位置被拿走了，变成了零，你现在需要任意放回去，新的排列产生一个权值：

这个位置和前一个位置的数字的奇偶性不一样 就会产生一个权值。

现问你如何重新分配0位置使得权值最小。

dp[i][j][k][z] i位置，奇偶性为j 时剩余奇数个数为k，剩余偶数个数为z时的 最小权值。

赛时想到了这个状态方程，无奈转移方程一直写不出，反应了我的dp水平还是很差。。赛后冷静下来，仔细想了想，嗯做出来了。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define pi pair<int, int>
#define mk make_pair
using namespace std;
typedef long long ll;
const int N=1e2+10,inf=0x3f3f3f3f;
int a[N],n,vis[N],s1,s2;
int dp[N][2][N][N];
int main()
{
    cin>>n;
    vector<int>G;
    rep(i,1,n) {
        scanf("%d",&a[i]);
        vis[a[i]]=1;
    }

    rep(i,1,n) {
        if(vis[i]) continue;
        if(i%2) s1++;
        else s2++;
    }
    memset(dp,inf,sizeof(dp));
    dp[0][0][s1][s2]=0;
    dp[0][1][s1][s2]=0;
    int id=1;
    if(a[1]==0){
        dp[1][0][s1][s2-1]=0;
        dp[1][1][s1-1][s2]=0;
    }
    else {
        if(a[1]%2==0)
        dp[1][0][s1][s2]=0;
        else
        dp[1][1][s1][s2]=0;
    }

    
    rep(i,2,n){
        if(a[i]==0){
            rep(jj,0,1)
            rep(j,0,1)
            rep(k,0,s1)
            rep(z,0,s2){
                if(j!=jj) {
                    if(j==0)
                    {
                        if(z-1>=0)
                        dp[i][j][k][z-1]=min(dp[i][j][k][z-1],dp[i-1][jj][k][z]+1);
                    }
                    else {
                        if(k-1>=0)
                        dp[i][j][k-1][z]=min(dp[i][j][k-1][z],dp[i-1][jj][k][z]+1);
                    }
                }
                else {
                    if(j==0) {
                        if(z-1>=0)
                        dp[i][j][k][z-1]=min(dp[i][j][k][z-1],dp[i-1][jj][k][z]);
                    }
                    else {
                        if(k-1>=0)
                        dp[i][j][k-1][z]=min(dp[i][j][k-1][z],dp[i-1][jj][k][z]);
                    }
                }
            }
        }
        else{
            rep(jj,0,1)
            rep(k,0,s1)
            rep(z,0,s2){
                int d=a[i]%2;
                if(d!=jj){
                        dp[i][d][k][z]=min(dp[i][d][k][z],dp[i-1][jj][k][z]+1);
                }
                else{
                    dp[i][d][k][z]=min(dp[i][d][k][z],dp[i-1][jj][k][z]);
                }
            }
        }
    }
    printf("%d/n",min(dp[n][1][0][0],dp[n][0][0][0]));
}

D. Numbers on Tree

题意：给你一个树，每个节点有个权值，然后每个节点有个c[i]，代表着i这个子树下有c[i]个点的值比i节点的权值小。

现问你能否构造每个节点的权值出来，能输出这些权值。

做法：参考javascript:void(0)

大概就从子树往上走，根据c[u]将每一个u，构造一个序列，如果u有多个子树，那么就将第二颗子树的序列接在第一颗子树的后面，为什么？

1，这时候很显然的子树之间是没有关系的，可以给一棵子树的值整体提高一个水平，使得得到的值也是相异的，最简单的是加上上一棵子树的最大值（而不一定是size，假如没有进行算不并列的排名的话）。

子树处理完，如何处理当前节点u呢？

子树构造一个序列出来，当前节点u的c[u]就是这个序列的第几位。

然后一直不知道这段怎么去弄，发现n只有2000，那我暴力将所有的数往后移不就可以了。

用vector的insert函数就不用自己写那么多的代码了。

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
vector<int>G[N];
int n,c[N],ans[N];
vector<int> dfs(int u,int fa)
{
    vector<int>tmp;
    for(int v:G[u]){
        if(v==fa) continue;
        vector<int>t=dfs(v,u);
        tmp.insert(tmp.end(),t.begin(),t.end());
    }

    if(c[u]>tmp.size()){puts("NO");exit(0);}
    tmp.insert(tmp.begin()+c[u],u);
    return tmp;
}

int main()
{
    scanf("%d",&n);
    int root=1;
    for(int i=1;i<=n;++i){
        int fa;
        scanf("%d%d",&fa,&c[i]);
        if(fa!=0) G[fa].push_back(i),G[i].push_back(fa);
        else root=i;
    }

    vector<int>res=dfs(root,0);
    puts("YES");
    for(int i=0;i<n;++i) ans[res[i]]=i+1;
    for(int i=1;i<=n;++i) printf("%d ",ans[i]);
    puts("");
    return 0;
}