Codeforces Round #700 (Div. 2)

B-The Great Hero

按总收到伤害排序是不行的,简单分析一下,你总是要打死n-1只怪,剩下一只怪你攻击x次杀死他,他只攻击你x-1次。那么就去找这个怪,直接枚举每一只,看看其

他怪的伤害综合加上这一只只攻击x-1次后剩余的生命值是否大于0。

C-Searching Local Minimum

wa5了4发才找到这个sb问题
Codeforces Round #700 (Div. 2)

每次二分mid与mid+1的两个值,如果a[mid]<a[mid+1],则r=mid-1,否则l=mid+2,最终l>r时,遍历一遍序列找那个值即可(肯定能找到,nextpermutation打个表画折线图)

代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
double pi = acos(-1);
const double eps = 1e-9;
const ll inf = 1e8 + 7;
const int maxn = 1e5 + 10;
ll mod = 1e9 + 7;

int main()
{
	int n;
	cin >> n;
	vector<int>a(n + 2, 0);
	if (n == 1)
	{
		cout << "! 1" << endl;
		return 0;
	}
	cout << "? 1" << endl;
	cout.flush();
	cin >> a[1];
	cout << "? 2" << endl;
	cout.flush();
	cin >> a[2];
	cout << "? " << n - 1 << endl;
	cout.flush();
	cin >> a[n - 1];
	cout << "? " << n << endl;
	cout.flush();
	cin >> a[n];
	if (a[2] > a[1])
	{
		cout << "! 1" << endl;
		return 0;
	}
	if(a[n] < a[n - 1])
	{
		cout << "! "<<n<<endl;
		return 0;
	}
	int l = 3, r = n - 2;
	while (l <= r)
	{
		int mid = l + r >> 1;
		if (!a[mid])
		{
			cout << "? " << mid << endl;
			cout.flush();
			cin >> a[mid];
		}
		if (!a[mid + 1])
		{
			cout << "? " << mid + 1 << endl;
			cout.flush();
			cin >> a[mid + 1];
		}
		cout.flush();
		if (a[mid] < a[mid + 1])
			r = mid - 1;
		else
			l = mid + 2;
	}
	cout.flush();
	for (int i = 2; i < n; i++)
		if (a[i] && a[i - 1] && a[i + 1] && a[i] < a[i - 1] && a[i] < a[i + 1])
		{
			cout <<"! "<< i << endl;
			break;
		}
	return 0;

}

D1-Painting the Array I

错误思路:先拿一组,剩下的全部给第二组,这样会wa6。。。

hack:11332133 错误做法:第一组:13213 第二组13 答案: 第一组:1323 第二组:1313(把1给了第二组)

只需要把这种处理掉就行了

代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
double pi = acos(-1);
const double eps = 1e-9;
const int inf = 1e9 + 7;
const int maxn = 1e5 + 10;
ll mod = 1e9 + 7;

int main()
{
	fastio;
	int n;
	cin >> n;
	vector<int>a(n + 1);
	int ans = 0, last1 = -1, last2 = -1;
	for (int i = 1; i <= n; i++)cin >> a[i];
	for (int i = 1; i <= n; i++)
	{
		int x = a[i];
		if (x != last1 && x != last2)
		{
			ans++;
			if (i < n && a[i + 1] == last2)last2 = x;
			else
				last1 = x;
		}
		else if (x != last1 && x == last2)
		{
			ans++;
			last1 = x;
		}
		else if (x == last1 && x != last2)
		{
			ans++;
			last2 = x;
		}
	}
	cout << ans;

	return 0;

}

上一篇:Codeforces Round #700 Div. 2


下一篇:补 : Codeforces Round #700 (Div. 2) A B