昨天模拟赛第三道提答题校验器爆int了233实力卡我6分
然后模拟赛打完得知自己的课放到了下星期的好消息233
非常开心 然而那道大贪心还是要刚出来吾心方安
卡了我好几天……然而现在还是没有看懂标程里面有一句是怎么写的……
算了算了反正就这样啦
题解→戳我戳我（是我自己写的）
代码就是这样啦自己理解一下
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
using namespace std;
inline ll IN(){
ll x=0,ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void Out(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) Out(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
const int N=5000005;
ll P,n,m,a[N],b[N];
ll Solve(){
ll MC=P*(P-1)/2*n,FD=min(m*P-MC,a[n]),ret=0;
Rep(i,1,n) FD=min(FD,a[i]-i*P+m);
ll now=FD;
Drp(i,n,1){
if (i!=n) now-=P;
now=min(now,a[i]);
if (now<MC+P||FD-now>m-P) return -1;
ret+=now;
}
return ret;
}
int main(){
n=IN(),m=IN();
Rep(i,1,n) a[i]=IN();
ll Ans=0;
for (P=1;P*n<=m;P++) Ans=max(Ans,Solve());
Out(Ans);
}
啊做了一下午和一晚上课件好♂爽
做点水题压压精惊
拆点网络流
把石柱拆成两半，下面向上面连流量为高度的边
每个石柱的上面向能到达的石柱的下面连流量为oo的边
地图边缘的石柱的上面向超级汇连流量为oo的边
超级源向有蜥蜴的石柱连流量为1的边
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
using namespace std;
inline int IN(){
int x=0,ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void Out(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) Out(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
int n,m,Res,S,T;
const int M=1000005;
char s[25][25];
int head[1005],to[M],next[M],cap[M],cnt,deep[1005],d;
int id(int i,int j){return (i-1)*m+j;}
void AddEdge(int u,int v,int w){
to[cnt]=v;next[cnt]=head[u];cap[cnt]=w;head[u]=cnt++;
to[cnt]=u;next[cnt]=head[v];cap[cnt]=0;head[v]=cnt++;
}
queue<int>q;
bool BFS(){
while (!q.empty()) q.pop();
q.push(S);
memset(deep,-1,sizeof deep);
deep[S]=1;
while (!q.empty()){
int u=q.front();q.pop();
Cross(i,u) if (cap[i]&&deep[to[i]]==-1){
deep[to[i]]=deep[u]+1;
if (to[i]==T) return 1;
q.push(to[i]);
}
}
return 0;
}
int DFS(int u,int f){
if (u==T||f==0) return f;
int F,ret=0;
Cross(i,u){
if (cap[i]&&deep[to[i]]==deep[u]+1&&(F=DFS(to[i],min(f,cap[i])))>0){
ret+=F,f-=F;
cap[i]-=F,cap[i^1]+=F;
if (!f) break;
}
}
return ret;
}
int Dinic(){
int ret=0;
while (BFS()) ret+=DFS(S,oo);
return ret;
}
int main(){
n=IN(),m=IN(),d=IN();
S=0,T=2*n*m+1;
cnt=0;memset(head,-1,sizeof head);
Rep(i,1,n) scanf("%s",s[i]+1);
Rep(i,1,n) Rep(j,1,m) if (s[i][j]!='0') AddEdge(id(i,j),id(i,j)+n*m,s[i][j]-'0');
Rep(i,1,n) Rep(j,1,m) Rep(k,1,n) Rep(l,1,m){
if (k==i&&l==j) continue;
if (s[i][j]!='0'&&s[k][l]!='0'&&(k-i)*(k-i)+(l-j)*(l-j)<=d*d) AddEdge(id(i,j)+n*m,id(k,l),oo);
}
Rep(i,1,n) Rep(j,1,m) if (s[i][j]!='0'&&(i<=d||i+d>n||j<=d||j+d>m)) AddEdge(id(i,j)+n*m,T,oo);
Rep(i,1,n) scanf("%s",s[i]+1);
Rep(i,1,n) Rep(j,1,m) if (s[i][j]=='L') AddEdge(S,id(i,j),1),Res++;
printf("%d\n",Res-Dinic());
}
评论 (0)
