一些贪心的解题报告
贪心题一般来说都是观察结论远简单于严谨证明，所以不会过多的去证明。
1.Tree compass
题目来源
codeforces div1 934 C
https://codeforces.com/problemset/problem/1943/C
题面翻译
给定一棵节点数为\(n\)的树(\(1\le n \le 2\cdot 10^3\))，一开始节点都是白色的。我们可以做以下操作
- 选择一个点\(u\in [1,n]\),选择一个距离\(d \in [0,n]\),将所有距离\(u\)恰好为\(d\)的点涂黑。点\(v\) 到点\(u\)的距离是 树上从 \(u\) 到 \(v\)所形成的简单路径中的边的数量。
问，想把树的所有节点涂黑，最少的操作数，并输出操作方案。
- 数据范围:\(\sum n \le 2\cdot 10^3\)
- 时空限制：时限2s,空间512MB
题外话
于我而言，这道题有一个很舒服的点，就是解法和证明是相辅相成的，最简单的贪心比较容易想，而在证明贪心的过程中真正的正确解法就呼之欲出。
解法
对于题目给出的操作，如果不固定\(u\)的话，操作相当眼花缭乱，只能想到一种非常简单粗暴的方式，就是我们固定\(u\)，取\(d=0,1,2,....,x\)。\(x\)为其他点到\(u\)的最远距离，然后我们再贪心的选择\(x\)最小的点，操作数就是\(x_{min}+1\)。
但是这么贪心正确性有待考察，因为树上情况还是太复杂，先从一般角度考虑。
首先考虑链上面的情况，方便起见，我们从链的一个端点到另一个端点依次递增的标号。也就是\(1 \lrarr 2\lrarr...\lrarr n。\)
链上操作显然我们一次操作最多只会给两个点染色，也就是说，想要涂黑一棵树，一次又最多只会涂黑两个点，我们的操作数至少为\(\lceil \frac n 2\rceil\)。
可以发现，如果我们有奇数个点，那么每次操作我们选择中心点\(\frac {n+1} 2\)，距离分别选\(0,1,2,...,\frac {n-1} 2\)，显然可以做到将链完全染色，而\(\frac {n+1} 2\)已经是操作次数的理论下限了，那么这一定就是最小操作次数。
再考虑偶数情况，事实上偶数仍然要分类讨论，就比如\(n=2\)时我们必须操作两次，达不到\(\frac n 2\)的下界，而\(n=4\)时我们只要\(u=2,d=1;u=3,d=1\)这般操作两次就可以，达到了下界。
对于\(n=4k,k\in N^+\),可以选择点\(\frac n 2\)与\(\frac n 2+1\),距离选择\(1,3,...,\frac n 2-1\),总共操作\(\frac n 2\)次，恰好将链涂黑。
对于\(n= 4k+2,k\in N\),可以证明\(\frac n 2\)次操作不可能将链涂黑。证明如下
- 有\(2k+1\)个点，编号为奇数，也就是有奇数个编号是奇数。同理，有奇数个编号为偶数。如果一次操作涂黑了两个点，那么它们的编号就是\(u-d,u+d\)，可以发现这两个编号奇偶性一致，这说明了对奇数编号与偶数编号的操作是互相独立的。那么，\(2k+1\) 个奇数编号至少要\(k+1\)次操作，同理偶数编号也要\(k+1\)次,也就是至少要\(2k+2\),或者说\(\frac n 2+1\)次才能完全涂黑整条链。
那么我们选择\(u=\frac n 2\),距离分别为\(0,1,2,3,...,\frac n 2\),操作\(\frac n 2+1\)次即可。
接下来从链回归到树。可以把树看做一系列链的并，链的操作次数下界对树也是成立的，只是这个下界不一定能够达到了。
树上最长的链就是树的直径。长度记作\(len\),对于一棵树而言，涂黑一条直径需要的最小操作次数就是树的操作次数下界。
对于\(len=2k+1\ 或\ len=4k+2,k\in N\)我们可以像链一般选择一个直径的中心点，根据直径的性质，其他点到中心点的距离小于等于直径两个端点到中心点的距离的较大值,一定会被染黑。
对于\(len=4k,k\in N^+\),无非是选择了两个中心点，仍然能够保证在染黑直径的同时就能把整一棵树染黑。
所以最后染黑直径的最小操作次数就是答案。
代码就是找直径，记长度，找中心点。
复杂度\(O(n)\),但是\(n\le 2\cdot 10^3\),或许是出题人觉得想出思路才是重要的，不卡\(O(n^2)\)，太仁慈了。
点我查看代码
#include<bits/stdc++.h>
#define ll long long
#define mid (l+r>>1)
#define lson u<<1,l,mid
#define rson u<<1|1,mid+1,r
#define pii std::pair<int,int>
typedef int LL;
const signed maxn=1e6+5;
inline LL Read(){LL x=0;char ch=getchar();bool f=0;for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=1;for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);if(f) x=-x;return x;
}
struct Edge{int to,nxt;
}edge[maxn<<1];
int head[maxn],ecnt;
void Adde(int u,int v){edge[++ecnt]=(Edge){v,head[u]};head[u]=ecnt;
}
int d;
int fa[maxn],dep[maxn];
void dfs(int u,int Fa){fa[u]=Fa;dep[u]=dep[Fa]+1;if(dep[u]>dep[d]) d=u;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to;if(v==Fa) continue;dfs(v,u);}
}
int chain[maxn],ccnt;
void get_chain(){ccnt=0;while(d) chain[++ccnt]=d,d=fa[d];
}
signed main(){LL T=Read();while(T--){int n=Read();for(int i=1;i<=n;++i) head[i]=0;ecnt=0;for(int i=1;i<n;++i){int u=Read(),v=Read();Adde(u,v),Adde(v,u);} dep[0]=0;d=0;dfs(1,0);dfs(d,0);get_chain();if(ccnt%2==1||ccnt%4==2){int x=ccnt>>1,c=chain[x+1];printf("%d\n",x+1);for(int i=0;i<=x;++i){printf("%d %d\n",c,i);}}else{int x=ccnt>>1;int c1=chain[x],c2=chain[x+1];printf("%d\n",x);for(int i=1;i<x;i+=2){printf("%d %d\n",c1,i);printf("%d %d\n",c2,i);}}}return 0;
}
2.开灯
题目来源
中南大学第17届校赛
题目链接http://122.207.108.21:20080/csuoj/problemset/problem?pid=2520
题目挂在csuoj上，只有中南大学的网才能连上。
题目
中文题面直接截图
解法
首先，边上的灯泡可以分为三类：
- 最后状态要求是初始状态，即总共被反转偶数次。
- 最后状态要求是初始状态的反转，即总共被反转奇数次。
- 最后状态随意，可以反转任意次。
本题灯泡在边上，其实可以等价的修改为在点上，映射规则如下：
- 选定一个点作为根，根没有边对应，然后作\(dfs\)，点与其入边对应。
做了映射后还要注意:对于路径\(u\) 到 \(v\)上的操作，不会对\(LCA(u,v)\)产生影响，因为其对应的边不在路径上。
那么，首先把路径看做一条或者由下而上拓展的链组成。因为LCA不被影响，链的顶端不受影响。贪心思路就是尽量把两条链组合为一条路径而不是单独一条链作路径。
在贪心之前要说明一些性质。
- 一定存在一种最优策略，任意两条路径没有边重复。
- 一个需要奇数反转的点，其一定恰好出现在一条向上拓展的链上(非顶端)，即其向上拓展一次也仅一次。
叶子节点策略：对于要求反转奇数次的点，向父亲节点传一个向上拓展计数，同时增加最终答案\(1\)。反转偶数的点和随意的点不传。
非叶节点：首先查看向上拓展计数，记为\(sum\),把尽量多的计数二合一减小答案。最终答案减小\(\frac {sum} 2\)。然后根据灯泡的类别分类讨论：
- 需要反转奇数次。一定会向上拓展。如果\(sum\)为奇数，恰好留了一条作为向上拓展的链，就不用额外再重新开一条，直接沿用。如果\(sum\)为偶数，就得像叶子结点一般，最终答案加\(1\)。
- 需要反转偶数次。一定不会向上拓展。
- 反转次数随意。如果\(sum\)为奇数，多余的一条作为向上拓展的链，记向上拓展计数。如果\(sum\)为偶数，不向上拓展。
\(1e5\)的\(O(n)\)，题目还是出的太保守了。
点我查看代码
#include<bits/stdc++.h>
#define ll long long
//#define int long long
#define mid ((l+r)>>1)
#define lson u<<1,l,mid
#define rson u<<1|1,mid+1,r
#define inf 0x3f3f3f3f
typedef int LL;
const signed maxn=(signed)1e6+5;
inline LL Read(){char ch=getchar();bool f=0;LL x=0;for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);if(f==1)x=-x;return x;
}
std::vector<int> g[maxn];
int type[maxn],sum[maxn],fa[maxn];
char ori[maxn],now[maxn];
int fin=0;
void dfs(int u){for(auto v:g[u]){dfs(v);}if(type[u]==1){fin-=sum[u]>>1;if(sum[u]&1^1) ++fin;++sum[fa[u]];}else if(type[u]==0){fin-=sum[u]>>1;}else{fin-=sum[u]>>1;if(sum[u]&1) ++sum[fa[u]];}
}
signed main(){ int n=Read();for(int i=1;i<n;++i){int Fa=Read();fa[i]=Fa;g[Fa].push_back(i);}scanf("%s%s",ori,now);for(int i=0;i<n;++i){if(now[i]=='1') type[i+1]=now[i]-ori[i];else type[i+1]=-1;}dfs(0);printf("%d\n",fin);return 0;} 3. ina of the mountain
题目来源
codefores div1 887 C
https://codeforces.com/contest/1943/problem/C
题目翻译
巨山下有一排不朽章鱼，编号为\(1\sim n\)。每个章鱼有初始生命值\(a_i\)，\(1\le a_i \le k\)。我们可以选择一个区间\([l,r]\),通过一次扔石头伤害编号在\([l,r]\)之间的章鱼，使他们生命值减\(1\)。不朽章鱼是不朽的，当他们生命值归零，他们会以生命值为\(k\)的状态复活。
问，最少需要扔多少次石头才能使所有章鱼生命值变为\(k\)。
- 数据范围:\(1\le n \le 2\cdot 10^5,1\le k \le 10^9\)
- 时空限制:时限2s,空间512MB
解法
显然\(a_i=a_{i+1}\)这种相邻相同的两只章鱼可以当做一只考虑，所以接下来不考虑相邻位置相等的情况(\(a_i\ne a_{i+1}\))。
首先假设我们找到了最少的操作情况。这种情况下，第\(i\)只章鱼被砸了\(c_i\)次，显然有\(|c_i-a_i|\%k=0\)。
我们以区间的左端点计算贡献,考虑最优情况下可以有的性质。
- 贡献计算：如果\(c_{i+1}< c_i\),位置\(i\)不提供贡献。\(c_{i+1}>c_i\),提供\(c_{i+1}-c_i\)的贡献。
- \(c_{i+1}<c_i+k\)。若\(c_{i+1}> c_i+k\),取\(c'_{i+1}=c_{i+1}-k\)不会使答案更劣。同理有\(c_{i+1}>c_i-k\)。
由第一点，我们得到贪心的总原则:最小化\(\sum_{i=1}^{n-1} max(0,c_{i+1}-c_i)\)。
由第二点，可以发现\(c_i\)与\(c_{i+1}\)的关系，当\(c_{i+1}\)作贡献时，当\(c_i<c_{i+1}<c_i+k\),\(c_{i+1}\)其实是确定的，那么一个位置的贡献是确定的。当不作贡献时，\(c_i-k<c'_{i+1}<c_i\),有\(c'_{i+1}=c_{i+1}-k\)。每一个位置只有做贡献与不做贡献两种情况。
接下来讲贪心的策略。
考虑每一位都作贡献，然后选择一些位置不作贡献，使被减去的贡献最大。
一开始每一位都做贡献，也就是\(c_{i+1}\ge c_i\)始终成立。
然后选择一些位置位置不作贡献。若位置\(i\)不作贡献,位置\(i\)及之后的\(c_j\)都少一个\(k\)。即\(\forall j\ge i,c_j-=k\)。
那么\(c_i=A*k+B(0\le B<k)\),\([1,i]\)之间最多有\(A\)个位置不作贡献。
\(c_i\)是递增的，可以不作贡献的位置量在增加。从左向右遍历，开一个优先队列记录\([1,i]\)位置的贡献中最大的几个，时刻保持队列大小和\(c_i/k\)相符合。最后把这些贡献减去就得到了答案。
遍历\(O(n)\),优先队列\(O(\log n)\),总复杂度\(O(n\log n)\)
点我查看代码
#include<bits/stdc++.h>
#define ll long long
//#define int long long
#define mid ((l+r)>>1)
#define lson u<<1,l,mid
#define rson u<<1|1,mid+1,r
#define inf 0x3f3f3f3f
typedef int LL;
const signed maxn=(signed)1e6+5;
inline LL Read(){char ch=getchar();bool f=0;LL x=0;for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);if(f) x=-x;return x;
}
int n,m,k;
ll ar[maxn];
std::priority_queue<int,std::vector<int>,std::greater<int> >q;
signed main(){ LL T=Read();while (T--){int n=Read(),k=Read();for(int i=1;i<=n;i++) ar[i]=Read();ar[0]=0;ll sum=0;int c=0,d=0;for(int i=1;i<=n;i++){ll b=(ar[i]+k-ar[i-1])%k;sum+=b;c=sum/k;q.push(b);d++;while(d>c){q.pop();d--;}}while(!q.empty()){sum-=q.top();q.pop();}printf("%lld\n",sum);}return 0;} 
