2021牛客高校暑假训练赛五

本文最后更新于：2021年8月19日 晚上

比赛过程

队友带我飞。
开场还是从后往前看，K感觉有点麻烦，一时没有思路就没有先看。队友说J他以前搞过就让他去搞。我去搞了H签到，构造01矩阵，想了一会儿就构造出来了。队友还在码K便去看B。B感觉是概率DP，由于概率DP不是很熟便与队友开始讨论。队友此时过了J和我一起看B。
我一直觉得C的位置可以插在任意两次打开盒子的时间段内，很麻烦不知道怎么下手去搞。还要处理组合数求概率并且题目中没有取模没法搞。队友说只需要把C放在最开头就行。剩下的排个序就行。我当时还觉得可能是队友想太简单了。交了一发WA了。然后和队友讨论是不是可以有其他方式，队友此时有些动摇（差点被我带跑），我准备再用自己的思路写一遍的时候，忽然发现一个Cornercase没有判断。加上去，A了（还好没重新打）。
之后我去看D队友看J。我卡在D的组合数呢快，之后就一直卡着知道比赛结束。（赛后改了下组合数的公式以及求逆元的过程就过了）
实际上还挺麻烦的，中间还换了多种求逆元的方式，最后在算阶乘时候就直接乘上逆元算的才过

总结

队友立大功，比赛果然是团队协作的更棒。
个人的话主要还是基础的思维题目还得多练（J），然后是走不通时候需要改变自己思路重新想（其实有队友的话这点会加成很大，因为会和队友交换观点一直刷新认知思考，而不是在死胡同中一条路走到黑）。

题目详情

C

题目链接
我个人是觉得我的处理方式还是不错的，根据大小拍了个序然后根据原本的位置增加相同的子串，写起来也很快。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
struct ss
{
    int id,num;
    string s1;
}e[5];
int n,kl;
bool mycmp(ss a1,ss a2){return a1.num<a2.num;}
bool cmp(ss a1,ss a2){return a1.id<a2.id;}
int main()
{
    for(int i=1;i<=3;i++)cin>>e[i].num,e[i].id=i;
    cin>>n;
    sort(e+1,e+4,mycmp);
    if(e[1].num!=0)
        for(int i=1;i<=e[1].num;i++)
        {
            e[1].s1+='a';
            e[2].s1+='a';
            e[3].s1+='a';
        }
    //for(int i=1;i<=3;i++)cout<<e[i].s1<<' ';cout<<endl;
    e[2].num-=e[1].num;
    e[3].num-=e[1].num;
    if(e[2].id==3)kl=1;
    else kl=e[2].id+1;
    for(int i=1;i<=e[2].num;i++)
    {
        e[e[2].id].s1+='b';
        e[kl].s1+='b';
    }
    if(e[3].id==3)kl=1;
    else kl=e[3].id+1;
    for(int i=1;i<=e[3].num;i++)
    {
        e[e[3].id].s1+='c';
        e[kl].s1+='c';
    }
    for(int i=1;i<=3;i++)if(e[i].s1.size()>n){cout<<"NO"<<endl;return 0;}
    for(int i=1;i<=3;i++)
    {
        while(e[i].s1.size()<n)e[i].s1+=(char)('a'+5+i);
        cout<<e[i].s1<<endl;
    }
     
    return 0;
}

E

