ICPC2020南京站(持续更新中)

发布于 2021-03-01  921 次阅读


这是本人上大学后第二次参加算法类的比赛,可能也是准备不足的原因吧,导致我这次的发挥也依旧有些不尽人意,简单复盘了一下发现并没有那么难。我才大一,未来机会还很多,很可惜同队的学长是要退役毕业工作去了,对他我心里多少也有些愧对吧,祝他工作顺利吧,队里缺人有想来组队的吗。

E.Evil Coordinate

这道题类似于模拟,但我当时想的太复杂了,越写越乱,最后没时间了害,这道题其实就是让机器人去走直线去避开爆炸区,我考虑了好多好多种情况去一一的进行考虑,后来发现想多了。。。其实可以四个方向全排列挨个去试。。。还没从OI中脱离出来,思维还是原来的,硬伤啊,贴一下我那个很长很长的代码吧,我是智障

#include <bits/stdc++.h>
using namespace std;
char s[1000005];

void solve(){
	int sx,sy,mx,my,l=0,r=0,d=0,u=0;
	scanf("%d%d",&mx,&my);
	scanf("%s",s+1);
	int len=strlen(s+1);
	for(int i=1;i<=len;i++){
		if(s[i]=='U') u++;
		if(s[i]=='D') d++;
		if(s[i]=='R') r++;
		if(s[i]=='L') l++;
	}
	sx=r-l,sy=u-d;
	if(mx==0&&my==0){
		printf("Impossible\n");
		return;
	}
	if(sx==mx&&sy==my){
		printf("Impossible\n");
		return;
	}
	if(mx!=0&&my!=0){
		if(mx==sx){
			for(int i=1;i<=u;i++)
				printf("U");
			for(int i=1;i<=d;i++)
				printf("D");
			for(int i=1;i<=l;i++)
				printf("L");
			for(int i=1;i<=r;i++)
				printf("R");
			printf("\n");
			return;
		}
		else{
			for(int i=1;i<=l;i++)
				printf("L");
			for(int i=1;i<=r;i++)
				printf("R");
			for(int i=1;i<=u;i++)
				printf("U");
			for(int i=1;i<=d;i++)
				printf("D");
			printf("\n");
			return;
		}
	}
	
	if(mx==0){
		if(sx==0){
			if(!l&&!r&&((sy>0&&my>0&&sy>my)||(sy<0&&my<0&&sy<my))){
				printf("Impossible\n");
				return;
			}
			if(l) for(int i=1;i<=l;i++) printf("L");
			else for(int i=1;i<=r;i++) printf("R");
			if(my<0){
				for(int i=1;i<=u;i++)
					printf("U");
				for(int i=1;i<=d;i++)
					printf("D");
			}
			else{
				for(int i=1;i<=d;i++)
					printf("D");
				for(int i=1;i<=u;i++)
					printf("U");
			}
			if(l) for(int i=1;i<=r;i++) printf("R");
			else for(int i=1;i<=l;i++) printf("L");
		}
		else{
			for(int i=1;i<=l;i++)
				printf("L");

			for(int i=1;i<=r;i++)
				printf("R");
			for(int i=1;i<=u;i++)
				printf("U");
			for(int i=1;i<=d;i++)
				printf("D");
		}
	}
	if(my==0){
		if(sy==0){
			if(!u&&!d&&((sx>0&&mx>0&&sx>mx)||(sx<0&&mx<0&&sx<mx))){
				printf("Impossible\n");
				return;
			}
			if(u) for(int i=1;i<=u;i++) printf("U");
			else for(int i=1;i<=d;i++) printf("D");
			if(mx>0){
				for(int i=1;i<=l;i++)
					printf("L");
				for(int i=1;i<=r;i++)
					printf("R");
			}
			else{
				for(int i=1;i<=r;i++)
					printf("R");
				for(int i=1;i<=l;i++)
					printf("L");
			}
			if(u) for(int i=1;i<=d;i++) printf("D");
			else for(int i=1;i<=u;i++) printf("U");
		}
		else{
			for(int i=1;i<=u;i++)
				printf("U");
			for(int i=1;i<=d;i++)
				printf("D");
			for(int i=1;i<=l;i++)
				printf("L");
			for(int i=1;i<=r;i++)
				printf("R");
		}
	}
	printf("\n");
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--)
		solve();
	return 0;
}

F. Fireworks

由于没学过概率论,只用高中那点知识来写期望表达式,结果就错了呜呜呜呜~~~期望计算方法为(n*x+m)/(1-(1-p,x)) (x为点燃烟花个数),但为什么表达式是这样的和我高中所学的概率期望有所不同,等到时候我去学学概率论吧。这样一个表达式可以通过求二阶导来证明出这是个单谷函数,我们选择三分其谷值

