2021牛客高校暑假训练赛三

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

防止出现上次比赛的睡过，这次定了五个闹钟，还专门10点定了外卖，11点坐到机房准备开赛。

比赛过程

但是没什么用（好悲伤啊蛤蛤蛤），比赛打的还是稀烂。
开赛前仅剩的一个队友给我说他回家了. . .
为啥每次打比赛都在单挑. . .
（熟悉的剧情。
开场先看了A看了一会儿（谁能想到4minA的人是Final爷啊！）。无果，发现J开始有些人过了于是去看J，感觉J是个组合数学上的例题但是忘了. . .看到B也有人过于是去看了B，这不是原题吗？我依稀记得正解是并查集。马上开码。样例本地过了但是在牛客上总是编出错误的结果(我后来才知道是数组开太大了牛客网页编译器炸了)。当时开始怀疑是不是自己记错了，于是去求证了一下。
HS也在单挑，不过他太强了3h过三题
无果，换了种写法，这次总算结果一致了，但还是Wa。
事后诸葛亮如我QAQ
然后放弃写B，开始看E（主要是跟着HS的榜看题），发现E是个找规律题。打了个10000以内的表，并且证实了下确有其实后开始继续打大表。然后发现了了比较优秀的性质，预处理出所有需要的数对，然后每次输入n二分查找。摆脱了坐一下午的尴尬境地（果然技能全点在找规律上）。
之后大概还剩不到1h的时间，本来应该再看一下F的，（因为看上去很水并且很多人过，赛后也证实了是道水题）。但是没有精力了. . .准备吃饭然后等题解。

总结

队友还是蛮重要的. . .一人坚持不了整场奋斗在一线（打代码）。需要看一遍所有题目（有队友的话就好说）。在B上消耗时间太多了（虽然是做过的但是一直改不出来，题目也不算水所以实际上阻碍很大）。感觉B是银牌水准的题目，E，J都是铜牌水题（二级签到？）。重点还是在补题以及练习上。暑假大概之后的一段时间都会留在实验室，希望能多学一些东西。

题目详情

补题不补签到了，费时间又没啥用

B

给你个权值矩阵，你可以随便填点，假如某一矩形三点都已经填好呢么第四点会自动填好，每次填点消耗权值。问你消耗的最小权值。
cf原题，用最小生成说或者并查集啥的都能乱搞。（做过的考场上还没做出来的你是屑）

代码 
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
#include<bits/stdc++.h>
using namespace std;
long long n,m,a,b,c,d,p;
long long A[25000010];
int Fa[100010];
vector<int>A1[100010],A2[100010];
long long mn,kl=0,sum=0;
inline int Find(int yu)
{
	if(Fa[yu]==yu)return yu;
	return Fa[yu]=Find(Fa[yu]);
}
int main()
{
	cin>>n>>m>>a>>b>>c>>d>>p;
	mn=m*n;
	A[0]=a;
    for(int i=1;i<=m+n;i++)Fa[i]=i;
	for(int i=1;i<=mn+3;i++)A[i]=(A[i-1]*A[i-1]*b+A[i-1]*c+d)%p;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			A1[A[m*(i-1)+j]].push_back(i);
            A2[A[m*(i-1)+j]].push_back(j);
			//cout<<e[kl].vv<<' ';
		}//cout<<endl;
	}
	for(int i=0;i<p;i++)
        for(int j=0,Farow,Farange;j<A1[i].size();j++)
		{
            Farow=Find(A1[i][j]);Farange=Find(A2[i][j]+n);
            if(Farow==Farange)continue;
            sum+=i;
            Fa[Farange]=Farow;
        }
	cout<<sum<<endl;
 	return 0;
}

E

让你找满足他的条件的数对数目
我是找规律，正解是用韦达定理推。

代码 
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
#include<bits/stdc++.h>
using namespace std;
long long maxx=1e18;
struct ss
{
	unsigned long long a,b;
}e[2100000];
unsigned long long kl,T,lmin,lmax,l1,l2,n;
int l,r,mid,yu;
bool mycmp(ss a1,ss a2){return a1.b<a2.b;}
void init()
{
	e[++kl].a=1;e[kl].b=1;
	for(unsigned long long i=2;i<=1000003;i++)
	{
		lmin=i;lmax=i*i*i;
		e[++kl].a=lmin;e[kl].b=lmax;
		while(lmax<=maxx)
		{
			//if(lmax==18446744073708560383ull/)break;
			if(lmax>maxx/i)break;
			if(lmax>maxx/(i*i))break;
			l1=lmax;l2=lmax*i*i-lmin;
			lmin=l1;lmax=l2;
			e[++kl].a=lmin;e[kl].b=lmax;
		}
	}
	sort(e+1,e+kl+1,mycmp);
	//for(int i=1;i<=100;i++)cout<<e[i].a<<' '<<e[i].b<<endl;
	//cout<<kl<<endl;
}
int main()
{
	init();
	cin>>T;
	while(T--)
	{
		scanf("%llu",&n);
		l=1,r=kl;mid=(l+r)/2;
		while(l+1<r)
		{
			mid=(l+r)/2;
			if(e[mid].b>n)r=mid;
			else l=mid;
		}
		for(yu=l-2;yu<=r+2;yu++)
			if(e[yu].b>n)break;
		printf("%d\n",yu-1);
	}
 	return 0;
}

