2022.11.18 模拟赛小结
目录成天写ODT，然后T2想了半天怎么维护，死活没往ODT上想，身败名裂了身败名裂了身败名裂了。。
更好的阅读体验戳此进入
赛时思路
T1
原题 LG-P1136 迎接仪式。
存在仅包含 j 和 z 的字符串，可以最多 $ k $ 次每次交换任意位置的两个字符，最大化最终串里 jz 子串的数量，求最大值。
想了半天然后糊了个贪心，这个贪心正常应该能过 $ 80% $ 以上的点，然后因为我写挂了。。。一遍过大样例就没拍，赛后测了一下，如果对拍一下把贪心调成我预期的贪心是应该能过一大半的。。
嗯最后 $ 80\texttt{pts} \rightarrow 10\texttt{pts} $。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
using namespace std;
// using namespace __gnu_pbds;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
template< typename T = int >
inline T read(void);
int N, K;
int cntj(0), cntz(0);
int cnt2j(0), cnt2z(0);
int ans(0);
// string S;
basic_string < char > a, b;
int main(){
freopen("string.in", "r", stdin);
freopen("string.out", "w", stdout);
N = read(), K = read();
if(N == 1)printf("0\n"), exit(0);
for(int i = 1; i <= N; ++i){
char c = getchar(); while(c != 'j' && c != 'z')c = getchar();
a += c;
}
for(auto it = a.begin(); it != a.end(); ++it){
if(it == prev(a.end())){b += *it; continue;}
// if(*it == 'j' && *next(it) == 'j')++cntj;
// else if(*it == 'z' && *next(it) == 'z')++cntz;
// else if(*it == 'z' && *next(it) == 'j')++cntz;
// else
if(*it == 'j' && *next(it) == 'z')++ans, advance(it, 1), b += '*';
else b += *it;
}a.clear(); a.swap(b);
for(auto it = a.begin(); it != a.end(); ++it){
if(it == prev(a.end())){*it == 'j' ? ++cntj : ++cntz; continue;}
if(*it == 'j' && *next(it) == 'j')++cnt2j, advance(it, 1);
else if(*it == 'z' && *next(it) == 'z')++cnt2z, advance(it, 1);
else if(*it == 'z' && *next(it) == 'j')++cntz;
else if(*it == 'j' && *next(it) == 'z')++ans, advance(it, 1);
}
while(K && cnt2j && cnt2z)--cnt2j, --cnt2z, --K, ans += 2;
cntj += cnt2j * 2, cntz += cnt2z * 2;
ans += min({cntj, cntz, K});
// for(auto it = a.begin(); it != a.end(); ++it){
// if(it == prev(a.end())){b += *it; continue;}
// // if(*it == 'j' && *next(it) == 'j')++cntj;
// // else if(*it == 'z' && *next(it) == 'z')++cntz;
// // else if(*it == 'z' && *next(it) == 'j')++cntz;
// // else
// if(*it == 'j' && *next(it) == 'z')++ans, advance(it, 1), --cntj, --cntz;
// else b += *it;
// a.clear();
// a.swap(b);
// }
// while(K && cntj >= 1 && cntz >= 1){
// for(auto it = a.begin(); it != a.end(); ++it){
// if(it == prev(a.end())){b += *it; continue;}
// // if(*it == 'j' && *next(it) == 'j')++cntj;
// // else if(*it == 'z' && *next(it) == 'z')++cntz;
// // else if(*it == 'z' && *next(it) == 'j')++cntz;
// // else
// if(*it == 'j' && *next(it) == 'z')++ans, advance(it, 1), --cntj, --cntz;
// else b += *it;
// a.clear();
// a.swap(b);
// }
// }
// cin >> S;
// auto lst = S.begin();
// for(auto cur = next(S.begin()); cur != S.end(); ++cur, ++lst){
// if(*lst == 'j' && *cur == 'j')++cntj;
// else if(*lst == 'z' && *cur == 'z')++cntz;
// else if(*lst == 'z' && *cur == 'j')++cntz;
// else if(*lst == 'j' && *cur == 'z'){
// ++ans;
// advance(lst, 1), advance(cur, 1);
// if(cur == S.end() || lst == S.end())break;
// }
// }
// if(!(*prev(S.end()) == 'z' && *prev(S.end(), 2) == 'j'))
// *prev(S.end()) == 'j' ? ++cntj : ++cntz;
// printf("before : %d\n", ans);
// ans += min({cntj, cntz, K});
printf("%d\n", ans);
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
T2
给定 $ n $ 个小朋友，$ m $ 次操作每次要么询问 $ [l, r] $ 之间有多少小朋友在笑，要么对 $ [x - l, x + l] $ 所有小朋友讲 $ l $ 的笑话，如果其以前听过则不继续笑，没听过则开始笑。
ODT没看出来，线段树部分分写一半发现这部分分直接暴力就能水过去，于是暴力跑路。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
using namespace std;
// using namespace __gnu_pbds;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define MAXN (110000)
template< typename T = int >
inline T read(void);
int N, M;
bitset < 11000 > vis[11000];
bool laugh[11000];
// class SegTree{
// private:
// unordered_map < int, int > tr[MAXN << 2];
// int v[MAXN << 2];
// basic_string < int > lz[MAXN << 2];
// #define LS (p << 1)
// #define RS (LS | 1)
// #define MID ((gl + gr) >> 1)
// public:
// void Pushup(int p){
// for(auto son : tr[LS])tr[p][son.first] += son.second;
// for(auto son : tr[RS])tr[p][son.first] += son.second;
// v[p] = v[LS] + v[RS];
// }
// void Pushdown(int p){
// lz[LS] += lz[p], lz[RS] += lz[p];
// for(auto modf : lz[p]){
// v[LS] -= tr[LS][modf], tr[LS][modf] = 0;
// }
// }
// }
int main(){
freopen("child.in", "r", stdin);
freopen("child.out", "w", stdout);
N = read(), M = read();
while(M--){
int opt = read();
if(opt == 1){
int x = read(), idx = read(), dis = read();
for(int i = max(1, x - dis); i <= min(N, x + dis); ++i){
if(!vis[i][idx])vis[i][idx] = true, laugh[i] = true;
else laugh[i] = false;
}
}else{
int l = read(), r = read();
int cnt(0);
for(int i = l; i <= r; ++i)if(laugh[i])++cnt;
printf("%d\n", cnt);
}
}
// if(N <= 20000){
// while(M--){
// int opt = read();
// if(opt == 1){
// int x = read(), idx = read(), dis = read();
// for(int i = max(1, x - dis); i <= min(N, x + dis); ++i){
// if(!vis[i][idx])vis[i][idx] = true, laugh[i] = true;
// else laugh[i] = false;
// }
// }else{
// int l = read(), r = read();
// int cnt(0);
// for(int i = l; i <= r; ++i)if(laugh[i])++cnt;
// printf("%d\n", cnt);
// }
// }
// }else{
// printf("qwq\n");
// exit(0);
// }
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
/*
10 14
1 3 11 0
2 3 3
1 3 11 2
2 1 5
1 5 12 1
2 4 6
1 8 13 2
2 6 10
1 7 11 2
2 5 9
1 10 12 1
2 9 10
1 9 12 0
2 1 10
*/
T3
原题 51nod-3188 字符王国。
虚树，不会，写了个 $ 10\texttt{pts} $ 的链部分分。
Code
#define _USE_MATH_DEFINES
#include <bits/extc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
using namespace std;
using namespace __gnu_pbds;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
template< typename T = int >
inline T read(void);
int N, Q;
struct Edge{
Edge* nxt;
int to;
OPNEW;
}ed[210000];
ROPNEW(ed);
Edge* head[110000];
bool vis[110000];
basic_string < int > vised;
int main(){
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
N = read();
for(int i = 1; i <= N - 1; ++i){
int s = read(), t = read();
head[s] = new Edge{head[s], t};
head[t] = new Edge{head[t], s};
}Q = read();
while(Q--){
int K = read();
bool flag(true);
for(int k = 1; k <= K; ++k){
int p = read();
vis[p] = true;
vised += p;
for(auto i = head[p]; i; i = i->nxt)
if(vis[SON]){flag = false; break;}
}
printf("%d\n", flag ? K - 1 : -1);
for(auto p : vised)vis[p] = false;
vised.clear();
}
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
/*
4
1 3
2 3
4 3
4
2 1 2
3 2 3 4
3 1 2 4
4 1 2 3 4
*/
T4
原题 CF555E-Case of Computer Network。
给定一张 \(n\) 个点 \(m\) 条边的无向图，给定 \(q\) 组有向点对 \((s, t)\)，询问是否存在使得所有 $ s $ 都能到达 $ t $ 的无向图中每条边的定向方案。
无脑输出 Yes 即可获得 $ 70\texttt{pts} $。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
using namespace std;
// using namespace __gnu_pbds;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
template< typename T = int >
inline T read(void);
int main(){
freopen("network.in", "r", stdin);
freopen("network.out", "w", stdout);
puts(rnddd(70) ? "Yes" : "No");
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
正解
T1
$ 80\texttt{pts} $ 的贪心。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
using namespace std;
// using namespace __gnu_pbds;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
template< typename T = int >
inline T read(void);
int N, K;
int cntj(0), cntz(0);
int cnt2j(0), cnt2z(0);
int ans(0);
// string S;
basic_string < char > a, b;
int main(){
// freopen("string.in", "r", stdin);
// freopen("string.out", "w", stdout);
N = read(), K = read();
if(N == 1)printf("0\n"), exit(0);
for(int i = 1; i <= N; ++i){
char c = getchar(); while(c != 'j' && c != 'z')c = getchar();
a += c;
}
for(auto it = a.begin(); it != a.end(); ++it){
if(it == prev(a.end())){b += *it; continue;}
// if(*it == 'j' && *next(it) == 'j')++cntj;
// else if(*it == 'z' && *next(it) == 'z')++cntz;
// else if(*it == 'z' && *next(it) == 'j')++cntz;
// else
if(*it == 'j' && *next(it) == 'z')++ans, advance(it, 1), b += '*';
else b += *it;
}a.clear(); a.swap(b);
printf("%d %d %d %d\n", cntj, cntz, cnt2j, cnt2z);
printf("curans : %d\n", ans);
for(auto c : a)printf("%c", c);
printf("\n");
for(auto it = a.begin(); it != a.end(); ++it){
if(it == prev(a.end())){*it == 'j' ? ++cntj : (*it == 'z' ? ++cntz : 0); continue;}
if(*it == 'j' && *next(it) == 'j')++cnt2j, advance(it, 1);
else if(*it == 'z' && *next(it) == 'z')++cnt2z, advance(it, 1);
else if(*it == 'z' && *next(it) == 'j')++cntz;
else if(*it == 'j' && *next(it) == 'z')++ans, advance(it, 1);
else if(*it == 'j' && *next(it) == '*')++cntj, advance(it, 1);
else if(*it == 'z' && *next(it) == '*')++cntz, advance(it, 1);
// printf("%d %d %d %d\n", cntj, cntz, cnt2j, cnt2z);
}
printf("%d %d %d %d\n", cntj, cntz, cnt2j, cnt2z);
while(K && cnt2j && cnt2z)--cnt2j, --cnt2z, --K, ans += 2;
cntj += cnt2j * 2, cntz += cnt2z * 2;
ans += min({cntj, cntz, K});
// for(auto it = a.begin(); it != a.end(); ++it){
// if(it == prev(a.end())){b += *it; continue;}
// // if(*it == 'j' && *next(it) == 'j')++cntj;
// // else if(*it == 'z' && *next(it) == 'z')++cntz;
// // else if(*it == 'z' && *next(it) == 'j')++cntz;
// // else
// if(*it == 'j' && *next(it) == 'z')++ans, advance(it, 1), --cntj, --cntz;
// else b += *it;
// a.clear();
// a.swap(b);
// }
// while(K && cntj >= 1 && cntz >= 1){
// for(auto it = a.begin(); it != a.end(); ++it){
// if(it == prev(a.end())){b += *it; continue;}
// // if(*it == 'j' && *next(it) == 'j')++cntj;
// // else if(*it == 'z' && *next(it) == 'z')++cntz;
// // else if(*it == 'z' && *next(it) == 'j')++cntz;
// // else
// if(*it == 'j' && *next(it) == 'z')++ans, advance(it, 1), --cntj, --cntz;
// else b += *it;
// a.clear();
// a.swap(b);
// }
// }
// cin >> S;
// auto lst = S.begin();
// for(auto cur = next(S.begin()); cur != S.end(); ++cur, ++lst){
// if(*lst == 'j' && *cur == 'j')++cntj;
// else if(*lst == 'z' && *cur == 'z')++cntz;
// else if(*lst == 'z' && *cur == 'j')++cntz;
// else if(*lst == 'j' && *cur == 'z'){
// ++ans;
// advance(lst, 1), advance(cur, 1);
// if(cur == S.end() || lst == S.end())break;
// }
// }
// if(!(*prev(S.end()) == 'z' && *prev(S.end(), 2) == 'j'))
// *prev(S.end()) == 'j' ? ++cntj : ++cntz;
// printf("before : %d\n", ans);
// ans += min({cntj, cntz, K});
printf("%d\n", ans);
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
AC 做法：
考虑 DP，令 $ dp(i, j, k, 0/1) $ 表示前 $ i $ 个数，改变了 $ j $ 个 j，$ k $ 个 z，最后一位是 j 或 z，然后转移一下即可。。
Code
#define _USE_MATH_DEFINES
#include <bits/extc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
using namespace std;
using namespace __gnu_pbds;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
template< typename T = int >
inline T read(void);
int N, K;
string S;
int dp[510][110][110][2];
int main(){
memset(dp, 0xc0, sizeof dp);
dp[0][0][0][1] = 0;
N = read(), K = read();
cin >> S;
for(int i = 1; i <= N; ++i)
for(int j = 0; j <= K; ++j)
for(int k = 0; k <= K; ++k)
if(S.at(i - 1) == 'j'){
dp[i][j][k][0] = max(dp[i - 1][j][k][0], dp[i - 1][j][k][1]);
if(j)dp[i][j][k][1] = max(dp[i - 1][j - 1][k][0] + 1, dp[i - 1][j - 1][k][1]);
}else{
dp[i][j][k][1] = max(dp[i - 1][j][k][0] + 1, dp[i - 1][j][k][1]);
if(k)dp[i][j][k][0] = max(dp[i - 1][j][k - 1][0], dp[i - 1][j][k - 1][1]);
}
int ans(0);
for(int i = 1; i <= K; ++i)ans = max({ans, dp[N][i][i][0], dp[N][i][i][1]});
printf("%d\n", ans);
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
T2
两只 ODT，一只维护颜色状态，一只维护小朋友状态，随便写写就过了。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
template< typename T = int >
inline T read(void);
int N, M;
struct Node{
int l, r;
mutable bool val;
friend const bool operator < (const Node &a, const Node &b){
return a.l < b.l;
}
};
class ODT{
private:
#define SIZ(it) (it->r - it->l + 1)
set < Node > tr;
public:
pair < set < Node >::iterator, bool > Insert(Node x){return tr.insert(x);}
set < Node >::iterator Split(int p){
auto it = tr.lower_bound(Node{p});
if(it != tr.end() && it->l == p)return it;
--it;
int l = it->l, r = it->r;
bool val = it->val;
tr.erase(it);
Insert(Node{l, p - 1, val});
return Insert(Node{p, r, val}).first;
}
void Assign(int l, int r, bool val){
auto itR = Split(r + 1), itL = Split(l);
tr.erase(itL, itR);
Insert(Node{l, r, val});
}
int Query(int l, int r){
int ret(0);
auto itR = Split(r + 1), itL = Split(l);
for(auto it = itL; it != itR; ++it)ret += SIZ(it) * it->val;
return ret;
}
}odt;
class ODT_COL{
private:
set < Node > tr;
public:
pair < set < Node >::iterator, bool > Insert(Node x){return tr.insert(x);}
set < Node >::iterator Split(int p){
auto it = tr.lower_bound(Node{p});
if(it != tr.end() && it->l == p)return it;
--it;
int l = it->l, r = it->r;
bool val = it->val;
tr.erase(it);
Insert(Node{l, p - 1, val});
return Insert(Node{p, r, val}).first;
}
void Modify(int l, int r){
auto itR = Split(r + 1), itL = Split(l);
for(auto it = itL; it != itR; ++it){
if(!it->val)it->val = true, odt.Assign(it->l, it->r, true);
else odt.Assign(it->l, it->r, false);
}
}
}odt_col[110000];
int main(){
N = read(), M = read();
odt.Insert(Node{1, N, false});
for(int i = 1; i <= 101000; ++i)odt_col[i].Insert(Node{1, N, false});
while(M--){
int opt = read();
if(opt == 1){
int x = read(), idx = read(), dis = read();
odt_col[idx].Modify(max(1, x - dis), min(N, x + dis));
}else{
int l = read(), r = read();
printf("%d\n", odt.Query(l, r));
}
}
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
T3
咕咕咕。
T4
感觉可以做一做，题还挺有意思的，这两天要是有时间就来补一下，没时间的话就 NOIP 没退役回来补。
UPD
update-2022_11_18 初稿
标签：return,int,18,void,ret,++,小结,2022.11,define From： https://www.cnblogs.com/tsawke/p/16945630.html