目录
废话
摘要
题解
- A
- Solution
- B
- Solution
- C
- Solution
- D
- Solution
- E
- Solution
- F
- Solution
废话
人生第一场实时的 CF, 感受到了自己手慢脑子更慢......
E 题的题面看了半天才看懂, F 题的子树定义也看不见
摘要
题号 | 题目描述 | 思路 |
---|---|---|
A | 略 | 当且仅当所有元素奇偶性相同 |
B | 给定一个序列,问有无长度 \(\geq 3\) 的回文子序列 | 只要两个相同元素中间还有元素就有长度 \(\geq 3\) 的回文子序列,于是 \(O(n^2)\) 扫一遍即可 |
C | 略 | 首先我们可以废掉所有 L 格子,只走 R 格子,那么答案就是所有 R 格子(包括 \(0,n+1\) )的最小间距 |
D | 有 \(n\) 个元素,每个元素有 \(a,b\) 两种权值。求 \((i,j)\) 的对数(无序),使得 \(a_i+a_j>b_i+b_j\) | 设 \(c_i=a_i-b_i\) ,为这个序列排序,然后用双指针扫一遍即可。具体地,对于 \(i\) 维护 \(pos\) 表示第一个 \(>-c[i]\) 的元素的位置,对答案有贡献 \(\max(0,pos-i)\) ,当 \(i\) 和 \(pos\) meet 的时候就退出 |
E | 每天有 \(h\) 个小时,要睡 \(n\) 次,第 \(i\) 次可以决定在上次醒来后的 \(a_i\) 小时或 \(a_i-1\) 小时后入睡,第一次醒来是在时间原点 \(0\) 。每次睡觉会花费 \(h\) 个小时。最大化睡眠开始时间在 \([l,r]\) 范围内的睡觉次数。 | 设 \(f[i][j]\) 表示睡了前 \(i\) 次,第 \(i\) 次入睡时时间为 \(j\) ,暴力转移即可,复杂度 \(O(n^2)\) |
F | 给定一棵 \(n\) 个点的无根树,每个结点为黑色或白色。对于每个点 \(i\) ,你需要选择一个包含 \(i\) 的子树,最大化子树内白色结点与黑色结点数目之差的最大值,求这个最大值。子树定义为树上的一个联通块。\(n \leq 2\times 10^5\) | 选取点 \(1\) 为根定为有根树,设 \(f[i]\) 表示在有根树上以 \(i\) 为根的子树中,选择一个包含 \(i\) 的联通块,所能获得的最大差值,设 \(g[i]\) 表示在除去以 \(i\) 为根的子树的其它部分中,选取一个与 \(i\) 连通的连通块,所能获得的最大差值,那么显然 \(ret[i]=f[i]+g[i]\) 。考虑如何求出 \(f[i]\) ,我们首先为它加上 \(i\) 自身的贡献,然后决策 \(i\) 的每一个有根树上的儿子是否选择即可,当然,选择了一个儿子也就意味着可以选择一个包含它的连通块,即加上 \(f[j]\) 。考虑如何求出 \(g[i]\) ,首先有边界条件 \(g[1]=0\) ,考虑自顶向下转移,把每个点放在它的父亲上计算,这样一个父亲点要计算它所有儿子节点,每个儿子节点要么不延续父亲,要么延续父亲并且可以额外选若干个父亲的其它孩子的子树 |
题解
A
略
Solution
当且仅当所有元素奇偶性相同
- #include <bits/stdc++.h>
- using namespace std;
- #define int long long
- const int N = 1000005;
- void sh(int &x,int y) {x=max(x,y);}
- int t,n,a[105];
- signed main() {
- cin>>t;
- while(t--) {
- cin>>n;
- for(int i=1;i<=n;i++) cin>>a[i],a[i]&=1;
- int flag=1;
- for(int i=2;i<=n;i++) if(a[i]!=a[1]) flag=0;
- cout<<(flag?"YES":"NO")<<endl;
- }
- }
- B
给定一个序列, 问有无长度 \(\geq 3\) 的回文子序列
Solution
只要两个相同元素中间还有元素就有长度 \(\geq 3\) 的回文子序列, 于是 \(O(n^2)\) 扫一遍即可
- #include <bits/stdc++.h>
- using namespace std;
- #define int long long
- const int N = 1000005;
- int t,n,a[N];
- signed main() {
- iOS::sync_with_stdio(false);
- cin>>t;
- while(t--) {
- cin>>n;
- for(int i=1;i<=n;i++) cin>>a[i];
- int flag=0;
- for(int i=1;i<=n;i++) {
- for(int j=i+2;j<=n;j++) {
- if(a[i]==a[j]) flag=1;
- }
- }
- cout<<(flag?"YES":"NO")<<endl;
- }
- }
- C
略
Solution
首先我们可以废掉所有 L 格子, 只走 R 格子, 那么答案就是所有 R 格子 (包括 \(0,n+1\)) 的最小间距
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 1000005;
- int t,n,ans;
- char str[N];
- signed main() {
- iOS::sync_with_stdio(false);
- cin>>t;
- while(t--) {
- cin>>str+1;
- n=strlen(str+1);
- int pos=0;
- ans=0;
- for(int i=1;i<=n;i++) {
- if(str[i]=='R') {
- ans=max(ans,i-pos);
- pos=i;
- }
- }
- ans=max(ans,n+1-pos);
- cout<<ans<<endl;
- }
- }
- D
有 \(n\) 个元素, 每个元素有 \(a,b\) 两种权值. 求 \((i,j)\) 的对数(无序), 使得 \(a_i+a_j>b_i+b_j\)
Solution
设 \(c_i=a_i-b_i\), 为这个序列排序, 然后用双指针扫一遍即可. 具体地, 对于 \(i\) 维护 \(pos\) 表示第一个 \(>-c[i]\) 的元素的位置, 对答案有贡献 \(\max(0,pos-i)\), 当 \(i\) 和 \(pos\) meet 的时候就退出
- #include <bits/stdc++.h>
- using namespace std;
- #define int long long
- const int N = 1000005;
- int a[N],b[N],n,ans;
- signed main() {
- cin>>n;
- for(int i=1;i<=n;i++) cin>>a[i];
- for(int i=1;i<=n;i++) cin>>b[i];
- for(int i=1;i<=n;i++) a[i]-=b[i];
- int pin=n;
- sort(a+1,a+n+1);
- reverse(a+1,a+n+1);
- for(int i=1;i<=n;i++) {
- while(a[i]+a[pin]<=0) --pin;
- ans+=max(0ll,pin-i);
- }
- cout<<ans;
- }
- E
每天有 \(h\) 个小时, 要睡 \(n\) 次, 第 \(i\) 次可以决定在上次醒来后的 \(a_i\) 小时或 \(a_i-1\) 小时后入睡, 第一次醒来是在时间原点 \(0\). 每次睡觉会花费 \(h\) 个小时. 最大化睡眠开始时间在 \([l,r]\) 范围内的睡觉次数.
Solution
设 \(f[i][j]\) 表示睡了前 \(i\) 次, 第 \(i\) 次入睡时时间为 \(j\), 暴力转移即可, 复杂度 \(O(n^2)\)
- #include <bits/stdc++.h>
- using namespace std;
- int n,h,l,r,a[2005],f[2005][2005];
- void sh(int &x,int y) {
- x=max(x,y);
- }
- signed main() {
- iOS::sync_with_stdio(false);
- cin>>n>>h>>l>>r;
- for(int i=1;i<=n;i++) cin>>a[i];
- memset(f,-0x3f,sizeof f);
- f[0][0]=0;
- for(int i=1;i<=n;i++) {
- for(int j=0;j<h;j++) {
- sh(f[i][(j+a[i])%h], f[i-1][j]+((j+a[i])%h>=l&&((j+a[i])%h<=r)));
- sh(f[i][(j+a[i]-1)%h], f[i-1][j]+((j+a[i]-1)%h>=l&&((j+a[i]-1)%h<=r)));
- }
- }
- cout<<*max_element(f[n],f[n]+h);
- }
- F
给定一棵 \(n\) 个点的无根树, 每个结点为黑色或白色. 对于每个点 \(i\), 你需要选择一个包含 \(i\) 的子树, 最大化子树内白色结点与黑色结点数目之差的最大值, 求这个最大值. 子树定义为树上的一个联通块.\(n \leq 2\times 10^5\)
Solution
选取点 \(1\) 为根定为有根树, 设 \(f[i]\) 表示在有根树上以 \(i\) 为根的子树中, 选择一个包含 \(i\) 的联通块, 所能获得的最大差值, 设 \(g[i]\) 表示在除去以 \(i\) 为根的子树的其它部分中, 选取一个与 \(i\) 连通的连通块, 所能获得的最大差值, 那么显然 \(ret[i]=f[i]+g[i]\)
考虑如何求出 \(f[i]\), 我们首先为它加上 \(i\) 自身的贡献, 然后决策 \(i\) 的每一个有根树上的儿子是否选择即可, 当然, 选择了一个儿子也就意味着可以选择一个包含它的连通块, 即加上 \(f[j]\)
考虑如何求出 \(g[i]\), 首先有边界条件 \(g[1]=0\), 考虑自顶向下转移, 把每个点放在它的父亲上计算, 这样一个父亲点要计算它所有儿子节点, 每个儿子节点要么不延续父亲, 要么延续父亲并且可以额外选若干个父亲的其它孩子的子树
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 200005;
- int n,f[N],h[N],a[N],b[N],w[N],fa[N],vis[N],sb,sw;
- vector <int> g[N];
- void dfs(int p) {
- vis[p]=1;
- if(a[p]==1) f[p]=1;
- else f[p]=-1;
- for(int q:g[p]) {
- if(vis[q]) continue;
- fa[q]=p;
- dfs(q);
- b[p]+=b[q];
- w[p]+=w[q];
- f[p]+=max(f[q],0);
- }
- }
- void dfs2(int p) {
- int sum=max(0,h[p]);
- if(a[p]) sum++;
- else sum--;
- for(int q:g[p]) if(q!=fa[p]) {
- sum+=max(0,f[q]);
- }
- for(int q:g[p]) if(q!=fa[p]) {
- h[q]=max(0,sum-max(f[q],0));
- }
- for(int q:g[p]) if(q!=fa[p]) dfs2(q);
- }
- signed main() {
- iOS::sync_with_stdio(false);
- cin>>n;
- for(int i=1;i<=n;i++) cin>>a[i];
- for(int i=1;i<n;i++) {
- int t1,t2;
- cin>>t1>>t2;
- g[t1].push_back(t2);
- g[t2].push_back(t1);
- }
- dfs(1);
- dfs2(1);
- for(int i=1;i<=n;i++) {
- cout<<f[i]+h[i]<<" ";
- }
- }
来源: http://www.bubuko.com/infodetail-3459133.html