Educational Codeforces Round 153 (Rated for Div. 2)

A.我直接构造（（（））））和（）（）（）这种了，因为这两种都很简便，只有（）和）（

连续字符，且只有这两种可能碰到，py写很简便，因为我忘了c++的find函数空等于啥了

import random
import sys
import os
import math
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from itertools import accumulate, combinations, permutations
from heapq import nsmallest, nlargest, heapify, heappop, heappush
from io import BytesIO, IOBase
from copy import deepcopy
import threading
import bisectBUFSIZE = 4096class FastIO(IOBase):newlines = 0def __init__(self, file):self._fd = file.fileno()self.buffer = BytesIO()self.writable = "x" in file.mode or "r" not in file.modeself.write = self.buffer.write if self.writable else Nonedef read(self):while True:b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))if not b:breakptr = self.buffer.tell()self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)self.newlines = 0return self.buffer.read()def readline(self):while self.newlines == 0:b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))self.newlines = b.count(b"\n") + (not b)ptr = self.buffer.tell()self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)self.newlines -= 1return self.buffer.readline()def flush(self):if self.writable:os.write(self._fd, self.buffer.getvalue())self.buffer.truncate(0), self.buffer.seek(0)class IOWrapper(IOBase):def __init__(self, file):self.buffer = FastIO(file)self.flush = self.buffer.flushself.writable = self.buffer.writableself.write = lambda s: self.buffer.write(s.encode("ascii"))self.read = lambda: self.buffer.read().decode("ascii")self.readline = lambda: self.buffer.readline().decode("ascii")sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")def I():return input()def II():return int(input())def MI():return map(int, input().split())def LI():return list(input().split())def LII():return list(map(int, input().split()))def GMI():return map(lambda x: int(x) - 1, input().split())def LGMI():return list(map(lambda x: int(x) - 1, input().split()))def solve():s=I()n=len(s)a=""b=""for i in range(1,n+1):a+="()"for i in range(1,n+1):b+="("for i in range(1,n+1):b+=")"if s not in a:print("YES")print(a)return if s not in b:print("YES")print(b)return print("NO")if __name__ == '__main__':for _ in range(II()):solve()

B.我还没看懂题...

C.博弈论题，emmm感觉很典没啥好说的

因为没法操作就获胜

所以当前点能走到任何一个必胜态，那么当前点就是必败态

下面注释的就是没优化过的记忆化搜索

可以观察到优化，找到前面的位置且数比当前数小，存在一个数的状态是必胜态，那么当前就是必败态

然后我脑子可能wa了，用树状数组维护了，

if(tr0.q(a[i]-1)!=tr1.q(a[i]-1)) f[i]=0;就是说前面比当前数小的个数和他们有几个是必败态的

如果相等就说明全是必败态，那么当前就是必胜态

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10,mod=998244353;
typedef long long LL;
typedef pair<int, int> PII;int n,m;
int a[N];
class BitTree {public:vector<int> tree;int n;BitTree(int _n) : n(_n) {tree.resize(n+1);fill(tree.begin(),tree.end(),0);//for(int i=0;i<=n;i++) tree[i]=0;}inline int lowbit(int x) { return x&-x; }inline void Modify(int x,int v) {for(;x<=n;x+=lowbit(x)) tree[x]+=v;}inline int q(int x) {int ret=0;if(x<=0) return 0;for(;x;x-=lowbit(x)) ret+=tree[x];return ret;}inline int Query(int l,int r) {return q(r)-q(l-1);}
};
void solve(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];vector<int> f(n+1,-1);vector<int> st;int mx=0x3f3f3f3f;BitTree tr0(n),tr1(n);for(int i=1;i<=n;i++){if(mx>a[i]) f[i]=0,mx=a[i];}// function<int(int)> dfs=[&](int x){//     if(f[x]!=-1) return f[x];//     f[x]=1;//     for(int i=x-1;i>=1;i--)//左边有一个1就寄//     {//         if(a[i]<a[x])//         {//             f[x]&=(dfs(i)^1);//         }//     }//     return f[x];// };int res=0;f[1]=0;for(int i=1;i<=n;i++){if(f[i]==-1){f[i]=1;if(tr0.q(a[i]-1)!=tr1.q(a[i]-1)) f[i]=0;}if(f[i]==0)tr0.Modify(a[i],1);tr1.Modify(a[i],1);}for(int i=1;i<=n;i++){if(f[i]==1){res++;//  cout<<i<<"\n";}}cout<<res<<"\n";
}signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

