2021牛客高校暑假训练赛四

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

上次打的太拉了，这次稍微好一点。

比赛过程

开场，找队友，开赛。
这次不顺序看题，直接从后往前看，大致扫了一遍J，发现由他的构造方式是只需要分别求出两个序列的最大平均值连续序列即可。速度写了一发过样例直接交！
然后Wa了. . .便又看了一遍题目，没发现啥问题啊，昨天晚上刚被精度卡了通宵，不会是精度问题吧。便改小了二分的精度。还是Wa. . .两发罚时。又检查了一遍，发现输出是cout，默认保留6位小数. . .给我把高位的四舍五入了。改了之后就过了。
看了眼队友状态在写F。我便选了过的人比较多的I来看。由于I的数列就是1~n的数组成，呢么通过+0+1能减少逆序对的只有i+1在i的前面的情况。也就是说从后往前扫一遍看i+1是不是在i的前面（假如i可以变），呢么就让i+1.（其实这个算法好像是比较贪心的搞法，正解是找最长的递增链，原理差不多但是这样写简单许多）。交上去1A. . .队友还卡在F，并且发现之前题目读错了. . .和他一起理了理思路后去看c了。
C是个构造题，没啥思想问题就是可能处理上会比较麻烦，我在这儿被数据为0的cornercase卡了一下，测了几个小数据后改了改代码很快就过了。然后去帮他看F（队友的充电器忘在宿舍了. . .电脑打了一半没电了）
F实际上是最水的签到，（所以肯定是他想麻烦了）。我复制他原本Wa的代码。问了下他几个数组含义，发现他把所有强连通区块和环的数目都处理了出来（这是签到. ..）然后根据F的性质，觉得他可能是判断条件写错了，改了下，交上去过了。
（队友实惨）
坐完四题后是1h55min. . .然后就干坐这没有进展。sw做题轨迹指路E但是真的对树和抑或很感冒就没准备冲，之后一直觉得B可以写码了很久（1.5h），但是没码出来. . .

总结

不要沉迷与水题了. . .这样下去是没有进展的. . .之后的练习可能会试着冲一下。还有记得补题。以及STL要多用。还有一些模板需要add一下，不至于每次需要时找不到还得baidu。以及，以后所有涉及到小数的题目统一计算和输出保留10位小数吧，呗这玩意坑麻了。

题目详情

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 协议 ，转载请注明出处！