codeforces round 894题解 A~F

A. Gift Carpet

A. Gift Carpet

题目大意

有n*m个格子，每个格子中有一个字符，问是否有从左往右的四列格子中，分别包含v，i，k，a四个字符。

思路

就从左往右枚举每一列，记录v，i，k，a有没有且是不是按顺序出现的。

AC代码

#include<iostream>
#include<map>
using namespace std;
char di[25][25];
char p[4] = { 'v','i','k','a' };
int main() {
	int t; cin >> t;
	while (t--) {
		map<char,int> mp;
		int n, m; cin >> n >> m;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cin >> di[i][j];
			}
		}
		int tot = 0;
		for (int j = 1; j <= m; j++) {
			for (int i = 1; i <= n; i++) {
				if (di[i][j] == p[tot]) {
					tot++;
					break;
				}
			}
			if (tot == 4) {
				break;
			}
		}
		if (tot-1 == 3) 
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
		
	}
}

B. Sequence Game

B. Sequence Game

题目大意

给定一个数组b，数组b中的元素是数组a中的元素中满足 a[i-1]<=a[i] 条件的a[i]。求一个可能的数组a。

思路

反着推回去，如果b[i-1]大于b[i]，就在b[i]前面加上一个小于等于它的数。

AC代码

#include<iostream>
using namespace std;
const int M = 2e5 + 5;
typedef long long ll;
ll b[M];
ll a[M];
int main() {
	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> b[i];
		}
		int tot = 0;
		a[++tot] = b[1];
		for (int i = 2; i <= n; i++) {
			if (b[i] >= b[i - 1]) {
				a[++tot] = b[i];
			}
			else {
				a[++tot] = b[i];
				a[++tot] = b[i];
			}
		}
		cout << tot << endl;
		for (int i = 1; i <= tot; i++) {
			cout << a[i] << " ";
		}
		cout << endl;
	}
}

C. Flower City Fence

C. Flower City Fence

题目大意

判断高度递减，宽度相等的几块长木板组成的形状是否是轴对称图形。

思路

不太好表述，可以就这样例画一画图，就会发现一些有趣的事情

AC代码

#include<iostream>
#include<map>
#include<cstring>
using namespace std;
typedef long long ll;
const int M = 2e5 + 5;
ll a[M];
ll cnt[M];
int main() {
	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		map<int, int> mp;
		memset(cnt, 0, sizeof(cnt));
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
		}
		int f = 0;
		int pre = 0; mp[pre] = 0;
		for (int i = 1; i <= n; i++) {
			ll len = a[i];
			/*if (len > n||len<n) {
				f = 1;
				break;
			}
			if(len==n)*/
			mp[len]=mp[pre]+1;
			pre = len;
		}
		/*for (auto it : mp) {
			cout << it.first << " " << it.second << endl;
		}*/
		for (auto it : mp) {
			if (it.first>n||a[it.first] != it.second) {
				f = 1;
				break;
			}
		}
		if (f == 1) {
			cout << "NO" << endl;
		}
		else
			cout << "YES" << endl;
	}
}

D. Ice Cream Balls

D. Ice Cream Balls

题目大意

给定一个集合，给定一个数n，求得到n种无序二元关系所需要的集合元素的最少数量。即{1，2}、{2，1}视为一种二元关系。

思路

给一个集合
{1，2，3，4}，可以组成的二元关系如下：

• {1，2}、{1，3}、{1，4}、{2，3}、{2，4}、{3，4} 一共6种，不难看出是C（4，2） 的排列组合关系。

而{1，1，2，3，4} 比上面多了一组{1，1}
{1，1，2，2，3，4} 比上面多了两组{1，1}、{2，2}
所以只要求出得到最接近n种无序关系的不同元素的数量s，然后再和n做差，将得到的差加到s种就可以得到结果。即s+n-(s-1)*s/2。
寻找不同元素数量的过程可以用二分查找来完成。注意二分边界。

AC代码

#include<iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
bool che(ull x, ull n) {
	if (x * (x - 1) >= 2 * n) return false;
	else
		return true;
}
ull check(ull n) {
	ull l = 2; ull r = 2e9+10;
	ull res = 0;
	while (l < r) {
		ull mid = (l + r) >> 1;
		if (che(mid, n)) {
		//	res = mid;
			l = mid+1;
		}
		else
			r = mid;
	}
	ull tmp = ((l -1) * l) / 2;
	//cout << tmp << endl;
	/*ull cha =n-tmp;
	cout << cha << endl;*/
	if (tmp == n) {
		return l;
	}
	else {
		ull p = l - 1; ull s = p * (p - 1) / 2;
	//	cout << s << endl;
		return p+n - s;
	}
}
int main() {
	int t; cin >> t;
	while (t--) {
		ull n; cin >> n;
		if (n == 1) {
			cout << "2" << endl;
			continue;
		}
		ull p=check(n);
		cout << p << endl;
	}
}

E. Kolya and Movie Theatre

E. Kolya and Movie Theatre

题目大意

思路

分析可知，当第i天最后一次去电影院是，减去的数大小为 i*d，所以可以枚举最后一次去电影院是哪一天，这里就是核心，剩下的用单增优先队列或者multiset处理就好，维护队列大小为m。队满后如果队头小于当前元素，就弹出队头，压入当前元素，这样可以保证每次更新都是最优的。

AC代码

#include<iostream>
#include<set>

using namespace std;
const int M = 2e5 + 5;
typedef long long ll;
ll a[M];
multiset<ll> p;
void sove() {
	p.clear();
	ll n, m, d; cin >> n >> m >> d;
	ll sum = 0; ll ans = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		if (a[i] > 0 && p.size() < m) {
			p.insert(a[i]);
			sum += a[i];
			
		}
		else if (p.size() >= m && *p.begin() < a[i]) {
			sum -= *p.begin();
			p.erase(p.begin());
			sum += a[i];
			p.insert(a[i]);
		}
		ans = max(ans, sum - i * d);
	}
	cout << ans << endl;
}

int main() {
	int t; cin >> t;
	while (t--) {
		sove();
	}
}

F. Magic Will Save the World

F. Magic Will Save the World

题目大意

一个魔法师，每秒钟可以恢复w个单位的水魔法和f个单位的火魔法，有n个怪，每个怪都有血量，求魔法师最少多久消灭所有的怪。

思路

** 后面补上，先上代码**

AC代码

#include<iostream>
#include<bitset>
using namespace std;
typedef long long ll;
int s[105];
int pre[105];
const int M = 1e6 + 10;
bitset<M> bt;
int main() {
	int t; cin >> t;
	while (t--) {
		int w, f; cin >> w >> f;
		int n; cin >> n;
		int num = 0;
		bt.reset();
		bt[0] = 1;
		for (int i = 1; i <= n; i++) {
			cin >> s[i];
			bt |= bt << s[i];
			num += s[i];
		}
	//	ll bitn=toBit(n);
	//	cout << bitn << endl;
		int ans = 0x3f3f3f3f;
		for (int i = 0; i <= num; i++)
			if(bt[i]){
			//	cout << "sumw  " << sumw << endl;
				int p1 = num - i;
			//	cout << p3 << endl;
				ans = min(ans, max((i+w-1)/w,(p1+f-1)/f));

			}
		cout << ans << endl;
	}
}