C/C++教程

记 ICPC2021昆明

本文主要是介绍记 ICPC2021昆明,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Friday

早八去上语文,上到九点发通知说十点开始上网课。
然后就去机房上数学网课了,后来说封校,突然意识到gxy如果回家周天比赛就进不来了。于是gxy趁封校前把被子搬来机房准备在躺椅上睡两天,但下午又有老师来说实验室都要锁门,我们就开始打算全队跑去gxy家住两天,打完比赛再回来。
问辅导员的时候辅导员说可以提供场所(B925)在校内打,然后就决定在校内打了(gxy在我宿舍打地铺)。后来发现B925空间很大,于是就把校队的三个队都拉来打了。不过把显示器打印机什么的搬到仲英楼and把躺椅搬到宿舍累死了

大概收拾完就带着gxy一块去仲英楼找他们 血 染 钟 楼 去了玩了一把就改玩狼人杀了。比较离谱的是因为人太多,二楼大厅不合适,刘梦欣竟然要到了B917的要是用来玩。甚至十一点多田博走的时候让我们也走,我们还以刘梦欣0点过生日为由没走

Saturday

因为前一天搬东西玩狼人杀太累,两点回到宿舍接着睡了,所以第二天九点就起床吃了个早饭+做核酸。
然后Diamond Sea队要去B925,我们过去开门,于是就在B925待了一天。晚上跟他们队一起去梧桐吃了晚饭,浅打了一下热身赛,就跟zxh一起去棋协打麻将了。
麻将集训内容是测试zxh搞的复式麻将,但我没打,去帮忙摆牌山了。累死
本来想回来做一下数学作业的,不过考虑到明天比赛,就早睡了。

Sunday

八点多起床吃早饭+做核酸+去兴华买东西。
9点到了本想做数学作业热身,结果吃的落兴华了跑一趟,充电线落宿舍了跑一趟,刚开始做作业就开始比赛了。

K

一人读四题,读完以后我感觉C可做,gxy感觉E可做(然而最后这俩都不会做)。做了一会没做出来于是跟榜开K。
Problem: 一个人打 \(n\) 场比赛,当胜率高于 \(\frac{a}{b}\) 时这场比赛会失败,否则胜利,问最后会赢几场(初始胜率为0)。
Solution:
赛时没有什么简单的思路,联想到前几天syh问的几道题,转换成赢一局积 \((b-a)\) 分,输一局扣 \(a\) 分,然后就变成 if((b-a)*x-a*y<0) ++x; else ++y;
所以 \(n\) 局中此人的战绩是一个围绕直线 \((b-a)x-ay=0\) 的折线(即折线上任一点距离直线的竖直距离不超过 \(1\))。
我们又知道结束时的点一定在直线 \(x+y=n\) 上,

画图可以发现,答案一定是两直线交点所在正方形的左上角或右下角(如果交线恰为整点则答案为交点),具体是左上还是右下只需考虑左下角在直线的上方还是下方。
再特判一下胜率为0的情况就ok了。
Code:

#include<iostream>
#include<algorithm>
using namespace std;
int T;
long long n,a,b,x,y;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>a>>b;
		if(a==0){
			cout<<1<<endl;
			continue;
		}
		x=a*n/b,y=(b-a)*n/b;
		if(x+y==n) cout<<x<<endl;
		else if(y*a-(b-a)*x>=0) cout<<x+1<<endl;
		else cout<<x<<endl;
	}
	return 0;
}

不过后来看别人代码就 \(a(n-1)/b\) ,不懂为什么。
过这题的时候已经一个多小时了,心态有点小崩。

F