F

让你用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
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-5;
long long n,sum=0;
double m;
int i[10];
int a[10010],b[10010],c[10010],d[10010],kl=0,kl1=0;
int flag=0;
char ch1[10],ch2[10]={'+','-','*','/'};
struct ss
{
	int a1,a2,a3,a4,a5;
}e[1000010];
void shuchu(){cout<<i[1]<<ch1[1]<<i[2]<<ch1[2]<<i[3]<<ch1[3]<<i[4]<<' '<<flag<<endl;}
inline void cun()
{
	int i1=i[1],i2=i[2],i3=i[3],i4=i[4];
	sort(i+1,i+5);
	e[++kl].a1=i[1];
	e[kl].a2=i[2];
	e[kl].a3=i[3];
	e[kl].a4=i[4];
	e[kl].a5=flag;
	i[1]=i1,i[2]=i2,i[3]=i3,i[4]=i4;
}
inline double ji(double num1,double num2,char ch)
{
	//flag=0;
	double ans,hj;
	if(ch=='+')ans=num1+num2;
	if(ch=='-')ans=num1-num2;
	if(ch=='*')ans=num1*num2;
	if(ch=='/'&&num2-0>=eps)ans=num1/num2;
	if(ch=='/'&&num2-0.0<=eps)return -30000;
	int aa=ans;
	if((double)(ans*1.0-(double)aa*1.0)<0.0)hj=0.0-(double)(ans*1.0-(double)aa*1.0);
	else hj=(double)(ans*1.0-(double)aa*1.0);
	//if(i[1]==1&&i[2]==1&&i[3]==1&&i[4]==12)cout<<hj<<' '<<ans<<endl;
	if(hj<eps)flag=-1;
	return ans;
}
inline bool Ji(double num1,double num2,char ch)
{
	double ans,hj;
	if(ch=='+')ans=num1+num2;
	if(ch=='-')ans=num1-num2;
	if(ch=='*')ans=num1*num2;
	if(ch=='/'&&num2-0>=eps)ans=num1/num2;
	if(ch=='/'&&num2-0.0<=eps)return 0;
	if((double)(ans-(double)m)<0.0)hj=0.0-(double)(ans-(double)m);
	else hj=(double)(ans-(double)m);
	/*if(i[1]==8&&i[2]==3&&i[3]==8&&i[4]==3)
	{
		printf("%0.20lf %lf\n",hj,m);
		shuchu();
		if(hj<eps)cout<<"^&%&$%^"<<endl;
	}*/
	if(hj<eps)return 1;
	return 0;
}
inline void dfs(int now)
{
	if(now==4)
	{
		flag=0;
		if(Ji(ji(ji(i[1],i[2],ch1[1]),i[3],ch1[2]),i[4],ch1[3])){flag=((flag==-1)?(-1):1);cun();}flag=0;
		if(Ji(ji(i[1],ji(i[2],i[3],ch1[2]),ch1[1]),i[4],ch1[3])){flag=((flag==-1)?(-1):1);cun();}flag=0;
		if(Ji(i[1],ji(ji(i[2],i[3],ch1[2]),i[4],ch1[3]),ch1[1])){flag=((flag==-1)?(-1):1);cun();}flag=0;
		/*if(i[1]==8&&i[2]==3&&i[3]==8&&i[4]==3)
		{
			printf("%0.20lf %lf\n",Ji(i[1],ji(i[2],ji(i[3],i[4],ch1[3]),ch1[2]),ch1[1]),m);
			shuchu();
			double ans=Ji(i[1],ji(i[2],ji(i[3],i[4],ch1[3]),ch1[2]),ch1[1]),hj;
			if((double)(ans*1.0-(double)m*1.0)<0.0)hj=0.0-(double)(ans*1.0-(double)m*1.0);
			else hj=(double)(ans*1.0-(double)m*1.0);
			if(hj<eps)
				cout<<"^&%&$%^"<<endl;
		}flag=0;*/
		if(Ji(i[1],ji(i[2],ji(i[3],i[4],ch1[3]),ch1[2]),ch1[1])){flag=((flag==-1)?(-1):1);cun();}flag=0;
		if(Ji(ji(i[1],i[2],ch1[1]),ji(i[3],i[4],ch1[3]),ch1[2])){flag=((flag==-1)?(-1):1);cun();}flag=0;
		return;
	}
	for(int i=0;i<4;i++)
	{
		ch1[now]=ch2[i];
		dfs(now+1);
	}
}
inline bool mycmp(ss s1,ss s2)
{
	if(s1.a1==s2.a1)
	{
		if(s1.a2==s2.a2)
		{
			if(s1.a3==s2.a3)return s1.a4<s2.a4;
			return s1.a3<s2.a3;
		}
		return s1.a2<s2.a2;
	}
	return s1.a1<s2.a1;
}
int main()
{
	cin>>n>>m;
    if(n<4){cout<<0<<endl;return 0;}
	for(i[1]=1;i[1]<=13;i[1]++)
	{
		for(i[2]=1;i[2]<=13;i[2]++)
		{
			for(i[3]=1;i[3]<=13;i[3]++)
			{
				for(i[4]=1;i[4]<=13;i[4]++)
				{
					flag=0;
					dfs(1);
				}
			}
		}
	}
	sort(e+1,e+kl+1,mycmp);
	for(int i=1,fl=0;i<=kl;i++)
	{
		fl=0;
		while(e[i].a1==e[i+1].a1&&e[i].a2==e[i+1].a2&&e[i].a3==e[i+1].a3&&e[i].a4==e[i+1].a4)
		{
			if(e[i].a5==-1)fl=1;
			if(e[i].a1==e[i+1].a1&&e[i].a2==e[i+1].a2&&e[i].a3==e[i+1].a3&&e[i].a4==e[i+1].a4)i++;
			else break;
		}
		if(fl==0&&e[i].a5==1)kl1++;
	}
	cout<<kl1<<endl;
	for(int i=1,fl=0;i<=kl;i++)
	{
		fl=0;
		while(e[i].a1==e[i+1].a1&&e[i].a2==e[i+1].a2&&e[i].a3==e[i+1].a3&&e[i].a4==e[i+1].a4)
		{
			if(e[i].a5==-1)fl=1;
			if(e[i].a1==e[i+1].a1&&e[i].a2==e[i+1].a2&&e[i].a3==e[i+1].a3&&e[i].a4==e[i+1].a4)i++;
			else break;
		}
		if(fl==0&&e[i].a5==1)printf("%d %d %d %d\n",e[i].a1,e[i].a2,e[i].a3,e[i].a4);
	}
 	return 0;
}

