“蔚来杯“2022牛客暑期多校训练营2 补题题解（C 、D 、G 、H 、J 、K 、L）

• • C Link with Nim Game
  • D Link with Game Glitch
  • G Link with Monotonic Subsequence
  • H Take the Elevator
  • J Link with Arithmetic Progression
  • K Link with Bracket Sequence I
  • L Link with Level Editor I

比赛地址
参考的大佬题解

#include

using namespace std;

#define int long long 

const int N = 2e5 + 10;

int T, n, m;
int a[N];  //记录石子值
int num;  //记录石子异或和
int sum;  //记录石子总数
int ans;  //记录答案  

signed main()
{
	cin>>T;
	while(T -- ){
		cin>>n;
		num = 0, sum = 0;
		ans = 0;
		//读入石子堆，计算所有石子的异或和、数量和 
		for(int i = 1; i <= n; i ++ ){
			cin>>a[i];
			num ^= a[i];
			sum += a[i];
		} 

		if(num){  //如果石子异或和不为0，先手只需要保证每次操作把石子的异或和置为0即可，所以这种情况下，先手必胜
			int maxv = 0;
			for(int i = 1; i <= n; i ++ ){  //找到能去除的最大石子数
				int t = a[i] - (num ^ a[i]);  //从a[i]中取出t颗石子可以让所有石子堆异或和为0
				maxv = max(t, maxv);  //记录最大的t值 
			}
			for(int i = 1; i <= n; i ++ ){  //找第一步有几个可以的方案 
				int t = a[i] - (num ^ a[i]);  //从a[i]中取出t颗石子可以让所有石子堆异或和为0
				if(t == maxv) ans ++ ;  //在某一堆石子中拿走maxv个石子，有几堆合适的就哪有几种操作数
			} 
			cout<  //先手必败 
			setS, tt;
			//记录每堆石子被Alice拿走一个石子之后的情况
			for(int i = 1; i <= n; i ++ ){
				int t = a[i] ^ (a[i] - 1);  //记录所有在第a[i]堆中取出一个石头后剩下的石子堆异或和的情况 
				S.insert(t);  //记录在集合中 
			}
			for(auto x : S){  //遍历所有 每堆石子被Alice拿走一个石子之后的情况
				for(int i = 1; i <= n; i ++ ){  //对于第i堆石子
					//下一步就是把a[i]变为a[i]^x 
					int t = a[i] ^ x;  //在第a[i]堆中取出1个石头 此时sum=x，我们想要sum重新变为0，需要让a[i]变成a[i] ^ x,这样才能抵消x
					if(a[i] - t > 1){  //这一步就是对于a[i]，需要拿走多少块可以让所有石子异或和为0，如果大于1，这个方案应该去除
						tt.insert(x);  // 如果剩余个数不为1，那么这个x需要删除，说明这种情况不行，后续要去除 
					}
				}
			}
			for(auto op : tt) S.erase(op);  //遍历去除不合适的情况 
			//第一轮可能的操作数就是取1后下一步必须取1的堆的数量
			for(int i = 1; i <= n; ++ i) if(S.count(a[i] ^ (a[i] - 1))) ans ++ ;
			cout< 
D Link with Game Glitch 

 
 大致思路就是：根据两种物品之间的转化率rate（a/c，k直接消去）建图，如果存在一个w值使得rate*w建立的图中存在正环且环的边权乘积>=1，也就是说在这个环里物品可以相互之间无线转换，则不行。所以要找到小于1的w值，使得图中不存在这样的正环，w越小，存在这样正环的可能性就越小，所以二分w，找到合适的最大值，就是答案（注意因为找的是正环，所以要用最长路）
 
G Link with Monotonic Subsequence 
算是前道题吧，但是这个道签的很痛苦，队友打表跑了半天列数据才找出来规律
 
 
 
#include
using namespace std;
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
         int n;
        cin>>n;
        int x=sqrt(n);
        if(n-x*x>0) x++;
        int ge=x;
        int zu=n/ge;
        int yu=n%ge,tt=yu;
        for(int i=yu;i>=1;i--)
        {
            cout<
        
            for(int j=ge;j>=1;j--)
            {
                cout< 
H Take the Elevator 
 
#include

using namespace std;

#define int long long 

const int N = 2e5 + 10;

struct Node{
	int pos, dir;
	bool operator < (const Node &t) const {
		if(t.pos != pos) return pos > t.pos;
		return dir < t.dir;  //因为要使电梯数量尽可能少，所以在楼层相同的情况下，应该先遍历人少的 
	}
}; 

int n, m, k;
vector up, down;  //分别记录上升的人和下降的人
int cnt1, cnt2;  //分别记录上升的和下降的电梯数
int ans1[N], ans2[N];  //ans1[i]记录第i趟上升的电梯到达的最大层数，ans2[i]记录第i趟下降的电梯到达的最大层数 
int num;  //记录答案 

signed main()
{
	cin>>n>>m>>k;
	
	up.clear(), down.clear();
	
	for(int i = 0; i < n; i ++ ){
		int a, b;
		cin>>a>>b;  //从a去b 
		if(a < b){  //如果是上楼的人，从上往下枚举，到入口b是人
			up.push_back({a, -1});  //从上往下经过这个点说明人要出去一个，所以减一 
			up.push_back({b, 1});  //经过这个点说明有人了，所以加一 
		}
		else{  //下楼的人 
			down.push_back({a, 1});  //经过这个点说明有人了，所以加一 
			down.push_back({b, -1});  //从上往下经过这个点说明人要出去一个，所以减一 
		}
	}
	
	//按楼层和人数对两者进行排序 
	sort(up.begin(), up.end());
	sort(down.begin(), down.end());
	
	int weight = 0;  //记录目前已承载的单方向的人数 
	for(auto op : up){  //遍历所有上升的人 
		weight += op.dir;
		//这里起cnt1是0，所以第一趟电梯一定会开 
		if(weight > cnt1 * m) ans1[cnt1 ++ ] = op.pos;
	}
	weight = 0;  //因为计算的是单向人数，所以这里要清零 
	for(auto op : down){
		weight += op.dir;
		if(weight > cnt2 * m) ans2[cnt2 ++ ] = op.pos;
	} 
	
	int cnt = max(cnt1, cnt2);  //最大的电梯数量
	
	for(int i = 0; i < cnt; i ++ ){
		num += (max(ans1[i], ans2[i]) - 1) * 2;
	} 
	cout< 
J Link with Arithmetic Progression 

 参考一个大佬的题解：
 线性回归的内容，如果懂公式的话可以直接套，显然这是一个单极的二次函数，但是有两个变量。我们可以先三分一个a1，然后通过a1计算d，就可以求的误差啦。我放个a1计算d的手推公式你们细品。
 
 这里我补充解释一下，图中f(x)（其实应该是f(d)）就是t，也就是差值积之和，我们的目的是让t最小，也就是f(x)（f(d)）最小，那想一下小学（也可能高中是）教过的怎样得出一个一元二次方程的最小值，就是将方程求导，令导数f’(x)=0，这个x就是整个一元二次方程为0时自变量的取值，也就是图中f(d)取最小值时d的取值应该是等号右边那一堆，因为这里的ai不是定值，所以d值应该是对于每一个ai求一个值x，x之和就是d的值（这个不会推，但很好记）
 不明白最小二乘法的可以看一下这个：只看前9分钟就可
 
#include
#include 
#include 

#define db double

using namespace std;

const int N = 1e5 + 10;

namespace GTI
{
    char gc(void)
       {
        const int S = 1 << 16;
        static char buf[S], *s = buf, *t = buf;
        if (s == t) t = buf + fread(s = buf, 1, S, stdin);
        if (s == t) return EOF;
        return *s++;
    }
    int gti(void)
       {
        int a = 0, b = 1, c = gc();
        for (; !isdigit(c); c = gc()) b ^= (c == '-');
        for (; isdigit(c); c = gc()) a = a * 10 + c - '0';
        return b ? a : -a;
    }
}
using GTI::gti;

int n, m;
int a[N];

db sxnb(db b1){  //函数名：数学nb | b1就是等差数列第一项，也是线性回归直线的截距 
	db q = 0, p = 0;
	//这里要解释一下，这个公式是根据最小二乘法得出的（上述有解释） 
	//理解的话，可以将每个a[i]-b1看做一个等差数列的两项之差，除i-1就是求出这个等差数列的差的平均值的一部分 
	//将所有p/q相加就是这个等差数列的差值，这里为什么不消去(i-1)和2因为按照最小二乘法推出的公式是这样，消去的话会有一部分数据过不去（可能是因为精度问题） 
	for(int i = 1; i <= n; i ++ ){
		p += 2.0 * (a[i] - b1) * (i - 1);
		q += 1.0 * (i - 1) * (i - 1);
	} 
	db d = p / (2 * q);
	db res = 0;
	for(int i = 1; i <= n; i ++ ){
		res += (a[i] - b1 - 1.0 * (i - 1) * d) * (a[i] - b1 - 1.0 * (i - 1) * d);
	}
	return res;
}

int main()
{
	int T;
	T = gti();
	while(T -- ){
		n = gti();
		for(int i = 1; i <= n; i ++ ){
			a[i] = gti();
		}
		
		db l = -2e10, r = 2e10;
		//等差数列的公式a1+(n-1)*d类比于b+ k * x
		//所以当二分左侧得出的a1的值得出来的和大于二分右侧的a1值时，就说明直线在靠上得出的和小于直线在靠下的时候（想象一条直线斜率不变随着b值上下移动）
		//所以如果sxnb(mid_l) >= sxnb(mid_r)，就让二分区间摒弃左边的部分，就是让直线上
		//else的话就是让直线下移
		//最终找到合适的直线的位置，也就是差值之积最小的 
		while(r - l > 1e-5){
			db mid = r - l;  
			db mid_l = l + mid / 3, mid_r = r - mid / 3;  //三分（参照二分思想） 
			if(sxnb(mid_l) >= sxnb(mid_r)) l = mid_l;
			else r = mid_r;
		}
		printf("%.20lfn", sxnb(r));
	}
	return 0;
}
 
K Link with Bracket Sequence I 
动态规划，时间太紧迫了场上有一点点思路但是没想出来，以后要记住括号匹配要考虑左括号比右括号多的数量
 
 记f[i][j][k]表示长度为i，匹配成功的部分为k，左括号比右括号多j的方案数
 
#include

using namespace std;

const int N = 210, mod = 1e9 + 7;

int dp[N][N][N];  //f[i][j][k]表示长度为i，匹配成功的部分为k，左括号比右括号多j的方案数
int n, m;
char str[210];
int T;

void add(int& a, int b){  //加上&可以让a原地址的值直接改变 
	a = (a + b) % mod;
}

int main()
{
	cin>>T;
	while(T -- ){
		scanf("%d%d%s", &n, &m, &str[1]);  //读字符串的时候从下标1开始读，因为遍历的时候从1开始遍历，k又必须从0开始才能承接状态转移 
		memset(dp, 0, sizeof(dp[0]) * (m + 1));
		
		dp[0][0][0] = 1;
		
		for(int i = 0; i < m; i ++ ){  //枚举字符串长度 
			for(int j = 0; j <= i; j ++ ){  //枚举左括号比右括号多的数量 
				for(int k = 0; k <= i; k ++ ){  //枚举匹配成功的长度 
					if(j > 0){  //为保证m串合法，在左括号数量大于右括号数量时，才进行右括号的匹配 
						if(str[k + 1] == ')'){  //匹配成功，匹配成功的长度加一，左括号多的数量减一 
							add(dp[i + 1][j - 1][k + 1], dp[i][j][k]);  
						}
						else{  //下一位该匹配的是左括号，但是还是匹配了右括号，没有匹配成功，但是这种数量还是要算 
							add(dp[i + 1][j - 1][k], dp[i][j][k]);
						} 
					}
					if(str[k + 1] == '('){  //任何时候都可以匹配左括号，如果下一位要匹配的刚好是左括号 
						add(dp[i + 1][j + 1][k + 1], dp[i][j][k]); 
					}
					else add(dp[i + 1][j + 1][k], dp[i][j][k]);
				}
			}
		}
		cout< 
L Link with Level Editor I 

 dp[i][j]表示在i个世界（i是滚动式呈现）到达点j，路过的最小世界数
 
#include

using namespace std;

const int N = 1e4 + 10, INF = 0x3f3f3f3f;

int dp[2][N];  //因为第i个状态只取决第i-1状态，所以第一维可以用滚动数组承接上一个状态 
int n, m;
int ans = INF;

int main()
{
	cin>>n>>m;
	for(int i = 2; i <= m; i ++ ) dp[0][i] = dp[1][i] = n + 1;  //初始化 
	
	for(int i = 1, t = 1; i <= n; i ++ , t ^= 1){
		//f[1][2]=min(f[0][2]+1, n+1)
		//第一部相当于从f[0][2]状态转移而来，所以会承接0 
		int cnt;
		cin>>cnt;
		for(int u =2; u <= m; u ++ ) dp[t][u] = min(dp[t^1][u] + 1, n + 1);  //更新最短步数是不是由上一个世界相同的点i转移来的 
		for(int j = 1; j <= cnt; j ++ ){
			int u, v;
			cin>>u>>v;
			dp[t][v] = min(dp[t][v], dp[t ^ 1][u] + 1);  //f[t^1][u]+1表示上一个世界到达u点的代价
		}
		ans = min(ans, dp[t][m]);  //第二维表示点，第一维用于滚动式记录世界
	}
	if(ans > n) ans = -1;
	cout<