Codeforces Round 584 题解

……

A,B 先秒切，C 是个毒瘤细节题，浪费了很多时间后终于过了。

D 本来是个 sb 题，然而还是想了很久，不过幸好没什么大事。

E1，看了一会就会了，然而被细节坑死，好久才过。

感觉 E2 很可做，一直想 E2，结果想了大半了就最后一点没想出来。

此时 G1 更多人做了。然而我不会啊……

没救了。掉分掉惨了。

A

排个序，如果前面有它的约数就染成同色，否则开个新颜色。

下面这个代码，因为刚开始以为要输出方案，所以比较丑。

    #include<bits/stdc++.h>

    using namespace std;

    typedef long long ll;

    typedef pair<int,int> PII;

    const int maxn=100010;

    #define MP make_pair

    #define PB push_back

    #define lson o<<1,l,mid

    #define rson o<<1|1,mid+1,r

    #define FOR(i,a,b) for(int i=(a);i<=(b);i++)

    #define ROF(i,a,b) for(int i=(a);i>=(b);i--)

    #define MEM(x,v) memset(x,v,sizeof(x))

    inline ll read(){

    	char ch=getchar();ll x=0,f=0;

    	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();

    	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();

    	return f?-x:x;

    }

    struct hhh{

    	int x,id;

    	bool operator<(const hhh &h)const{return x<h.x;}

    }h[maxn];

    int n,cnt;

    int main(){

    	n=read();

    	FOR(i,1,n) h[i].x=read(),h[i].id=i;

    	sort(h+1,h+n+1);

    	FOR(i,1,n){

    		int pos=0;

    		FOR(j,1,i-1) if(h[i].x%h[j].x==0) pos=j;

    		if(!pos) cnt++;

    	}

    	printf("%d\n",cnt);

    }

B

明显会有周期，直接模拟。周期是 \(125\)，然而只要不 T 就行了。

    #include<bits/stdc++.h>

    using namespace std;

    typedef long long ll;

    typedef pair<int,int> PII;

    const int maxn=100010;

    #define MP make_pair

    #define PB push_back

    #define lson o<<1,l,mid

    #define rson o<<1|1,mid+1,r

    #define FOR(i,a,b) for(int i=(a);i<=(b);i++)

    #define ROF(i,a,b) for(int i=(a);i>=(b);i--)

    #define MEM(x,v) memset(x,v,sizeof(x))

    inline ll read(){

    	char ch=getchar();ll x=0,f=0;

    	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();

    	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();

    	return f?-x:x;

    }

    int n,a[maxn],b[maxn],ans;

    char s[maxn];

    int calc(){

    	int sum=0;

    	FOR(i,1,n) if(s[i]=='1') sum++;

    	return sum;

    }

    int main(){

    	n=read();

    	scanf("%s",s+1);

    	FOR(i,1,n) a[i]=read(),b[i]=read();

    	FOR(i,1,100000){

    		ans=max(ans,calc());

    		FOR(j,1,n) if(i>=b[j] && (i-b[j])%a[j]==0) s[j]^=1;

    	}

    	printf("%d\n",ans);

    }

C

没什么好说的，想怎么搞怎么搞。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> PII;

const int maxn=200020;

#define MP make_pair

#define PB push_back

#define lson o<<1,l,mid

#define rson o<<1|1,mid+1,r

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline ll read(){

	char ch=getchar();ll x=0,f=0;

	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();

	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();

	return f?-x:x;

}

struct item{

	int x,id;

	bool operator<(const item &i)const{

		if(x!=i.x) return x<i.x;

		return id<i.id;

	}

}it[maxn];

int t,n,ans[maxn],back[maxn];

vector<int> hhh[10];

bool in[maxn];

char s[maxn];

