https://codeforces.com/contest/1324
D. Pair of Topics
ai + aj > bi + bj 移项 ai - bi + aj - bj > 0 ，输入a数组和b数组后，做减法构造一个c数组为ai - bi，c数组排序一下，二分找ci - cj 大于0的对数即可。
做这题我很沙雕，离散化之后上了树状数组做，有点麻烦了
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn = 2e5+5; 5 int a[maxn],b[maxn],c[maxn]; 6 int bit[maxn]; 7 int n; 8 int lowbit(int x){ 9 return x&-x; 10 } 11 void add(int x,int k){ 12 while(x<=n){ 13 bit[x] = bit[x] + k; 14 x = x + lowbit(x); 15 } 16 } 17 int getsum(int x){ 18 int ans = 0; 19 while(x>=1){ 20 ans = ans + bit[x]; 21 x = x - lowbit(x); 22 } 23 return ans; 24 } 25 int main() 26 { 27 scanf("%d",&n); 28 for(int i = 1;i<=n;i++) scanf("%d",&a[i]); 29 for(int i = 1;i<=n;i++){ 30 scanf("%d",&b[i]); 31 c[i] = b[i] - a[i]; 32 b[i] = a[i] - b[i]; 33 } 34 map<int,int> m; 35 sort(c+1,c+1+n); 36 int indx = 1; 37 for(int i = 1;i<=n;i++){ 38 if(i == 1) {m[c[i]] = 1;continue;} 39 if(c[i] > c[i] - 1){ 40 indx++; 41 m[c[i]] = indx; 42 } 43 else m[c[i]] = indx; 44 } 45 ll ans = 0; 46 for(int i = 1;i<=n;i++){ 47 int pos = lower_bound(c+1,c+1+n,b[i]) - c; 48 ans+=getsum(pos-1); 49 // cout<<getsum(pos-1)<<endl; 50 pos = m[-b[i]]; 51 add(pos,1); 52 } 53 cout<<ans; 54 return 0; 55 }
E. Sleeping Schedule
比较简单的dp。dp[i][j]表示第i天，第j时间点的方案数，那么当dp[i-1][j]存在时，也就是说可以从第i-1天的j时间点转移时，才可以进行dp转移。
转移的方式有题中所述的两种情况，一种是(j + a[i] - 1)%h，一种是(j + a[i])%h;。
转移方程为dp[i][c] = max(dp[i-1][j] + 1,dp[i][c]) 和 dp[i][c] = max(dp[i-1][j],dp[i][c])，c为可以转移到的时间点。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn = 2e3+5; 5 ll dp[maxn][maxn]; 6 int a[maxn]; 7 int n,h,l,r; 8 int main() 9 { 10 scanf("%d%d%d%d",&n,&h,&l,&r); 11 for(int i = 1;i<=n;i++){ 12 scanf("%d",&a[i]); 13 } 14 memset(dp,-1,sizeof(dp)); 15 dp[0][0] = 0; 16 ll ans = 0; 17 for(int i = 1;i<=n;i++){ 18 for(int j = 0;j<h;j++){ 19 if(dp[i-1][j]!=-1){ 20 int c = (j + a[i] - 1)%h; 21 if(c>=l && c<=r) dp[i][c] = max(dp[i-1][j] + 1,dp[i][c]); 22 else dp[i][c] = max(dp[i-1][j],dp[i][c]); 23 c = (j + a[i])%h; 24 if(c>=l && c<=r) dp[i][c] = max(dp[i-1][j] + 1,dp[i][c]); 25 else dp[i][c] = max(dp[i-1][j],dp[i][c]); 26 } 27 } 28 } 29 for(int i = 0;i<h;i++) ans = max(ans,dp[n][i]); 30 cout<<ans; 31 return 0; 32 }
F. Maximum White Subtree
树型dp，换根法。题目所给定的数据结构是树，随意选择一个结点作为root根，开始dfs搜索回溯，用一个cnt数组来记录以i为根的子树对答案的贡献，这里用回溯的办法，先搜索下去再回溯上来，那么cnt[i] = cnt[i] + max(0,cnt[j])，j为i的儿子结点，只有cnt[j]是大于0 的时候，才对i结点有所贡献。这样预处理完毕之后，cnt[root]其实就是root的答案。但是其他结点不是最终答案。
dfs了一遍之后就开始换根，继续从root开始dfs，用dp数组来记录答案，dp数组包含两个部分，一个部分是以i为根的子树对dp[i]的贡献，另一部分是子树外面对答案的贡献，所以在换根的时候需要计算出子树外面的部分。假设遍历i的子树的根v，那么转移方程为 dp[v] = cnt[v] + max(0,dp[i] - max(0,cnt[v]) );
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn = 2e5+5; 5 int n; 6 int a[maxn],vis[maxn],cnt[maxn],dp[maxn]; 7 struct node{ 8 vector<int> v; 9 }g[maxn]; 10 void add(int u,int v){ 11 g[u].v.push_back(v); 12 g[v].v.push_back(u); 13 } 14 int dfs(int cur,int fa){ 15 vis[cur] = 1; 16 if(a[cur]) cnt[cur]++; 17 else cnt[cur]--; 18 for(auto v:g[cur].v){ 19 if(vis[v]) continue; 20 int res = dfs(v,cur); 21 if(res>0) cnt[cur] +=res; 22 } 23 return cnt[cur]; 24 } 25 void getdp(int cur,int fa){ 26 if(cur == 1) dp[cur] = cnt[cur]; 27 for(auto v : g[cur].v ){ 28 if(v == fa) continue; 29 dp[v] = cnt[v] + max(0,dp[cur] - max(0,cnt[v]) ); 30 getdp(v,cur); 31 } 32 } 33 int main() 34 { 35 scanf("%d",&n); 36 for(int i = 1;i<=n;i++){ 37 scanf("%d",&a[i]); 38 } 39 for(int i = 1;i<=n-1;i++){ 40 int u,v; 41 scanf("%d%d",&u,&v); 42 add(u,v); 43 } 44 dp[1] = dfs(1,0); 45 getdp(1,0); 46 for(int i = 1;i<=n;i++) printf("%d ",dp[i]); 47 return 0; 48 }