#include <bits/stdc++.h>
using namespace std;
int T,n,m;
double p;
double cal(double x){
	return (n*x+m)/(1.0-pow(1-p,x));
}
void solve(){
	scanf("%d%d%lf",&n,&m,&p);
	p*=1e-4;
	double l=0,r=1e9;
	while(r-l>1e-9){
		double ll=l+(r-l)/3,rr=r-(r-l)/3;
		if(cal(ll)<cal(rr)) r=rr;
		else l=ll;
	}
	int ans=l;
	printf("%.10f\n",min(cal(ans),cal(ans+1)));
}
int main(){
	scanf("%d",&T);
	while(T--)
		solve();
	return 0;
}

K. K Co-prime Permutation

相邻必互质!!!!

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int n,a[1000006],k;
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		a[i]=i;
	if((k==0)||(k>n)){
		printf("-1");
		return 0;
	}

	for(int i=2;i<=k;i++)
		printf("%d ",i);
	printf("1");
	for(int i=k+1;i<=n;i++)
		printf(" %d",i);
	return 0;
}

L. Let's Play Curling

这道题有点像一个脑筋急转弯,其实就是统计两个蓝队球之间有几个红队球,贴一份学长写的代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node{
	int val;
	int pos;
	bool operator < (const node &n1){
		if(pos == n1.pos){
			return val > n1.val;
		}
		return pos < n1.pos;
	}
};
int main(int argc, char const *argv[])
{
	/* code */
	int t, a, b;
	cin >> t;
	while(t--){
		vector<node> vec;
		cin >> a >> b;
		while(a--){
			node tmp;
			tmp.val = 1;
			cin >> tmp.pos;
			vec.push_back(tmp);
		}
		while(b--){
			node tmp;
			tmp.val = 0;
			cin >> tmp.pos;
			vec.push_back(tmp);
		}
		sort(vec.begin(), vec.end());
		int ans = 0;
		int total = 0;
		int len = vec.size();
		for(int i=0;i<len;i++){
			if(vec[i].val == 1){
				total++;
			}
			if(vec[i].val == 0){
				int tmp = i-1;
				while(tmp>=0 && vec[tmp].pos == vec[i].pos){
					tmp--;
					total--;
				}
				ans = max(total, ans);
				total = 0;
			}
		}
		int lst = 0;
		for(int i=len-1;i>=0;i--){
			if(vec[i].val == 0){
				lst = i;
				break;
			}
		}
		ans = max(ans, len-1-lst);
		if(ans == 0){
			cout << "Impossible" <<endl;
		}else{
			cout << ans << endl;
		}
		

	}
	return 0;
}

M.Monster Hunter

一个树形dp问题,用dp[i][j][0/1],第一维代表的是节点i,第二维代表的是节点i极其子节点有j个点被魔法杀掉了,第三维是代表i点有没有被魔法杀掉

#include <bits/stdc++.h>
#define inf 100000000000000
#define ll long long
using namespace std;
ll hp[5000],dp[4000][4000][2],siz[4000],g[4000][2];
vector<int>G[5000];
void dfs(int now,int fa){
	siz[now]=1;
	dp[now][0][0]=hp[now];
	for(auto v:G[now]){
		if(v==fa) continue;
		dfs(v,now);
		for(int i=0;i<=siz[now]+siz[v];i++) g[i][0]=g[i][1]=inf;
		for(int i=0;i<=siz[now];i++){
			for(int j=0;j<=siz[v];j++){
				if(i+j<siz[now]+siz[v]){
					g[i+j][0]=min(g[i+j][0],dp[now][i][0]+dp[v][j][0]+hp[v]);
					if(j>0) g[i+j][0]=min(g[i+j][0],dp[now][i][0]+dp[v][j][1]);
				}
				if(i>0){
					g[i+j][1]=min(g[i+j][1],dp[now][i][1]+dp[v][j][0]);
					if(j>0) g[i+j][1]=min(g[i+j][1],dp[now][i][1]+dp[v][j][1]);
				}
			}
		}
		siz[now]+=siz[v];
		for(int i=0;i<=siz[now];i++) dp[now][i][0]=g[i][0],dp[now][i][1]=g[i][1];
	}
	//for(int i=0;i<=siz[now];i++) dp[now][i][0]+=hp[now];
}
void solve(){
	int n;
	cin>>n;
	for(int i=0;i<=n;i++)
	for(int j=0;j<=n;j++) dp[i][j][0]=dp[i][j][1]=0;
	for(int i=1;i<=n;i++) G[i].clear();
	for(int i=2;i<=n;i++){
		int x;
		cin>>x;
		G[x].push_back(i),G[i].push_back(x);
	}
	for(int i=1;i<=n;i++) cin>>hp[i];
	dfs(1,0);
	for(int i=0;i<=n;i++) cout<<min(dp[1][i][0],dp[1][i][1])<<" ";
	cout<<endl;
}
int main(){
	int T;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

回忆这理想不够理想,沿途逛世间一趟只有向上