赛时4题，策略重大失误，g题思路假了但是以为是代码问题硬调3.5h，m题本来是可以过的，e是网络流说不定也能过呢。
xixike大力平衡树直接打过k题省去思考双优先队列算法的时间，太强
A
观察到同级同形状括号如果有四个就一定可以交换顺序，而且是充要的，经典括号匹配用栈存储就过了，我代码比较丑
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
struct Node{
bool shp=0;
int ji=0;
}sta[maxn];
bool vis[maxn][2];
int main(){
int t;cin>>t;while(t--){
string s;cin>>s;
int k=0,tot=0;
bool ans=0;
for(int i=0;i<s.size();i++){
if(s[i]=='('||s[i]==')'){
if(
tot==0)sta[tot].ji=++k,sta[tot].shp=1,tot++;
else if(sta[tot-1].shp==0)sta[tot].ji=++k,sta[tot].shp=1,tot++;
else{
int tmp=sta[tot-1].ji,tmp1=sta[tot-1].shp;
if(vis[tmp][tmp1]){
ans=1;break;
}
else vis[tmp][tmp1]=1;
tot--;k=tmp-1;
}
}
else{
if(tot==0)sta[tot].ji=++k,sta[tot].shp=0,tot++;
else if(sta[tot-1].shp)sta[tot].ji=++k,sta[tot].shp=0,tot++;
else{
int tmp=sta[tot-1].ji,tmp1=sta[tot-1].shp;
if(vis[tmp][tmp1]){
ans=1;break;
}
else vis[tmp][tmp1]=1;
tot--;k=tmp-1;
}
}
}
int n=s.size();
for(int i=0;i<=n;i++)vis[i][0]=0,vis[i][1]=0,sta[i].ji=0,sta[i].shp=0;
if(ans)cout<<"NO"<<endl;
else cout<<"Yes"<<endl;
}
}
K
思路是首先发现区间一定取最大的，就可以双指针操作，只要操作次数小于k就合法，可以继续移动指针r，否则移动l。计算是难点，首先先预处理-0，-1，-2，把每个数的差值减掉，然后每个数就只需要再减去中位数即可。这个中位数其实是l，r区间的中位数因为显然如果不是中位数的话操作次数一定会+x(离中位数的距离），所以不优。然后每次插入一个数中位数只会移动一下所以也是可以维护小于中位数的数和大于中位数的数计算的。
队友写的平衡树（multiset显然也能写）
#define ll long long
#define int long long
using namespace std;
const int N = 5e5 + 10;
int T, n;
ll k;
int a[N];
int ls[N], rs[N], val[N];
int wei[N], siz[N];
inline void pushup(int x){
siz[x] = siz[ls[x]] + siz[rs[x]] + 1;
}
inline void split(int x, int k, int &a, int &b){
if(!x) return a = b = 0, void();
if(val[x] <= k) a = x, split(rs[x], k, rs[x], b);
else b = x, split(ls[x], k, a, ls[x]);
pushup(x);
}
inline int merge(int x, int y){
if(!x || !y) return x | y;
if(wei[x] <= wei[y]){
rs[x] = merge(rs[x], y);
return pushup(x), x;
}else{
ls[y] = merge(x, ls[y]);
return pushup(y), y;
}
}
int rt, tot;
inline int newnode(int k){
siz[++tot] = 1, val[tot] = k, wei[tot] = rand();
return tot;
}
inline void ins(int k){
int a, b; split(rt, k, a, b);
rt = merge(merge(a, newnode(k)), b);
}
inline void del(int k){
int a, b, c; split(rt, k, a, b); split(a, k - 1, a, c);
c = merge(ls[c], rs[c]), rt = merge(merge(a, c), b);
}
inline int kth(int x, int k){
if(k == siz[ls[x]] + 1) return val[x];
if(k > siz[ls[x]] + 1) return kth(rs[x], k - siz[ls[x]] - 1);
else return kth(ls[x], k);
}
inline void solve(){
cin >> n >> k;
for(int i = 1; i <= n; ++i) siz[i] = val[i] = wei[i] = ls[i] = rs[i] = 0;
for(int i = 1; i <= n; ++i) cin >> a[i], a[i] -= i;
rt = tot = 0;
int dlt = 0, val = 0, tmp = 0, ans = 0;
for(int l = 1, r = 1; r <= n; ++r){
// cout << l << " " << r << endl;
// int w = a[r] - dlt;
ins(a[r]), dlt++;
// cout << "? " << (r - l + 1 + 1) / 2 << endl;
int ak = kth(rt, (r - l + 1 + 1) / 2);
// cout << "aj " << l << " " << r << " " << ak << " " << val << endl;
if(ak == val){
tmp += abs(a[r] - val);
}else{
if(!(siz[rt] & 1)){
// cout << "? " << val << endl;
tmp += abs(a[r] - val);
}else tmp += abs(a[r] - ak);
val = ak;
}
while(tmp > k){
del(a[l]);
ak = kth(rt, (r - l + 1 + 1) / 2);
if(ak == val) tmp -= abs(a[l] - val);
else{
if(siz[rt] & 1) tmp -= abs(ak - a[l]);
else tmp -= abs(val - a[l]);
val = ak;
}
l++;
}
if(tmp <= k) ans = max(ans, r - l + 1);
}
cout << ans << endl;
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
ios :: sync_with_stdio(false);
cin >> T;
while(T--) solve();
return 0;
}
G
最搞笑的一题。
一开始搞染色后面以为是2-sat最后发现小丑。首先要观察到01，11这两种1的情况，然后对于两个有限制关系的操作想到建图，主要问题是要把选和不选建成两个点（赛时就是没这样做直接假了），然后并查集不建图宝宝也能过。（我写法建图的）
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
const int maxn=2e6+10,mod=1e9+7;
int n,m,vis[maxn],k;
vector<int>E[maxn];
string s[maxn];
void mul(int &x,int y){x=1ll*x*y%mod;}
void dfs(int x){
vis[x]=k;//cout<<x<<' '<<vis[x]<<endl;
for(auto y:E[x]){
if(!vis[y])dfs(y);
}
return;
}
void solve(){
cin>>n>>m;k=0;
for(int i=1;i<=2*n;i++)E[i].clear(),vis[i]=0;
for(int i=1;i<=n;i++)cin>>s[i],s[i]=" "+s[i];
//建图
for(int i=1;i<=m/2;i++){
int u=0,v=0,cnt=0;
for(int j=1;j<=n;j++){
if(s[j][i]=='1'){
if(u)v=j;
else u=j;
cnt++;
}
if(s[j][m-i+1]=='1'){
if(u)v=j;
else u=j;
cnt++;
}
}
if(u&&v&&u!=v){
if(s[u][i]!=s[v][i]){
E[u].pb(v);E[v].pb(u);
E[u+n].pb(v+n);E[v+n].pb(u+n);
}
else{
E[u].pb(v+n);E[v+n].pb(u);
E[u+n].pb(v);E[v].pb(u+n);
}
}
if(cnt>2)return cout<<0<<endl,void();
}
if(m&1){
int cnt=0;
for(int i=1;i<=n;i++)if(s[i][m/2+1]=='1')cnt++;
if(cnt>1)return cout<<0<<endl,void();
}
int ans=1;
for(int i=1;i<=n*2;i++){
if(!vis[i])++k,dfs(i);
}
k/=2;for(int i=1;i<=k;i++)mul(ans,2);
for(int i=1;i<=n;i++){
if(vis[i]==vis[i+n])ans=0;
}
cout<<ans<<endl;
}
signed main(){
int t;cin>>t;while(t--){
solve();
}
}
没有回复内容