牛客寒假集训营第一场补题

第一场就是被爆锤的一天，人麻了，题目各种骗术，出题人坏得很。。。
慢慢补题吧

1、D 题《现在是，学术时间 (II)》

题目描述

目标检测任务旨在编写一个程序检测出图中存在的各种目标，每个目标可以用一个四边都平行于图像边界的矩形框来描述，我们称为目标框。而图像上完全正确的框出了目标的目标框称为GT目标框，程序所输出的目标框称为预测目标框。

为了评价程序的精确度，常常使用IOU这一标准来判断。定义两个矩形A, B的IOU为两个矩形交集部分的面积除以两个矩形并集部分的面积。例如，对于平面直角坐标系中(0,0), (3,3) 所确定的矩形与(−1,1), (4,2)所确定的矩形，两矩形交集面积为3，并集面积为11，因此IOU为 $3 / 11$ 。显然，IOU越大代表程序预测越精确。

现在，给出一个由平面上两点(0,0),(x,y)所确定的GT目标框和一个点P(xp,yp)。请你求出在所有以P点作为其中一个顶点且边都平行于坐标轴的预测目标框中，可以使其与GT目标框取到的最大IOU为多少。

输入描述:

第一行输入一个整数 $T(1≤T≤104)$ ，表示测试组数。

每组测试输入四个整数 $x,y,x_p,y_p(0< x,y,x_p,y_p\leq 1000)$ ，含义如题所述。

输出描述:

对每组测试用例，输出一个小数，表示该组询问的答案，你的答案与正确答案的相对误差不超过 $10^{-4}$ 即被视为正确。

示例1

输入

输出

0.333333333
0.480000000
0.571428571

分析

Screenshot_20230116_220108

AC代码

#include <bits/stdc++.h>
using namespace std;

int x, y, xp, yp;

int main(){
	int T;
	scanf("%d", &T);
	while(T -- ){
		scanf("%d%d%d%d", &x, &y, &xp, &yp);
		//分类讨论
		if(xp <= x && yp <= y){
			double SA = 1.0 * xp * (y - yp) / (x * y);
			double SB = 1.0 * (x - xp) * (y - yp) / (x * y);
			double SC = 1.0 * (x - xp) * yp / (x * y);
			double SD = 1.0 * xp * yp / (x * y);
			printf("%lf\n", max(max(SA, SB), max(SC, SD))); 
		} 
		else if(xp > x && yp <= y){
			double s1 = 1.0 * x * yp / (1.0 * xp * yp + x * y - (1.0 * x * yp));
			double s2 = 1.0 * x * (y - yp) / (1.0 * xp * (y - yp) + x * y - 1.0 * x * (y - yp));
			printf("%lf\n", max(s1, s2));
		}
		else if(xp <= x && yp > y){
			double s1 = 1.0 * xp * y / (1.0 * xp * yp + x * y - (1.0 * xp * y));
			double s2 = 1.0 * (x - xp) * y / (1.0 * (x - xp) * yp + x * y - (1.0 * (x - xp) * y));
			printf("%lf\n", max(s1, s2));
		}
		else if(xp > x && yp > y){
			printf("%lf\n", 1.0 * x * y / (xp * yp));
		}
	}
	
	return 0;
}

2、F题《鸡玩炸蛋人》

题目描述

炸鸡最近在 ɔiq彐平台上白嫖了一款游戏：《炸蛋人》。

《炸蛋人》的主角炸蛋人生活在一张 $n$ 个结点（编号 $1$ 到 $n$ ） $m$ 条边的无向图上（图不一定联通），炸鸡可以控制炸蛋人进行两种操作：移动和放置炸蛋。具体说明如下。

移动： 炸蛋人可以移动到当前所在结点通过一条边相连的相邻节点，但炸蛋人只能移动到没有炸蛋的结点。注意，尽管不能移动到有炸蛋的结点，但允许炸蛋人从一个当前有炸蛋的结点出发，移动到相邻没有炸蛋的结点。

放置炸蛋： 炸蛋人在当前位置放置一枚炸蛋，炸蛋一经放置就会永久存在于图中（炸蛋全称为炸制金黄色的农家土鸡蛋，因此当然不会爆炸），每个位置可以放置多枚炸蛋。

已知炸蛋人所在的无向图初始没有炸蛋，炸蛋人出现在了地图上的 $S$ 点，炸鸡对炸蛋人进行了一系列的操作，炸蛋人最终停留在了 $T$ 点。现在，给出无向图最终的情况，请你求出有多少种可能的起点终点方案 $(S,T)$ ，两种方案不同当且仅当它们的起点和终点至少有一个不同。若无合法方案输出 $0$ 。

