A. Grasshopper on a Line
题意：给出n，k，从0开始，每次可以加一个数，最快到达n需要，输出首先跳几次，然后每次跳多少，限制只有一个跳的长度不能整除k。
分析：n%k，有余直接跳，没余数，先跳一个，再跳剩余的长度。
代码：
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int n, m, t, k;
void init() {}
void solve()
{
int a, b;
cin >> a >> b;
if (a % b == 0) {
printf("2\n");
printf("%d %d\n", 1, a-1);
}
else {
printf("1\n");
printf("%d\n", a);
}
}
int main()
{
init();
t = 1;
cin >> t;
while(t--)
solve();
return 0;
}
B. Comparison String
题意：给出n，n组，每组给出m，字符串str，m为str长度，str是一个仅包含'<','>'的字符串,要求填入数字，使得整个字符串合法，比如<<>>，1<2<3>2>1，其中数的类别最小为多少。
分析：求最长连续相同字符的长度+1即可。因为可以根据具体情况在范围内进行调节。
代码：
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int n, m, t, k;
string str;
void init() {}
void solve()
{
cin >> n >> str;
m = 0;
for (int i = 0; i < str.size(); i++) {
int j = i;
while(str[j] == str[i] && j + 1 < str.size()) j++;
if (str[j] == str[i]) {
m = max(j - i + 1, m);
break;
}
else {
m = max(j - i, m);
}
}
cout << m + 1 << endl;
}
int main()
{
init();
t = 1;
cin >> t;
while(t--)
solve();
return 0;
}
C. Best Binary String
题意：给出n，一下n组字符串，仅包含'?','0','1'的字符串，对'?'进行更改，可以替换为'0'或'1'，要求使得最后按非降序排序字符串所需的“反转字符串的任意连续子字符串”形式的最小操作次数。也就是最终变为一段0，,一段1的情况，可以进行任意区间的反转。
分析：如果最终一定要变成左0右1的情况，那么对于所有不合法的情况一定会翻转，对于0和1的交点一定最多只会留下一个点，那么，最左开始的连续'?'0比1好，因为可以不参与转化，最右开始的连续'?'，1比0好，对于中间的'?'，要跟两边的值相关联，都是0就改为0，都是1就改为1，否则0或1都可以。
代码：
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int n, m, t, k;
string str;
void init() {}
void solve()
{
cin >> str;
for (int i = 0; i < str.size(); i++) {
if (str[i] == '?') {
str[i] = '0';
} else {
break;
}
}
for (int i = str.size() - 1; i > 0; i--) {
if (str[i] == '?') {
str[i] = '1';
} else {
break;
}
}
for (int i = 0; i < str.size(); i++) {
if (str[i] != '?') continue;
int j = i;
while (j < str.size() && str[j] == '?') j++;
if (str[i-1] == str[j]) {
for (int k = i; k < j; k++) {
str[k] = str[j];
}
}
else {
for (int k = i; k < j; k++) {
str[k] = str[j];
}
}
}
cout << str << endl;
}
int main()
{
init();
t = 1;
cin >> t;
while(t--)
solve();
return 0;
}
D. Bracket Coloring
题意：给出n，以下n组，每组给出m，字符串str，为字符串的长度，字符串仅包含括号'(',')'，定义漂亮的字符串为，1.合法括号序列，2.每个括号进行反转后，')'与'('互换，变为合法括号序列。对str每一个字符进行染色，第一行输出k，表示染k个色，以下颜色仅包含1-k，第二行输出m个数，表示对该字符进行的染色值，要求使得每种颜色单独排列后是漂亮的字符串，颜色数尽量少，如果没有情况符合，输出-1.
分析：
对于漂亮的字符串这个定义来看，显然，左右括号数量必须相同，否则绝对不可能，直接输出-1即可，其次颜色数最多为2，为1的情况只需要对两种情况单判即可。将字符串中所有的合法括号序列选取后，一定为x个右括号，x个左括号，刚好是第二种情况。所以最多颜色数为2，就一定会符合要求。
合法括号序列的判断：初始定值n为0，遇到左括号+1，右括号-1，如果n为负数，那么该序列不合法。对于情况为2时的情况，如果遇到n为负数的时候，那么直接当做给第二种颜色，n归回0。继续算即可。
代码：
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
int n, m, t, k;
int s[N];
string str;
void init() {}
bool judge(string str) {
int bj = 0;
for (int i = 0; i < str.size(); i++) {
if (str[i] == ')') bj++;
else bj--;
if (bj < 0) return false;
}
return true;
}
void solve()
{
cin >> n >> str;
int a = 0, b = 0;
for (int i = 0; i < str.size(); i++) {
if (str[i] == '(') a++;
else b++;
}
if (a != b) {
cout << -1 << endl;
return;
}
if (judge(str)) {
cout << 1 << endl;
cout << 1;
for (int i = 1; i < str.size(); i++) {
cout << ' ' << 1;
} cout << endl;
return;
}
for (int i = 0; i < str.size(); i++) {
s[i] = 1;
}
a = 0, b = 0;
for (int i = 0; i < str.size(); i++) {
if (str[i] == '(') a++;
else a--;
if (a < 0) {
b++;
s[i] = 2;
a = 0;
}
}
for (int i = str.size() - 1; i > 0 && b > 0; i--) {
if (str[i] == '(') {
s[i] = 2;
b--;
}
}
a = 0;
for (int i = 0; i < str.size(); i++) {
if (s[i] == 2) {
a = 1;
}
}
if (a == 0) cout << 1 << endl;
else cout << 2 << endl;
cout << s[0];
for (int i = 1; i < str.size(); i++) {
cout << ' ' << s[i];
}
cout << endl;
}
int main()
{
init();
t = 1;
cin >> t;
while(t--)
solve();
return 0;
}
E. Playoff Fixing
题意：给出k，然后给出\(2^{k}\) 个数，为1到\(2^{k}\),这些数有些未知, 给出-1表示, 每次奇数位置的值跟其后面偶数位置的值比较，小的胜，要求最终每次都是后一半的数淘汰，比如 k=2 1，3，4，2，第一次1和3比，4和2比，3,4淘汰，第二次1和2比，2淘汰。对于未知的数，可以任意给定数值，问最终有多少种合法情况。考虑到情况过多，取模998244353。如果没有任何情况输出-1.
分析：
1.取模了，直接定为long long，防止中途爆int的问题。
2.考虑转化，如果我们有一种方法可以将\(2^{k}\)操作一段后，变成\(2^{k-1}\)，那么迭代后，最终会变成\(2^{0}\)，就会非常简单了。
3.如何转化呢，\(2^{k}\)个人与\(2^{k-1}\)个人有什么区别呢，显然操作就是后者在转化中淘汰掉后一半的人了。
4.因为每次比较是两两比较，所以我们也一样是两两比较获取下一阶段的情况的。
5.对于两个数值的情况:
(1).如果两个数都给出，且都是后一半，那么绝对不合法，输出-1。
(2).如果两个数都给出，但都不是后一半，那么也绝对不合法，输出-1。
(3).如果有一个数是后一半，那么无条件将第二个数留给下一轮。就算有不合法那也是之后的轮数了。
(4).如果有两个数是未知，都是-1，那么就要在这里进行选定放值，有两种情况，所以ans2，值可以放后一半的任意情况，要预先统计当轮有多少可以放置的后一半数记作cnt，放置一个少一个，所以anscnt，过程中要记得取模。
(5).如果只有一个数值未知，那么一种情况可以选，所以只进行ans*cnt的操作。
6.所有轮数统计完后得到答案。中途不合法直接输出-1并退出。
代码：
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10, mod = 998244353;
int n, m, t, k;
int s[N];
long long answer;
string str;
vector<int> vec;
void init()
{
s[0] = 1;
for (int i = 1; i < 21; i++) {
s[i] = s[i-1] * 2;
}
}
bool judge(string str) {
int bj = 0;
for (int i = 0; i < str.size(); i++) {
if (str[i] == ')') bj++;
else bj--;
if (bj < 0) return false;
}
return true;
}
long long sol(int k) {
long long cnt = 1;
if (k > 0) cnt = 1 << (k - 1);
if (k > 0)
for (int i = 0; i < 1 << k; i += 1) {
if (vec[i] > s[k - 1]) {
cnt --;
}
}
long long ans = 1;
vector<int> vec1;
for (int i = 0; i + 1 < 1 << k; i += 2) {
long long a = vec[i], b = vec[i + 1];
if (a > s[k - 1] && b > s[k - 1]) return -1;
if (a > s[k - 1]) {
vec1.push_back(b);
}
else if (b > s[k - 1]) {
vec1.push_back(a);
}
else if (a == -1 && b == -1) {
vec1.push_back(-1);
ans = ans * 2 * cnt % mod;
cnt--;
}
else if (a == -1) {
vec1.push_back(b);
ans = ans * cnt % mod;
cnt--;
} else if (b == -1) {
vec1.push_back(a);
ans = ans * cnt % mod;
cnt--;
} else {
return -1;
}
}
vec.swap(vec1);
return ans;
}
void solve()
{
cin >> n;
for (int i = 0; i < 1 << n; i++) {
cin >> m;
vec.push_back(m);
}
answer = 1ll;
for (int i = n; i >= 0; i--) {
long long a = sol(i);
if (a == -1) {
cout << 0 << endl;
return;
}
answer = answer * a % mod;
}
cout << answer << endl;
}
int main()
{
init();
t = 1;
while(t--)
solve();
return 0;
}
F. Editorial for Two
题意：给出n，k，第二行给出n个数，从n个数中选取k个数，顺序不变，对于这k个数进行截断，分为左右两部分，其中一部分的数量可以为0，求左右两部分的数值和最大的最小值。
分析：
我的思路(错误)
优先取小，但是盲猜取得的一定是小的，不会有一个特别大的存在，所以sort后，找到第k个的值，就可以知道标准线了，算一波答案，如果多的话，两边哪个大，删那边的最大值，依次删除，错掉了，
wa示例：
4 3
1 2 1 2
答案是2，选择选到了左边1 2，右边1 2，没有办法降到2，输出答案是3.
大佬的思路（ilyushaa）排行榜第一，从读题到a题，只有8分钟，tql
二分答案
l[i]表示算出从第1个数到第i个数中，不超过ans的最大数量，放入到优先队列中，维护最大值，每次到第i个数，就将这个数加入到优先队列里，并保存总和，如果已经超过二分的答案ans后，那么就从优先队列中找到当前最大值，然后减掉，因为之前合法，是加入当前值后超过ans的，所以理论上最多只会抛出一次。用while或者if都是可以的。
那么正着推，求出从第1个数到第i个数不超过ans的最大数量，反着推，求出第i个数到第n个数不超过ans的最大数量，只需要遍利一遍,去查是否存在l[i]+r[i+1]\(\geq\)k的情况，也就是枚举切割点，就可以知道当前n个数，是否可以组合成答案不超过ans，且加起来数量大于等于k的情况了，有返回true，无返回false。
代码：
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <map>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <list>
#include <cmath>
#define x first
#define y second
#define MAX(a,b,c) max(max(a, b),c)
#define MIN(a,b,c) min(min(a, b),c)
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
template<class T, class T1>
void print(const T &vec, T1 it)
{
for (; it != vec.end(); it++)
{
if (it != vec.begin()) cout << ' ';
cout << (*it);
}puts("");
}
typedef long long ll;
typedef pair<int, int> PII;
const int N = 2e6 + 10, mod = 998244353;
int n, m, t, k;
long long s[N], dp[N], h[N], g[N];
long long answer = 0;
vector<int> vec;
map<int, int> ma;
vector<int> ans;
string str, str1;
stack<int> sta;
PII p[N];
queue<int> q;
//int ans;
void init()
{
}
bool check(ll mid) {
ll sum = 0;
priority_queue<int> q;
vector<int> cnt(n+1);
for (int i = 1; i <= n; i++){
q.push(s[i]);
sum += s[i];
while (sum > mid)
{
sum -= q.top();
q.pop();
}
cnt[i] = q.size();
}
sum = 0;
priority_queue<int>().swap(q);
for (int i = n; i >= 1; i--) {
q.push(s[i]);
sum += s[i];
if (sum > mid) {
sum -= q.top();
q.pop();
}
if (q.size() + cnt[i - 1] >= k) {
return true;
}
}
return false;
}
void solve()
{
ans.clear();
cin >> n >> k;
long long sum = 0;
for (int i = 1; i <= n; i++) {
cin >> s[i];
sum += s[i];
}
ll l = 0, r = sum;
while (l < r) {
ll mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
cout << r << endl;
}
int main()
{
init();
t = 1;
cin >> t;
while(t--)
solve();
return 0;
}
- Educational Codeforces Round Rated 149educational codeforces round rated round codeforces rated based 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