vp济南银牌 沈阳铜牌 感觉被其他人偷走了我的人生 哎。。。 菜就多练吧
A
玩了很多样例发现 好像是 合法括号的最小划分不超过2就可以 写出来造了很多很多数据 才敢交 1A
// ([])[]() ([]([]))
void solve(){
string s;cin>>s;s='='+s;int n=s.size();
for(auto &c:s)if(c=='(')c=')';else if(c=='[')c=']';
char pre='0';
int cnt=0;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(s[j]==s[j-1]){
cnt++;
int len=j-i;
if(s[i]==pre){
NO return;
}
pre=s[i];
string l=s.substr(i,len);
string r=s.substr(j,len);
reverse(all(r));
// cout<<l<<' '<<r<<endl;
if(l!=r){
NO return;
}
i=j+len-1;
break;
}
}
}
if(cnt>=3){
NO return;
}
YES
}
D
暴力 找到9不会很多次
void solve(){
int la,ra,lb,rb;cin>>la>>ra>>lb>>rb;
int ans=0;
for(int a=la;a<=ra;a++){
for(int b=lb;b<=rb;b++){
int x=a+b;
vector<int>nums;
while(x)nums.push_back(x%10),x/=10;
ans=max(ans,*max_element(all(nums)));
if(ans==9){
cout<<9<<endl;
return;
}
}
}
cout<<ans<<endl;
}
G
很容易看出来 第i列和第m-i+1列 的1不会超过3个
这样我们考虑连边
比如考虑第i列和第m-i+1列
我们第i列（左边）第1行出现了1
第m-i+1列（右边）第2行出现了1
这样这第1行和第2行就不能属性（颜色相同）
考虑染色过程 就这样分类讨论一下连一下边就可以了
对于每一个连通块我们可以*2
int n,m,color[1000010],flag;
vector<PII>g[1000010];
void dfs(int u,int st){
if(flag)return;
color[u]=st;
for(auto [v,w]:g[u]){
if(color[v]==-1)dfs(v,(st+w)%2);
else{
if(color[v]!=(st+w)%2){
cout<<0<<endl;
flag=1;
return;
}
}
if(flag)return;
}
}
void solve(){
flag=0;
cin>>n>>m;
int a[n+1][m+1];
for(int i=1;i<=n;i++){
g[i].clear();
color[i]=-1;
for(int j=1;j<=m;j++){
char c;cin>>c;
a[i][j]=(c=='1');
}
}
for(int i=1,j=m;i<=j;i++,j--){
vector<int>l,r;
for(int k=1;k<=n;k++)if(a[k][i])l.push_back(k);
for(int k=1;k<=n;k++)if(a[k][j])r.push_back(k);
if(l.size()+r.size()>=3){
cout<<0<<endl;
return;
}
if(l.size()==2){
g[l[0]].push_back({l[1],1});
g[l[1]].push_back({l[0],1});
}
if(r.size()==2){
g[r[0]].push_back({r[1],1});
g[r[1]].push_back({r[0],1});
}
if(l.size()==1&&r.size()==1){
g[r[0]].push_back({l[0],0});
g[l[0]].push_back({r[0],0});
}
}
int ans=1;
for(int i=1;i<=n;i++){
if(color[i]==-1){
dfs(i,0);
if(flag)return;
(ans*=2)%=mod;
}
}
cout<<ans<<endl;
}
I
每次暴力去找后面小于他的那一个的位置
复杂度好似5e7
实际只有3ms
void solve(){
int n;cin>>n;
vector<int>a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
}
vector<PII>ans;
for(int cnt=1;cnt<=n/2;cnt++){
int i,j;
for(i=1;i<=n;i++){
for(j=n;j>=i+1;j--){
if(a[i]>a[j]){
ans.push_back({i,j});
goto out;
}
}
}
out:
sort(a.begin()+i,a.begin()+j+1);
}
cout<<ans.size()<<endl;
for(auto [x,y]:ans)cout<<x<<' '<<y<<endl;
}
K
我们发现等差数列 公差恒为1
这样我们在输入的时候就可以-下标 就是来找一个数 让他们都相等 而不是等差数列就好求多了
然后发现具有单调性
二分是肯定的
check mid长度类是否有一个数让他们路径和<=k
这个数我们必然是选中位数的路径 肯定是最短的
然后就是权值线段树二分找中位数 以及 维护一些val cnt的计算路径和了
struct node{
int l,r,v,cnt;
}tr[N<<2];
int n,m;
void pushup(int i){
auto &u=tr[i],&l=tr[i<<1],&r=tr[i<<1|1];
u.v=l.v+r.v;
u.cnt=l.cnt+r.cnt;
}
void build(int i,int l,int r){
tr[i].l=l,tr[i].r=r,tr[i].cnt=0,tr[i].v=0;
if(l==r){
return;
}
int mid=l+r>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
pushup(i);
}
void modify(int i,int x,int k,int k2){
if(tr[i].l>=x&&tr[i].r<=x){
auto &u=tr[i];
u.v+=k;
u.cnt+=k2;
return;
}
if(tr[i].l>x||tr[i].r<x)return;
if(tr[i<<1].r>=x)modify(i<<1,x,k,k2);
if(tr[i<<1|1].l<=x)modify(i<<1|1,x,k,k2);
pushup(i);
}
int query(int i,int f){
if(tr[i].l==tr[i].r){
return tr[i].l;
}
if(tr[i<<1].cnt>=f)return query(i<<1,f);
else{
return query(i<<1|1,f-tr[i<<1].cnt);
}
}
PII query(int i,int l,int r){
PII res={0,0};
if(tr[i].l>=l&&tr[i].r<=r){
auto &u=tr[i];
return {u.v,u.cnt};
}
if(tr[i].l>r||tr[i].r<l)return res;
if(tr[i<<1].r>=l){
PII now= query(i<<1,l,r);
res.first+=now.first;
res.second+=now.second;
}
if(tr[i<<1|1].l<=r){
PII now= query(i<<1|1,l,r);
res.first+=now.first;
res.second+=now.second;
}
return res;
}
void solve(){
cin>>n>>m;
vector<int>a(n+1);
map<int,int>mp;
vector<int>mpp(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]-=i;
mp[a[i]]++;
}
int idx=0;
for(auto [pos,w]:mp){
++idx;
mp[pos]=idx;
mpp[idx]=pos;
}
int ans=1;
build(1,1,n);
for(int i=1,j=i;i<=n&&j<=n;i++){
while(j<=n) {
modify(1, mp[a[j]], a[j], 1);
int mid = j - i + 1;
int z = mpp[query(1, up(mid, 2))];
// cout<<i<<' '<<z<<endl;
auto[lv, lcnt]=query(1, 1, mp[z]);
auto[rv, rcnt]=query(1, mp[z] + 1, idx);
// cout<<lcnt<<' '<<lv<<' '<<rcnt<<' '<<rv<<endl;
// cout<<lcnt*z-lv+rv-rcnt*z<<' '<<m<<endl;
if (lcnt * z - lv + rv - rcnt * z <= m){
ans = max(ans, mid);
j++;
}else {
modify(1, mp[a[i]], -a[i], -1);
modify(1, mp[a[j]], -a[j], -1);
break;
}
}
}
cout<<ans<<endl;
}