Educational Codeforces Round 77 (Rated for Div. 2)

A - Heating

大概就是将  个物品要覆盖  个位置，每个物品安装的代价是 这个物品覆盖直径的平方。

显然平分答案最优。

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
int main()
{
	int T;
	sc("%d", &T);
	while (T--)
	{
		int a, b;
		sc("%d%d", &a, &b);
		ll cnt1 = b % a;
		ll sum1 = b / a + 1;
		ll cnt2 = a - b % a;
		ll sum2 = b / a;
		ll ans = cnt1 * sum1 * sum1 + cnt2 * sum2 * sum2;
		pr("%lld\n", ans);
	}
}

B - Obtain Two Zeroes

两个数字，每次只能将第一个数字减一，第二个数字减二，或者将第一个数字减二，第二个数字减一。操作次数无限制，问这两个数字能否相等。

1. 若两个数字相等，一定要是3的倍数才行

2. 先将两个数字变相等，不就行了。

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
int main()
{
	int T;
	sc("%d", &T);
	while (T--)
	{
		int a, b;
		sc("%d%d", &a, &b);
		if (a > b)
			swap(a, b);
		int cha = b - a;
		b -= cha * 2;
		a -= cha;
		if (a < 0 || b < 0)
		{
			puts("NO");
			continue;
		}
		if (a % 3 == 0)
			puts("YES");
		else
			puts("NO");
	}
}

C - Infinite Fence

一块无限长的线性木板，所有下标是  的倍数的位置被涂成颜色1，所有下标是  的倍数的位置被涂成颜色2，如果下标即是  的倍数也是  的倍数，可以涂成任意一种颜色，其他位置不涂颜色。将所有没有颜色的模板去掉，问是否会有连续 K 个相同颜色。

假设 a < b，题目就是问两个 b 的倍数之间能否存在 k 个 a，显然，我们只需要找到离 b 的倍数最近的并且比 b 大的 a 的倍数，然后以这一位为第一个 a ，一次排列下去就可以知道答案了。

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
ll gcd(ll a, ll b)
{
	return b == 0 ? a : gcd(b, a % b);
}
int main()
{
	int T;
	sc("%d", &T);
	while (T--)
	{
		ll a, b, k;
		sc("%lld%lld%lld", &a, &b, &k);	
		if (a == b)
		{
			puts("OBEY");
			continue;
		}
		if (a > b)
			swap(a, b);
		ll g = gcd(a, b);
		ll num = g + (k - 1) * a;
		if (b - 1 >= num)
			puts("REBEL");
		else
			puts("OBEY");
	}
}

D - A Game with Traps

有 m 个士兵，有 k 个陷阱，你有一队兵，每个兵有一个敏捷值，你的目标是从0走到n+1，每个陷阱有 3 个值， ，如果一个兵走到位置 ，且敏捷小于 ，他就GG了，但是假如你走到 ，就可以花费 1s 取消这个陷阱，你不受陷阱的限制。

题面太恶心了，说不清了。。。

做法就是二分+模拟，每次模拟的时候，尽量往后走，如果遇到需要解除的陷阱，不断更新右端点就可以。

slove by yp.  （我WA３）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 2e5+5;
const int INF = 0x3f3f3f3f;
multiset<int> list1[MAX];
int m,n,k,t,a[MAX],l[MAX],r[MAX],d[MAX];
vector<pair<int,int>> list2[MAX];
bool check(int mid){
	for(int i=1;i<=k;++i) list1[l[i]].insert(d[i]);
	int now=0,cost=0,i;
	bool flag=false;
	for(i=1;i<=n;++i){
		++cost;
		flag=false;
		for(;now<i;){
			if(list1[now+1].empty()){
				++now;
				if(now!=i) cost+=2;
			}
			else if((*list1[now+1].rbegin())<=a[mid]){
				++now;
				if(now!=i) cost+=2;
			}
			else break;
		}
		
		int len = list2[i].size();
		for(int j=0;j<len;++j){
			int la = list2[i][j].first,lb = list2[i][j].second;
			list1[la].erase(list1[la].find(lb));
		}
	}
	flag=false;
	for(;now<i;){
		if(list1[now+1].empty()){
			++now;
			if(now!=i) cost+=2;
		}
		else if((*list1[now+1].rbegin())<=a[mid]){
			++now;
			if(now!=i) cost+=2;
		}
		else break;
	}
	++cost;
	if(cost<=t) return true;
	else return false;
}
bool cmp(int a,int b){
	return a>b;
}
void solve(){
	scanf("%d%d%d%d",&m,&n,&k,&t);
	for(int i=1;i<=m;++i) scanf("%d",&a[i]);
	sort(a+1,a+1+m,cmp);
	for(int i=1;i<=k;++i){
		scanf("%d%d%d",&l[i],&r[i],&d[i]);
		list2[r[i]].push_back({l[i],d[i]});
	}
	if(t>=3*n){
		printf("%d\n",m);
		return;
	}
	int left = 0,right=m;
	while(left+1<right){
		int mid = (left+right)/2;
		if(check(mid)) left=mid;
		else right=mid;
	}
	int ans;
	if(check(right)) ans=right;
	else ans=left;
	printf("%d\n",ans);
}
int main(void)
{
	solve();
	return 0;
}