输入描述：

输入第一行包括两个整数 $n,m(1≤n≤10^5,1≤m≤2×10^5)$ ，表示无向图的结点个数和边的个数。

接下来 $m$ 行，每行两个正整数 $u,v(1≤u,v≤n)$ 表示 $u,v$ 之间有一条边，可能有自环或重边。

最后一行包括 $n$ 个正整数，第 $i$ 个正整数 $c_i(0≤c_i≤2)$ 表示 $i$ 号结点上最终有多少个炸蛋。

输出描述：

输出一个正整数，表示题目所求的 $(S,T)$ 的对儿数，若无合法的方案输出 $0$ 。

示例1

输入:
6 4
1 2
2 3
1 3
4 6
0 0 0 0 0 0

输出:
14

示例2

输入：
6 4
1 2
2 3
1 3
4 6
0 0 0 0 2 0

输出:
1

分析

注意到对于一个大小为 $sz$ 的联通块，无论块内的炸蛋如何放置这个联通块任意两点作为起点终点的 $sz*sz$ 种方案都可以做到。

证明: 考虑联通块是一颗树的情况（要实现这一要求必定是边越多越容易实现，那么树结构是一个连通块边较少的特殊情况，如果树能够做到，那么其他结构也能做到），可以先从 $S$ 不放炸蛋的走到 $T$ ，然后从 $T$ 出发，按照类似 $dfs$ 的方式遍历这棵树，在回溯时选择放炸蛋即可做到放完所有炸蛋最终回到 $T$ 。这样根据 $dfs$ 的特性，回溯的时候先放完的子树之后不会在进入了，因此不会有冲突。
因此，记第 $i$ 个联通块的大小为 $sz$ ，有炸蛋的联通块数量为 $B$ 则：

$B = 0:$ 输出 $\sum (sz_i) ^2$ ;

$B=1:$ 输出有炸弹联通块 $j$ 的 $(sz_j) ^2$ ;

$B \ge 2:$ 无解，输出 $0$ ；

AC代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 100010;
int p[N], cnt[N];
bool st[N];   //记录炸弹连通块 
int n, m; 
LL cc, ans;
int z;

int find(int x){
	if(x != p[x]) p[x] = find(p[x]);
	return p[x];
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) p[i] = i, cnt[i] = 1;
	while(m -- ){
		int a, b;
		scanf("%d%d", &a, &b);
		int pa = find(a), pb = find(b);
		if(pa != pb){
			cnt[pb] += cnt[pa];
			p[pa] = pb;
		}
	}
	bool flag = false;
	for(int i = 1; i <= n; i++){
		int x;
		scanf("%d", &x);
		if(x > 0) {
			z = i;
			int p = find(i);
			if(!st[p]){
				st[p] = true;
				cc++;  //炸弹连通块数量加1 
				if(cc >= 2) {
					flag = true;
					ans = 0;
					break;
				}
			}
		}

	}
	if(flag) printf("%d\n", ans); 
	else{
		memset(st, 0, sizeof st);
		if(cc == 0){  //所有连通块cnt平方和 
			for(int i = 1; i <= n; i++){
				int p = find(i);
				if(st[p]) continue;
				st[p] = true;
				ans += 1LL* cnt[p] * cnt[p];
			}
			printf("%lld\n", ans);
		}
		else if(cc == 1){ //计算炸弹所在的连通块 
			int p = find(z);
			printf("%lld\n", 1LL* cnt[p] * cnt[p]);
		}
	}
	
	return 0;
}

3、G题《鸡格线》

题目描述

你有一个长为 $n$ 的数组 $a$ ，你需要支持以下两种操作：

1、输入 $l$ ， $r$ ， $k$ ，对区间 $[l, r]$ 中所有数字执行 $a_i=f(a_i)$ 操作 $k$ 次（式中等号表示赋值操作），其中 $f(x)=round(10\sqrt x)$ ，round为四舍五入函数。

2、输出当前数组所有数字的和。

你需要正确处理 $m$ 次这样的操作。

输入描述：

输入第一行包含两个整数 $n,m(1\leq n,m\leq 10^5)$ ，表示数组长度与操作次数。

接下来一行输入 $n$ 个整数，第 $i$ 个整数 $a_i(0\leq a_i \leq 10^9)$ 表示数组第 $i$ 个数。

接下来 $m$ 行，每行先输入一个操作类别 $op(op∈{1,2})$ ，表示两类操作之一，若 $op=1$ ，则继续输入三个整数 $l,r,k(1\leq l \leq r\leq n,1\leq k \leq 10^5)$ ，含义如题目所示。

