Problems
| # | Name |
|---|---|
| A | Two distinct points |
| B | Divisors of Two Integers |
| C | Nice Garland |
| D | Diverse Garland |
| E1 | Array and Segments (Easy version) |
| E2 | Array and Segments (Hard version) |
| F | MST Unification |
像我这种蒟蒻也就只能写到D了，E1题意还没看完，是抄ZincSabian大佬的。Orzn
下面的代码前面如果有一坨FastIO优化，请自动忽略,因为这就是我直接提交上去的代码
A：
这种水题就不讲了QwQ
#include<bits/stdc++.h>
namespace FastIO{struct Reader{char buf[1<<25],*s,*t;bool EOF_FLG;Reader():s(buf),t(buf),EOF_FLG(false) {};char gt() {return s==t&&((t=(s=buf)+fread(buf,1,1<<20,stdin))==s)?EOF:(*s++);}Reader& operator>>(char* str) {if(EOF_FLG)return *str=0,*this;while((*str=gt())!=' '&&*str!='
'&&*str!=EOF)++str;if(*str==EOF)EOF_FLG=true;*str=0;return *this;}template<typename T>Reader&operator>>(T&x) {if(EOF_FLG)return *this;char c=0,d;while(c!=EOF&&(c<'0'||c>'9'))d=c,c=gt();if(c==EOF){EOF_FLG=true;return *this;}else x=0;while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=gt();if(d=='-')x=-x;return *this;}}in;struct Writer{char buf[1<<25],*s,*t;Writer():s(buf),t(buf+(1<<25)){}~Writer(){fwrite(buf,1,s-buf,stdout);}void pt(char c){(s==t)?(fwrite(s=buf,1,1<<25,stdout),*s++=c):(*s++=c);}template<typename T>Writer&operator<<(T x){if(!x)return pt('0'),*this;if(x<0)pt('-'),x=-x;char a[40],t=0;while(x)a[t++]=x%10,x/=10;while(t--)pt(a[t]+'0');return *this;}Writer&operator<<(const char*s) {while(*s)pt(*s++);return *this;}}out;}using namespace FastIO;
namespace ZDY{
#define ll long long
#define db double
#define sht short
#define MB template <class T>
#define Fur(i,x,y) for(int i=x;i<=y;i++)
#define fur(i,x,y) for(int i=x;i<=y;i++)
#define Fdr(i,x,y) for(int i=x;i>=y;i--)
#define clr(x,y) memset(x,y,sizeof(x))
#define cpy(x,y) memcpy(x,y,sizeof(x))
#define inf 0x3f3f3f3f
#define fin(s) freopen(s".in","r",stdin)
#define fout(s) freopen(s".out","w",stdout)
#define l2(n) (ceil(log2(n)))
#define fl(i,x) for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
MB T ABS(T x){return x>0?x:-x;}
MB T MAX(T x,T y){return x>=y?x:y;}
MB T MIN(T x,T y){return x<=y?x:y;}
MB T GCD(T x,T y){return y?GCD(y,x%y):x;}
void SWAP(int &x,int &y){x^=y;y^=x;x^=y;}
}using namespace ZDY;using namespace std;
#define N 100010
int main(){
int q,x,y,xx,yy;
in>>q;
while(q--){
in>>x>>y>>xx>>yy;
if(x<=xx)out<<x<<" "<<yy<<"
";
else out<<y<<" "<<xx<<"
";
}
}
B：
题意：
有两个数(x,y),给(x)的所有约数和(y)的所有约数打乱组成的长度为(n(2≤n≤128))的序列(d_1,d_2,…,d_n(1≤d_i≤10^4),),求(x)和(y)。
题解：
因为(n)很小，所以可以暴力枚举。
(x)肯定是序列中最大的那个，先把序列中x的约数打上标记(重复的只能打一次)，然后枚举(y)，看(y)能不能覆盖其他所有约数。
#include<bits/stdc++.h>
namespace FastIO{struct Reader{char buf[1<<25],*s,*t;bool EOF_FLG;Reader():s(buf),t(buf),EOF_FLG(false) {};char gt() {return s==t&&((t=(s=buf)+fread(buf,1,1<<20,stdin))==s)?EOF:(*s++);}Reader& operator>>(char* str) {if(EOF_FLG)return *str=0,*this;while((*str=gt())!=' '&&*str!='
'&&*str!=EOF)++str;if(*str==EOF)EOF_FLG=true;*str=0;return *this;}template<typename T>Reader&operator>>(T&x) {if(EOF_FLG)return *this;char c=0,d;while(c!=EOF&&(c<'0'||c>'9'))d=c,c=gt();if(c==EOF){EOF_FLG=true;return *this;}else x=0;while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=gt();if(d=='-')x=-x;return *this;}}in;struct Writer{char buf[1<<25],*s,*t;Writer():s(buf),t(buf+(1<<25)){}~Writer(){fwrite(buf,1,s-buf,stdout);}void pt(char c){(s==t)?(fwrite(s=buf,1,1<<25,stdout),*s++=c):(*s++=c);}template<typename T>Writer&operator<<(T x){if(!x)return pt('0'),*this;if(x<0)pt('-'),x=-x;char a[40],t=0;while(x)a[t++]=x%10,x/=10;while(t--)pt(a[t]+'0');return *this;}Writer&operator<<(const char*s) {while(*s)pt(*s++);return *this;}}out;}using namespace FastIO;
namespace ZDY{
#define ll long long
#define db double
#define sht short
#define MB template <class T>
#define Fur(i,x,y) for(int i=x;i<=y;i++)
#define fur(i,x,y) for(int i=x;i<=y;i++)
#define Fdr(i,x,y) for(int i=x;i>=y;i--)
#define clr(x,y) memset(x,y,sizeof(x))
#define cpy(x,y) memcpy(x,y,sizeof(x))
#define inf 0x3f3f3f3f
#define fin(s) freopen(s".in","r",stdin)
#define fout(s) freopen(s".out","w",stdout)
#define l2(n) (ceil(log2(n)))
#define fl(i,x) for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
MB T ABS(T x){return x>0?x:-x;}
MB T MAX(T x,T y){return x>=y?x:y;}
MB T MIN(T x,T y){return x<=y?x:y;}
MB T GCD(T x,T y){return y?GCD(y,x%y):x;}
void SWAP(int &x,int &y){x^=y;y^=x;x^=y;}
}using namespace ZDY;using namespace std;
#define N 100010
int a[N],x,y,n;
bool b[N];
int main(){
in>>n;
Fur(i,1,n)in>>a[i];
sort(a+1,a+n+1);y=a[n];
Fur(i,1,n)if(y%a[i]==0&&a[i]!=a[i-1])b[i]=1;
Fur(i,1,n-1)if(a[i]!=a[i-1]){
bool f=1;
Fur(j,1,n)if(!b[j]&&a[i]%a[j]){f=0;break;}
if(f)return out<<y<<" "<<a[i]<<"
",0;
}
}
C：
题意：
序列(t)由(‘B','G','R')组成，可以将其中改变某一位。求至少改变多少次，可以满足对于每个((i,j)),(t_i=t_j)并且(|i−j| mod 3=0)，并输出改变后的序列。
比如, "RGBRGBRG", "GB", "R", "GRBGRBG", "BRGBRGB"符合要求， "RR", "RGBG"不符合要求。
题解：
贪心，不要想太多，考虑6种情况(“BRG","BGR","GRB","GBR","RBG","RGB")只有怎么一直排下去序列才是完整的。
#include<bits/stdc++.h>
namespace ZDY{
#define ll long long
#define db double
#define sht short
#define MB template <class T>
#define Fur(i,x,y) for(int i=x;i<=y;i++)
#define fur(i,x,y) for(int i=x;i<=y;i++)
#define Fdr(i,x,y) for(int i=x;i>=y;i--)
#define clr(x,y) memset(x,y,sizeof(x))
#define cpy(x,y) memcpy(x,y,sizeof(x))
#define inf 0x3f3f3f3f
#define fin(s) freopen(s".in","r",stdin)
#define fout(s) freopen(s".out","w",stdout)
#define l2(n) (ceil(log2(n)))
#define fl(i,x) for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
MB T ABS(T x){return x>0?x:-x;}
MB T MAX(T x,T y){return x>=y?x:y;}
MB T MIN(T x,T y){return x<=y?x:y;}
MB T GCD(T x,T y){return y?GCD(y,x%y):x;}
void SWAP(int &x,int &y){x^=y;y^=x;x^=y;}
}using namespace ZDY;using namespace std;
#define N 200010
int n,ans=inf,k;
char s[N];
string s2[6];
int main(){
cin>>n;
scanf("%s",s);
s2[0]="BRG";s2[1]="BGR";s2[2]="GRB";s2[3]="GBR";s2[4]="RBG";s2[5]="RGB";
Fur(i,0,5){
int d=0;
Fur(j,0,n-1)if(s[j]!=s2[i][j%3])d++;
if(d<ans)ans=d,k=i;
}
cout<<ans<<endl;
Fur(i,0,n-1)putchar(s2[k][i%3]);
}
D：
题意：
序列(t)由(‘B','G','R')组成，可以将其中改变某一位。求至少改变多少次，可以使序列中任意相邻的两位都不相同，并输出改变后的序列。
题解：
我的解法是DP。
设(f[i][k])为第i位为k时最少要改变多少次，在用一个数组(t)来记录上一步是什么。
(f[i-1][k]+(a[i]!=c)<f[i][c])f[i][c]=f[i-1][k]+(a[i]!=c))
(c!=k)
(a[i])指序列第i位
#include<bits/stdc++.h>
namespace ZDY{
#define ll long long
#define db double
#define sht short
#define MB template <class T>
#define Fur(i,x,y) for(int i=x;i<=y;i++)
#define fur(i,x,y) for(int i=x;i<=y;i++)
#define Fdr(i,x,y) for(int i=x;i>=y;i--)
#define clr(x,y) memset(x,y,sizeof(x))
#define cpy(x,y) memcpy(x,y,sizeof(x))
#define inf 0x3f3f3f3f
#define fin(s) freopen(s".in","r",stdin)
#define fout(s) freopen(s".out","w",stdout)
#define l2(n) (ceil(log2(n)))
#define fl(i,x) for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
MB T ABS(T x){return x>0?x:-x;}
MB T MAX(T x,T y){return x>=y?x:y;}
MB T MIN(T x,T y){return x<=y?x:y;}
MB T GCD(T x,T y){return y?GCD(y,x%y):x;}
void SWAP(int &x,int &y){x^=y;y^=x;x^=y;}
}using namespace ZDY;using namespace std;
#define N 200010
int n,a[N],f[N][3],t[N][3];
char s[N];
void dfs(int d,int tt){
if(d==0)return;
dfs(d-1,t[d][tt]);
if(tt==0)putchar('B');
if(tt==1)putchar('G');
if(tt==2)putchar('R');
}
int main(){
cin>>n;
scanf("%s",s+1);
Fur(i,1,n)
if(s[i]=='B')a[i]=0;
else if(s[i]=='G')a[i]=1;
else a[i]=2;
clr(f,126);f[0][0]=f[0][1]=f[0][2]=0;
Fur(i,1,n){
if(f[i-1][1]+(a[i]!=0)<f[i][0])f[i][0]=f[i-1][1]+(a[i]!=0),t[i][0]=1;
if(f[i-1][2]+(a[i]!=0)<f[i][0])f[i][0]=f[i-1][2]+(a[i]!=0),t[i][0]=2;
if(f[i-1][0]+(a[i]!=1)<f[i][1])f[i][1]=f[i-1][0]+(a[i]!=1),t[i][1]=0;
if(f[i-1][2]+(a[i]!=1)<f[i][1])f[i][1]=f[i-1][2]+(a[i]!=1),t[i][1]=2;
if(f[i-1][1]+(a[i]!=2)<f[i][2])f[i][2]=f[i-1][1]+(a[i]!=2),t[i][2]=1;
if(f[i-1][0]+(a[i]!=2)<f[i][2])f[i][2]=f[i-1][0]+(a[i]!=2),t[i][2]=0;
}
int tt=0;
if(f[n][1]<f[n][tt])tt=1;
if(f[n][2]<f[n][tt])tt=2;
cout<<f[n][tt]<<endl;
dfs(n,tt);
}