hhhh感觉我真的太久没有接触过OI了
大约是前天听到JK他们约着一起刷codeforces，假期里觉得有些颓废的我忽然也心血来潮来看看题目
今天看codeforces才知道居然有div3了，感觉应该看名字比div2还要简单吧，于是我就做了做....发现确实还蛮简单的hhhh
但是我又突发奇想，干脆更新一篇博客吧，毕竟这也是我少有的能刷完一整套CF的题，那也可以记录一下啦...(虽然div3的题解似乎拿来充当一个题解还是有点水的hhhh)
A - Two distinct points
题目大意：n组数据，每次给你[l1,r1]和[l2,r2]让你输出两个不同的元素a,b，使得a在[l1,r1]中,b在[l2,r2]中，题目保证一定有解
这两个数的限制实在是....没什么限制hhhh，第一眼看到居然感觉不知道怎么下手。
然后就想了一下，那要不选个a就不在[l2,r2]里面，然后b就可以随便选，发现这样的话就要比一下什么区间谁在前谁在后，或者谁包含谁什么的，实在有点麻烦。
后面想了一下，唔那我a就选个端点吧，感觉它容易不在[l2,r2]里面一些，那再想一下，那我b也选端点吧
于是那就a=l1或r1，b=l2或r2，然后要求a!=b，这就实在太水了hhhh 果然是div3，不过既然这是一篇题解，我就水到底吧：
所以我们判断一下l1是不是等于l2
如果不相等，那就a=l1,b=l2；
如果相等的话，我就比一下l1是不是等于r2
如果不等就a=l1,b=r2,；
如果相等，说明l1==l2==r2，那么b就一定要等于l2，题目又保证有解，那就有r1!=l2，那么a=r1,b=l2就好了。
#include<cstdio>
using namespace std;
int main(){
int Kase,l1,r1,l2,r2;
scanf("%d",&Kase);
while(Kase--){
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
if(l1!=l2)
printf("%d %d\n",l1,l2);
else if(l1!=r2)
printf("%d %d\n",l1,r2);
else
printf("%d %d\n",r1,l2);
}
return ;
}
然后交上去，刷新，1A！哇好开心啊！ [虽然不知道这种题过了有什么好开心的Hhhhh，可能是codeforce的题确实会给你一种实现超简单，但是想法是自己独创的这种很棒的成就感吧]
不过也就对B题也充满了信心。
B. Divisors of Two Integers
题目大意：这题大概就是先告诉你一种获得集合的方法：给你x和y，然后把他们的因子分别放到集合A,B中去，最后把A,B直接融合在一起，变成一个大的可重复元素的集合C。题目给你这个集合C，让你求出x和y的确切值。集合大小<200，元素大小<10000
刚开始感觉这大约是一个数学题，可能需要分解因式什么的，或者是什么通过最大公约数来反推两个元素的值的题。
然后忽然发现，好像它是所有的因子都在里面hhh，也就是包括了x和y自己，所以我只需要通过找最大值肯定就能找到x和y中的一个，不妨令x是那个最大的。
那么我现在的任务就是把x的因子从集合C中拿走，然后剩下的就是集合B了，那么剩下的里面最大的就是元素y了。
当然你没有必要真的把x的所有因子从集合中拿走，你只需要判断一下集合中的某个元素能否被x整除就行了，然后剩下的不能整除的最大的就是y。
上面是y不是x的因子的情况，如果y是x的因子，那么你就需要找到一个最大的出现了两次的元素，因为元素大小<10000所以可以用桶来实现，如果元素大小大到不能用桶的话，就可以用排序来实现。
#include<cstdio> const int maxn=; int n;
int a[maxn],cnt[];
int x,y,z; int main(){
#ifndef ONLINE_JUDGE
freopen("x.in","r",stdin);
#endif scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
x=x>a[i]?x:a[i];
}
for(int i=;i<=n;i++){
if(x%a[i])
y=y>a[i]?y:a[i];
else if(++cnt[a[i]]>=)
z=z>a[i]?z:a[i];
}
y=(y==)?z:y;
printf("%d %d",x,y); return ;
}
然后又是1A，哇太感动了，简直神清气爽，于是对C题也充满了自信。
C. Nice Garland
题目大意：给你一个只包含RGB三种字符的字符串，希望你把它改造成它想要的样子，它想要的样子就是相同颜色的元素之间的距离为3的倍数。字符串大小为200000，需要输出一个改造最少的次数以及改造后的字符串。
刚开始看到改造字符串这种题，就感觉是个DP，然后研究了一下样例，发现好像样例输出都是类似RGBRGBRG...或者BRGBRGBRG...唔，然后发现好像它这个要求相同颜色的元素之间的距离都为3的倍数的要求确实十分苛刻了。
例如第一个元素你放上了R，那么你考虑它后面的三个元素R _ _ _，如果第三个位置上不放R，那么只能放G或者B，不妨假设放了G
R _ _ G 那么你会发现第二个空位只能放B，因为如果放R或者G都会让距离不满足3的倍数的条件，于是就变成了R B _ G 然后第三个空位上就什么也放不了了。
所以如果第一个元素是R，那么第四个元素就必须也是R，所以就只有6种全排列的扩展串或者扩展串的子串了，于是就只需要比较6次取最小的就好了。
/*
File : C.cpp
Author : Robert_Yuan
Date : 2019/1/29
Discription :
*/
#include<cstdio>
#include<cstring> using namespace std; const int maxn=; int n,ans,ansi;
char ch[maxn];
char s[][]={"RGB","RBG","GRB","GBR","BRG","BGR"}; int main(){
#ifndef ONLINE_JUDGE
freopen("x.in","r",stdin);
#endif scanf("%d%s",&n,ch);
ans=n;
for(int i=;i<;i++){
int cnt=;
for(int j=;j<n;j+=){
cnt+=(ch[j]!=s[i][])&(j<n);
cnt+=(ch[j+]!=s[i][])&(j+<n);
cnt+=(ch[j+]!=s[i][])&(j+<n);
}
if(cnt<ans)
ans=cnt,ansi=i;
}
printf("%d\n",ans);
for(int i=;i<n;i+=){
if(i<n) printf("%c",s[ansi][]);
if(i+<n) printf("%c",s[ansi][]);
if(i+<n) printf("%c",s[ansi][]);
} return ;
}
这题我maxn打错了RE了一次，于是开始慢慢谨慎起来Hhh，接着是D题
D. Diverse Garland
题目大意：还是一个只包含RGB三种字符的字符串，希望你把它改造成相邻的两个元素不相等的样子，问你最少需要改造多少次，然后输出改造后的字符串。字符串长度<200000.
这个就很经典了，就是上面想到的DP了，f[i][j]表示第i个元素修改成j的代价，其中j只能取0,1,2
然后转移方程大概就是每次从前一个是那种颜色转移过来，如果枚举的颜色和当前的不一样就要+1，一样的话就不用加
f[i][0]=Min(f[i-1][1],f[i-1][2])+(ch[i]!='R'); [其他两个也类似]
然后用一个pre[i][j]记录一下当前状态从i-1的哪一个状态转移过来，就可以输出改造后的字符串了。
/*
File :
Author : Robert_Yuan
Date : 2019/1/29
Discription :
*/
#include<cstdio>
#include<cstring> using namespace std; const int maxn=; int n;
int f[maxn][],pre[maxn][];
char ch[maxn];
char Turn[]={'G','R','B'}; int main(){
#ifndef ONLINE_JUDGE
freopen("x.in","r",stdin);
#endif scanf("%d%s",&n,ch);
memset(f,0x3f,sizeof(f));
for(int i=;i<;i++)
f[][i]=(ch[]!=Turn[i]);
for(int i=;i<n;i++)
for(int j=;j<;j++)
for(int k=;k<;k++)
if(j!=k){
int val=f[i-][k]+(ch[i]!=Turn[j]);
if(f[i][j]>val)
f[i][j]=val,pre[i][j]=k;
}
int ans=0x3f3f3f3f,ansi;
for(int i=;i<;i++){
if(ans>f[n-][i])
ans=f[n-][i],ansi=i;
}
for(int i=n-;i>=;i--){
ch[i]=Turn[ansi];
ansi=pre[i][ansi];
}
printf("%d\n",ans);
printf("%s",ch);
return ;
}
这题因为实在经典，所以似乎没有之前得到的乐趣那么多了。不过能1A还是比较开心的。
感觉div3从这里终于进入了div2的难度
难道？！div3的C题相当于div2的A题....唔那好吧，感觉很有道理
E1. Array and Segments (Easy version)
题目大意：给你一个长度为n的数组，然后给你m个区间，然后你可以选择若干个区间，让这个区间内的每个数-1，最后希望整个数组的最大值-最小值最大。最后要输出这个最大的最大值-最小值，还有输出你选择的区间。
E1是一个简单版本，n,m<300
因为是最大值减去最小值最大，所以我们需要知道最后减完之后的最大值和最小值分别在什么位置，那既然n,m这么小，我的想法就是枚举最后的最小值在哪个位置，然后去枚举区间，看看哪个区间包括了这个最小值，就选择这个区间来减，因为我一定希望最后的最小值更小，所以每个能让它变小的机会都不能放过，而且即使我选择区间可能让最后的最大值也减小了，但是因为是同时减小1，所以这个差值还是不变的，所以这样去选择区间，最大值-最小值的值肯定是只增不减的。
然后我就这样打了，然后区间减的话，懒得打线段树来做了，复杂度是O(n*m*n)，发现嗯300^3可以过。
/*
File :
Author : Robert_Yuan
Date : 2019/1/29
Discription :
*/
#include<cstdio> const int maxn=; struct Node{
int l,r;
}s[maxn]; int ans,ansi;
int n,m;
int a[maxn],b[maxn];
int st[maxn],tp; int judge(int t){
for(int i=;i<=n;i++)
b[i]=a[i];
for(int i=;i<=m;i++){
if(s[i].l<=t && s[i].r>=t)
for(int j=s[i].l;j<=s[i].r;j++)
b[j]--;
}
int MAX=b[],MIN=b[];
for(int i=;i<=n;i++){
MAX=MAX>b[i]?MAX:b[i];
MIN=MIN<b[i]?MIN:b[i];
}
return MAX-MIN;
} int main(){
#ifndef ONLINE_JUDGE
freopen("x.in","r",stdin);
#endif
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(int i=;i<=m;i++)
scanf("%d%d",&s[i].l,&s[i].r); for(int i=;i<=n;i++){
int t=judge(i);
if(t>ans)
ans=t,ansi=i;
}
printf("%d\n",ans);
for(int i=;i<=m;i++)
if(s[i].l<=ansi && s[i].r>=ansi)
st[++tp]=i;
printf("%d\n",tp);
for(int i=;i<=tp;i++)
printf("%d ",st[i]);
return ;
}
1A，而且意外发现速度还可以。
然后看E2
E2的题目描述一模一样，然后只是把n改成了200000。
于是我想，那就是逼着我写线段树来实现区间加和区间减了？然后一看tag有data structure，嗯嗯，更加印证了。
不过在枚举谁是最后的最小值的时候，我之前的暴力有复制一遍原数组的操作，刚开始我想这个线段树要是也这样，那我岂不是要写一个可持久化线段树？然后感觉空间什么的就要算，有点小麻烦。不过又仔细想了一下，发现我只要每次做一个区间加就可以把之前的恢复到最初状态了，也就省了一个可持久化线段树。不过只要用到了线段树，那么时间复杂度至少还是在O(nmlogn)这个数量级，感觉还是会超时。
于是观察一下这个算法中最占时间的，就是在选择每一个位置来假设它是最后的最小值这个操作上，于是我就想应该不是所有的位置都可能是最小值，因为n>>m，所以有的位置它们在选择区间上是等价的 [就是说如果选它们作为最小值，选择到的区间会是一模一样的]，所以在这些可以选到相同区间的位置中，只有这一段中的最小值可能成为最后的最小值，同时因为最后要求的值是最大值-最小值，所以这样一片具有相同选择区间的位置中，我只需要留下最大值和最小值就可以了，同时因为只有m个区间，也就是2*m个端点，那么我在每两个端点之间的点的区间选择上一定是等价的，所以我最后可以把n缩小到(3*2*m)[最大值、最小值、端点]这样一个量级，也就是1800左右，那么现在nmlogn就完全可以了，甚至于不用线段树可能也能过。
于是我就写了一个不用线段树的试了一下，发现诶？！真的过了Hhhhhh，那我就懒得写线段树的区间加减和取最大最小值了。
所以这题大概就是只用了一个离散化的思想就过了...感觉做出来也还蛮有成就感的。
/*
File :
Author : Robert_Yuan
Date : 2019/1/29
Discription :
*/
#include<cstdio>
#include<algorithm> using namespace std; const int maxn=;
const int maxm=; struct Node{
int l,r;
}s[maxm]; int n,m,Mark;
int tp;
int a[maxn],b[maxn],st[maxn];
int Turn[maxn]; int judge(int t){
for(int i=;i<=Mark;i++)
a[i]=b[i];
for(int i=;i<=m;i++){
if(s[i].l<=t && s[i].r>=t)
for(int j=s[i].l;j<=s[i].r;j++)
a[j]--;
}
int MAX=a[],MIN=a[];
for(int i=;i<=Mark;i++){
MAX=MAX>a[i]?MAX:a[i];
MIN=MIN<a[i]?MIN:a[i];
}
return MAX-MIN;
} int main(){
#ifndef ONLINE_JUDGE
freopen("x.in","r",stdin);
#endif scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(int i=;i<=m;i++){
scanf("%d%d",&s[i].l,&s[i].r);
st[++tp]=s[i].l,st[++tp]=s[i].r;
}
sort(st+,st+tp+);
st[]=;st[tp+]=n+;
for(int i=;i<=tp+;i++){
if(st[i]==st[i-]) Turn[st[i]]=Mark;
else if(st[i-]+==st[i]) b[++Mark]=a[st[i]],Turn[st[i]]=Mark;
else{
int Max=a[st[i-]+],Min=a[st[i-]+];
for(int j=st[i-]+;j<st[i];j++){
Max=Max>a[j]?Max:a[j];
Min=Min<a[j]?Min:a[j];
}
if(Max==Min)
b[++Mark]=Max;
else
b[++Mark]=Max,b[++Mark]=Min;
b[++Mark]=a[st[i]];
Turn[st[i]]=Mark;
}
}
Mark--;
for(int i=;i<=m;i++){
s[i].l=Turn[s[i].l];
s[i].r=Turn[s[i].r];
} int ans=,ansi=;
for(int i=;i<=n;i++){
int t=judge(i);
if(t>ans)
ans=t,ansi=i;
}
tp=;
printf("%d\n",ans);
for(int i=;i<=m;i++)
if(s[i].l<=ansi && s[i].r>=ansi)
st[++tp]=i;
printf("%d\n",tp);
for(int i=;i<=tp;i++)
printf("%d ",st[i]); return ;
}
题目大意：就是给你一个图，让你找一个最小生成树，但是最小生成树可能不唯一，所以你需要把某些边的值加一些权值，你现在可以每次给一条边+1，问你最后你最少需要加多少次才能使得这个最小生成树唯一。
感觉就是在kruskal的时候，你把所有边权相同的边先都找到，然后看看哪些是能连接两个之前未联通的块的，那么这些边都是可能选的，那么你就尽可能地用到他们，但是可能会有多的，那么这些边就都要加一，加完之后，他们就不会构成最小生成树了，具体实现还挺简单的。时间复杂度和kruskal一样也是O(mlogm)
/*
File :
Author : Robert_Yuan
Date : 2019/1/29
Discription :
*/
#include<cstdio>
#include<algorithm> using namespace std; const int maxn=; struct Node{
int u,v,w;
}e[maxn]; int n,m,ans;
int p[maxn]; int Find(int x){
int r=x,pre;
while(r!=p[r]) r=p[r];
while(x!=r)
pre=p[x],p[x]=r,x=pre;
return r;
} bool cmp(const Node &A,const Node &B){
return A.w<B.w;
} int main(){
#ifndef ONLINE_JUDGE
freopen("x.in","r",stdin);
#endif
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) p[i]=i;
for(int i=;i<=m;i++)
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
sort(e+,e+m+,cmp);
for(int i=,j=;i<=m;i=j){
while(j<=m && e[j].w==e[i].w) j++;
int cnt=j-i;
for(int t=i;t<j;t++){
int fx=Find(e[t].u),fy=Find(e[t].v);
if(fx==fy) cnt--;
}
for(int t=i;t<j;t++){
int fx=Find(e[t].u),fy=Find(e[t].v);
if(fx==fy) continue;
cnt--;
p[fx]=fy;
}
ans+=cnt;
}
printf("%d",ans);
return ;
}
然后div3就做完啦，感觉确实比div2还要简单一点的，之后可能还会再刷刷题哈嗯嗯