输出描述：

对于所有第二类操作，输出一个整数表示当前数组所有数字的和。

示例1

分析

区间问题，自然想到线段树。

本题实际上是区间修改，需要对区间内的每个数做 $k$ 次操作，且不能像普通的区间修改（每个数加上 $d$ ）那样用 $O(1)$ 的时间算出区间中每个数都加上 $d$ 后区间的和tr[u].sum += (tr[u].r - tr[u].l + 1) * d，因此难以用懒标记维护从而减小时间复杂度。因此单次修改的时间复杂度为 $O(n)$ ，我们可以用过维护一个flag来标记某个区间是否每个数都已经收敛，如果是则在 $modify$ 时直接return即可，这样就能省去一些操作，减小时间复杂度。

本题还有一个关键点是找到 $f(x)$ 的性质。

性质：

可以通过简单打表发现该性质。

$f(x)$ 经过不多次数的操作会收敛到一个不变的值 $f(x_0)$ = $x_0$ ， $x_0$ 有三个： $0$ 、 $99$ 、 $100$ ，因此总操作次数不大。

我们在对一个数进行 $k$ 次变换时，当检测到收敛后，就可以break结束操作。因此虽然 $k$ 可能很大，但是真正的变换次数却很少。

AC代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 100010;

struct Node{
	int l, r;
	bool flag;   //标记[l, r]区间是否完全收敛（每一个数都已经f(x)收敛） 
	LL sum;
}tr[N * 4];

int a[N];
int n, m; 

void pushup(int u){
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
	tr[u].flag = tr[u << 1].flag & tr[u << 1 | 1].flag;
}

void build(int u, int l, int r){
	tr[u] = {l, r, 0};
	if(l == r){
		tr[u].sum = a[l];
		return;
	}
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	pushup(u);
}

void modify(int u, int l, int r, int k){
	if(tr[u].flag) return;
	if(tr[u].l == tr[u].r){  //到达叶子 
		for(int i = 0; i < k; i++){
			LL t = tr[u].sum;
			tr[u].sum = round(10.0 * sqrt(tr[u].sum));
			if(t == tr[u].sum){
				tr[u].flag = 1;
				break;			
			}
		}
	}
	else{
		int mid = tr[u].l + tr[u].r >> 1;
		if(l <= mid) modify(u << 1, l, r, k);
		if(r > mid) modify(u << 1 | 1, l, r, k);
		pushup(u);
	}
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	build(1, 1, n);
	while(m -- ){
		int op;
		scanf("%d", &op);
		if(op == 1){
			int l, r, k;
			scanf("%d%d%d", &l, &r, &k);
			modify(1, l, r, k);
		} 
		else printf("%lld\n", tr[1].sum);
	}
	
	return 0;
}

4、K题《最少的坏区间》

题目描述

你需要写出一个仅有0和1组成的长为n的字符串，要求之中恰有m个字符是1。

现在，规定对于原序列中一个长恰好为3的子区间（子区间是连续的），若之中1的个数多于0的个数，则这个区间是坏的。

请求出满足条件的字符串中，坏区间总数最少的字符串中有几个坏区间。

输入描述

输入只有一行两个整数 $n,m(1≤m≤n≤1000)$ ，含义如题目所述。

输出描述

输出一个整数，表示满足条件的字符串中，坏区间最少为多少个。

示例1

输入:
4 3

输出:
2

说明:
0111、1011、1101、1110都是可能的答案，它们之中都有两个长为3的区间满足1的数量多于0的数量。

示例2

输入:
10 4

输出:
0

示例3

输入:
10 5

输出:
2

分析

本题有两种做法：1、贪心，2、状压DP

赛时被题目提示骗了以为只能dp，就没写出来，其实已经想到了贪心的正确思路。。。

1、贪心做法

通过手玩小样例，发现类似1001001001……11111这样的串（也就是密的部分全是1，松的部分一个1占多数的区间都没有）比较优，因此据此模拟一下即可。

注意最终要分类讨论一下，根据剩余0的情况和是否进行过轮次f来进行讨论，别忘了和0取max。

AC代码：

#include <bits/stdc++.h>
using namespace std;

int n, m; 

int main(){
	scanf("%d%d", &n, &m);
	int cnt = n, k = m;
	int f = 0;
	//循环条件：0的剩余个数>=2并且1的剩余个数>=1
	while(n - m - 2 * f >= 2 && k >= 1){
		k--;
		f++;
	}
	int rz = n - m - 2 * f;  //剩余0的数量
	//注意要和0取max 
	if(rz == 0) printf("%d\n", max(0, f ? k - 1 : k - 2));
	else printf("%d\n", max(0, k - 1));
	
	return 0;
}

