div.2

给定n(<= 3000)个整数Ai，有一种操作：给某个数加1。问最少操作几次，使得n个数都不一样。

考虑这样一个问题：已知一个数组B，用上面的操作，把A变成B的最小代价怎么算。

一个最优的方法是，把A中最小的数变成B中最小的数，把A中次小的数变成B中次小的数...把A中最大的数变成B中最大的数。

所以做法就出来了。先把A数组排序，然后把A[i]变成max(A[i],B[i - 1] + 1)即可。(因为同样要保证变化完后B数组递增)

1 #include 
      
        2 #include 
       
         3  4 int A[3000]; 5 int n; 6  7 int main() { 8     scanf("%d",&n); 9     for (int i = 0; i < n; ++ i) {10         scanf("%d",A + i);11     }12     std::sort(A,A + n);13     int answer = 0;14     for (int i = 1; i < n; ++ i) {15         if (A[i] <= A[i - 1]) {16             answer += A[i - 1] + 1 - A[i];17             A[i] = A[i - 1] + 1;18         }19     }20     printf("%d\n",answer);21 }
       
      

 

div.1

给定一棵n(<=1e5)个节点的树，每个节点有颜色(黑或白)，让你删掉一些边使得剩下的每个连通块内都恰好只有1个黑点。问删边的方案数。

那么就dp(u,c)表示节点u的子数，与u关联的连通块有/无黑点的状态是c，的方案数。

然后就是一个树dp啦。

1 #include 
      
        2  3 const int MOD = (int)1e9 + 7; 4 const int N = 100000 + 5; 5 std::vector
       
         edges[N]; 6 int color[N]; 7 int n; 8 int dp[N][2]; 9 10 inline void add(int &a,int b) {11     a += b;12     if (a >= MOD) a -= MOD;13 }14 15 void dfs(int u) {16     if (color[u] == 1) {17         dp[u][1] = 1;18         dp[u][0] = 0;19     } else {20         dp[u][0] = 1;21         dp[u][1] = 0;22     }23     for (int i = 0; i < edges[u].size(); ++ i) {24         int v = edges[u][i];25         dfs(v);26         int tmp[2] = {};27         for (int a = 0; a < 2; ++ a) {28             for (int b = 0; b < 2; ++ b) {29                 add(tmp[a | b],dp[u][a] * 1ll * dp[v][b] % MOD);30                 if (a == 0 && b == 1) {31                     add(tmp[0],dp[u][a] * 1ll * dp[v][b] % MOD);32                 }33             }34         }35         dp[u][0] = tmp[0];36         dp[u][1] = tmp[1];37     }38 39 }40 41 int work() {42     dfs(0);43     return dp[0][1];44 }45 46 int main() {47     scanf("%d",&n);48     for (int i = 1; i < n; ++ i) {49         int x;50         scanf("%d",&x);51         edges[x].push_back(i);52     }53     for (int i = 0; i < n; ++ i) {54         scanf("%d",color + i);55     }56     printf("%d\n",work());57 }