时间戳

首页 > 技术文章 > Educational Codeforces Round 55 (Rated for Div. 2)

Educational Codeforces Round 55 (Rated for Div. 2)

shanxieng 2018-11-29 18:14 原文

Educational Codeforces Round 55 (Rated for Div. 2)

链接

A Vasya and Book

傻逼题。。注意判边界。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cmath>
using namespace std;

typedef long long ll;

int t,n,x,y,d;

int main() {
	scanf("%d",&t);
	while(t--) {
		scanf("%d%d%d%d",&n,&x,&y,&d);
		int sxz=abs(x-y);
		if(sxz%d==0) {
			printf("%d\n",sxz/d);
			continue;
		}
		int ans=0x7fffffff;
		if((y-1)%d==0)
			ans=min(ans,(x==1?0:(int)ceil((double)(x-1)/d))+(y-1)/d);
		if((n-y)%d==0)
			ans=min(ans,(x==n?0:(int)ceil((double)(n-x)/d))+(n-y)/d);
		if(ans==0x7fffffff) printf("-1\n");
		else printf("%d\n",ans);
	}
	return 0;
}

B Vova and Trophies

还是傻逼题。。还是要判好边界。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cmath>
using namespace std;

typedef long long ll;
const int Maxn=110000;

int n,a[Maxn],l[Maxn],ok[Maxn],tot;

char getach() {
	char ch=getchar();
	while(ch!='G'&&ch!='S') ch=getchar();
	return ch;
}

int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		if(getach()=='G') {
			a[i]=1;
			if(i>2&&a[i-1]==0&&a[i-2])
				ok[tot]=1;
			l[tot]++;
		}
		else if(a[i-1]) tot++;
	}
	if(a[n]==1) tot++;
	if(tot==1) {
		printf("%d",l[0]);
		return 0;
	}
	int ans=0;
	for(int i=0;i<tot;i++) {
		ans=max(ans,l[i]+1);
		if(ok[i]) {
			if(tot==2)
				ans=max(ans,l[i]+l[i-1]);
			else ans=max(ans,l[i]+l[i-1]+1);
		}
	}
	printf("%d",ans);
	return 0;
}

C Multi-Subject Competition

开n个堆就好了，用队列存着目前堆非空且和不为负数的堆分别是那几个，时间复杂度\(O(n \log n)\)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cmath>
using namespace std;

typedef long long ll;
const int Maxn=110000;

int n,m,c[Maxn],b[Maxn],ans,x,y,tot;

priority_queue<int> q[Maxn];

int main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) {
		scanf("%d%d",&x,&y);
		q[x].push(y);
	}
	for(int i=1;i<=m;i++)
		if(!q[i].empty()&&q[i].top()>0) {
			b[++tot]=q[i].top();
			c[tot]=i;
			q[i].pop();
		}
	int num=0;
	for(int i=1;i<=tot;i++)
		num+=b[i];
	ans=max(ans,num);
	while(tot) {
		int sxz=tot;
		tot=0;
		num=0;
		for(int i=1;i<=sxz;i++)
			if(!q[c[i]].empty()&&b[i]+q[c[i]].top()>0) {
				b[++tot]=b[i]+q[c[i]].top();
				c[tot]=c[i];
				q[c[i]].pop();
			}
		for(int i=1;i<=tot;i++)
			num+=b[i];
		ans=max(ans,num);
	}
	printf("%d",ans);
	return 0;
}

D Maximum Diameter Graph

这个题可以贪心，把所有的点按照度数限制排个序，然后枚举直径的长度，直径两边选度数限制最小的，其余的点选度数限制最大的，然后把其他的点挂上就好了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cmath>
using namespace std;

typedef long long ll;
const int Maxn=110000;

int n,m,a[Maxn],b[Maxn];

int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]),b[i]=i;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			if(a[j]>a[i]) {
				swap(a[i],a[j]);
				swap(b[i],b[j]);
			}
	for(int i=n-2;i>=1;i--) {
		int num=0;
		for(int j=1;j<=i;j++)
			if(a[j]>=2) num+=a[j]-2;
			else {
				num=-1;
				break;
			}
		if(num>=n-i-2) {
			printf("YES %d\n",i+1);
			printf("%d\n",n-1);
			printf("%d %d\n",b[n],b[1]);
			printf("%d %d\n",b[n-1],b[i]);
			for(int j=1;j<i;j++) printf("%d %d\n",b[j],b[j+1]);
			int temp=1;
			for(int j=i+1;j<=n-2;j++)
				if(a[temp]>2) {
					a[temp]--;
					printf("%d %d\n",b[temp],b[j]);
				}
				else {
					while(a[temp]==2) temp++;
					a[temp]--;
					printf("%d %d\n",b[temp],b[j]);
				}
			return 0;
		}
	}
	puts("NO");
	return 0;
}

E Increasing Frequency

这道题是傻逼贪心，我竟然没看出来。。