D.

cnt0=0的个数

cnt1=1的个数

首先00和11的个数我们是知道的因为00和11无论顺序怎么样都是 cnt0*(cnt0-1)/2和cnt1*(cnt1-1)/2

又因为01=10，所以最好01和10的个数就是(n-11-00)/2的个数了

然后问题就变成了前i个位置，当前位置填1，且目前01个数是k的最小次数的方程了

当前如果当前填1了，那么难点在怎么知道增加了几个01个数呢

这里有个比较巧妙的思路

由于第i位填1了，已经填了i个，所以增加了i-1个（01和11）因为前面不管填0还是1，01和11的总和是不变的，稳定增加i-1个，且最后答案的11+01的总和也是固定的

所以可以把方程变成

前i个位置，当前位置填1，且目前01+11的个数是k的最小次数的方程了

f[i][k]=f[i-1][k-j](j+i<=k)+(s[i]=='0')

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10,mod=998244353;
typedef long long LL;
typedef pair<int, int> PII;int n,m;
int a[N];void solve(){string s;cin>>s;n=s.size();int c1=count(s.begin(),s.end(),'1'),c0=n-c1;int need=c1*(c1-1)/2+(n*(n-1)/2-c1*(c1-1)/2-c0*(c0-1)/2)/2;//11个数+01个数vector<vector<int>> f(c1+1,vector<int>(need+1,0x3f3f3f3f));f[0][0]=0;for(int i=0;i<n;i++){for(int j=min(c1-1,i);j>=0;j--){for(int k=0;k+i<=need;k++){f[j+1][k+i]=min(f[j+1][k+i],f[j][k]+(s[i]=='0'));}}}cout<<f[c1][need]<<"\n";
}signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;//  cin>>t;while(t--) solve();
}

E：

直接01bfs搜全部点即可，枚举中点

#include<bits/stdc++.h>
using namespace std;
const int N = 60010,mod=99824435;
typedef long long LL;
typedef pair<int, int> PII;int n,m;
int a[N];
int id[N];
vector<int> g[N];
int dist[676][N];
void solve(){string s;cin>>s;n=s.size();s="?"+s;for(int i=1;i<n;i++){id[i]=(s[i]-'a')*26+s[i+1]-'a';g[id[i]+n+1].push_back(i);g[i].push_back(id[i]+n+1);}for(int i=2;i<n;i++)g[i].push_back(i-1),g[i-1].push_back(i);auto bfs=[&](int x){for(int i=1;i<=n+676;i++)dist[x][i]=1e9;deque<int> q;dist[x][x+n+1]=0;q.push_back(x+n+1);while(q.size()){int y=q.front();q.pop_front();for(auto z:g[y]){if((z>n||y>n)&&dist[x][z]>dist[x][y]+1){dist[x][z]=dist[x][y]+1;q.push_front(z);}if(dist[x][z]>dist[x][y]+2){dist[x][z]=dist[x][y]+2;q.push_back(z);}}}};for(int i=0;i<=675;i++)bfs(i);cin>>m;while(m--){int s,t;cin>>s>>t;int tmp=1e9;for(int j=0;j<=675;j++)tmp=min(tmp,dist[j][s]+dist[j][t]);cout<<min(min(abs(t-s),(id[s]==id[t]?1:1145141919)),tmp/2)<<"\n";}
}signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;// cin>>t;while(t--) solve();
}