卡牌游戏
题意
有 (n) 张牌，正反面各有一数字 (a_i,b_i)。初始时所有牌正面朝上。你可以选择至多 (m) 张牌翻转，使得朝上的数字的极差最小。(nleq 10^6)。
输入已经按照 (a_i) 排序。
题解
显然最优解一定是取一段连续 (a_i) 不翻转，剩下的翻转。于是先处理 (b_i) 的前、后缀最值。二分答案，讨论最小值是 (a_i) 的左端、在左边翻转的部分还是在右边翻转的部分。假的。因为“连续的一段 (a_i)” 不一定是最长的或最短的。
我们把 (a_i,b_i) 混起来排序，枚举左端点，取尽可能短的一段满足：
- 每个位置都有个 (a) 或 (b) 在范围内；
- (a) 的总量至少是 (n-m)。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],b[N],n,m,u[N],us,s;
struct C{int v,i,u;}c[N*2];
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)scanf("%d",a+i),c[i]=C{a[i],i,1};
for(int i=0;i<n;i++)scanf("%d",b+i),c[n+i]=C{b[i],i,0};
sort(c,c+n*2,[&](C a,C b){ return a.v<b.v; });
int ans=0x7f7f7f7f;
for(int l=0,r=-1;l<n*2;l++){
while(s<n-m||us<n){
r++;
if(r>=n*2)goto e;
if(!u[c[r].i])++us;
++u[c[r].i];
s+=c[r].u;
}
ans=min(ans,c[r].v-c[l].v);
s-=c[l].u;
--u[c[l].i];
if(!u[c[l].i])--us;
}
e:
cout<<ans;
}
矩阵游戏
题意
有一 (n imes m) 的矩阵 (a_{i,j})，每个数在 (0) 到 (10^6) 间。给出 (b_{i,j}=a_{i,j}+a_{i+1,j}+a_{i,j+1}+a_{i+1,j+1}(1leq i<n, 1leq j<m))，构造 (a)，或输出无解。(n,mleq 300)，(10) 组数据。
题解
先设 (a_{n,j}) 与 (a_{i,m}) 为 (0)。接着建点分别表示 (pm a_{n,j}(1leq j<m))、(a_{n,m}pm a_{i,m}(1leq i<n))、(a_{n,m})、(0)，正负号取决于 (m-j,n-i) 的奇偶性。通过连边表示原矩阵每个位置的数的范围限制，跑差分约束。SPFA 需要一些玄学优化。
垃圾样例让我多测不清空、(n,m) 弄反以及各种出锅。
#include<bits/stdc++.h>
using namespace std;
int getint(){
int ans=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
ans=ans*10+c-'0';
c=getchar();
}
return ans;
}
#define ll long long
const int N=610,M=310*310*4;
struct bian{
int l,e,n;
};
bian b[M];
int s[N],tot=0;
void add(int x,int y,int z){
tot++;
b[tot].l=z;
b[tot].e=y;
b[tot].n=s[x];
s[x]=tot;
}
int n,m;
ll dis[N];bool inq[N];
int cnt[N];
ll a[N/2][N/2],c[N/2][N/2];
bool spfa(int u){
memset(dis,0x3f,sizeof(dis));
memset(cnt,0,sizeof(cnt));
memset(inq,0,sizeof(inq));
deque<int>q;
q.push_back(u);dis[u]=0;
while(q.size()){
int t=q.front();q.pop_front();inq[t]=0;
++cnt[t];if(cnt[t]>n+m+4)return 1;
for(int i=s[t];i;i=b[i].n){
int v=b[i].e;
if(dis[v]>dis[t]+b[i].l){
dis[v]=dis[t]+b[i].l;
if(!inq[v]){
if(b[i].l<0)q.push_front(v);
else q.push_back(v);
}
inq[v]=1;
}
}
}
return 0;
}
int main(){
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
int T=getint();
while(T--){
n=getint(),m=getint();
memset(b,0,sizeof(b));
memset(s,0,sizeof(s));
tot=0;
for(int i=1;i<n;i++)
for(int j=1;j<m;j++)
c[i][j]=getint();
for(int i=1;i<=n;i++)a[i][m]=0;
for(int i=1;i<=m;i++)a[n][i]=0;
for(int i=n-1;i;i--)
for(int j=m-1;j;j--)
a[i][j]=(c[i][j]-a[i+1][j]-a[i][j+1]-a[i+1][j+1]);
for(int i=1;i<n;i++)
for(int j=1;j<m;j++){
if(((n-i)&1)^((m-j)&1)){
add(j,i+300,-a[i][j]+1e6);
add(i+300,j,a[i][j]);
}else{
add(i+300,j,-a[i][j]+1e6);
add(j,i+300,a[i][j]);
}
}
for(int i=1;i<m;i++){
if((m-i)&1)add(601,i,0),add(i,601,1e6);
else add(601,i,1e6),add(i,601,0);
}
for(int i=1;i<n;i++){
if((n-i)&1)add(602,300+i,1e6),add(300+i,602,0);
else add(602,300+i,0),add(300+i,602,1e6);
}
add(601,602,1e6);
add(602,601,0);
if(spfa(601))puts("NO");
else{
a[n][m]=dis[602];
for(int i=1;i<m;i++){
if((m-i)&1)a[n][i]=-dis[i];
else a[n][i]=dis[i];
}
for(int i=1;i<n;i++){
if((n-i)&1)a[i][m]=dis[300+i]-dis[602];
else a[i][m]=-dis[300+i]+dis[602];
}
for(int i=n-1;i;i--)
for(int j=m-1;j;j--)
a[i][j]=(c[i][j]-a[i+1][j]-a[i][j+1]-a[i+1][j+1]);
puts("YES");
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
printf("%d ",a[i][j]);
printf("
");
}
}
}
}
图函数
题意
对于一张 (n) 个点 (m) 条边的有向图 (G)（顶点从 (1 sim n) 编号），定义函数 (f(u, G))：
- 初始化返回值 (cnt = 0)，图 (G' = G)。
- 从 (1) 至 (n) 按顺序枚举顶点 (v)，如果当前的图 (G') 中，从 (u) 到 (v) 与从 (v) 到 (u) 的路径都存在，则将 (cnt + 1)，并在图 (G') 中删去顶点 (v) 以及与它相关的边。
- 第 (2) 步结束后，返回值 (cnt) 即为函数值。
现在给定一张有向图 (G)，求 (h(G) = f(1, G) + f(2, G) + cdots + f(n, G)) 的值。
更进一步地，记删除（按输入顺序给出的）第 (1) 到 (i) 条边后的图为 (G_i)（(1 le i le m)），请你求出所有 (h(G_i)) 的值。
(nleq 10^3)，(mleq 2 imes 10^5)。
题解
第二步可以变为直接删除枚举到的所有点，因为不强连通的点删不删都是一回事。
于是问题变为：对于每个 (i,j)，统计保留点 ([i,n]) 和边 ([0,j]) 得到的图中 (i) 所在连通块大小。与 (i) 强连通可以看作 (i) 能到它、它能到 (i)，于是转而考虑正图、反图上 (i) 能够到达的点。（也可以考虑成 kosaraju）
枚举 (i)；将边按照编号从大到小加入，并用边来尝试更新 (i) 到终点的【最小边权尽可能大】的路径，从如果更新成功就从它开始 D(B)FS，继续更新其他点，bitset 优化。每个点的贡献范围是一个前缀。
复杂度 (O(dfrac{n^3]{omega}+nm))
#include<bits/stdc++.h>
using namespace std;
int getint(){
int ans=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
ans=ans*10+c-'0';
c=getchar();
}
return ans;
}
#define ll long long
#define ull unsigned long long
const int N=1010,M=2e5+10;
int n,m,qaqaq;
int lb[1<<16];
inline void flip(ull *a,int x){
a[x>>6]^=1ull<<(x&63);
}
inline bool get(ull *a,int x){
return (a[x>>6]>>(x&63))&1;
}
int lowbit(ull *a,ull *b,int x=0){
int y=x>>6;
while(y<N/64+2&&!(a[y]&b[y]))++y;
if(y>=N/64+2)return -1;
ull z=a[y]&b[y];
if(z&((1ull<<16)-1))return lb[z&((1ull<<16)-1)]+(y<<6);
if(z&((1ull<<32)-1))return lb[(z>>16)&((1ull<<16)-1)]+16+(y<<6);
if(z&((1ull<<48)-1))return lb[(z>>32)&((1ull<<16)-1)]+32+(y<<6);
return lb[z>>48]+48+(y<<6);
}
struct gragh{
ull b[N][N/64+3];
int c[N][N];
int u[M],v[M],tot=0;
void add(int x,int y){
tot++;u[tot]=x;v[tot]=y;
c[x][y]=tot;
}
int dis[N];
ull uvis[N/64+3];
void init(int i){
memset(dis,0,sizeof(dis));
memset(b,0,sizeof(b));
memset(uvis,-1,sizeof(uvis));
memset(uvis,0,sizeof(ull)*max(i/64-1,0));
dis[i]=m+1;for(int j=i/64*64;j<=i;j++)flip(uvis,j);
}
int q[N],top;
inline void add_(int l,int i){
int u=this->u[i],v=this->v[i];
flip(b[u],v);
if(dis[u]&&!dis[v]){
dis[v]=i;flip(uvis,v);
q[top++]=v;
while(top){
int t=q[--top];
for(int v=lowbit(uvis,b[t]);~v;v=lowbit(uvis,b[t],v)){
++qaqaq;
dis[v]=i,q[top++]=v,flip(uvis,v);
}
}
}
}
} g,h;
int ans[M];
list<int>b;
int main(){
// freopen("graph.in","r",stdin);
// freopen("graph.out","w",stdout);
for(int i=0;i<16;i++)for(int j=1<<i;j<1<<16;j+=2<<i)lb[j]=i;
n=getint(),m=getint();
for(int i=1;i<=m;i++){
int u=getint(),v=getint();
g.add(u,v);
h.add(v,u);
}
for(int i=m;i;i--)b.push_back(i);
for(int i=1;i<=n;i++){
// cerr<<">>>> "<<i<<endl;
g.init(i),h.init(i);
for(auto j=b.begin();j!=b.end();){
// cerr<<"> "<<g.u[*j]<<" "<<g.v[*j];
g.add_(i,*j);
h.add_(i,*j);
if(g.u[*j]==i||g.v[*j]==i){
auto k=j;j++;b.erase(k);
}else j++;
}
// cerr<<endl;
// for(int j=i;j<=n;j++)cerr<<"> "<<g.dis[j];cerr<<endl;
// for(int j=i;j<=n;j++)cerr<<"> "<<h.dis[j];cerr<<endl;
for(int j=i;j<=n;j++)ans[min(g.dis[j],h.dis[j])]++;
// qaqaq=0;
}
for(int i=m+1;i;--i)ans[i]+=ans[i+1];
for(int i=1;i<=m+1;i++)printf("%d ",ans[i]);
}