int main(){

	t=read();

	while(t--){

		n=read();

		scanf("%s",s+1);

		bool flag=true;

		FOR(i,0,9) hhh[i].clear();

		FOR(i,1,n) hhh[s[i]-'0'].push_back(i);

		int pos=-1,lst=-1;

		FOR(i,0,9) if(hhh[i].size()){

			back[i]=hhh[i].back();

			FOR(j,0,(int)hhh[i].size()-1){

				if(pos!=-1) ans[hhh[i][j]]=2;

				else if(lst!=-1 && hhh[i][j]<hhh[lst].back()) ans[hhh[i][j]]=2,back[i]=hhh[i][j];

				else ans[hhh[i][j]]=1;

			}

			if(lst!=-1){

				if(pos==-1){

					if(hhh[i].front()<back[lst]) pos=i;

				}

				else{

					if(hhh[i].front()<back[lst]){puts("-");flag=false;break;}

				}

			}

			lst=i;

		}

		if(flag){

			FOR(i,1,n) printf("%d",ans[i]);

			puts("");

		}

	}

}

D

对每个人 \(x\) 和 \(y\) 连边。

考虑一个环，上面至少一个人不能被满足。方案只需要把这个人塞到最后面就行了。

如果是一棵树，那么可以全都被满足。方案构造不难。

那么考虑每个联通块，随便弄一棵生成树，让树边的人满足，非树边的人不满足（塞到最后面）就行了。明显是最优。

实际上只需要算边数和点数。

    #include<bits/stdc++.h>

    using namespace std;

    typedef long long ll;

    typedef pair<int,int> PII;

    const int maxn=200020;

    #define MP make_pair

    #define PB push_back

    #define lson o<<1,l,mid

    #define rson o<<1|1,mid+1,r

    #define FOR(i,a,b) for(int i=(a);i<=(b);i++)

    #define ROF(i,a,b) for(int i=(a);i>=(b);i--)

    #define MEM(x,v) memset(x,v,sizeof(x))

    inline ll read(){

    	char ch=getchar();ll x=0,f=0;

    	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();

    	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();

    	return f?-x:x;

    }

    int n,k,ans,el,head[maxn],to[maxn],nxt[maxn];

    bool vis[maxn];

    map<PII,bool> vise;

    inline void add(int u,int v){

    	to[++el]=v;nxt[el]=head[u];head[u]=el;

    }

    void dfs(int u,int f){

    	vis[u]=true;

    	for(int i=head[u];i;i=nxt[i]){

    		int v=to[i];

    		if(v==f) continue;

    		if(vis[v]){

    			ans++;continue;

    		}

    		dfs(v,u);

    	}

    }

    int main(){

    	n=read();k=read();

    	FOR(i,1,k){

    		int x=read(),y=read();

    		if(x>y) swap(x,y);

    		if(vise[MP(x,y)]) ans+=2;

    		else{

    			vise[MP(x,y)]=true;

    			add(x,y);add(y,x);

    		}

    	}

    	FOR(i,1,n) if(!vis[i]) dfs(i,0);

    	printf("%d\n",ans/2);

    }

E

把要求的东西转化一下：循环移列之后，从每一行选出一个数，求这些数最大的和。

简单 DP：\(f[i][j]\) 表示前 \(i\) 列，其中 \(j\) 这些行已经选了数。

时间复杂度 \(O(t(2^nn^2m+3^nm))\)。可以通过 E1。

对于 E2，发现把每列按最大值排序，当 \(m>n\) 时，只需要考虑最大的 \(n\) 列。

证明，先考虑这 \(n\) 列的最优解，肯定大于等于这 \(n\) 列的最大值之和（而且将这 \(n\) 列的最大值按某个排列排在每一行肯定是最优解）。将其中一列替换成比这 \(n\) 列的最大值都小的列之后，无论怎么循环移这一列，选这一列上的一个数都不如选别的某个列上的一个数。