我读完题发现确定 \(x\) 的取值和树上问题是完全独立的,于是只需考虑在树上找一条路径使得点权平均值最大。
ljj说可以分数规划:二分平均值k然后令点权'=点权-k,树形dp选点权和不小于0的路径即可。
然后写完交一发,WA了,调高精度,还是WA。
ljj写的时候我想出了D的构造,就先换我写D了。
写完D继续魔改F,先是优化了常数交了下,1WA 1TLE。
然后gxy发现二分的上下界可以从 \(\pm 1e10\) 改成 \(\pm 1e5\), 交,2WA 2TLE。
这时我以为想出了B正解,就换我写B,写着写着ljj说把long double改成double试试,1TLE 1AC。
真的是很玄学了……
Problem:
有一棵树,每个点有点权 \(b_i\),要求选择一个路径 \(V\),最大化 \(\frac{\sum_{u\in V} (-x^2+b_ux)}{|V|}\)
Solution:
\(\frac{\sum_{u\in V} (-x^2+b_ux)}{|V|}=-x^2+x\frac{\sum_{u\in V} b_u}{|V|}=-x^2+x\bar{b}\leq \frac{\bar{b}^2}{4}\)
二分 \(\bar{b}\),令 \(b'_i=b_i-\bar{b}\),树形dp check 是否存在 \(\sum b_i' \geq 0\) 的路径
Code:

#include<cmath>
#include<cstdio>
#include<iomanip>
#include<iostream>
#include<algorithm>
#define eps 1e-9
const int maxn=100005;
using namespace std;
int n,head[maxn],nxt[maxn<<1],to[maxn<<1],cnt;
inline void add(int u,int v){
	nxt[++cnt]=head[u],head[u]=cnt,to[cnt]=v;
	nxt[++cnt]=head[v],head[v]=cnt,to[cnt]=u;
}
double L,R,mid,s[maxn],ans,f[maxn][2],tmp;
void dfsmax(int pos,int pre){
	f[pos][0]=s[pos]-mid,f[pos][1]=-1e5;
	for(int i=head[pos];i;i=nxt[i]){
		if(to[i]==pre) continue;
		dfsmax(to[i],pos);
		tmp=max(tmp,max(f[pos][1],f[pos][0])+max(f[to[i]][0],f[to[i]][1]));
		f[pos][1]=max(f[pos][1],f[pos][0]+max(f[to[i]][0],f[to[i]][1]));
	}
}
void dfsmin(int pos,int pre){
	f[pos][0]=s[pos]-mid,f[pos][1]=1e5;
	for(int i=head[pos];i;i=nxt[i]){
		if(to[i]==pre) continue;
		dfsmin(to[i],pos);
		tmp=min(tmp,min(f[pos][1],f[pos][0])+min(f[to[i]][0],f[to[i]][1]));
		f[pos][1]=min(f[pos][1],f[pos][0]+min(f[to[i]][0],f[to[i]][1]));
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i) cin>>s[i];
	for(int i=1,u,v;i<n;++i) cin>>u>>v,add(u,v);
	L=-1e5,R=1e5;
	while(R-L>eps){
		mid=(L+R)/2;
		tmp=-1e5,dfsmax(1,1);
		if(tmp>0) L=mid;
		else R=mid;
	}
	ans=abs(L);
	//cout<<ans<<endl;
	L=-1e5,R=1e5;
	while(R-L>eps){
		mid=(L+R)/2;
		tmp=1e5,dfsmin(1,1);
		if(tmp>0) L=mid;
		else R=mid;
	}
	//cout<<abs(L)<<endl;
	ans=max(ans,abs(L));
	//cout<<ans<<endl;
	ans=ans * ans / 4;
	//printf("%lf\n", ans);
	cout<<fixed<<setprecision(6)<<ans<<endl;
	return 0;
}

赛后syr说其实路径长度一定不超过三,因为超过三的路径可以拆成两个,必有一个路径平均值不小于原路径的平均值。这样就不用二分了,也就不会有卡时间卡精度的问题了。

D

D是个构造,刚开始没考虑k=0,WA了一发
Problem:
将一个长 \(n\) 的数列划分成两个子序列A,B,若A单调不降,B单调不增,则称为一个好的划分。共有\(2^n\)种不同的划分
给定 \(k\),输出一个恰有 \(k\) 个好的划分的数列(长度不超过365,值域不超过1e8)。
Solution:
不好描述,看代码吧。大概就是把k二进制拆分,然后一段连续的相同数字会贡献\(2^{len}-1\),最后再用若干个单独的数字补齐差的\(O(\log k)\)个。其中,段/单独数字 与 段/单独数字 的关系是单调降的,这样可以保证A只在其中某个里选,可以适用加法原理。
Code:

