The 18th Zhejiang Provincial Collegiate Programming Contest

参考wp：https://blog.csdn.net/qq_33957603/article/details/124156811

补题链接：https://codeforces.com/gym/103055

A. League of Legends

签到题

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	long long blue=0,red=0;
	for (int i=0;i<5;i++){
		long long x;
		cin>>x;
		blue+=x;
	}
	for (int i=0;i<5;i++){
		long long x;
		cin>>x;
		red+=x;
	}
	if (blue>=red){
		cout<<"Blue";
	}
	else{
		cout<<"Red";
	}
}

C. Cube

题目大意：

给出八个点，求这八个点能否构成正方体

思路

枚举所有的边，数量满足12/12/4（边长，面对角线，体对角线），且长度平方满足1：2：3，即可证明为立方体。

#include<bits/stdc++.h>
using namespace std;
long long d[100];
int x[9],y[9],z[9];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		for(int i = 1;i<=8;i++)
		{
			cin>>x[i]>>y[i]>>z[i];
		}
 
		int k = 0;
		for(int i = 1;i<=8;i++)
		{
			for(int j = i+1;j<=8;j++)
			{
				d[++k] = (x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i])+(z[j]-z[i])*(z[j]-z[i]);
//				cout << d[k-1] <<endl;
			}
		}
		sort(d+1,d+k+1);
//		for(int i = 1;i<=k;i++)
//		{
//			cout<<d[i]<<" ";
//			//if(i%7==0)
//			//cout<<endl;
//		}
		if(d[1]==0)
		{
			cout<<"NO"<<endl;
		}else if(d[1]==d[12]&&d[13]==d[24]&&d[25]==d[28]&&d[13]==2*d[1]&&d[25]==3*d[1])
		{
			cout<<"YES"<<endl;
		}else
		{
			cout<<"NO"<<endl;
		}
		
	} 
	return 0;
}

F. Fair Distribution

题目大意：

有n个机器人和m个能量块，有一个枪手能够有两种操作，一是销毁一个机器人，二是创造一个能量块。每次操作都会有一个代价，求最小的代价能够使得能量块的数量能够被机器人的数量整除（也就是均分）

思路：

• 当n>=m时，代价为n-m。要么把机器人的数量减少到m，或者把能量块的数量加到n。

• 当n<m时，讨论机器人的数量在1~m中的每种可能。在1~m中的每个数只有m%i==0和m%i!=0两种情况，因此分类讨论：

• 当m%i==0时，说明m整除i，可以把n减少到i为一种代价。因为一个数若整除另一个数，那么m%(m/i)也是等于0的，所以可以再讨论一种情况当n>=m/i时，可以把n变成m/i.

• 当m%i!=0时，说明m不能整除i，但是（m/i+1）i是可以整除i的，当n>=i时，能量块数量需要从m变到（m/i+1)i，代价为|m%i-i|，那么机器人数量从n变到i代价为n-i，此时（m/i+1)*i%i是等于零的。当n>=m/i+1时，与上述一致。

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		ll n, m;
		cin >> n >> m;
		if (n >= m)
			cout << n - m << endl;
		else
		{
			ll s = sqrt(m);
			ll t = 1e8 + 10;
			for (int i = 1; i <= s; i++)
			{
				if (m % i == 0)
				{
					if (n >= i)
					{
						t = min(t, abs(n - i));
					}
					if (n >= m / i)
					{
						t = min(t, abs(n - m / i));
					}
				}
				else
				{
					if (n >= i)
						t = min(t, n - i + abs(m % i - i));
					if (n >= m / i + 1)
						t = min(t, n - m / i -1 + abs(m/i+1-m%(m/i+1)));
				}

			}		cout << t << endl;
		}

	}
	return 0;
}

G Wall Game

题目大意：

n组输入，每组输入三个数字，第一个数字代表操作类型， 第二三个数字代表坐标。
操作1：在整个图上添加点，并和相邻的点联通
操作2：查询这个点的整个联通的快，输出整个块的边的数量（点与点间边将被忽略）

思路：

并查集+离散化

推导发现：

1. 若只有一个点：边=6
2. 若多个点相连：n个点有x条重边，边数=6n-2x

map mp;不能使用unordered_map，因为unordered_map是基于离散化的，对node节点要提供离散化函数。

#include <iostream>
#include <map>
using namespace std;
typedef long long LL;
const int N = 5e5 +10; 

int p[N];
int siz[N] ;      // 记录集合大小
int rpp[N];      // 记录集合内部边数
int idx = 0;    // 并查集索引
int n,m;

