18thZJCPC

A - League of Legends

格莱美喜欢玩世界著名的英雄联盟游戏。
在最新版本中，有一个特殊的规则供玩家选择玩。根据此规则, 10 玩家将被分为红队和蓝队。每支队伍由 5 名玩家组成，每个玩家都有一个初始生命值。如果一支队伍中的所有 5 玩家均没有正HP值，则该队伍将输掉这场比赛。每回合，队伍可以选择一名球员并减少他的生命值 1。蓝队首先开始。
现在格莱美想知道两支球队是否都按照最优策略比赛，哪支球队会赢得比赛。
枚举，比大小，平局蓝队赢

C - Cube

给你三维空间中的八个点，请检查它们是否可以组成一个立方体。
立方体是正六面体，由六个正方形面包围，每个顶点有三个相交点。
T≤100组数据。
两两枚举点对之间的距离，根据对角线，体对角线，面对角线，棱的长度和数量关系判断。

cpp

#include <bits/stdc++.h>
using namespace std;
int t,x[8],y[8],z[8];
int main(){
    cin>>t;
    while (t--){
        for (int i=0;i<8;++i)cin>>x[i]>>y[i]>>z[i];
        bool tr= true;
        for (int h=0;h<8;++h){
            map<int,int>mp;
            for (int i=0;i<8;++i){
               if(i!=h){
                   int q=0;
                   q+=abs(x[h]-x[i])*abs(x[h]-x[i]);
                   q+=abs(y[h]-y[i])*abs(y[h]-y[i]);
                   q+=abs(z[h]-z[i])*abs(z[h]-z[i]);
                   mp[q]++;
               }
            }
            if(mp.size()!=3){
                tr= false;
                break;
            }
            else{
                int q[3],w[3],T=0;
                for(auto i:mp){
                    q[T]=i.first;
                    w[T]=i.second;
                    T++;
                }
                if(q[0]*2==q[1]&&q[0]*3==q[2]&&w[0]==3&&w[1]==3)continue;
                else {
                    tr= false;
                    break;
                }
            }
        }
        if(tr)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

M - Game Theory

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

因为这道题给了样例，发现是班上有一个同学的情况下老师的期望得分是0。
所以我们充分发扬人类的智慧大胆猜测这个不管来多少人都是0。
仔细想一想好像是对的，因为根据期望有线性性质，对于E(X1+X2+……+Xn) = E(X1)+E(X2)+……+E(Xn)
又因为这个是独立重复实验，学生之间的选择互不干扰。
所以E(X1+X2+……+Xn) = n*E(x1) = 0
至于为什么有一个同学的时候期望是0，这个写个程序枚举一下答案就是0，或者根据对称性乱搞一下应该也能分析出。
vp和队友开麦打的，当时就一个输出0敲上去发现真的对了就觉得离谱感觉被诈骗了。

L - String Freshman

给出一个字符匹配的假算法，和一个字符串T，要你找到一个字符串S是得T在匹配的时候使其返回值出错。
假算法：

cpp

int Find_Answer () {
	int j = 1, ans = 0;
	for ( int i = 1; i <= n ; i ++) {
		if (S[i] != T[j]) j = 1;
		if (S[i] == T[j]) j++;
		if (j > m) {
			ans ++;
			j = 1;
		}
	}
	return ans;
}

vp的时候看代码长得像kmp就往kmp上想了，因为这个在失配的时候直接跳回到原串的第一个位置，而kmp算法是跳到next数组的位置，所以只要有一个位置不是跳到第一个位置，也就是说只要有一个和第一个位置上的字符一样的，那么就是无解。赛时代码写的很乱，其实就判断是否有字符和第一个字符相等即可，有的话就输出false。

cpp

#include <bits/stdc++.h>
using namespace std;
int m,a[100001];
string s;
bool kmp(){
    int i=1,len=0;
    while (i<m){
        if(s[i]==s[len]){
            return false;
        }
        else{
            if(len>0)len=a[len-1];
            else i++;
        }
    }
    return true;
}
int main(){
    cin>>m>>s;
    kmp();
    if(m==1)cout<<"Correct"<<endl;
    else{
        if(!kmp())cout<<"Wrong Answer"<<endl;
        else cout<<"Correct"<<endl;
    }
    return 0;
}

J - Grammy and Jewelry

有一个连通无向图，其中有 $n$ 个顶点和 $m$ 条边。顶点的索引从 $1$ 到 $n$ 。顶点 $i$ （ $2 \leq i \leq n$ ）中有无限多的珠宝，每个珠宝的价值都是 $a_{i}$ 。格莱美从点 $1$ 开始。经过每条边需要消耗 $1$ 个单位的时间。她可以在顶点 $i$ 拿起一件首饰，并在顶点 $1$ 放下。拿起珠宝和放下珠宝可以瞬间完成。此外，她在任何时候最多只能携带一件首饰。当她在顶点 $1$ 放下一件价值为 $x$ 的首饰时，她会得到它的价值。现在，对于 $1$ 和 $T$ （含）之间的每个 $k$ ，她想知道在 $k$ 个单位的时间内她能得到的最大价值是多少。

先跑一遍最短路然后在点与点之间dp就行。将其乘2存在cost数组中表示返回要花的时间。
由于边长都是1，可以直接跑bfs
令dp[i]表示第i个时间内能拿到的最大值。然后dp[i]=max(dp[i],dp[i-cost[j]]+a[j]);这样转移就可以了。

cpp

void solve(){
	int n,m,T;
	cin>>n>>m>>T;
	
	int a[n+1];
	a[1]=0;
	per(i,2,n)cin>>a[i];
	
	vector<int> e[n+1];
	per(i,1,m){
		int x,y;
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	
	int cost[n+1];//到达每个节点的最短时间
	
	queue<array<int,2>>q;
	q.push({1,0});
	bitset<3005>vis;
	vis[1]=true;
	while(q.size()){
		array<int,2>now=q.front();
		q.pop();
		
		for(auto nxt:e[now[0]]){
			if(!vis[nxt]){
				vis[nxt]=true;
				q.push({nxt,now[1]+1});
				cost[nxt]=now[1]+1;
			}
		}
	}
	per(i,2,n)cost[i]=cost[i]*2;
	
	//定义dp[T]为使用时间T可以获得的最大价值
	
	int dp[T+1];
	per(i,0,T)dp[i]=0;
	
	//拿a[i]价值需要付出 cost[i]时间
	
	//显然从前面转移
	per(i,1,T){
		per(j,2,n){
			if(i-cost[j]>=0)
				dp[i]=max(dp[i],dp[i-cost[j]]+a[j]);
		}
	}
	
	per(i,1,T)cout<<dp[i]<<" ";
}

F - Fair Distribution

梦幻王国里有 $n$ 个机器人和 $m$ 根能量棒。国王 DreamGrid 正试图公平分配能量棒。当且仅当能量棒的数量是机器人数量的倍数时，才存在公平分配。
DreamGrid 唯一的工具是一把威力强大的激光枪。每次打开激光枪，他都可以做以下两件事中的一件：

创建一个新的能量条。
摧毁一个机器人。

为了避免机器人灭绝，禁止摧毁所有 $n$ 机器人。打开一次激光枪需要一美元。要求你找出公平分配的最小成本。

有多个测试用例。输入的第一行包含一个整数 $T$ ( $1 \leq T \leq 1 000$ )，表示测试用例的数量。对于每个测试用例
唯一一行包含两个整数 $n$ 和 $m$ （ $1 \leq n, m \leq 10^{8}$ ）。表示机器人和能量棒的初始数量。
对每个测试用例输出一行，其中包含一个整数，表示获得公平分配的最小成本。

一开始看范围想的是带根号的做法，想过根号分治但是后面想了半天没想到是整除分块，后面用扩欧解方程搓了半天结果失败了。
题目的大概意思是(m+x) % (n-y) == 0;x,y为正数，且n-y要求大于0，求x+y最小值

正解是整除分块。
分类讨论：
对于n>m的情况，答案显然为n − m，即m%n == m,此时只能把n变到和m一样大小，或者是m变到和n一样大小。
对于n<m的情况，考虑暴力做法，枚举n减小的次数，比如减小了y次，那么对于m而言想要被整除，需要变成

⌈ \frac{m}{n - y} ⌉ * (n - y)

所以总代价是

y + ⌈ \frac{m}{n - y} ⌉ * (n - y) - m = ⌈ \frac{m}{n - y} - 1 ⌉ * (n - y) + n - m

令n-y = i,枚举i所有的可能，但是暴力枚举会超时。
因为这个带有一个整除函数，联想到整除分块
可以将其转换为下取整，整理得

⌈ \frac{m - 1}{i} ⌉ * i + n - m

所以对其用分块算法即可

cpp

void solve() {
	int n, m;  cin>>n>>m;
	if(n > m)cout<<n-m<<"\n";
	else{
		int ans = 1e9+10;
		for(int l = 1, r; l <= n; l = r+1){
			int k = m-1;
			r = min(n, k/(k/l));
			int res = k/l*l;
			ans = min(ans,res);
		}
		cout<<ans+n-m<<endl;
	}
}

有点离谱vp前几天刚学的直接就没想到

G - Wall Game

给了一个图，蜂巢结构
对于此二维的图，有n次操作：
每次操作有两种：
op == 1，输入一个点（x，y），占领（ x , y )。
op == 2，查询点（x，y）所在连通块的的外围边的数量。比如(0,0)构成的外围边是6，(0,0),(0,1)构成的外围边是10。
保证op == 2的时候的点是被占领的，op == 1的时候点是没有被占领的。
并查集求联通块即可。维护当前联通块的点数以及重边的个数，回答的时候就是联通块中点数6 - 重边个数2.

cpp

int dx[6] = {-1,0,1,1,0,-1};
int dy[6] = {0,-1,-1,0,1,1};

void solve() {
	int n,cnt = 0;
	cin>>n;
	DSU comb(n);
	vector<int> edge(n+1),vex(n+1,1);
	map<PII,int> h;
	
	for(int i = 1,x,y,op;i<=n;++i){
		cin>>op>>x>>y;
		if(op == 1){
			int res = 0;
			h[{x,y}] = ++cnt;
			for(int j = 0;j<6;++j){
				int cx = x + dx[j],cy = y + dy[j];
				if(h.count({cx,cy})){
					res++;
					int x1 = comb.find(cnt);
					int x2 = comb.find(h[{cx,cy}]);
					if(x1 ^ x2){
						comb.par[x2] = x1;
						vex[x1] += vex[x2];
						edge[x1] += edge[x2];
					}
				}
			}
			edge[comb.find(cnt)] += res;
		}else{
			int t = comb.find(h[{x,y}]);
			cout<<vex[t] * 6 - edge[t] * 2<<endl;
		}
	}
}

I - Grammy and Ropes

给三个圆绳环形绳子构成的韦恩图：

如图所示，这些绳索(索引号从一到三)有六个重叠的交点，索引号分别从一到六。
格莱美想把这些绳子拉开，但它们似乎是绑在一起的，所以她需要用剪刀剪断这三根绳子中的一个子集。她想知道有多少种不同的方法来选择子集，以便之后这些绳子可以分开。你能告诉她答案吗？
注意：两个子集是不同的，当且仅当至少有一条绳子在其中一个子集中被选中，而在另一个子集中没有被选中。空集也应考虑在内。

考虑枚举子集的大小。
容易发现当子集的大小是3的时候，这个肯定是可以分开所有的绳子，这里只有一种情况。
当子集大小是2的时候，也是一定可以分开所有的绳子，一共有C(2,3) = 3种情况。
所以至少有4种情况是一定可以的。
当子集大小是1的时候，需要去枚举剩余的两根绳子是不是能够分开，两根绳子两个交点，即枚举第i个交点和第i+3个交点是不是一样的，如果不是那么这个剪法不对。
当子集大小是0的时候，要考虑三根绳子是不是原本就是分开的。
这个不太好想，用餐巾纸搓三条线之后玩了一下可以发现：
显然只有两个交点都是一样的才有机会。
在交点一样的情况下，比如第一条绳子在交点部分是全部在第二条绳子的上面时，可以理解为1->2有一条有向边，同理可以判断出1和3,2和3之间的关系，如果这个构成了一个环那么一定是错误的。

cpp

void solve() {
	vector<int> a(6);
	for(int i = 0;i<6;++i){
		string s;
		cin>>s;
		if(s[0] == 't') a[i] = 1;
		else a[i] = 0;
	}
	int ans = 4;
//	统计只剪一个的时候哪些是合法的
	for(int i = 0;i<3;++i) ans += a[i] == a[i+3];
//	用入度出度关系判环
	vector<int> d(4);
//	1 2
	if(a[0] == a[3]) d[0+(a[0] == 1)]++;
//	1 3
	if(a[1] == a[4]) d[0+2*(a[1] == 1)]++;
//	2 3
	if(a[2] == a[5]) d[1+(a[2] == 1)]++;
	if(ans == 7) ans += !(d[0] && d[1] && d[2]);
	cout<<ans<<endl;
}

微信扫一扫：分享