简单题
快速计算摆放棋子攻击对数的方法:拿出每个行/列连续段,设它有(p)个点。
则(ans+=frac{p(p+1)}{2})
一个棋子会让它所在的行/列连续段贡献+1。
用一条路径进行限制。
(frac{p(p+1)}{2})可以拆边。
具体看代码。
做了这么久发现看错题了,口可
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 1200010
int h[N],nxt[N],v[N],ct,w[N],s,t,pre[N],dis[N],pa[N],ec,q,co[N],inq[N],n,ans[N],i1[100][100],i2[100][100],c1,ss[N],ok[N];
char st[100][100];
struct no{
int a,b,c,d;
};
vector<no>vc;
void add(int a,int b,int c,int d){
v[++ec]=b;w[ec]=c;nxt[ec]=h[a];co[ec]=d;h[a]=ec;
}
void adj(int a,int b,int c,int d){
add(a,b,c,d);
add(b,a,0,-d);
}
bool bfs(){
for(int i=0;i<=t;i++){
dis[i]=999999999;
pre[i]=-1;
}
dis[s]=0;
queue<int>q;
q.push(s);
inq[s]=1;
while(!q.empty()){
int x=q.front();
q.pop();
inq[x]=0;
for(int i=h[x];i;i=nxt[i])
if(w[i]>0&&co[i]+dis[x]<dis[v[i]]){
dis[v[i]]=co[i]+dis[x];
pa[v[i]]=i;
pre[v[i]]=x;
if(!inq[v[i]]){
inq[v[i]]=1;
q.push(v[i]);
}
}
}
if(pre[t]==-1)
return false;
return true;
}
int mcmf(){
int c=0,f=0;
while(bfs()){
int fl=1e9;
for(int i=t;s!=i;i=pre[i])
fl=min(fl,w[pa[i]]);
f+=fl;
c+=fl*dis[t];
ans[f]=c;
for(int i=t;i!=s;i=pre[i])
w[pa[i]]-=fl,w[pa[i]^1]+=fl;
}
return c;
}
signed main(){
ec=1;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%s",st[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(st[i][j]=='.'){
if(!i1[i][j-1])
i1[i][j]=++c1;
else
i1[i][j]=i1[i][j-1];
if(!i2[i-1][j]){
i2[i][j]=++c1;
ok[c1]=1;
}
else
i2[i][j]=i2[i-1][j];
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
ss[i1[i][j]]++;
ss[i2[i][j]]++;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(st[i][j]!='#'){
adj(i1[i][j],i2[i][j],1,0);
}
t=c1+1;
for(int i=1;i<=c1;i++)
for(int j=0;j<ss[i];j++){
if(!ok[i])
adj(s,i,1,j);
else
adj(i,t,1,j);
}
mcmf();
scanf("%d",&q);
for(int i=1;i<=q;i++){
int x;
scanf("%d",&x);
printf("%d
",ans[x]);
}
}