A. Binary Protocol
开头和结尾添上(0)，然后找出所有(0)的位置，把相邻位置的差字符串连接起来就好了
view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define endl "
"
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define pll pair<LL,LL>
#ifndef ONLINE_JUDGE
#define cout cerr
#endif
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x) cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
template <typename T> void operator << (vector<T> &__container, T x){ __container.push_back(x); }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; }
const int MAXN = 2e5+7;
char s[MAXN];
void solve(){
int n; sci(n);
scanf("%s",s+1);
s[++n] = '0';
vi A;
A << 0;
string ret;
for(int i = 1; i <= n; i++) if(s[i]=='0') A << i;
for(int i = 1; i < (int) A.size(); i++) ret += to_string(A[i]-A[i-1]-1);
cout << ret << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
B. Five-In-a-Row
暴力枚举每个位置就好了，横着竖着两种斜着的判断一下就好了
view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define endl "
"
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define pll pair<LL,LL>
#ifndef ONLINE_JUDGE
#define cout cerr
#endif
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x) cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
template <typename T> void operator << (vector<T> &__container, T x){ __container.push_back(x); }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; }
const int MAXN = 2e5+7;
char s[20][20];
void solve(){
for(int i = 1; i <= 10; i++) cin >> s[i] + 1;
for(int i = 1; i <= 10; i++) for(int j = 1; j <= 6; j++){
int c0 = 0, c1 = 0;
for(int k = 0; k < 5; k++){
if(s[i][j+k]=='X') c0++;
if(s[i][j+k]=='O') c1++;
}
if(c0==4 and !c1){
cout << "YES" << endl;
return;
}
}
for(int i = 1; i <= 6; i++) for(int j = 1; j <= 10; j++){
int c0 = 0, c1 = 0;
for(int k = 0; k < 5; k++){
if(s[i+k][j]=='X') c0++;
if(s[i+k][j]=='O') c1++;
}
if(c0==4 and !c1){
cout << "YES" << endl;
return;
}
}
for(int i = 1; i <= 6; i++) for(int j = 1; j <= 6; j++){
int c0 = 0, c1 = 0;
c0 = 0, c1 = 0;
for(int k = 0; k < 5; k++){
if(s[i+k][j+k]=='X') c0++;
if(s[i+k][j+k]=='O') c1++;
}
if(c0==4 and !c1){
cout << "YES" << endl;
return;
}
}
for(int i = 10; i >= 5; i--) for(int j = 1; j <= 6; j++){
int c0 = 0, c1 = 0;
for(int k = 0; k < 5; k++){
if(s[i-k][j+k]=='X') c0++;
if(s[i-k][j+k]=='O') c1++;
}
if(c0==4 and !c1){
cout << "YES" << endl;
return;
}
}
cout << "NO" << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
C. Multi-judge Solving
排序一下，然后维护当前最大值，如果遇到做不了的，就不断把最大值翻倍，然后计数(++)
view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define endl "
"
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define pll pair<LL,LL>
#ifndef ONLINE_JUDGE
#define cout cerr
#endif
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x) cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
template <typename T> void operator << (vector<T> &__container, T x){ __container.push_back(x); }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; }
const int MAXN = 1e6+7;
char s[MAXN], t[MAXN];
int cnt1[26], cnt2[26];
void solve(){
____();
cin >> s >> t;
int k = 0, n = strlen(s), m = strlen(t);
set<int> pos;
for(int i = 0; i < n; i++){
if(s[i]=='?') k++, pos.insert(i);
else cnt1[s[i]-'a']++;
}
for(int i = 0; i < m; i++) cnt2[t[i]-'a']++;
auto check = [&](int mid){
int ned = 0;
for(int i = 0; i < 26; i++) ned += max(0,mid*cnt2[i]-cnt1[i]);
return ned<=k;
};
int l = 0, r = n / m;
while(l<=r){
int mid = (l + r) >> 1;
if(check(mid)) l = mid + 1;
else r = mid - 1;
}
int ptr = 0;
while(!pos.empty()){
while(ptr<26 and cnt1[ptr]>=cnt2[ptr]*r) ptr++;
if(ptr==26) s[*pos.begin()] = 'a';
else s[*pos.begin()] = ptr+'a', cnt1[ptr]++;
pos.erase(pos.begin());
}
cout << s << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
D. Suitable Replacement
显然和顺序没有关系，只需要关心各个字符出现了多少次，二分匹配次数，看能不能用(?)补上就好了，贰分到答案之后把缺的字符补上即可
view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define endl "
"
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define pll pair<LL,LL>
#ifndef ONLINE_JUDGE
#define cout cerr
#endif
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x) cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
template <typename T> void operator << (vector<T> &__container, T x){ __container.push_back(x); }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; }
const int MAXN = 1e6+7;
char s[MAXN], t[MAXN];
int cnt1[26], cnt2[26];
void solve(){
____();
cin >> s >> t;
int k = 0, n = strlen(s), m = strlen(t);
set<int> pos;
for(int i = 0; i < n; i++){
if(s[i]=='?') k++, pos.insert(i);
else cnt1[s[i]-'a']++;
}
for(int i = 0; i < m; i++) cnt2[t[i]-'a']++;
auto check = [&](int mid){
int ned = 0;
for(int i = 0; i < 26; i++) ned += max(0,mid*cnt2[i]-cnt1[i]);
return ned<=k;
};
int l = 0, r = n / m;
while(l<=r){
int mid = (l + r) >> 1;
if(check(mid)) l = mid + 1;
else r = mid - 1;
}
int ptr = 0;
while(!pos.empty()){
while(ptr<26 and cnt1[ptr]>=cnt2[ptr]*r) ptr++;
if(ptr==26) s[*pos.begin()] = 'a';
else s[*pos.begin()] = ptr+'a', cnt1[ptr]++;
pos.erase(pos.begin());
}
cout << s << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
E. Minimal Labels
(DAG)考虑建反图然后把连通块找出来之后分别拓扑排序，为了让小的数能够分配到小的值，拓扑排序过程考虑用优先队列来维护，让编号大的尽量先出队
然后每次找到编号最小的还没有标号的点，把这个点所在的连通块中拓扑序在它之后的全部标上号，具体就是从后往前把当前可用的最小标号赋给当前值
view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define endl "
"
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define pll pair<LL,LL>
#ifndef ONLINE_JUDGE
#define cout cerr
#endif
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x) cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
template <typename T> void operator << (vector<T> &__container, T x){ __container.push_back(x); }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; return out; }
const int MAXN = 2e5+7;
vi G[MAXN];
int n, m, deg[MAXN], f[MAXN];
int findx(int x){ return x==f[x] ? x : f[x] = findx(f[x]); }
set<int> S;
pii pos[MAXN];
vi vec[MAXN], topo[MAXN];
void solve(){
sci(n); sci(m);
for(int i = 1; i <= n; i++) f[i] = i;
for(int i = 1; i <= m; i++){
int u, v; sci(u); sci(v);
G[v] << u;
deg[u]++;
if(findx(u)!=findx(v)) f[findx(u)] = findx(v);
}
for(int i = 1; i <= n; i++) S.insert(i);
for(int i = 1; i <= n; i++) vec[findx(i)] << i;
for(int i = 1; i <= n; i++){
if(vec[i].empty()) continue;
priority_queue<int> que;
for(int &x : vec[i]) if(!deg[x]) que.push(x);
while(!que.empty()){
int u = que.top(); que.pop();
pos[u] = {i,topo[i].size()};
topo[i] << u;
for(int &v : G[u]) if(!--deg[v]) que.push(v);
}
}
vi ret(n);
int cur = 1;
while(!S.empty()){
auto p = *S.begin();
auto ps = pos[p].first, id = pos[p].second;
int num = topo[ps].size() - id;
for(int i = cur + num - 1, j = id; i >= cur; i--, j++) ret[topo[ps][j]-1] = i;
while(topo[ps].size()>id){
S.erase(topo[ps].back());
topo[ps].pop_back();
}
cur += num;
}
cout << ret << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
F. String Compression
考虑(dp[i])表示考虑子串(s[1:i])的最短表示，那么(dp[i]=min(dp[j]+cost[j+1:i]))
可以发现(cost[a:b])就是找子串(s[a:b])的最小循环节，然后用最小循环节乘上出现次数
考虑对字符串的每个位置作为起点分别跑一次(KMP)，得到(fail)数组，然后就可以得到任意子串的最小循环节了
复杂度(O(n^2))
view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define endl "
"
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define pll pair<LL,LL>
#ifndef ONLINE_JUDGE
#define cout cerr
#endif
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x) cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
template <typename T> void operator << (vector<T> &__container, T x){ __container.push_back(x); }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; return out; }
const int MAXN = 2e5+7;
char s[MAXN];
int n, f[MAXN], lp[8008][8008];
vi kmp(char *s, int n){
vi fail(n);
for(int i = 1, len = 0; i < n;){
if(s[i]==s[len]) fail[i++] = ++len;
else{
if(len) len = fail[len-1];
else fail[i++] = len;
}
}
return fail;
}
int diglen(int x){
int len = 0;
while(x) len++, x /= 10;
return len;
}
void solve(){
____();
cin >> s + 1;
n = strlen(s+1);
for(int i = 1; i <= n; i++){
auto fail = kmp(s+i,n-i+1);
for(int j = 0; j < n - i + 1; j++){
lp[i][i+j] = j - fail[j] + 1;
if((j+1)%lp[i][i+j]!=0) lp[i][i+j] = j + 1;
}
}
memset(f,0x3f,sizeof(f));
f[0] = 0;
for(int i = 1; i <= n; i++){
for(int j = 0; j < i; j++) cmin(f[i],f[j]+diglen((i-j)/lp[j+1][i])+lp[j+1][i]);
}
cout << f[n] << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
G. Tree Queries
题目似乎并不难
把第一次变成黑点的点作为根，然后(dfs)一下，记录每个点到根路径上的最小值
然后维护一个全局最小值，每次多一个黑点，把全局最小值和这个黑点到根路径上的所有点的最小值取(min)，如果之前已经取过了就退出
查询就(O(1))就没了
复杂度(O(n))
view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define endl "
"
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define pll pair<LL,LL>
#ifndef ONLINE_JUDGE
#define cout cerr
#endif
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x) cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
template <typename T> void operator << (vector<T> &__container, T x){ __container.push_back(x); }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; return out; }
const int MAXN = 1e6+7;
int n, q, root, minn[MAXN], globalmin, fa[MAXN];
vi G[MAXN];
bool vis[MAXN];
void dfs(int u, int par, int MIN){
cmin(MIN,u); fa[u] = par;
minn[u] = MIN;
for(int &v : G[u]) if(v!=par) dfs(v,u,MIN);
}
void solve(){
sci(n); sci(q);
for(int i = 1; i < n; i++){
int u, v; sci(u); sci(v);
G[u] << v; G[v] << u;
}
sci(root); sci(root);
root = root % n + 1;
int lastans = 0;
globalmin = root;
dfs(root,0,root);
vis[root] = true;
for(int i = 1; i < q; i++){
int tp, x;
sci(tp); sci(x);
x = (x + lastans) % n + 1;
if(tp==1) while(!vis[x]) cmin(globalmin,x), vis[x] = true, x = fa[x];
else printf("%d
",lastans = min(globalmin,minn[x]));
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}