2、状压DP

11_25_19_1673936448702-1673963653874

AC代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int n, m;
int f[N][N][4];

int main(){
	scanf("%d%d", &n, &m);
	memset(f, 0x3f, sizeof f);
	//初始状态 
	for(int i = 0; i < 4; i++){
		int cnt = (i & 1) + (i >> 1 & 1);
		f[2][cnt][i] = 0;
	}
	
	//dp
	for(int i = 3; i <= n; i++){
		for(int j = 0; j <= m; j++){
			for(int k = 0; k < 4; k++){
				for(int u = 0; u <= 1; u++){
					int cnt = (k & 1) + (k >> 1 & 1); //i - 1状态最后两位有几个1 
					int now = ((k & 1) << 1) | u;  //i状态最后两位的二进制状态 
					int x = cnt + u >= 2;  //x表示第i为取u是，能够与前两位构成坏区间 
					f[i][j + u][now] = min(f[i][j + u][now], f[i - 1][j][k] + x);
				}
			}
		}
	}
	
	int ans = 0x3f3f3f3f;
	for(int i = 0; i < 4; i++) ans = min(ans, f[n][m][i]);
	printf("%d\n", ans);
		
	return 0;
}

5、M题《章鱼仙贝》

题目描述

小波奇由于冲动消费，不小心买多了章鱼仙贝，买了一共m份章鱼仙贝，于是她只能把这些仙贝分给n位朋友。

小波奇日常想太多，她认为分仙贝时好感度的变化是有规律的，不过并不是给的仙贝越多，好感度上升的就越多，而是应该看小波奇给出的仙贝数与她当前手里总仙贝的比值。也就是说，若小波奇当前还剩下 $x(x>0)$ 个仙贝，并给了一位朋友 $y$ 个仙贝（ $x$ ， $y$ 都为整数），则这位朋友对小波奇的好感度将增加 $y/x$ （这个值可以为小数）。

现在，小波奇可以任意安排送仙贝的顺序和每次送仙贝的个数，但不能给同一个人送两次仙贝，允许最后手中还有剩余的仙贝，允许最终有朋友没有分到仙贝。社恐的朋友非常重要，所以请你帮助小波奇算一算，在最优送仙贝策略下，小波奇和所有人的好感度之和最大为多少（假设初始小波奇和所有人好感度都为 $0$ ）。

输入描述：

输入包括两个整数 $n,m(1≤n,m≤500)$ ，表示小波奇的朋友数和仙贝数。

输出描述：

输出问题的答案，即小波奇与朋友们的好感度之和的最大值，考虑到可能存在的浮点误差，你的答案与标准答案的相对误差若在 $10^{-6}$ 之内，就将被判为正确。

示例1

输入:
3 3

输出:
1.833333333

说明

对应的分配方案是：小波奇初始有 $3$ 个仙贝，给第一个朋友 $1$ 块，收获了 $1/3$ 的好感度；现在小波奇有 $2$ 个仙贝，给第二个朋友 $1$ 块，收获了 $1/2$ 的好感度；最后，小波奇把最后一块仙贝给了第三个朋友，收获了 $1/1$ 的好感度。因此，总好感度为 $11/6$ ，并且可以看出没有更好的分配方案。

分析

11_25_21_1673939345965

AC代码

#include <bits/stdc++.h>
using namespace std;

const int N = 510;
double f[N][N]; 
int n, m;

int main(){
	scanf("%d%d", &n, &m);
	memset(f, -0x3f, sizeof f);
	for(int i = 0; i <= m; i++) f[0][i] = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= m; j++){
			for(int k = 0; k <= j; k++){
				f[i][j] = max(f[i][j], f[i - 1][k] + (1.0 * j - k) / (m - k));
			}
		}
	}
	double ans = -0x3f3f3f3f;
	for(int i = 0; i <= m; i++) ans = max(ans, f[n][i]);
	printf("%lf\n", ans);
	
	return 0;
}

未完待续。。。

牛客寒假集训营第一场补题

1、D 题《现在是，学术时间 (II)》

2、F题 《鸡玩炸蛋人》

3、G题 《鸡格线》

4、K题 《最少的坏区间》

5、M题 《章鱼仙贝》

2、F题《鸡玩炸蛋人》

3、G题《鸡格线》

4、K题《最少的坏区间》

5、M题《章鱼仙贝》