给你一棵树，这棵树上所有点都有一个点权，树的边权为点权的抑或值。现给出每个点的点权范围和边权的具体值，问你每个使点的点权满足关系的情况数是多少。
很妙的一题，首先是通过处理把点权用一个未知数表示，再考虑点权的范围给的限制。实际上是每个点点权范围和边权的抑或值的共有部分。题解使用了线段树来处理。是由于抑或的性质：一个区间抑或上一个数会得到多个连续的区间，其中每个连续的区间在原区间上对应的是线段树上的一段区间。（线段树的奇妙用法+1）
注意 我这里开了个结构体来存新得到的区间，区间数尽量开大一点（最坏可能是 ）

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<bits/stdc++.h>
using namespace std;
struct ss
{
	int w,l,r; 
}point[100010];
struct s1
{
	int y,v,next;
}e[1000010];
struct s2
{
	int id,num;
}Q[50000010];
int n,qkl=0,ans=0;
int Link[100010],kl=0,c[100010];
inline void insert(int xx,int yy,int vv)
{
	e[++kl].next=Link[xx];
	Link[xx]=kl;
	e[kl].y=yy;
	e[kl].v=vv;
}
inline void dfs(int now)
{
	for(int i=Link[now];i;i=e[i].next)
	{
		if(point[e[i].y].w!=-1)continue;
		point[e[i].y].w=point[now].w^e[i].v;
		dfs(e[i].y);
	}
}
inline void addqu(int ll,int rr,int bb,int ww)
{
	//cout<<ll<<' '<<rr<<' '<<bb<<' '<<ww<<endl;
	int jkl=((1<<30)-1)^((1<<bb)-1);
	ll&=jkl;rr&=jkl;ww&=jkl;
	//cout<<ll<<' '<<rr<<' '<<bb<<' '<<ww<<endl;
	Q[++qkl].num=(ll^ww);Q[qkl].id=1;
	Q[++qkl].num=(ll^ww)+(1<<bb);Q[qkl].id=2;
	//cout<<Q[qkl-1].num<<' '<<Q[qkl].num<<endl;
}
inline void find(int nowl,int nowr,int ceng,int ll,int rr,int ww)
{
	//cout<<nowl<<' '<<nowr<<' '<<endl;
	if(nowl>=ll&&nowr<=rr)
	{
		addqu(nowl,nowr,ceng,ww);
		return ;
	}
	//if(ll>nowr||rr<nowl)return ;
	int mid=(nowl+nowr)/2;
	if(ll<=mid)find(nowl,mid,ceng-1,ll,rr,ww);
	if(rr>mid)find(mid+1,nowr,ceng-1,ll,rr,ww);
}
bool mycmp(s2 a1,s2 a2){return a1.num<a2.num;}
int main()
{
	//freopen("a.out","w",stdout);
	//int jkl=(((1<<30)-1)^((1<<10)-1));//造一个前30-b位为1，后b位为0的数。
	//for(int i=jkl;i;i/=2)cout<<i%2;cout<<endl;
    cin>>n;
	for(int i=1;i<=n;i++)point[i].w=-1;
	for(int i=1;i<=n;i++)scanf("%d%d",&point[i].l,&point[i].r);
	for(int i=1,xx,yy,vv;i<n;i++)
	{
		scanf("%d%d%d",&xx,&yy,&vv);
		insert(xx,yy,vv);
		insert(yy,xx,vv);
	}
	point[1].w=0;
	dfs(1);
	//for(int i=1;i<=n;i++)printf("%d ",point[i].w);printf("\n");
	for(int i=1;i<=n;i++)find(0,((1<<30)-1),30,point[i].l,point[i].r,point[i].w);//,cout<<endl;
	//cout<<qkl<<endl;
	sort(Q+1,Q+qkl+1,mycmp);
	for(int i=1,lastnum=0,j=0;i<=qkl;i++)
	{
		if(Q[i].id==1)
		{
			j++;
			if(j==n)lastnum=Q[i].num;
		}
		else 
		{
			if(j==n)ans+=Q[i].num-lastnum;
			j--;
		}
	}
	cout<<ans<<endl;
	return 0;
}

F

一个博弈问题，给一个图，每次操作可以删一条边或者删一整颗树（不含环的强连通子块）。两人轮流操作问谁能赢。
对于第一种操作, 会使得边数 -1
对于第二种操作, 会使得点数 -k, 边数 -(k-1)
任何一种操作都会使得点数+边数的和减少一个奇数, 所以答案只跟 n+m 的奇偶性有关
（所以就是很水的签到）

我们当时的代码（逆十字的代码好nb啊） 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include< iostream >
#include< map >
using namespace std;
const int maxn = 1e6;
struct node{
	int to,next;	
}e[maxn];	//边集
int cnt;	//计数
int nums = 0;
int head[maxn],vis[maxn],pre[maxn];
int f[11000];
map< int,int> M;
int n,m;
int cntn=0;

