目录

• • • 前言
    • A.Anti Light's Cell Guessing
    • CODE
    • B.. Kalindrome Array
    • CODE
    • C.Keshi Is Throwing a Party
    • CODE

前言

传送门 :

太久没打了,这一场怎么这么难QAQ

A.Anti Light’s Cell Guessing

给你一个 n ∗ m n*m n∗m的网格, 然后你有一下操作 :

• 从网格中任选一点, 然后电脑告诉你 隐藏点 和 这个点的曼哈顿距离

问你需要至少选几个点才可以确定出来这个隐藏点

(一开始看这题懵的不行

显然 :

• 图是一条直线, 只需要一次
• 图是一个网 , 只需要两次(两个未知数,两个方程)
• 那么0次,就是只有只有一个点了,特判一下就行

CODE

void solve()
{
	int a,b;cin>>a>>b;
	if(a==1 && b==1)
	{
		cout<<0<<endl;
		return;
	}
	if(a == 1||b==1)
	cout<<1<<endl;
	else
	
	cout<<2<<endl;
	
}
 

B… Kalindrome Array

日常B比A简单

给定你一串数,你有如下操作 :

• 选择一个数,删除这个数在这个串中的任意个数(0,1,2…)

问是否可以通过该操作,得到回文串

显然 :

• 对于这个数 其实只有 全删 和 不删两个操作

为什么呢？
比如 :
5个相同的数, 你删除3个显然 和 全删一样 因为你剩下的两个要么对称不删,要么不对称必删
你删除2个,剩下的必然是3个 无法对称,你必然都删除

因此我们只需要在串不相同的时候,分别判断不包含该数的串是否为回文即可

CODE

void solve()
{
	cin>>n;
	vector<int> a(n);
	for(int i=0;i<n;i++)
	cin>>a[i];
	
	if(a == vector<int>(a.rbegin(),a.rend())){
		cout<<"YES"<<endl;
		return;
	}
	
	bool ok = false;
	
	auto check = [&](int x){
		vector<int> b;
		for(int i=0;i<n;i++)
		{
			if(a[i]!=x){
				b.pb(a[i]);
			}
		}
		ok|=(b == (vector<int>(b.rbegin(),b.rend())));
	};
	
	for(int i = 0 ;i<n;i++){
		if(a[i]!= a[n-i-1]){
			check(a[i]);
			check(a[n-1-i]);
			break;
		}		
	}
	cout<<(ok?"YES":"NO")<<endl;
}
 

C.Keshi Is Throwing a Party

给你 n n n个人,每个人两个属性 a , b a,b a,b

a 表示 最多在你后面的人数
b 表示 最多在你前面的人数

如果一次聚会你邀请的人 都满足他们的ab那么他们就是开心的

求满足开心的最大人数

对于这题我们可以二分答案 m i d mid mid 然后贪心的选

假设当前选择了 x x x人 ,那么出现在他前面的就是 x x x人,在他后面的就是 m i d − x − 1 mid-x-1 mid−x−1人

(二分好难,没记错上一场也调T了hh)

CODE

vector<pii> save;

bool check(int x)
{
	int cnt=0;
	for(auto it : save)
	{
		if(it.first>=cnt && it.second>=x-cnt-1)
		{
			cnt++;
		}
		if(cnt>=x)
		return 1;
	}
	return 0;
}
void solve()
{
	cin>>n;
	save.clear();
	for(int i = 0;i<n;i++)
	{
		int x,y;cin>>y>>x;
		save.pb({min(x,i),y});
	}
	
	int l = 0 ,r = n;
	while(l+1<r)
	{
		int mid =(l+r)>>1;
		if(check(mid))
		l = mid;
		else
		r = mid;
	}
	if(check(r))
	cout<<r<<endl;
	else
	cout<<l<<endl;
	
}