#include<iostream>
using namespace std;
int ans[400],top;
int main(){
    int k,cnt=0;cin>>k;
    if(k==0){
        printf("9\n1 2 3 2 1 2 3 2 1");
        return 0;
    }
    if(k==1){
        printf("6\n1 1 4 5 1 4");
        return 0;
    }
    for(int i=1;i<=k;i<<=1,++cnt){
        if(k&i)
            for(int t=0;t<cnt;++t)
                ans[++top]=cnt+1;
    }
    for(int i=1;i<cnt;++i) ans[++top]=50000000+i;
    printf("%d\n",cnt);
    for(int i=1;i<=top;++i) printf("%d ",ans[i]);
    return 0;
}

B

这题刚开始理解错题意了,以为可以直接枚举全排列然后枚举每个排列的每个前缀然后check能不能覆盖
值得一提的是,前几天训练台北场刚做了个题,gxy的做法恰好可以用来快速check能不能覆盖,于是很早就开了这个题,然后死活过不了样例。
后来发公告说可以重复选,就不会做了。
过了好久又想这题,以为是一个等差*等比的级数求和,结果还是过不去样例。
然后刚刚过了B题的ljj说可以dp,然后恍然大悟,但是交上去TLE了。
一算时间复杂度 \(O(Tn^32^n)\),而且gxy的check会有个4的常数。
然后发现常数可以优化到2,又卡了卡常,把重复算了好几遍的逆元存了一下,就玄学的卡过了。
Problem:
大矩形中有若干小矩形区域,每次随机在这些区域里选一个染黑,可能重复选,问期望多少次把大矩形全染黑。
Solution:
首先由gxy在台北场想出的算法,记为Algo G,可以\(O(n^2)\)预处理 \(n\) 个块能否完全覆盖某个区域。
对 \(O(2^n)\) 个子集,枚举每个块,用Algo G判断子集能否完全覆盖该块。将一个集合 \(i\) 能覆盖的块的个数记为 \(cnt_i\)。
记 \(f_i\) 表示集合 \(i\) 期望需要几步可以把大矩形完全染黑。
先用Algo G判断全集是否能覆盖大矩形,若不能,直接输出-1。否则:
有 \(f_U=0\),\(f_i=\sum_{u} (1+f_{i\cup u})[cnt_{i\cup u}>cnt_i]\)
Code:

#include <bits/stdc++.h>
#define int long long
using namespace std;