J

给你边权的构造函数，让你判断完全图的同色三角形数目
鸽巢原理. . .通过“异色角”的概念得出。
一个异色三角形势必拥有两个异色角一个同色角。所以总三角形个数减去异色角个数除以二就行了。

代码 
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
#include<bits/stdc++.h>
using namespace std;
namespace GenHelper
{
    unsigned z1,z2,z3,z4,b,u;
    unsigned get()
    {
        b=((z1<<6)^z1)>>13;
        z1=((z1&4294967294U)<<18)^b;
        b=((z2<<2)^z2)>>27;
        z2=((z2&4294967288U)<<2)^b;
        b=((z3<<13)^z3)>>21;
        z3=((z3&4294967280U)<<7)^b;
        b=((z4<<3)^z4)>>12;
        z4=((z4&4294967168U)<<13)^b;
        return (z1^z2^z3^z4);
    }
    bool read() {
      while (!u) u = get();
      bool res = u & 1;
      u >>= 1; return res;
    }
    void srand(int x)
    {
        z1=x;
        z2=(~x)^0x233333333U;
        z3=x^0x1234598766U;
        z4=(~x)+51;
      	u = 0;
    }
}
using namespace GenHelper;
bool edge[8005][8005];
long long num1=0,num0=0,ans=0,num=0;
int main()
{
    int n, seed;
    cin >> n >> seed;
    srand(seed);
    for (int i = 0; i < n; i++)
    	for (int j = i + 1; j < n; j++)
			edge[j][i] = edge[i][j] = read();
	for(int i=0;i<n;i++)
	{
		num1=0;
		for(int j=0;j<=n;j++)
			if(edge[i][j]==1)
				num1++;
		num+=num1*(n-num1-1);
	}
	ans=(long long)(n-2)*(n-1)*n/6;
	//cout<<ans<<endl;
	ans-=num/2;
	cout<<ans<<endl;
 	return 0;
}
2021 比赛 暑期牛客高校训练赛
大学 牛客 icpc

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