CF1617B Madoka and the Elegant Gift、CF1654C Alice and the Cake、 CF1696C Fishingprince Plays With Arr

记录一些一开始没想到正解的氵题

cf1617B

Madoka and the Elegant Gift

Problem - 1647B - Codeforces

 

 题目大意是说图中最大的黑色矩形区域没有交叉的就输出yes，否则输出no

分析：

一开始看到这个题还想着用bfs搜索一下，找到每个1区域的最左、最右、最上、最下的位置，然后判断这个区域里是否有0，但是这样的话太复杂了，不像是一个1200分的题的做法

然后发现是把矩形细化，找每个2*2矩形，如果有任何一个2*2矩形中含有3个1，一个0，就不符合题意，输出no，否则输出yes

比较简单，不贴代码了

CF1654C

 Alice and the Cake

Problem - C - Codeforces

错误的写法：

一开始思路是，先把所有的相加，求出总和sum，把a[i]存入set，用map数组记录每个a[i]数量，再用queue存sum，逐次分解，每次分解为a,b；若a,b是a[i[中的元素，就删除，否则再分解；分解到最后如果分解为1且set中没有一，就说明不可能分解成功，反之可以成功。

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <map>
#include <stack>
#include <vector>
#include <queue>
#include <set>
#define bug(x) cout<<#x<<"=="<<x<<endl
#define memset(x) memset(x,0,sizeof(x))
#define lowbit(x) x&(-x)
#define INF 0x7fffffff
#define inf 0x3f3f3f3f
#define pi acos(-1)
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int, int> PII;
#define int long long
void clear(queue<int>& q) {queue<int> empty;swap(empty, q);}
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;
}

int T;
set<int>s;
map<int, int>num;
signed main()
{
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		int sum = 0;
		for (int i = 1; i <= n; i++) {
			int x;
			cin >> x;
			sum += x;
			s.insert(x);
			num[x]++;
		}
		queue<int>q;
		q.push(sum);
		int f = 1;
		while (!q.empty()) {
			int t = q.front();
			q.pop();
			if (s.find(t) == s.end()) {
				if (t == 1) { f = 0; break; }
				int a = ceil(1.0*t / 2);
				q.push(a);
				int b = floor(1.0*t / 2);
				q.push(b);
			}
			else {
				num[t]--;
				if (!num[t]) s.erase(t);
			}
			
		}
		//if(!q.empty())
		if (f) cout << "YES\n";
		else cout << "NO\n";
		num.clear();
		s.clear();
	}
	return 0;
}

但是这样写，喜提MLE

然后看了题解发现了更简便的做法

正确的做法：

仍然用map数组存入每个a[i]的数量，把所有a[i]的和sum存入set,逐次分解，如果分解到有和a[i]相同的，就erase掉，否则直接分解并存入set,注意因为题中只有n个数，所以最多分解n-1次，然后就可以跳出，最后判断set是否为空，如果可以分解成功的话，那set中的元素一定全被erase掉了，因此可以通过set是否为空来输出yes或no

void solve()
{
	int n; cin >> n;
	ll tot = 0;
	ll a[n + 1];
	map<ll, int> mp;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		tot += a[i];
		mp[a[i]]++;
	}

	multiset<ll> s;
	s.insert(tot); //初始状态

	for (int i = 0; i < n;)
	{
		if (s.empty()) break;
		ll t = *s.begin(); 
		if (mp[t] == 0)
		{
			s.erase(s.find(t));
			s.insert(t / 2);
			s.insert(t - t / 2);
			i++; //拆分次数++
		}
		else
		{
			s.erase(s.find(t));
			mp[t]--;
		}
	}
	cout << (s.empty() ? "YES\n" : "NO\n");
}
int main()
{
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
}

记录一下自己改bug的时的错误:set删除元素的时候删除的是对应下标的值，如果要删除set中的元素2，应该写成s.erase(s.find(2))，而不是s.erase(2)      (Ｔ▽Ｔ)

CF1696C

Fishingprince Plays With Array

Problem - C - Codeforces

题意：给出了两个序列，每次可以将序列中的任意一个数x拆成m个x/m；或将连续m个x变成m*x；

两个序列的最小拆分一定是相同的，用queue存最小拆分，因为拆分完后可能数量很大，所以用pair{x,cnt}存放拆之后数字和对应数量，每次拆到最小的数字如果和上一个拆的数字相同，就和上一次的合并。

int T;
int main()
{
	cin >> T;
	while (T--) {
		vector<pair<ll,ll> >a, b;
		int n, m;
		cin >> n >> m;
		for (int i = 1; i <= n; i++) {
			int x;
			cin >> x;
			int cnt = 1;
			while (x % m == 0) { cnt *= m; x /= m; }
			if (a.empty() || a.back().first != x) a.push_back({ x,cnt });
			else a.back().second += cnt;
		}
		int k;
		cin >> k;
		for (int i = 1; i <= k; i++) {
			int x;
			cin >> x;
			int cnt = 1;
			while (x % m == 0) { cnt *= m; x /= m; }
			if (b.empty() || b.back().first != x) b.push_back({ x,cnt });
			else b.back().second += cnt;
		}
		if (a == b) cout << "Yes\n";
		else cout << "No\n";
	}
	return 0;
}