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

Record some problems you didn't expect to solve at the beginning

cf1617B

Madoka and the Elegant Gift

Problem - 1647B - Codeforces

 

  The main idea of the title is that the largest black rectangular area in the figure is output without crossing yes, Otherwise output no

analysis ：

At first, I saw this problem and wanted to use bfs Search for , Find each 1 The leftmost part of the area 、 The most right 、 At the top 、 The lowest position , Then judge whether there is 0, But such words are too complicated , It's not like a 1200 The practice of dividing questions

Then I found that it is to refine the rectangle , Find each 2*2 rectangular , If there is any one 2*2 Rectangle contains 3 individual 1, One 0, It doesn't accord with the meaning of the question , Output no, Otherwise output yes

Relatively simple , No more code

CF1654C

 Alice and the Cake

Problem - C - Codeforces

The wrong way to write ：

At first, the idea was , First add up all , Find the sum sum, hold a[i] Deposit in set, use map The array records each a[i] Number , Reuse queue save sum, Successive decomposition , Each decomposition is a,b; if a,b yes a[i[ The elements in , Just delete , Otherwise, it will be decomposed ; In the end, if it is decomposed into 1 And set None of them , It means that it is impossible to decompose successfully , On the contrary, it can succeed .

#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;
}

But write like this , Hi Ti MLE

Then I read the solution and found a simpler way

The right way ：

Still use map The array is stored in each a[i] The number of , Put all the a[i] And sum Deposit in set, Successive decomposition , If it is decomposed to have and a[i] same , Just erase fall , Otherwise, it is directly decomposed and stored set, Note that there is only n Number , So at most n-1 Time , Then you can jump out , Finally, judge set Is it empty , If it can be decomposed successfully , that set All the elements in must be erase It fell off , So you can use set Whether it is empty to output yes or 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); // The initial state 

	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++; // Number of splits ++
		}
		else
		{
			s.erase(s.find(t));
			mp[t]--;
		}
	}
	cout << (s.empty() ? "YES\n" : "NO\n");
}
int main()
{
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
}

Record your changes bug The error of time :set When deleting an element, you delete the value of the corresponding subscript , If you want to delete set The elements in 2, Should be written as s.erase(s.find(2)), instead of s.erase(2)      (Ｔ▽Ｔ)

CF1696C

Fishingprince Plays With Array

Problem - C - Codeforces

The question ： Two sequences are given , You can set any number in the sequence x Split into m individual x/m; Or will continue m individual x become m*x;

The minimum split of two sequences must be the same , use queue Save the minimum split , Because there may be a large number after splitting , So use pair{x,cnt} Store the numbers and corresponding quantities after disassembly , If the smallest number is the same as that of the previous one , Just merge with the last one .

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;
}