时间复杂度 \(O(t(2^nn^3+3^nn+nm))\)。

    #include<bits/stdc++.h>

    using namespace std;

    typedef long long ll;

    typedef pair<int,int> PII;

    const int maxn=100010;

    #define MP make_pair

    #define PB push_back

    #define lson o<<1,l,mid

    #define rson o<<1|1,mid+1,r

    #define FOR(i,a,b) for(int i=(a);i<=(b);i++)

    #define ROF(i,a,b) for(int i=(a);i>=(b);i--)

    #define MEM(x,v) memset(x,v,sizeof(x))

    inline ll read(){

    	char ch=getchar();ll x=0,f=0;

    	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();

    	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();

    	return f?-x:x;

    }

    int t,n,m,a[22][22],b[22][2222],mx[2222],p[2222],sum[22][4444],f[22][4444];

    bool cmp(int x,int y){return mx[x]>mx[y];}

    int main(){

    	t=read();

    	while(t--){

    		n=read();m=read();

    		FOR(i,0,n-1) FOR(j,0,m-1) b[i][j]=read();

    		FOR(i,0,m-1){

    			mx[i]=0;

    			FOR(j,0,n-1) mx[i]=max(mx[i],b[j][i]);

    		}

    		FOR(i,0,m-1) p[i]=i;

    		sort(p,p+m,cmp);

    		FOR(i,0,min(n,m)-1) FOR(j,0,n-1) a[j][i]=b[j][p[i]];

    		FOR(i,0,min(n,m)-1) FOR(S,0,(1<<n)-1){

    			sum[i][S]=0;

    			FOR(j,0,n-1){

    				int s=0;

    				FOR(k,0,n-1) if((S>>k)&1) s+=a[(j+k)%n][i];

    				sum[i][S]=max(sum[i][S],s);

    			}

    		}

    		FOR(S,0,(1<<n)-1) f[0][S]=sum[0][S];

    		FOR(i,1,min(n,m)-1) FOR(S,0,(1<<n)-1){

    			f[i][S]=f[i-1][S];

    			for(int S0=S;S0;S0=(S0-1)&S) f[i][S]=max(f[i][S],f[i-1][S^S0]+sum[i][S0]);

    		}

    		printf("%d\n",f[min(n,m)-1][(1<<n)-1]);

    	}

    }

G1

传说是个 sb 题？完了……

先分成若干块，每个颜色都恰好在一个块内，且块尽可能多。显然只有一种方案而且可以贪心做。这样块内就要变成一个颜色，而且每个块互不影响。对于一个块，除了出现次数最多的颜色，其它的都要变成那个颜色。

    #include<bits/stdc++.h>

    using namespace std;

    typedef long long ll;

    typedef pair<int,int> PII;

    const int maxn=222222;

    #define MP make_pair

    #define PB push_back

    #define lson o<<1,l,mid

    #define rson o<<1|1,mid+1,r

    #define FOR(i,a,b) for(int i=(a);i<=(b);i++)

    #define ROF(i,a,b) for(int i=(a);i>=(b);i--)

    #define MEM(x,v) memset(x,v,sizeof(x))

    inline ll read(){

    	char ch=getchar();ll x=0,f=0;

    	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();

    	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();

    	return f?-x:x;

    }

    int n,q,a[maxn],mn[maxn],l,r,tmp[maxn],tl,cnt[maxn],ans;

    int calc(){

    	tl=0;

    	FOR(i,l,r) if(++cnt[a[i]]==1) tmp[++tl]=a[i];

    	FOR(i,1,tl) tmp[i]=cnt[tmp[i]];

    	sort(tmp+1,tmp+tl+1);

    	int s=0;

    	FOR(i,1,tl-1) s+=tmp[i];

    	FOR(i,l,r) cnt[a[i]]--;

    	return s;

    }

    int main(){

    	n=read();q=read();

    	FOR(i,1,n){

    		a[i]=read();

    		if(!mn[a[i]]) mn[a[i]]=i;

    	}

    	int curmn=1e9;

    	r=n;

    	ROF(i,n,1){

    		curmn=min(curmn,mn[a[i]]);

    		if(i==curmn){

    			curmn=1e9;

    			l=i;

    			ans+=calc();

    			r=i-1;

    		}

    	}

    	printf("%d\n",ans);

    	while(q--) puts("PB AK ZROI");

    }

剩下的，咕了。

巴特西

Codeforces Round 584 题解

A

B

C

D

E

G1

最新文章

热门文章