Codeforces Round #814 / 815 (Div. 2) C题

1.大意是，给出一个 1 - n的排列，ai表示运动员的实力，每次前两名运动员进行比较，实力强的保留，实力弱的排到最后。
每次给出一个询问 i 和 k，i为初始状态下的第i个选手，k为比赛次数，求出获胜次数。

思路：我们易发现，在第一个位置为实力最强的选手时，之后的所有比赛将是最强选手胜利。所以除了最强选手之外的选手的获胜次数都是固定的。

我们可以先取出n-1次状态下的每个选手获胜的次数。

对于每次查询，我们先用场次k减去前两个，这样我们选择的选手就在最前面，然后我们来比较一下剩余的k和选手n-1次比赛获胜的次数，取最小。

当然，最小不能超过0。

code：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,q,x=1;
		map<int,int> mp;
		cin>>n>>q;
		int v[n+1];
		for(int i=1;i<=n;i++)
		cin>>v[i];
		for(int i=2;i<=n;i++)
		{
			if(v[i]>v[x])
			x=i;
			mp[x]++;
		}
		mp[x]=INT_MAX;
		while(q--)
		{
			int a,k;
			cin>>a>>k;
			k-=max(a-2,0);
			cout<<max(min(mp[a],k),0)<<endl;//如果k<amp[a]就说明，a在比较过程中被淘汰过了 
		}
	}
}

2.大意是给出一个n*m的01矩阵，每次操作可以使得一个L形状的区域编程0，求出最多多少次使得所有的元素为0，每次至少使得一个1变为0，也就是有效操作。

这个题可以分情况讨论，我们通过贪心的思想易知，如果存在一个L区域中有两个0，那么我们可以制作出更多的区域有两个0，这样每次我们只改变了一个
1，相同的思想，如果不存在一个L有两个0，但是存在0，那么在操作一次后可以使得有更多区域有两个0，这样第一次改变了两个1，没有0则改变3个1。

code：

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
const int nn = 510;
int a[nn][nn];
void solve()
{
	int n,m;
	int have_zero=0;bool ser_zero= false;
	for(int i=0;i<nn;i++) for(int j=0;j<nn;j++) a[i][j] = 1; 
	cin>>n>>m;
	string str;
	for(int i=1;i<=n;i++)
	{
		cin>>str;
		for(int j=1;j<=m;j++)
		{
			a[i][j] = str[j-1]-'0';
			if(a[i][j]==0) have_zero++;
			if(a[i][j]==0&&a[i-1][j]==0||a[i][j]==0&&a[i][j-1]==0||a[i][j]==0&&a[i-1][j-1]==0||a[i][j]==0&&a[i-1][j+1]==0) ser_zero = true;
		}
	}
	//如果有连续的0，那么答案是1的数量-0
	//如果有一个0，答案是1的数量-1 
	//如果没有0，答案是1的数量-2
	if(have_zero>0&&ser_zero==true) cout<<n*m-have_zero<<endl;
	else if(have_zero>0) cout<<n*m-have_zero-1<<endl;
	else cout<<n*m-have_zero-2<<endl;
}
int main()
{
//	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

搜索

标签

存档