int MP[30][30];
int X1[30], X2[30], Y1[30], Y2[30];
int x_1[30], y_1[30], x_2[30], y_2[30];
int CNT[1500];
vector<int> V[30];
int cntx, cnty;
int w, h, wx, hy,n;
bool check(int x) {
	for(int i = 0; i < 21; i++) {
		for(int j = 0; j < 21; j++) {
			MP[i][j] = 0;
		}
	}
	for(int i = 0; i < cntx; i++) {
		for(int j = 0; j < 21; j++) {
			V[j].clear();
		}
		//printf("i:%d\n", i);
		for(int j = 0; j < n; j++) {
			if((1 << j) & x) {
				if(x_1[j] <= i && x_2[j] > i) {
					//printf("%d %d\n", y_1[j], y_2[j]);
					V[y_1[j]].push_back(1);
					V[y_2[j]].push_back(0);
				}
			}
		}
		int pt = 0;
		for(int j = 0; j < cnty; j++) {
			//printf("%d size:%d\n", j, (int)V[j].size());
			for(int k = 0; k < (int)V[j].size(); k++) {
				if(V[j][k]) pt++;
				else pt--;
			}
			if(pt) MP[i][j] = 1;
		}
	}
//	for(int i = 0; i < wx; i++) {
//		for(int j = 0; j < hy; j++) {
//			printf("%d ", MP[i][j]);
//		}
//		printf("\n");
//	}
	CNT[x] = 0;
	for(int k = 0; k < n; k++) {
		int flag = 1;
		for(int i = x_1[k]; i < x_2[k]; i++) {
			for(int j = y_1[k]; j < y_2[k]; j++) {
				if(!MP[i][j]) {
					flag = 0;
					break;
				}
			}
		}
		if(flag) CNT[x]++;
	}
	for(int i = 0; i < wx; i++) {
		for(int j = 0; j < hy; j++) {
			if(!MP[i][j]) {return false;}
		}
	}
	return true;
}
int cnt(int x) {
	return CNT[x];
}
const int P=998244353;
bool vis[12];int p[12],ans;
int fct(int n){
	int res=1;
	for(int i=1;i<=n;++i)
		res=res*i%P;
	return res;
}
int mpow(int a,int b,int c){
	if(a==0) return 0;
	long long res=1,base=a;
	for(int i=1;i<=b;i<<=1){
		if(b&i) res=res*base%c;
		base=base*base%c;
	}
	return res;
}
int ck[1500],f[1500];
signed main() {
	int T;
	scanf("%lld", &T);
	while(T--) {
		map<int, int> mx;
		map<int, int> my;
		scanf("%lld%lld%lld", &n, &w, &h);
		mx[0]=0;
		my[0]=0;
		mx[w]=0;
		my[h]=0;
		for(int i = 0; i < n; i++) {
			scanf("%lld%lld%lld%lld", &X1[i], &Y1[i], &X2[i], &Y2[i]);
			mx[X1[i]] = 0;
			my[Y1[i]] = 0;
			mx[X2[i]] = 0;
			my[Y2[i]] = 0;
		}
		cntx = 0;
		for(auto i = mx.begin(); i != mx.end(); i++) {
			i->second = cntx++;
		}
		cnty = 0;
		for(auto i = my.begin(); i != my.end(); i++) {
			i->second = cnty++;
		}
		wx=mx[w];
		hy=my[h];
		for(int i = 0; i < n; i++) {
			x_1[i] = mx[X1[i]];
			x_2[i] = mx[X2[i]];
			y_1[i] = my[Y1[i]];
			y_2[i] = my[Y2[i]];
		}
//		cout << check(7);
		if(!check((1<<n)-1)) puts("-1");
		
		else{
			for(int i=1;i<(1<<n);++i){
				ck[i]=check(i);
			}
			f[(1 << n) - 1] = 0;
			int invn=mpow(n,P-2,P);
			for(int i=(1<<n)-2;i>=0;--i){
				f[i]=cnt(i)*invn%P;
				for(int u=1;u<(1<<n);u<<=1){
					if(cnt(i|u)>cnt(i)){
						f[i]=(f[i]+(1+f[i|u])*invn%P);
					}
				}
				f[i]=f[i]*mpow( (1-cnt(i)*invn%P+P)%P,P-2,P )%P;
			}
			cout<<f[0]<<endl;
		}
	}
	return 0;
}

不过赛后得知这题正解是 \(O(Tn2^n)\) 的。

A

纯纯的大模拟。本来预留了一小时来写,不过B卡常用了不少时间,只有40分钟了。还剩13分钟左右的时候写完了,修修bug过样例时只有几分钟了,交上去发现段错误,应该是数组越界。还剩3分钟的时候我们交了好多发,然后莫名其妙调大数组以后就过了。

Summary

最后这场比赛拿了银首,不知道成绩够不够进EC Final,不过因为成绩在校内三个队里最好,所以至少能靠奖励名额进。
5题罚时少或者6题就能金了,而我们其实还有两题都有思路(G,L),所以还稍稍有点可惜,不过也很满意了。
回顾一下,A题能过主要得益于ljj的代码能力,gxy的debug能力,还有嘉然外套的加成();B能过主要得益于gxy台北场的算法和卡常卡过了的运气;D能过我也不知道靠什么,就靠我灵机一动刚好构造出来了吧;F能过主要还是ljj的代码能力和gxy的debug能力,考虑到做法并不是正解所以能过也很看运气;K能过主要靠syh之前问过我一个类似的题,不然真就卡签到题了。
所以其实除了大模拟和构造是正常做的,剩下三个一个签到题做麻烦了,两个复杂度不对。
然后复杂度不对的两个和大模拟还都是玄学debug,莫名其妙就AC了。而做麻烦的那个签到题,要不是有过类似的idea,可能根本做不出来。B题也是,如果不是训练过台北场且gxy又能把那个算法实现出来,我们也不可能做出这题。
然后B和F分别是多俩log和多一个log且精度不够,但是都卡过了。
总而言之,运气成分很大,但最近训练的效果也明显有了体现,要在EC final取得好成绩还需要更加努力。

这篇关于记 ICPC2021昆明的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!