int find(int x){
	return f[x]==x?x:f[x]=find(f[x]);
}
void addnode(int u,int v){	//加边(链式前向星)
	e[++cnt].to = v;
	e[cnt].next = head[u];
	head[u] = cnt;
}
void dfs(int x,int fa){		//dfs
	vis[x] = 1;
	for(int i = head[x];i;i=e[i].next){
		int y = e[i].to;	
		if(y==fa)	continue;	//如果是无向的 a-->b 的同时也有 b-->a,所以直接排除另外的一种情况
		if(vis[y]==0){			//如果没有访问就标记当前元素的前一个元素
			pre[y] = x;
			dfs(y,x);			//并且一直递归访问下去
		}else if(vis[y]==1){
			int temp = x;		
			int count = 1;
			while (temp!=y)		//找路径
			{
				count++;
				temp = pre[temp];
			}
			nums++;				//环数+1
		}
	}
	vis[x] = 2;
}
void init()
{
	cin>>n>>m;
	int u,v;
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		addnode(u,v);
		addnode(v,u);
		f[find(u)]=find(v);
	}
}
int main(){
	init();
	for(int i = 1;i <= n;i++)
		if(vis[i]==0)dfs(i,-1);
	for(int i=1;i<=n;i++) if(M[find(i)]==0){
		M[find(i)]=1;
		cntn++;
	}
	cntn+=nums;
	if(cntn%2==1)
		cout<<"Alice";
	else cout<<"Bob";
	return 0;
}

I

不再赘述，说的很清楚
开启传送门！

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
const int maxn=200010;
int a[maxn],c[maxn];
struct ss
{
	int v,index;
}node[maxn];
bool mycmp1(ss a1,ss a2){return a1.v<a2.v;}
int n;
void add(int i)
{
	while(i<=n)
	{
		c[i]++;
		i+=i&(-i);	
	}
}
long long sum(int i)
{
	long long res=0;
	while(i>0)
	{
		res+=c[i];
		i-=i&(-i);
	}
	return res;
}
int main()
{
	cin>>n;
	for(int i=1,kl;i<=n;i++)
	{
		scanf("%d",&kl);
		node[i].index=i;
		node[i].v=kl;
	}
	sort(node+1,node+1+n,mycmp1);
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		add(node[i].index);
		a[i]=i-sum(node[i].index); //得到之前有多少个比你大的数（逆序对）
		ans+=a[i];
	}
	for(int i=1;i<n;i++)
	{
		if(node[i].index>=node[i+1].index){ans--;i++;}
	}
	cout<<ans;
	return 0;
}

J

给你两个数列，让你用这两个数列构造一个n，m矩阵，求矩阵的最大平均子矩阵。
水（不对我不是说不拉签到的吗？哦原来是这场只过了签到啊好悲伤啊蛤蛤蛤）

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y;
int a[100010],amin=100010,b[100010],bmin=100010;
double sum[100010],ans=0;
inline bool checka(double now)
{
    for(int i=1;i<=n;++i)sum[i]=sum[i-1]+a[i]-now;
    double minv =0;
    for(int i=x;i<=n;++i)
	{
        minv=min(minv,sum[i-x]);
        if(sum[i]>=minv)return true;
    }
    return false;
}
inline bool checkb(double now)
{
    for(int i=1;i<=m;++i)sum[i]=sum[i-1]+b[i]-now;
    double minv =0;
    for(int i=y;i<=m;++i)
	{
        minv=min(minv,sum[i-y]);
        if(sum[i]>=minv)return true;
    }
    return false;
}
int main()
{
	cin>>n>>m>>x>>y;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),amin=max(amin,a[i]);
	for(int i=1;i<=m;i++)scanf("%d",&b[i]),bmin=max(bmin,b[i]);
	double l = 0, r = amin;
	while(r-l>1e-9)
	{
        double mid = (l + r) / 2;
        if(checka(mid)) l = mid;
        else r = mid;
    }
	ans+=(l+r)/2;
	//cout<<ans<<endl;
	l = 0, r = bmin;
	while(r-l>1e-9)
	{
        double mid = (l + r) / 2;
		//cout<<mid<<' '<<checkb(mid)<<endl;
        if(checkb(mid)) l = mid;
        else r = mid;
    }
	ans+=(l+r)/2;
	printf("%0.10lf\n",ans);
 	return 0;
}
2021 比赛 暑期牛客高校训练赛
大学 牛客 icpc

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！