本文主要是介绍记 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昆明的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！