Codeforces Round 866 (Div. 2)(A - D)

Dashboard - Codeforces Round 866 (Div. 2) - Codeforces

A. Yura’s New Name（思维）

思路：枚举每个下划线 ， 计算其前后需要补齐的 ‘^’ 个数 ， 注意特判样例四的特殊情况。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int n , t;
string s;signed main(){IOScin >> t;while(t --){cin >> s;n = s.size();int res = 0;if(s == "^") res += 1;for(int i = 0 ; i < n ; i ++){if(s[i] == '_'){if(i == 0) res += 1;else{if(s[i - 1] == '_') res += 1;}}}if(s[n - 1] == '_') res += 1;cout << res << "\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

B. JoJo’s Incredible Adventures（思维）

思路：手模一下可以发现 ，全是 1 的时候 ， 答案就是 n * n ， 当不全是 1 的时候 ， 需要找到环上最长的连续 1 的个数 ， 假设为 y ， 答案就是 1 * y ， 2 * (y - 1) , …… , (y - 1) * 2 , y * 1 里面最大的。把环复制两边断环为链。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int t , n;
string s;bool judge(string s){for(int i = 0 ; i < n ; i ++) if(s[i] == '0') return 0;return 1;
}signed main(){IOScin >> t;while(t --){cin >> s;n = s.size();int maxx = 0;int res = 0;if(judge(s)){res = n * n;}else{s = s + s;for(int i = 0 ; i < 2 * n ; i ++){if(s[i] == '0') s[i] = ' ';}stringstream cin(s);while(cin >> s){int now = s.size();maxx = max(maxx , now);}for(int i = 1 ; i <= maxx ; i ++){res = max(res , i * (maxx - i + 1));}	}cout << res << "\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

C. Constructive Problem（思维）

思路：这题的样例给的很全 ， 手摸一下就能出来做法 ， 首先求出当前序列的 mex ， 假设为 x， 我们操作完之后序列的 mex 变成 x + 1 。我们分两种情况 ： 第一种 ：序列中原本有 x + 1 ， 我们就要贪心的把含有 x + 1 的最小区间推平 ， 然后检查操作后的 mex 是否是 x + 1 即可。第二种 ：序列中没有 x + 1 ， 这时候我们需要找一个不影响组成原来 mex 的元素进行推平 ， 比如 0 1 1 2 2 4 5 ，012是影响 mex 的元素 ， 多出来的 1245 显然对于 mex 没影响 ， 选择一个执行区间推平操作即可。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int t , n;
int a[N];signed main(){IOScin >> t;while(t --){cin >> n;map<int , int>mp;int res = 0;for(int i = 1 ; i <= n ; i ++) cin >> a[i] , mp[a[i]] = 1;for(int i = 0 ; ; i ++) if(mp[i] == 0){res = i;break;} res += 1;bool tag = 0;if(mp[res]){int l = 0 , r = 0;for(int i = 1 ; i <= n ; i ++) if(a[i] == res){l = i;break;}for(int i = n ; i >= 1 ; i --) if(a[i] == res){r = i;break;}for(int i = l ; i <= r ; i ++) a[i] = res - 1;mp.clear();for(int i = 1 ; i <= n ; i ++) mp[a[i]] = 1;int ans = 0;for(int i = 0 ; ; i ++) if(mp[i] == 0){ans = i;break;} if(res == ans) tag = 1;}else{int need = n - (res - 1);if(need) tag = 1;}if(tag) cout << "YES\n";else cout << "NO\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

D. The Butcher（思维 + 模拟）

思路：对于每一个矩形 ， 面积是确定的 ， 且第一次切割的时候横切还是竖切 ， 原本矩形另一维度的值会保留。我们求出切割后矩形长宽两个维度的最值 ， 这样就能得出两组答案。(maxh , area / maxh) , (area / maxw , maxw). 现在只需要验证这两组答案即可。验证的过程就是模拟切割的过程 ， 我们每次切割过后 ， 当前矩形的一个长 / 宽 是会保留下来的 ， 并且是剩余中最大的那个 ， 用优先队列分别维护最大的 长 / 宽 ，这样我们就能确定每一步切割的是哪个块。

复杂度 nlogn

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int t , n ;
int area;
int a[N] , b[N];
bool vis[N];
int h , w;
set<PII>ans;void solve(int x , int y){int now_h = x , now_w = y;if(x * y != area) return ;for(int i = 1 ; i <= n ; i ++) vis[i] = 0;priority_queue<PII , vector<PII> , less<PII>> hx , wx;for(int i = 1 ; i <= n ; i ++){hx.push({a[i] , i});wx.push({b[i] , i});}for(int i = 1 ; i <= n ; i ++){while(vis[hx.top().se]) hx.pop();while(vis[wx.top().se]) wx.pop();int pos = -1;if(hx.top().fi == x) pos = hx.top().se;if(wx.top().fi == y) pos = wx.top().se;if(pos == -1) return ;if(hx.top().fi == x){y -= b[pos];}else{x -= a[pos];}vis[pos] = 1;}if(!(x * y)) ans.insert({now_h , now_w});
}signed main(){IOScin >> t;while(t --){cin >> n;area = 0;for(int i = 1 ; i <= n ; i ++){cin >> a[i] >> b[i];area += a[i] * b[i];}h = *max_element(a + 1 , a + 1 + n);w = *max_element(b + 1 , b + 1 + n);solve(h , area / h);solve(area / w , w);cout << ans.size() << "\n";for(auto [x , y] : ans) cout << x << " " << y << "\n";ans.clear();}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);