// 方向数组
int dx[] = {1,1,0,0,-1,-1};
int dy[] = {0,-1,-1,1,0,1};
int find(int x)
{
    if(p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

struct node {
    int x, y;
    node(){} node(int x, int y) : x(x), y(y) {} //为arr提供默认构造函数
    bool operator < (const node& b) const {  // 为map提供比较函数
        if (x == b.x) {
            return y < b.y;
        } else {
            return x < b.x;
        }
    }
} arr[N];

map<node,int> mp;       //并查集索引

void init()
{
    for(int i = 1; i < N; i++)
    {
        p[i] = i;
        siz[i] = 1;
    }
}

void merge(int x, int y)
{
    x = find(x);
    y = find(y);
    if(x!=y)
    {
        if(siz[x] < siz[y])
            swap(x,y);
        p[y] = x;
        siz[x] += siz[y];
        rpp[x] += rpp[y] + 1; // 合并时增加1条内部边
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);			
    cin >> n;
    init();
    int op,x,y;
    while(n--) {
        cin >> op >> x >> y;
        if(op == 1)
        {
            node nd = node(x,y);
            if (!mp.count(nd)) {  // 避免重复添加
                mp[nd] = ++idx;
                for(int i = 0; i < 6; i++)
                {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    node ndd = node(nx,ny);
                    if(mp.count(ndd))
                    {
                        if (find(mp[ndd]) != find(mp[nd])) {
                            merge(mp[ndd], mp[nd]); // 合并
                        } else {
                            rpp[find(mp[nd])]++;    //与同一集合内点相邻
                        }
                    }
                }
            }
        }
        else if(op == 2)
        {
            node nd = node(x,y);
            
            if(mp.count(nd))
            {
                int root = find(mp[nd]);
                cout << siz[root]*6 - 2*rpp[root] << endl;
            }
            else
            {
                cout << 6 << endl;
            }
        }

    }
}

J. Grammy and Jewelry

题目大意：

给定一个权值全为1（消耗1单位的时间）的无向图，n个点，m条边，除去第一个顶点外其余顶点均有珠宝。

从起点出发，拿起和放下珠宝不占时间，每次只能携带一件珠宝，当珠宝放回七点即获得该珠宝。

每个点的珠宝是无限的。

求x在[1,T]中的每个时间段内能获得的最大珠宝数。

思路

用迪杰斯特拉（或BFS）求最短路径，然后用完全背包问题求解

v = 路径长度*2（往返）

w = 该点珠宝数

#include<bits/stdc++.h>
using namespace std;
int n,m,T;
 
 
const int N = 6100;
int h[N],ne[N],e[N],idx;
int dist[N];
int st[N];
 
int jew[N]; 
 
int v[N],w[N],f[N];
 
 
void add(int a, int b)
{
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx++;
}
 
void Dijkstra()
{
	memset(dist,0x3f,sizeof(dist));
	dist[1] = 0;
	queue<int> q;
	q.push(1);
	st[1] = 1;
	while(q.size())
	{
		int t = q.front();
		q.pop();
		for(int i = h[t]; i!=-1;i = ne[i])
		{
			int j = e[i];
			if(!st[j])
			{
				dist[j] = dist[t] + 1;
				q.push(j);
				st[j] = 1;
			}
		}
	}
}
 
 
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(h,-1, sizeof h);
	cin >>n >>m >>T;
 
	for(int i = 2; i<=n;i++)
	{
		cin >> jew[i];
	}
	for(int j = 0;j<m;j++)
	{
		int a,b;
		cin >> a >>b;
		add(a,b);
		add(b,a); 
	}
	Dijkstra();
//	for(int i = 1; i<=n;i++)
//	{
//		cout <<dist[i] <<endl;
//	}
 
	
	for(int i = 2; i<=n;i++)
	{
		v[i] = dist[i]*2;
		w[i] = jew[i];
//		cout << v[i] << " " <<w[i] <<endl;
	}
	for(int i = 1; i<=n;i++)
	{
		for(int j = v[i]; j<=T;j++)
		{
			f[j] = max(f[j], f[j-v[i]] +w[i]);
		}
	}
	for(int i = 1; i<=T;i++)
	{
		cout <<f[i] <<" ";
	}
	
	
}

L String Freshman

题目大意：

给出一个错误的kmp算法，问字符串T在匹配的时候答案是否与正确的kmp算法一致

思路

该kmp算法在每次匹配后都会回到字符串开头重新匹配，而正确的kmp算法应该是跳转到next数组（到当前位置为止，前缀和后缀的最长公共元素长度）里。

因此有字符和第一个字符相等（不会跳转到被匹配的字符串开头）即为错误。

M. Game Theory

题目大意：

老师和学生互相给对方打分（需要从自己有的分数里扣），范围在[1,20]，假设老师打了x，学生打了y。如果x>y学生多给老师10分，反之老师多给学生10分。
问如果老师随机出值，每个学生可以自己选择值，面对n个学生的情况下（对每个学生都是独立情况）老师的期望得分是多少。

思路

通过代码计算期望，得出答案恒为0

#include<bits/stdc++.h>
using namespace std;
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	double max=0,x=0;
	
	for(int y = 1; y <=20;y++)
	{
		double tot = 0;
		for(int x = 1; x<=20;x++)
		{
			double xue = 0;
			double lao = 0;
			xue += x;
            lao -= x;
            xue -= y;
			lao += y;
			if(x>y)
			{
				xue-=10;
				lao+=10;
			}
			if(x<y)
			{
				xue+=10;
				lao-=10;
			}
			tot+=lao; 
		}
		cout << tot;
		cout <<endl;
	}
 
	printf("%.4f",0);
}