一直不会 E 这种题，看到就晕，没想到 F 是个简单题[疑问]
A.Grasshopper on a Line
题目描述：
给定两个整数 \(x\) 和 \(k\)。蚂蚱从 \(0\) 点出发，沿着数轴上的 \(OX\) 轴进行跳跃，每次可以向左或向右跳跃一定距离（距离必须为整数），但是不能跳到距离为 \(k\) 的整数倍的位置上。
请你计算蚂蚱到达位置 \(x\) 最少需要多少次跳跃，并输出蚂蚱的跳跃方案。如果有多种方案，请输出其中任意一种。
题目分析：
考虑 \(p\) 和 \(p-1\) 一定互质，也就是至少有一个不是 \(k\) 的倍数。
所以如果可以直接跳到 \(x\) 就跳，否则就先跳到 \(x-1\) 再跳到 \(x\)
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int T;scanf("%d",&T);
while(T--){
int x,k;scanf("%d%d",&x,&k);
if(x % k == 0){
printf("2\n");
printf("%d\n%d\n",x-1,1);
}
else printf("1\n%d\n",x);
}
return 0;
}
B.Comparison String
题目描述：
- 给你一个长度为 \(n\) 的由 < 和 > 构成的字符串 \(s\)，如果一个数列 \(a\) 能满足将字符串 \(s\) 的所有大于号和小于号按顺序填入后满足大小关系，则 \(a\) 数列和 \(s\) 字符串是“相容的”。
- 定义一个数列的花费是这个数列中不同元素的数量。
- 已知字符串 \(s\)，让你求出与 \(s\) 相容的所有数列中花费最小的数列的花费。
题目分析：
考虑对于一个极长的 \(<\) 设其长度为 \(len\)，则至少需要 \(len+1\) 的花费。
而对于中间出现一个 \(>\) 的极长的 \(<\) 段，我们可以从 \(>\) 处劈开，因为我们一定可以通过一些手段让他们尽量地对应位置相等。
所以就扫一遍求出连续的 \(<\) 和 \(>\) 的最大长度，然后取 \(\max\) 就好。
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
char s[N];
int main(){
int T;scanf("%d",&T);
while(T--){
int n;scanf("%d",&n);
scanf("%s",s+1);
int ans = 1,tot = 1;
for(int i=2; i<=n; i++){
if(s[i] == s[i-1]) ++tot,ans = max(ans,tot);
else tot = 1;
}
printf("%d\n",ans+1);
}
return 0;
}
C.Best Binary String
题目描述：
给定由 1 0 ? 所组成的字符串，你需要用 0 或 1 替换 ?。
我们将 \(s_{l},s_{l+1},\dots,s_r\) 反转成为一次操作。
你要使通过“反转”操作使原字符串成为升序的操作次数尽可能的小。
问最终构造出的字符串，有多解输出其一。
题目分析：
其实问号完全可以不考虑，因为我们可以让问号全部变成某个与它相连的数，这样只需要在翻转对应数的时候把问号段也翻转就好了。
而最小的操作次数必然不少于忽略所有问号时的操作次数，所以这种做法就是正确的。
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
char s[N];
int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%s",s+1);
s[0] = '0';
int n = strlen(s+1);
for(int i=1; i<=n; i++){
if(s[i] == '?') s[i] = s[i-1];
}
for(int i=1; i<=n; i++) printf("%c",s[i]);
printf("\n");
}
return 0;
}
D.Bracket Coloring
题目描述：
如果一个括号序列符合以下两个条件中的一个，那么它是优美的：
1、序列的任意一个前缀中，左括号的个数不少于右括号的个数，且整个序列中，左括号的个数等于右括号的个数。
2、序列的任意一个前缀中，右括号的个数不少于左括号的个数，且整个序列中，左括号的个数等于右括号的个数。
给定一个括号序列，你需要把它分成若干组，使得每一组的括号构成的序列都是优美的。求最少需要分成多少组，并输出分组方案。如果无解，输出 $ -1 $。
题目分析：
首先条件其实就是要么正常的括号匹配可以执行，要么全部取反后正常的括号匹配可以执行。
显然若原串中左括号右括号数量不等则无解。
可以发现如果我们按照正常的括号匹配匹配一遍，将匹配上的化为一组，没匹配的上的化为另一组这样一定是合法的。
因为考虑对于没匹配上的一定是形如 ))))...((((...，因为此时它的左右括号数相等所以取反后一定可以匹配上。
这样就是考虑怎么判断答案为 \(1\) 的情况，要么此时可以完全匹配，要么全部取反后可以完全匹配。
写写分讨这个题就做完了。
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
char s[N];
int bl[N];
bool flag[N];
int main(){
int T;scanf("%d",&T);
while(T--){
int n;scanf("%d",&n);
scanf("%s",s+1);
int tot1 = 0,tot2 = 0;
for(int i=1; i<=n; i++){
if(s[i] == '(') tot1++;
else tot2++;
}
if(tot1 != tot2){
printf("-1\n");
continue;
}
stack<pair<char,int> > st;
while(!st.empty()) st.pop();
for(int i=1; i<=n; i++){
if(!st.empty() && st.top().first == '(' && s[i] == ')'){
st.pop();
}
else st.push({s[i],i});
}
if(st.empty()){
printf("1\n");
for(int i=1; i<=n; i++) printf("%d ",1);
printf("\n");
continue;
}
for(int i=1; i<=n; i++) s[i] = s[i] == '(' ? ')' : '(';
while(!st.empty()) st.pop();
for(int i=1; i<=n; i++){
if(!st.empty() && st.top().first == '(' && s[i] == ')'){
st.pop();
}
else st.push({s[i],i});
}
if(st.empty()){
printf("1\n");
for(int i=1; i<=n; i++) printf("%d ",1);
printf("\n");
continue;
}
else{
while(!st.empty()){
flag[st.top().second] = true;
st.pop();
}
for(int i=1; i<=n; i++){
if(flag[i]) bl[i] = 1;
else bl[i] = 2;
}
printf("2\n");
for(int i=1; i<=n; i++) printf("%d ",bl[i]);
}
for(int i=1; i<=n; i++) flag[i] = false;
}
return 0;
}
E.Playoff Fixing
题目描述：
有 \(2^n\) 个人参加淘汰赛，每场位置相邻的两个人比，编号小者获胜，现在固定若干位置上的人，求在其余位置放人使得以下条件满足的方案数：
- 编号位于 \([2^i,2^{i+1}-1](i \in [0,n-1])\) 的人的排名为 \(i+1\)
形象一点就是排名按编号单调不升。
题目分析：
显然要先将他们 PK 的过程表示出来，就是形如一个二叉树的结构。
我们考虑从上到下确定位置，这样就好做很多。
若没有位置固定人，假设考虑到了第 \(i\) 层，也就是我们已经确定了 \(2^{i-1}\) 个人，要新放 \(2^{i-1}\) 个人，则贡献即：
\(2^{i-1}! \times (2^{2^{i-1}})\)，就是每个人可以任意的位置，每一个 PK 的两个人可以任意换位。
这样的话直接乘法原理就是答案了。
如果有位置固定的，就分别看看对这两个的指数产生什么影响就好了。
代码：
点击查看代码
#include<bits/stdc++.h>
#define up(l, r, i) for(int i = l, END##i = r;i <= END##i;++ i)
#define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
using namespace std;
typedef long long i64;
const int INF = 2147483647;
int qread(){
int w = 1, c, ret;
while((c = getchar()) > '9' || c < '0') w = (c == '-' ? -1 : 1); ret = c - '0';
while((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + c - '0';
return ret * w;
}
const int MAXN = (1 << 19) + 3;
const int MOD = 998244353;
int F[MAXN], G[MAXN];
int solve(vector <int> V){
if(V.size() == 1) return 1;
int ret = 1, n = V.size(), t = n / 2;
int c = 0, d = n / 2, e = 0;
vector <int> T;
up(0, n - 1, i) d -= (V[i] > t);
up(0, n / 2 - 1, i){
int p = 2 * i;
int q = 2 * i + 1;
if(V[p] != -1 && V[q] != -1){
if((V[p] <= t) == (V[q] <= t))
return 0;
}
{
if(V[p] == -1 && V[q] == -1) ++ c;
if(V[p] != -1 && V[p] <= t) T.push_back(V[p]); else
if(V[q] != -1 && V[q] <= t) T.push_back(V[q]); else
T.push_back(-1);
}
}
return 1ll * G[c] * F[d] % MOD * solve(T) % MOD;
}
int main(){
int k = qread(); vector <int> P;
G[0] = F[0] = 1;
up(1, 1 << k, i)
G[i] = 1ll * G[i - 1] * 2 % MOD,
F[i] = 1ll * F[i - 1] * i % MOD;
up(1, 1 << k, i) P.push_back(qread());
printf("%d\n", solve(P));
return 0;
}
F.Editorial for Two
题目描述：
给定一个长度为 $ n $ 的序列，从中找出一个长度为 $ k $ 的子序列（可以不连续），然后将这个子序列划分为前后两部分，使得前半部分元素和与后半部分元素和的 $ \max $ 最小。输出这个最小值。
题目分析：
既然是最大值最小首先考虑二分答案。
二分答案之后可以发现这个前后的分界点很重要，就枚举这个分界点，然后就是记录 \(f[i][j]\) 表示前 \(i\) 个数选择 \(j\) 个使得它们的和小于等于 \(mid\) 是否可行，\(g[i][j]\) 表示 \(i\) 这个后缀选择 \(j\) 个使得它们的和小于等于 \(mid\) 是否可行，然后统计答案就是卷起来。
会发现我们每一个 \(dp\) 值只记一个 0/1 实在是太亏了，就多记一点东西，也就是设 \(f[i]\) 表示前 \(i\) 个数为了使得和小于等于 \(mid\) 最多选择多少个数，\(g[i]\) 同理。
这样只需要判断 \(f[i] + g[i+1]\) 是否大于等于 \(k\) 即可。
对于 \(f,g\) 数组的处理可以直接贪心。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5+5;
int n,k,f[N],g[N],a[N];
bool chk(int mid){
priority_queue<int> q;
int sum = 0;
for(int i=1; i<=n; i++){
q.push(a[i]);sum += a[i];
while(sum > mid){
sum -= q.top();q.pop();
}
f[i] = q.size();
}
while(!q.empty()) q.pop();
sum = 0;
for(int i=n; i>=1; i--){
q.push(a[i]);sum += a[i];
while(sum > mid){
sum -= q.top();q.pop();
}
g[i] = q.size();
}
bool flag = false;
for(int i=0; i<=n; i++){
if(f[i] + g[i+1] >= k) flag = true;
}
for(int i=1; i<=n; i++) f[i] = g[i] = 0;
return flag;
}
signed main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int T;scanf("%lld",&T);
while(T--){
scanf("%lld%lld",&n,&k);
for(int i=1; i<=n; i++) scanf("%lld",&a[i]);
int l = 0,r = 1e15,ans = 0;
while(l <= r){
int mid = (l + r) >> 1;
if(chk(mid)) ans = mid,r = mid - 1;
else l = mid + 1;
}
printf("%lld\n",ans);
}
return 0;
}
- 题解 Educational Codeforces Round 1837题解educational codeforces round educational codeforces round rated educational codeforces round 151 construction educational codeforces round educational codeforces round 147 cf-educational educational codeforces round educational codeforces round 158 educational codeforces contest round educational codeforces monsters round educational codeforces together round