AI Summary
周测总结了三题：合并果子用二分，旮旯给木为博弈论，括号序列采用分治和树状数组。
T1 合并果子
赛时并没有想到正解，写了一个贪心，之后又写了一个并查集贪心，做法都是假的（
）获得35pts高分
正解是二分，注意到原题等价为划分 个区间，并求出区间和最小值的最大值。
考虑二分答案 ，并使用贪心划分区间即可。
/*---------------------
by DRheEheAM (awa)-----
love hanser forever!---
---------------------*/
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=1e6+10;
int n,k,a[N];
bool solve (int res) {
int idx=0,nw=0;
for (int i=1;i<=n;i++) {
nw+=a[i];
if (nw>=res) idx++,nw=0;
}
if (nw>=res) idx++;
return idx>=n-k;
}
signed main() {
Cios;
int c,q;
cin>>c>>q;
while (q--) {
cin>>n>>k;
int l=0,r=0,res=0x3f3f3f3f3f3f3f3f;
for (int i=1;i<=n;i++) cin>>a[i],r+=a[i],res=min(res,a[i]);
while (l<=r) {
int mid=(l+r)>>1;
if (solve(mid)) l=mid+1,res=mid;
else r=mid-1;
}
cout<<res<<"\n";
}
return 0;
}T2 旮旯给木
这道题观察大样例/打表都不难发现，如果 ，那么后手（小lizimin）必胜，否则先手（小B）必胜。
/*---------------------
by DRheEheAM (awa)-----
love hanser forever!---
---------------------*/
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define intl long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
signed main() {
Cios;
int t;
cin>>t;
while (t--) {
int a;
cin>>a;
if (a==(a&(-a))) cout<<"Win\n";
else cout<<"Lose\n";
}
return 0;
}T4 括号序列
考虑转换括号序列，( 映射为 ， ) 映射为 ，并求出前缀和 。
显然有一个结论 。
比较难发现，若区间 合法，则 。
因为 所以 。
于是考虑分治，并使用树状数组统计答案。
/*---------------------
by DRheEheAM (awa)-----
love hanser forever!---
---------------------*/
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=1e6+10;
int res,n,a[N],sum[N],mx[N];
class Fenwick {
int tr[N<<2];
inline int lb (int x) {return x&(-x);}
public:
void update (int x,int v) {
x+=(N<<1);
while (x<(N<<2)) {
tr[x]+=v;
x+=lb(x);
}
}
int query (int x) {
int res=0;
x+=(N<<1);
while (x) {
res+=tr[x];
x-=lb(x);
}
return res;
}
}bit;
void solve (int l,int r) {
if (l==r) return res++,void();
int mid=(l+r)>>1;
solve(l,mid);
solve(mid+1,r);
mx[mid]=-sum[mid];
mx[mid+1]=-sum[mid+1];
for (int i=mid+2;i<=r;i++) mx[i]=min(mx[i-1],-sum[i]);
for (int i=mid-1;i>=l;i--) mx[i]=min(mx[i+1],-sum[i]);
int p=r;
for (int i=l;i<=mid;i++) {
while (p>=mid+1&&mx[i]>=mx[p]) bit.update(-sum[p]-mx[p],1),p--;
res+=bit.query(sum[i-1]);
}
for (int i=p+1;i<=r;i++) bit.update(-sum[i]-mx[i],-1);
p=l;
for (int i=r;i>=mid+1;i--) {
while (p<=mid&&mx[i]>mx[p]) bit.update(-sum[p-1]-mx[p], 1),p++;
res+=bit.query(sum[i]);
}
for (int i=l;i<=p-1;i++) bit.update(-sum[i-1]-mx[i],-1);
}
signed main() {
Cios;
string s;
cin>>s;
n=s.size();
for (int i=1;i<=n;i++) {
a[i]=(s[i-1]=='('?1:-1);
sum[i]=sum[i-1]+a[i];
}
solve(1,n);
cout<<res<<'\n';
return 0;
}
评论（3）