CF1440A Buy the String
每个点有两种决策，要么选当前的字符，要么选跟当前字符不同的字符，取个较小值相加。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1005;
int T;
int n,c[2],h;
int a[N];
void solve()
{
scanf("%d%d%d%d",&n,&c[0],&c[1],&h);
for(int i=1;i<=n;i++)
scanf("%1d",&a[i]);
int ans=0;
for(int i=1;i<=n;i++)
{
int t=c[a[i]];
t=min(t,c[a[i]^1]+h);
ans+=t;
}
printf("%d\n",ans);
return;
}
int main()
{
scanf("%d",&T);
while(T--)
solve();
return 0;
}
CF1440B Sum of Medians
考虑一组的情况，对于最大的 \(\lfloor \frac{n}{2}\rfloor\) 的数，肯定不能成为中位数，能成为中位数的为第 \(\lfloor \frac{n}{2}\rfloor-1\) 大的数，将这 \(\frac{n}{2}+1\) 个数删去，找下一组即可。
#include <bits/stdc++.h>
using namespace std;
const int N=200005;
int T;
int n,k;
int a[N];
void solve()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n*k;i++)
scanf("%d",&a[i]);
long long ans=0;
if(n==1)
{
for(int i=1;i<=n*k;i++)
ans+=a[i];
printf("%lld\n",ans);
return ;
}
if(n==2)
{
for(int i=1;i<=n*k;i+=2)
ans+=a[i];
printf("%lld\n",ans);
return ;
}
int mid=(n+1)/2-1;
for(int i=k*mid+1;i<=n*k;i+=n-mid)
ans+=a[i];
printf("%lld\n",ans);
return;
}
int main()
{
scanf("%d",&T);
while(T--)
solve();
return 0;
}
CF1440C Binary Table
将前 \(n-2\) 行，前 \(m-2\) 列全部移到右下角，然后就变成 \(2\times 2\) 的情况了。
#include<iostream>
#include<cstdio>
#include<tuple>
#include<vector>
using namespace std;
const int N=105;
int T;
int n,m;
int a[N][N];
void solve()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%1d",&a[i][j]);
vector<tuple<int,int,int,int,int,int>>res;
for(int i=1;i<=n-2;i++)
for(int j=1;j<=m-2;j++)
if(a[i][j]) res.emplace_back(i,j,i+1,j,i,j+1),a[i][j]^=1,a[i+1][j]^=1,a[i][j+1]^=1;
for(int i=1;i<=n-2;i++)
if(a[i][m])
{
if(a[i][m-1]) res.emplace_back(i,m,i,m-1,i+1,m),a[i][m]^=1,a[i][m-1]^=1,a[i+1][m]^=1;
else if(a[i+1][m])
{
res.emplace_back(i,m,i+1,m-1,i,m-1),a[i][m]^=1,a[i+1][m-1]^=1,a[i][m-1]^=1;
res.emplace_back(i+1,m,i+1,m-1,i,m-1),a[i+1][m]^=1,a[i+1][m-1]^=1,a[i][m-1]^=1;
}
else res.emplace_back(i,m,i+1,m-1,i+1,m),a[i][m]^=1,a[i+1][m-1]^=1,a[i+1][m]^=1;
}
else if(a[i][m-1]) res.emplace_back(i+1,m,i+1,m-1,i,m-1),a[i+1][m]^=1,a[i+1][m-1]^=1,a[i][m-1]^=1;
for(int j=1;j<=m-2;j++)
if(a[n][j])
{
if(a[n-1][j]) res.emplace_back(n,j,n-1,j,n,j+1),a[n][j]^=1,a[n-1][j]^=1,a[n][j+1]^=1;
else if(a[n][j+1])
{
res.emplace_back(n,j,n-1,j,n-1,j+1),a[n][j]^=1,a[n-1][j]^=1,a[n-1][j+1]^=1;
res.emplace_back(n,j+1,n-1,j,n-1,j+1),a[n][j+1]^=1,a[n-1][j]^=1,a[n-1][j+1]^=1;
}
else res.emplace_back(n,j,n-1,j+1,n,j+1),a[n][j]^=1,a[n-1][j+1]^=1,a[n][j+1]^=1;
}
else if(a[n-1][j]) res.emplace_back(n,j+1,n-1,j,n-1,j+1),a[n][j+1]^=1,a[n-1][j]^=1,a[n-1][j+1]^=1;
int cnt=a[n][m]+a[n-1][m]+a[n][m-1]+a[n-1][m-1];
if(cnt==4)
{
res.emplace_back(n,m,n-1,m,n,m-1);
res.emplace_back(n,m,n-1,m-1,n,m-1);
res.emplace_back(n,m,n-1,m,n-1,m-1);
res.emplace_back(n,m-1,n-1,m,n-1,m-1);
}
else if(cnt==3)
{
vector<pair<int,int>>pos;
if(a[n][m]) pos.emplace_back(n,m);
if(a[n-1][m]) pos.emplace_back(n-1,m);
if(a[n][m-1]) pos.emplace_back(n,m-1);
if(a[n-1][m-1]) pos.emplace_back(n-1,m-1);
res.emplace_back(pos[0].first,pos[0].second,pos[1].first,pos[1].second,pos[2].first,pos[2].second);
}
else if(cnt==2)
{
vector<pair<int,int>>one,zero;
if(a[n][m]) one.emplace_back(n,m);
else zero.emplace_back(n,m);
if(a[n-1][m]) one.emplace_back(n-1,m);
else zero.emplace_back(n-1,m);
if(a[n][m-1]) one.emplace_back(n,m-1);
else zero.emplace_back(n,m-1);
if(a[n-1][m-1]) one.emplace_back(n-1,m-1);
else zero.emplace_back(n-1,m-1);
res.emplace_back(one[0].first,one[0].second,zero[0].first,zero[0].second,zero[1].first,zero[1].second);
res.emplace_back(one[1].first,one[1].second,zero[0].first,zero[0].second,zero[1].first,zero[1].second);
}
else if(cnt==1)
{
vector<pair<int,int>>one,zero;
if(a[n][m]) one.emplace_back(n,m);
else zero.emplace_back(n,m);
if(a[n-1][m]) one.emplace_back(n-1,m);
else zero.emplace_back(n-1,m);
if(a[n][m-1]) one.emplace_back(n,m-1);
else zero.emplace_back(n,m-1);
if(a[n-1][m-1]) one.emplace_back(n-1,m-1);
else zero.emplace_back(n-1,m-1);
res.emplace_back(one[0].first,one[0].second,zero[0].first,zero[0].second,zero[1].first,zero[1].second);
res.emplace_back(zero[0].first,zero[0].second,one[0].first,one[0].second,zero[2].first,zero[2].second);
res.emplace_back(zero[1].first,zero[1].second,one[0].first,one[0].second,zero[2].first,zero[2].second);
}
int k=res.size();
printf("%d\n",k);
for(auto [x1,y1,x2,y2,x3,y3]:res)
printf("%d %d %d %d %d %d\n",x1,y1,x2,y2,x3,y3);
return;
}
int main()
{
scanf("%d",&T);
while(T--)
solve();
return 0;
}
CF1440D Graph Subset Problem
点集的话可以用一种奇怪的方法找，先将图按照类似拓扑排序的方式处理，如果某个点的度数小于 \(k\) 就加入队列，没有访问过的点就是对应的点集。
大小为 \(k\) 的团因为有一个条件就是没有上述的点集，我们可以在拓扑排序的时候处理。具体地，我们可以对于度数为 \(k-1\) 的某个点 \(u\)，找出它的所有出度，判断一下这些点之间是否有边，如果有边就是这个点集合法的，否则这个点不能在最大团中出现，将这个点的边全部删去。
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int N=100005;
int T;
int n,m,k;
int d[N];
vector<int>G[N];
bool check(int x,int y)
{
vector<int>::iterator it=lower_bound(G[x].begin(),G[x].end(),y);
if(it==G[x].end()) return false;
else return *it==y;
}
bool book[N];
vector<int>check_clique(int u)
{
vector<int>res;
res.emplace_back(u);
for(int v:G[u])
if(!book[v]) res.emplace_back(v);
for(int u:res)
for(int v:res)
if(u!=v)
{
if(!check(u,v)) return {};
}
return res;
}
bool vis[N];
void toposort()
{
for(int i=1;i<=n;i++)
vis[i]=book[i]=false;
queue<int>q;
for(int i=1;i<=n;i++)
if(d[i]<k)
{
vis[i]=true;
q.emplace(i);
}
vector<int>clique;
while(!q.empty())
{
int u=q.front();
q.pop();
book[u]=true;
if(d[u]==k-1)
{
vector<int>res=check_clique(u);
if(!res.empty()) clique=res;
}
for(int v:G[u])
{
d[v]--;
if(vis[v]) continue;
if(d[v]<k)
{
vis[v]=true;
q.emplace(v);
}
}
}
vector<int>subset;
for(int i=1;i<=n;i++)
if(!vis[i]) subset.emplace_back(i);
if(!subset.empty())
{
int s=subset.size();
printf("1 %d\n",s);
for(int u:subset)
printf("%d ",u);
printf("\n");
}
else if(!clique.empty())
{
printf("2\n");
for(int u:clique)
printf("%d ",u);
printf("\n");
}
else printf("-1\n");
return;
}
void solve()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
G[i].clear(),d[i]=0;
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
G[x].emplace_back(y);
G[y].emplace_back(x);
d[x]++,d[y]++;
}
if(1LL*k*(k-1)/2>m)
{
printf("-1\n");
return;
}
for(int i=1;i<=n;i++)
sort(G[i].begin(),G[i].end());
toposort();
return;
}
int main()
{
scanf("%d",&T);
while(T--)
solve();
return 0;
}
CF1440E Greedy Shopping
可以发现，最后选的连续段的个数为 \(O(\log a_i)\) 级别的，因为多一个空位意味着这个位置的数要比后面选的所有的数之和要大，这样每个空位的数就会一直乘二。然后就可以在线段树上暴力做了，线段树上维护一下 \(\max(a_i),\min(a_i)\)，如果当前节点的 \(\min(a_i)> y\) 就退出，这样询问一次的复杂度为 \(O(\log n\log a_i)\)，修改同理。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=200005;
int n,Q;
int a[N];
struct Node
{
int l,r;
int tag;
int Min,Max;
long long sum;
}tree[N<<2];
void push_up(int i)
{
tree[i].Min=min(tree[i*2].Min,tree[i*2+1].Min);
tree[i].Max=max(tree[i*2].Max,tree[i*2+1].Max);
tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
return;
}
void build(int i,int l,int r)
{
tree[i].l=l,tree[i].r=r;
if(l==r)
{
tree[i].Min=tree[i].Max=a[l];
tree[i].sum=a[l];
return;
}
int mid=(l+r)/2;
build(i*2,l,mid);
build(i*2+1,mid+1,r);
push_up(i);
return;
}
void add(int i,int y)
{
tree[i].Min=tree[i].Max=y;
tree[i].tag=y;
tree[i].sum=1LL*(tree[i].r-tree[i].l+1)*y;
return;
}
void push_down(int i)
{
if(!tree[i].tag) return;
add(i*2,tree[i].tag);
add(i*2+1,tree[i].tag);
tree[i].tag=0;
return;
}
void modify(int i,int l,int r,int y)
{
if(tree[i].Min>=y) return;
if(l<=tree[i].l&&tree[i].r<=r&&tree[i].Max<=y) return add(i,y);
push_down(i);
if(l<=tree[i*2].r) modify(i*2,l,r,y);
if(r>=tree[i*2+1].l) modify(i*2+1,l,r,y);
push_up(i);
return;
}
int query(int i,int l,int r,int &y)
{
if(tree[i].Min>y) return 0;
if(l<=tree[i].l&&tree[i].r<=r&&tree[i].sum<=y)
{
y-=tree[i].sum;
return tree[i].r-tree[i].l+1;
}
if(tree[i].l==tree[i].r) return 0;
push_down(i);
int res=0;
if(l<=tree[i*2].r) res+=query(i*2,l,r,y);
if(r>=tree[i*2+1].l) res+=query(i*2+1,l,r,y);
return res;
}
int main()
{
scanf("%d%d",&n,&Q);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,1,n);
while(Q--)
{
int t,x,y;
scanf("%d%d%d",&t,&x,&y);
if(t==1) modify(1,1,x,y);
else printf("%d\n",query(1,x,n,y));
}
return 0;
}