大概就是记一下c出现个数的前缀和，然后枚举其他的每个数，把这个数在数列中出现的位置排个序，从前往后扫一遍，维护左右端点，然后对于一个区间，如果在这个区间中c的出现次数比这个数多，那就把这个区间扔掉。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

typedef long long ll;
const int Maxn=510000;
const double eps=1e-9;

int n,c,x,a[Maxn],ans;

priority_queue<int,vector<int>,greater<int> >h[Maxn];

int main() {
//	freopen("test.in","r",stdin);
	scanf("%d%d",&n,&c);
	for(int i=1;i<=n;i++) {
		scanf("%d",&x);a[i]=a[i-1];
		if(x==c) a[i]++;
		h[x].push(i);
	}
	for(int i=1;i<=500000;i++)
		if(i!=c&&!h[i].empty()) {
			int sxz=0,zhy=1,last=h[i].top();
			h[i].pop();
			ans=max(ans,zhy);
			while(!h[i].empty()) {
				int temp=h[i].top();
				h[i].pop();
				sxz+=a[temp]-a[last];
				zhy++;
				if(sxz>=zhy) {
					sxz=0;
					zhy=1;
				}
				ans=max(ans,zhy-sxz);
				last=temp;
			}
		}
	printf("%d",ans+a[n]);
	return 0;
}

F

毒瘤。。。

正解就是在trie上做个背包，时间复杂度为\(O(n^2k^2)\)

交了十遍终于过了。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const int Maxn=1520;
const int Maxm=11;
const double eps=1e-9;

int f[Maxn][Maxn][Maxm],n,k,zhy,vis[Maxn][Maxn],ch[Maxn][Maxm],siz[Maxn],tot,ans;
char a[Maxn];

void dp(int root,int len) {
	if(vis[root][len]) return;
	vis[root][len]=1;
	int ans[Maxm];
	memset(ans,0x80,sizeof(ans));
	ans[0]=0;
	int ans2[Maxm];
	memset(ans2,0x80,sizeof(ans2));
	ans2[1]=len*siz[root];
	for(int i=0;i<10;i++) 
		if(ch[root][i]) {
			int sxz=ch[root][i];
			dp(sxz,len+1);dp(sxz,1);
			for(int j=k;j;j--) for(int l=1;l<=j;l++)
				ans[j]=max(ans[j],ans[j-l]+f[sxz][len+1][l]);
			for(int j=k;j;j--) for(int l=1;l<=j;l++)
				ans2[j]=max(ans2[j],ans2[j-l]+f[sxz][1][l]);
		}
	for(int i=0;i<=k;i++) f[root][len][i]=max(0,max(ans[i],ans2[i]));
}

int main() {
//	freopen("test.in","r",stdin);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) {
		scanf("%s%d",a,&zhy);
		int now=0,len=strlen(a),temp=0;
		while(temp<len) {
			int x=a[temp]-'0';
			if(ch[now][x]==0) ch[now][x]=++tot;
			now=ch[now][x];
			siz[now]+=zhy;
			temp++;
		}
		ans+=len*zhy;
	}
	dp(0,0);
	int sxz=0;
	for(int i=0;i<=k;i++) sxz=max(sxz,f[0][0][i]);
	printf("%d",ans-sxz);
	return 0;
}

G Petya and Graph

这个题是个傻逼网络流。。我竟然没看出来。

大概就是最小割建图，把每个点和每个边建点，每个边从他的两个端点连边，流量为正无穷；从原点向所有的点连边，流量为点的点权；从所有边向汇点连边，流量为边权。


	memset(b,0,sizeof(b));
	b[s]=1;
	while(!q.empty()) {
		int now=q.front();q.pop();
		for(int i=first[now];i;i=nxt[i])
			if(w[i]&&b[to[i]]==0) {
				b[to[i]]=b[now]+1;
				q.push(to[i]);
			}
	}
	return b[t];
}

ll dfs(int root,int flow) {
	if(root==t) return flow;
	for(int i=first[root];i;i=nxt[i])
		if(w[i]&&b[to[i]]==b[root]+1) {
			int temp=dfs(to[i],min(flow,w[i]));
			if(temp) {
				w[i]-=temp;
				w[i^1]+=temp;
				return temp;
			}
		}
	return 0;
}

ll dinic() {
	ll ans=0,temp;
	while(bfs())
		while(temp=dfs(s,inf))
			ans+=temp;
	return ans;
}

int main() {
//	freopen("test.in","r",stdin);
	scanf("%d%d",&n,&m);
	s=0,t=n+m+1;
	for(int i=1;i<=n;i++) {
		scanf("%I64d",&x);
		add(s,i,x);
	}
	for(int i=1,sxz=n+1;i<=m;i++,sxz++) {
		scanf("%d%d%I64d",&u,&v,&x);
		add(u,sxz,inf);
		add(v,sxz,inf);
		add(sxz,t,x);
		ans+=x;
	}
	printf("%I64d",ans-dinic());
	return 0;
}

推荐阅读