ICPC训练赛补题集

标签：cnt return cin int mid ICPC 训练赛补题 define

文章目录

ICPC训练赛补题集

D - Fast and Fat (负重越野)

原题链接：原题链接
题意：体重大的背体重小的速度不变，体重小的背体重大的速度会变化，变化 v i − ( w j − w i ) vi−(wj−wi) vi−(wj−wi)程度。有T组数据，有多组测试数据。第一行输入一个整数T 表示测试数据组数，对于每组测试数据：
第一行输入一个整数n表示队员人数。
对于接下来n行，第 i i i行输入两个整数 v i v_i vi和 w i w_i wi,表示速度和体重的大小。
The optimal strategy for the sample test case is shown as follows:

Let member 1 1 1 carry member 4 4 4. As w 1 > w 4 w_1 > w_4 w1>w4, member 1 1 1’s speed remains unchanged, which is still 10 10 10.
Let member 3 3 3 carry member 2 2 2. As w 3 < w 2 w_3 < w_2 w3<w2, member 3 3 3’s speed will decrease by w 2 − w 3 = 2 w_2 - w_3 = 2 w2−w3=2 and becomes 10 − 2 = 8 10 - 2 = 8 10−2=8.
Member 5 5 5 shall move alone. His/Her speed is 9 9 9.
So the answer is 8 8 8.
思路：利用二分的方法，二分答案，尽量往右找，最后输出 l l l的值就是答案。主要思想是check函数里面的内容，主要就是找出来速度低于mid的，判断它们是否能被背起来达到速度最小是mid，速度大于mid的都是来背或者不背其它人的。当速度小于mid的人数大于速度大于等于mid的人时，这个mid一定不能用，要 r e t u r n 0 return 0 return0掉。而且还要判断能否通过别人背起来达到mid的速度。

#include <bits/stdc++.h>
#define int long long 
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define fi first
#define se second
#define PII pair<int,int>
using namespace std;
const int N = 1e5+5;
//int a[N],b[N];
int n;
vector<PII> a;
int check(int mid)
{
	priority_queue <int> b,c;//这里用到的优先队列会从大到小自动排序。
	for (int i=0;i<n;i++)
	{
		if (a[i].fi>=mid)
		{
			b.push(a[i].fi+a[i].se);
		}
		else 
		{
			c.push(a[i].se);
		}
	}
	if (b.size()<c.size()) return 0;
	while (b.size()&&c.size())
	{
		if (b.top()-c.top()>=mid)
		{
			b.pop();c.pop();
		}
		else return 0;
	}
	if (!c.empty()) return 0;
	return 1;
	
}

void solve ()
{	
   	a.clear();//注意这里一定要清空vector的值
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		int x,y;cin>>x>>y;
		a.push_back({x,y});//这里用vector加pair的方式存入两个变量，也可以用结构体啥的
	}
	int l=0,r=1e9+1,mid;//标准二分答案板子
	while (l<r)
	{
		int mid=l+r+1>>1;
		if (check(mid)) l=mid;
		else r=mid-1;
	}
	cout<<l<<'\n';
}

signed main ()
{
	IOS;
	int T =1;
	cin>>T;
	while(T--) solve ();
	return 0;
}

I-路径规划

原题链接：此处跳转
刚拿到这一题的时候一点思路都没有，更别说能想到是二分的方法来写了。但是看完答案过后“柳暗花明又一村”，豁然开朗。因为有最大的字眼，所以就用二分？反正这一题用二分是正解。
题意：给出 n × m n×m n×m的序列，从左上角走到右下角找到最大的 M E X MEX MEX， M E X MEX MEX是路径中没出现的最小非负整数，例如路径中的数字为“0 2 4 5 6”，那么 M E X MEX MEX的值就是1，因为1没有出现过。因此我们就要找出来最大的 M E X MEX MEX的值；
思路：因为范围比较大 1 ≤ n , m ≤ 1 0 6 1 \le n, m \le 10^6 1≤n,m≤106, 1 ≤ n × m ≤ 1 0 6 1 \le n \times m \le 10^6 1≤n×m≤106 所以我们用一般的二维数组肯定是存不了的，会爆掉，我们这里用到cin>>a[i*m+j]（i为行，j为列）这样的方式给数组存进来。输入问题解决之后就要用到很奇妙的思维了，因为要求最大的mex，我们这里可以用二分的思想，尽量向右找，然后输出l即可。那么check函数该怎么写？怎么写？怎么写？问三遍。这里的思维很奇妙，我们知道如果要让一个数符合标准，例如3，让3成为最小的没出现过的数，我们就要找到它之前的所有数字“0 1 2 ”都要找到，那么重中之重就是能不能找到这几个数字。因为只能向右和向下走，那么我们可以定义一个k来存储位置，判断能不能往下一个方向出发。例如:

bool check (int x)
{
	int k=0;//定义一个k
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<m;j++)
		{
			if (a[i*m+j]<x)//找小于x的数字
			{
				if (k>j) return false;//如果走不到这个位置，无法到达就肯定不符合条件，二分return掉
				k=j;//更改位置
			}
		}
	}
	return true;//如果都符合条件就return true
}

加上二分的模板之后就能轻松AC了，主要还是要知道这是一到二分的题目，看不出来那这道题还写个集贸，直接寄了吧

#include <bits/stdc++.h>
#define int long long 
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define fi first
#define se second
#define PII pair<int,int>
using namespace std;
const int N = 1e6+5;
int a[N],b[N];
int n,m;
bool check (int x)
{
	int k=0;
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<m;j++)
		{
			if (a[i*m+j]<x)
			{
				if (k>j) return false;
				k=j;
			}
		}
	}
	return true;
}

void solve ()
{
	cin>>n>>m;
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<m;j++)
		cin>>a[i*m+j];
	}
	int l=0,r=n*m,mid;
	while (l<r)
	{
		int mid=l+r+1>>1;
		if (check(mid)) l=mid;
		else r=mid-1;
	}
	cout<<l<<'\n';
}

signed main ()
{
	IOS;
	int T =1;
	cin>>T;
	while(T--) solve ();
	return 0;
}

G. Inscryption(邪恶铭刻)

原题链接：点击此处
题意：有T组数据，每组数据有一个n，接下来有n个数据

如图所示，一些题目要求。分别用1 -1 0 来表示。
这道题我们写了好久没有写出来，果真还是太菜了，看完别人的代码感觉好简单，但是这种思路我们肯定也想不到。
思路：用sum来表示总共的攻击力，用cnt来表示有多少人，用choice来表示可以反悔多少次。这个反悔很奇妙，真的太妙了。因为0可以变成1或者-1.假设我们就让0变成-1，因为尽量变成-1才会让平均数最大。假设先变成-1，再往后看，如果后面行不通了，就反悔回来，sum++，cnt++，choice–。主要思想看代码

#include <bits/stdc++.h>
#define int long long 
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define fi first
#define se second
#define PII pair<int,int>
using namespace std;
const int N = 1e5+5;
int a[N],b[N];
void solve ()
{
	int n;cin>>n;int flag=0;
	int sum=1,cnt=1,choice=0;
	for (int i=1;i<=n;i++)
	{
		int x;cin>>x;
		if (x==1) sum++,cnt++;//这种情况只能sum++，cnt++
		else if (x==-1)
		{
			if (cnt>1) cnt--;//为-1的时候cnt--，sum不用减，因为牺牲了，但攻击力给别人了
			else if (choice>=1) sum++,cnt++,choice--;//如果cnt不大于1那么看看是否能反悔，能反悔就可以，否则输出-1
			else 
			flag=1;
		}
		else 
		{
			if (cnt>1) cnt--,choice++;//假设变成-1
			else sum++,cnt++;//变成1
		}
	}
	int k=__gcd(sum,cnt);
	if (flag==1) cout<<"-1"<<'\n';	
	else cout<<sum/k<<' '<<cnt/k<<'\n';//约分，直接求出最大公约数再除以他们就ok了，但是手写gcd函数会更快
}

signed main ()
{
	IOS;
	int T =1;
	cin>>T;
	while(T--) solve ();
	return 0;
}

感觉就是考了一个思维，没想到我们却写的如此稀碎，能写对的也就最大公约数的函数了。怎么办呢？？？？
还是 cai jiu duo lian吧

持续更新中 . . . . . . . . . . . . . . . . . . . . . . . ....................... .......................

标签：cnt,return,cin,int,mid,ICPC,训练赛,补题,define
From： https://blog.csdn.net/a13997460860/article/details/139244815

ICPC训练赛补题集