2016.11.15
BZOJ1009:DP+矩阵乘法+KMP
BZOJ1898:矩阵乘法
BZOJ4101:贪心，考虑我们往右边撞的时候，我们会向左边冲
，于是枚举答案点利用一个指针计算即可！
2016.11.14
OI队内测试
2016.11.13
BZOJ4512：乱搞
BZOJ4102：DP+bfs
BZOJ4395：bfs
BZOJ3889：双键值最短路
BZOJ4512 #include <bits/stdc++.h>
using namespace std;
#define LL long long
int N,sx,sy,ans;
char s[];
bool vis[][],north[][],east[][];
int main(){
// freopen("data.in","r",stdin);
// freopen("A.out","w",stdout);
scanf("%d%s",&N,s);
sx=sy=;
for (int i=;i<N;i++){
vis[sx][sy]=;
char ch=s[i];
if (ch=='N'){
sy++;
if (!north[sx][sy-]&&vis[sx][sy])ans++;
north[sx][sy-]=;
}
if (ch=='S'){
sy--;
if (!north[sx][sy]&&vis[sx][sy])ans++;
north[sx][sy]=;
}
if (ch=='E'){
sx++;
if (!east[sx-][sy]&&vis[sx][sy])ans++;
east[sx-][sy]=;
}
if (ch=='W'){
sx--;
if (!east[sx][sy]&&vis[sx][sy])ans++;
east[sx][sy]=;
}
}
printf("%d\n",ans);
} BZOJ4102 #include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ll long long
#define ld long double
#define N 1005
#define M N*(N+1)
using namespace std;
int n,p,tot;
int pre[M],v[M],now[N],f[N],dis[N][N];
bool vis[N];
queue<int>q;
struct data{
int val,pos;
}a[N];
int read()
{
int x=,f=; char ch;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
return x*f;
}
void ins(int a,int b){++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b;
}
bool cmp(data a,data b){return a.val<b.val;
}
void bfs(int u)
{
memset(vis,,sizeof(vis));
q.push(u); dis[u][u]=; vis[u]=;
while (!q.empty())
{
int x=q.front(); q.pop();
for (int p=now[x]; p; p=pre[p])
{
int son=v[p];
if (!vis[son])
{
dis[u][son]=dis[u][x]+;
q.push(son); vis[son]=;
}
}
}
}
int main()
{
n=read(); p=read();
for (int i=; i<=n; i++)
{
int x=read(),d=read();
a[i].val=x; a[i].pos=i;
for (int j=; j<=d; j++) {int y=read(); ins(i,y); ins(y,i);}
}
for (int i=; i<=n; i++) bfs(i);
sort(a+,a+n+,cmp);
for (int i=; i<=n; i++) f[i]=a[i].val;
for (int i=; i<=n; i++)
for (int j=; j<=i-; j++)
{
if (a[i].val>a[j].val && dis[a[i].pos][a[j].pos])
{
f[i]=max(f[i],f[j]-dis[a[i].pos][a[j].pos]*p+a[i].val);
}
}
int ans=;
for (int i=; i<=n; i++) ans=max(ans,f[i]);
printf("%d\n",ans);
return ;
} BZOJ4395 #include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ll long long
#define ld long double
#define N 205
#define M 40005
using namespace std;
int dx[]={,,,-},dy[]={,-,,};
int pre[M],v[M],now[N*N],tot;
int n,m,ans;
queue<int>q;
bool vis[N][N],lig[N][N];
int read()
{
int x=,f=; char ch;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
return x*f;
}
int encode(int a,int b){return (a-)*n+b;
}
void ins(int a,int b){
++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b;
}
int main()
{
n=read(); m=read();
for (int i=; i<=m; i++)
{
int a=read(),b=read(),c=read(),d=read();
ins(encode(a,b),encode(c,d));
}
int last=; ans=;
for (;;)
{
q.push(encode(,));
memset(vis,,sizeof(vis)); vis[][]=; lig[][]=;
while (!q.empty())
{
int pp=q.front(),x,y; q.pop(); //last++;
for (int p=now[pp]; p; p=pre[p])
{
int son=v[p]; x=(son-)/n+,y=(son-)%n+;
if (!lig[x][y]) lig[x][y]=,ans++;
}
x=(pp-)/n+,y=(pp-)%n+;
for (int i=; i<; i++)
{
int xx=x+dx[i],yy=y+dy[i];
if (xx< || xx>n || yy< || yy>n || !lig[xx][yy] || vis[xx][yy]) continue;
vis[xx][yy]=; q.push(encode(xx,yy));
}
}
if (last==ans) break;
last=ans;
}
printf("%d\n",ans);
return ;
} BZOJ3889 #include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ll long long
#define ld long double
#define inf 100000000000000
#define N 1005
using namespace std;
int s,t,m,n;
ll a[N][N],b[N][N],dis[N],d[N];
int c[N];
bool vis[N];
queue<int>q;
int read()
{
int x=,f=; char ch;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
return x*f;
}
void spfa()
{
for (int i=; i<=m; i++) dis[i]=inf;
dis[s]=d[s]=; vis[s]=; q.push(s);
while (!q.empty())
{
int x=q.front(); q.pop(); vis[x]=;
//cout<<" "<<x<<endl;
for (int i=; i<=m; i++)
{
// cout<<i<<" "<<dis[i]<<" "<<dis[x]<<" "<<a[x][i]<<endl;
if (dis[i]>dis[x]+a[x][i] || ((dis[i]==dis[x]+a[x][i]) && d[i]>d[x]+b[x][i]))
{
// cout<<" "<<x<<" "<<i<<" "<<a[x][i]+dis[x]<<endl;
dis[i]=dis[x]+a[x][i]; d[i]=d[x]+b[x][i];
if (!vis[i]) vis[i]=,q.push(i);
}
}
//|| (dis[i]==dis[x]+a[x][i] && d[i]>d[x]+b[x][i])
}
}
int main()
{
s=read(); t=read(); n=read();
for (int i=; i<=; i++)
for (int j=; j<=; j++) a[i][j]=inf;
for (int i=; i<=n; i++)
{
int len=read(),cnt=read();
for (int j=; j<=cnt; j++) c[j]=read(),m=max(m,c[j]);
for (int j=; j<=cnt; j++)
for (int k=j+; k<=cnt; k++)
if (a[c[j]][c[k]]>len || ((a[c[j]][c[k]]==len) && (b[c[j]][c[k]]>(k-j)))) a[c[j]][c[k]]=len,b[c[j]][c[k]]=k-j;
}
spfa();
if (dis[t]==inf) dis[t]=-,d[t]=-;
cout<<dis[t]<<" "<<d[t]<<endl;
return ;
}
2016.11.12
BZOJ3887: spfa（正边一次+反边一次）
BZOJ3886：状态压缩dp+二分（f[i]表示看电影状态为i的最长连续时间）
BZOJ4098：DP优化（f[i][j][k][l]：（i+j）==（k+l） 优化为f[i][j][k]：（i+j)满足滚动数组
BZOJ3888：把时间求出来+线段树
BZOJ3887 #include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define N 100005
#define M 200005
using namespace std;
int read()
{
int x=,f=; char ch;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
return x*f;
}
int n,m;
int a[N],b[N];
int tot,pre[M],v[M],now[N];
int bel[N],low[N],dfn[N],num[N],total,ind,top,z[N];
int dist1[N],dist2[N];
bool inq[N],vis[N];
queue<int> q;
void ins(int a,int b){++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b;}
void tarjan(int x)
{
low[x]=dfn[x]=++ind;
++top; z[top]=x; inq[x]=;
for (int p=now[x]; p; p=pre[p])
{
int son=v[p];
if (!dfn[son]) tarjan(son),low[x]=min(low[x],low[son]);
else if (inq[son]) low[x]=min(low[x],dfn[son]);
}
if (low[x]==dfn[x])
{
++total; num[total]=; inq[x]=; bel[x]=total;
while (z[top]!=x)
{
int son=z[top]; bel[son]=total; inq[son]=; num[total]++; top--;
}
top--;
}
}
void build(int X)
{
memset(now,,sizeof(now)); tot=;
for (int i=; i<=m; i++)
{
int x=a[i],y=b[i];
if (bel[x]!=bel[y])
{
if (X==) ins(bel[x],bel[y]); else ins(bel[y],bel[x]);
}
}
}
void spfa1()
{
vis[bel[]]=; dist1[bel[]]=num[bel[]]; q.push(bel[]);
while (!q.empty())
{
int x=q.front(); q.pop(); vis[x]=;
for (int p=now[x]; p; p=pre[p])
{
int son=v[p];
if (dist1[son]<dist1[x]+num[son])
{
dist1[son]=dist1[x]+num[son];
if (!vis[son]) q.push(son),vis[son]=;
}
}
}
}
void spfa2()
{
vis[bel[]]=; dist2[bel[]]=num[bel[]]; q.push(bel[]);
while (!q.empty())
{
int x=q.front(); q.pop(); vis[x]=;
for (int p=now[x]; p; p=pre[p])
{
int son=v[p];
if (dist2[son]<dist2[x]+num[son])
{
dist2[son]=dist2[x]+num[son];
if (!vis[son]) q.push(son),vis[son]=;
}
}
}
}
int main()
{
n=read(); m=read();
for (int i=; i<=m; i++) a[i]=read(),b[i]=read(),ins(a[i],b[i]);
for (int i=; i<=n; i++) if (!dfn[i]) tarjan(i);
build(); spfa1();
build(); spfa2();
int ans=;
for (int i=; i<=m; i++) if (bel[a[i]]!=bel[b[i]] && dist1[bel[b[i]]] && dist2[bel[a[i]]])
{
ans=max(ans,dist1[bel[b[i]]]+dist2[bel[a[i]]]-num[bel[]]);
}
printf("%d\n",ans);
return ;
} BZOJ3886 #include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int n,L;
int num[],len[],c[][];
int f[];
int read()
{
int x=,f=; char ch;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
return x*f;
}
int find(int x,int s)
{
int l=,r=num[x],Ans=-;
while (l<=r)
{
int mid=(l+r)>>;
if (c[x][mid]<=s) Ans=mid,l=mid+; else r=mid-;
}
return Ans;
}
int main()
{
n=read(); L=read();
for (int i=; i<=n; i++)
{
len[i]=read(); num[i]=read();
for (int j=; j<=num[i]; j++) c[i][j]=read();
}
f[]=;
int s=<<n,ans=0x7fffffff;
for (int i=; i<s; i++) f[i]=-;
for (int i=; i<s; i++)
{
if (f[i]==-) continue;
int k=;
if (f[i]>L)
{
for (int j=i; j; j>>=) if (j&) k++;
ans=min(ans,k); continue;
}
for (int j=; j<=n; j++)
{
if (i&(<<(j-))) continue;
int k=find(j,f[i]); if (k==-) continue;
f[i|(<<(j-))]=max(f[i|(<<(j-))],c[j][k]+len[j]);
}
}
if (ans==0x7fffffff) ans=-;
printf("%d\n",ans);
return ;
} BZOJ4098 #include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define N 505
#define mod 1000000007
#define add(a,b) (a=(a+b)%mod)
using namespace std;
int n,f[][N][N];
char s[N][N];
int main()
{
scanf("%d",&n);
for (int i=; i<=n; i++) scanf("%s",s[i]+);
if(s[][]!=s[n][n])
{
puts("");
return ;
}
int now=,last=;
f[now][][]=;
for (int h=; h<n; h++)
{
now^=; last^=;
memset(f[now],,sizeof(f[now]));
for (int i=; i<=h; i++)
{
int j=(h-i),a=i+,b=j+;
for (int k=; k<=h; k++)
{
int l=h-k,x=n-l,y=n-k;
/* if (s[a+1][b]==s[x][y-1]) (f[now][i+1][k+1]+=f[last][i][k])%mod;
if (s[a+1][b]==s[x-1][y]) (f[now][i+1][k]+=f[last][i][k])%mod;
if (s[a][b+1]==s[x][y-1]) (f[now][i][k+1]+=f[last][i][k])%mod;
if (s[a][b+1]==s[x-1][y]) (f[now][i][k]+=f[last][i][k])%mod; */
if(s[a+][b]==s[x-][y])add(f[now][i+][ k ],f[last][i][k]);
if(s[a+][b]==s[x][y-])add(f[now][i+][k+],f[last][i][k]);
if(s[a][b+]==s[x-][y])add(f[now][ i ][ k ],f[last][i][k]);
if(s[a][b+]==s[x][y-])add(f[now][ i ][k+],f[last][i][k]);
}
}
}
int ans=;
for (int i=; i<n; i++) add(ans,f[last][i][i]);
printf("%d\n",ans);
return ;
} BZOJ3888 #include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define N 50005
using namespace std;
int n,tot;
struct data{
int h,l,r;
}a[N];
int b[*N],cov[N*];
int read()
{
int x=,f=; char ch;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
return x*f;
}
bool cmp2(data a,data b){return a.h<b.h;
}
int get(int x,int c)
{
return x>=?:-x*c;
}
int cover(int k,int l,int r,int x,int y)
{
if (cov[k]) return ;
if (x<=l && r<=y)
{
cov[k]=; return ;
}
bool ret=;
int mid=(l+r)>>;
if (x<=mid) ret|=cover(k*,l,mid,x,y);
if (mid<y) ret|=cover(k*+,mid+,r,x,y);
cov[k]=cov[k*]&cov[k*+];
return ret;
}
int find(int x)
{
int l=,r=tot,ans=;
while (l<=r)
{
int mid=(l+r)>>;
if (b[mid]<=x) ans=mid,l=mid+; else r=mid-;
}
return ans;
}
int main()
{
n=read();
for (int i=; i<=n; i++)
{
int x=read(),y=read(),c=read();
int l=get(x+,c),r=get(x,c);
a[i].l=l,a[i].r=r,a[i].h=y;
b[++tot]=l; b[++tot]=r;
}
sort(b+,b+tot+);
for (int i=; i<=n; i++) a[i].l=find(a[i].l),a[i].r=find(a[i].r)-;
sort(a+,a+n+,cmp2);
int ans=;
for (int i=; i<=n; i++) ans+=cover(,,tot,a[i].l,a[i].r);
printf("%d\n",ans);
return ;
}
2016.11.11
BZOJ4396 ：贪心
BZOJ4397 ：前缀和
BZOJ3943 ：最小生成树
BZOJ4576：DP：这道题还可以网上有很多种写法
BZOJ4582：DP：之前看错题想了好久最后发现题目意思 好水
BZOJ4412：贪心：这道题也不错，我们首先将每个数减1，如果存在j-->x的子段和大于0，
则说明一定有牛走出去，而我们可以知道在顺时针方向一定存在一个
点没有牛越过去，于是我们找到那个点将环转化为链即可，而这个点
一定是最大子段和的左节点，于是问题解决
2016.11.10
BZOJ1592 Usaco2008 Feb]Making the Grade 路面修整：离散+DP
BZOJ1051 HAOI 受欢迎的牛 ：tarjan
BZOJ2442 修建草坪 ：单调队列优化DP
BZOJ3890 Meeting time : 分层DP
BZOJ4390 Max Flow ：树上差分
BZOJ4525 ：二分答案判定
BZOJ4511 ：DP
BZOJ1592 #include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define N 3005
#define inf 0x7fffffff
using namespace std;
int n,m,ans,a[N],c[N],f[N][N];
int read()
{
int x=,f=; char ch;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
while (x=x*+ch-'',ch=getchar(),ch>='' && ch<='');
return x*f;
}
void solve()
{
sort(c+,c+n+);
m=unique(c+,c+n+)-(c+);
for (int i=; i<=n; i++) f[i][]=inf/;
for (int i=; i<=n; i++)
{
for (int j=; j<=m; j++)
{
f[i][j]=min(f[i-][j]+abs(a[i]-c[j]),f[i][j-]);
}
}
ans=f[n][m];
for (int i=; i<=n; i++) f[i][m+]=inf/;
for (int i=; i<=n; i++)
{
for (int j=m; j>=; j--)
{
f[i][j]=min(f[i-][j]+abs(a[i]-c[j]),f[i][j+]);
}
}
ans=min(ans,f[n][]);
}
int main()
{
n=read();
for (int i=; i<=n; i++) c[i]=a[i]=read();
solve();
printf("%d\n",ans);
return ;
} BZOJ1051 #include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define ll long long
#define N 10005
#define M 50005
using namespace std;
int n,m,ans,u[M],V[M];
int now[N],pre[M],v[M],tot;
int ind,top,total,z[N],dfn[N],low[N],num[N],in[N],out[N],belong[N];
bool vis[N],inq[N];
int read()
{
int x=,f=; char ch;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
return x*f;
}
void ins(int a,int b){
++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b;
}
void dfs(int x)
{ dfn[x]=low[x]=++ind;
vis[x]=inq[x]=; z[++top]=x;
for (int p=now[x]; p; p=pre[p])
{
int son=v[p];
if (!dfn[son]) {dfs(son); low[x]=min(low[x],low[son]);}
else if (inq[son]) low[x]=min(low[x],dfn[son]);
}
if (low[x]==dfn[x])
{
++total;
belong[x]=total; inq[x]=; num[total]=;
while (z[top]!=x)
{
int son=z[top];
belong[son]=total; inq[son]=; num[total]++;
top--;
}
top--;
}
}
int main()
{
n=read(); m=read();
for (int i=; i<=m; i++)
{
int x=read(),y=read();
u[i]=x; V[i]=y;
ins(x,y);
}
for (int i=; i<=n; i++) if (!dfn[i]) dfs(i);
for (int i=; i<=m; i++) if (belong[u[i]]!=belong[V[i]])
{
// cout<<" "<<belong[u[i]]<<" "<<belong[V[i]]<<endl;
++out[belong[u[i]]]; ++in[belong[V[i]]];
}
// for (int i=1; i<=total; i++) cout<<num[i]<<endl;
int sum=;
for (int i=; i<=total; i++)
{
if (!out[i]) {ans=num[i]; sum++; if (sum>=) break;}
}
// cout<<ans<<endl;
if (sum>) ans=; printf("%d\n",ans);
return ;
} BZOJ #include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define ll long long
#define N 100005
using namespace std;
int n,k,head,tail;
ll ans,sum,f[N];
int a[N],pos[N];
int read()
{
int x=,f=; char ch;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
return x*f;
}
int main()
{
n=read(); k=read();
for (int i=; i<=n; i++) a[i]=read(),sum+=a[i];
for (int i=; i<=n; i++)
{
while (head<=tail && pos[head]<i-k-) head++;
f[i]=f[pos[head]]+a[i];
while (head<=tail && f[pos[tail]]>=f[i]) tail--;
++tail; pos[tail]=i;
}
ans=;
for (int i=n-k; i<=n; i++) ans=min(ans,f[i]);
printf("%lld\n",sum-ans);
return ;
} BZOJ3890 #include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define N 105
#define M (N*(N+1))
#define ll long long
using namespace std;
int pre[M],v[M],val1[M],val2[M],now[N],n,m,tot;
bool f[N][M],g[N][M];
int read()
{
int x=,f=; char ch;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
return x*f;
}
void ins(int a,int b,int c,int d)
{
++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b; val1[tot]=c; val2[tot]=d;
}
int main()
{
n=read(); m=read();
for (int i=; i<=m; i++)
{
int u=read(),v=read(),a=read(),b=read();
ins(u,v,a,b);
}
f[][]=g[][]=;
for (int i=; i<=n-; i++)
{
for (int p=now[i]; p; p=pre[p])
{
int son=v[p];
for (int j=val1[p]; j<=; j++) f[son][j]|=f[i][j-val1[p]];
for (int j=val2[p]; j<=; j++) g[son][j]|=g[i][j-val2[p]];
}
}
bool bo=false;
for (int i=; i<=; i++)
if (g[n][i] && f[n][i])
{
bo=true;
printf("%d\n",i);
break;
}
if (!bo) printf("IMPOSSIBLE\n");
return ;
} BZOJ4390 #include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define N 60005
#define M N*2
#define ll long long
using namespace std;
int pre[M],v[M],now[N],tot,n,k,ans;
int f[N][],bin[],deep[N],val[N];
int read()
{
int x=,f=; char ch;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
return x*f;
}
void ins(int a,int b){++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b;
}
void dfs(int x)
{
for (int i=; i<= && bin[i]<=deep[x]; i++) f[x][i]=f[f[x][i-]][i-];
for (int p=now[x]; p; p=pre[p])
{
int son=v[p]; if (son==f[x][]) continue;
deep[son]=deep[x]+; f[son][]=x;
dfs(son);
}
}
int lca(int x,int y)
{
if (deep[x]<deep[y]) swap(x,y);
int t=deep[x]-deep[y];
for (int i=; bin[i]<=t; i++)
{
if (t&bin[i]) x=f[x][i];
}
for (int i=; i>=; i--) if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
if (x==y) return x;
return f[x][];
}
void dfs2(int x,int fa)
{
for (int p=now[x]; p; p=pre[p])
{
int son=v[p]; if (son==fa) continue;
dfs2(son,x); val[x]+=val[son];
}
ans=max(ans,val[x]);
}
int main()
{
n=read(); k=read();
for (int i=; i<n; i++)
{
int x=read(),y=read();
ins(x,y); ins(y,x);
}
bin[]=; for (int i=; i<=; i++) bin[i]=bin[i-]*;
deep[]=; dfs();
for (int i=; i<=k; i++)
{
int x=read(),y=read();
int t=lca(x,y);
val[x]++; val[y]++; val[t]--; val[f[t][]]--;
}
dfs2(,);
printf("%d\n",ans);
return ;
} BZOJ4525 #include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define ll long long
#define inf 0x7ffffff
using namespace std;
int n,k,ans;
int a[];
int read()
{
int x=,f=; char ch;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
return x*f;
}
bool pd(int mid)
{
int l=;
for (int i=; i<=k; i++)
{
int pos=a[l+];
while (l+<=n && ((a[l+]-pos)<=*mid)) l++;
}
if (l>=n) return true;
return false;
}
int main()
{
n=read(); k=read();
for (int i=; i<=n; i++) a[i]=read();
sort(a+,a+n+);
int l=,r=inf-;
while (l<=r)
{
int mid=(l+r)>>;
if (pd(mid)) ans=mid,r=mid-; else l=mid+;
}
printf("%d\n",ans);
return ;
} BZOJ4511 #include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define ll long long
#define N 50005
using namespace std;
int ans,n,a[N],f[N][];
int read()
{
int x=,f=; char ch;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
return x*f;
}
int main()
{
n=read();
for (int i=; i<=n; i++) a[i]=read()%;
memset(f,-,sizeof(f));
f[][]=; for (int i=; i<=n; i++) f[i][a[i]]=;
for (int i=; i<=n; i++)
for (int j=; j<=; j++)
if (f[i-][j]!=-) f[i][(j+a[i])%]=max(f[i][(j+a[i])%],f[i-][j]+);
for (int i=; i<=n; i++) ans=max(ans,f[i][]);
printf("%d\n",ans);
return ;
}
代码集合
2016.11.9
BZOJ1711： 最大流
BZOJ1642: 排序+DP
BZOJ1711 #include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<queue>
#define inf 0x7fffffff
#define ll long long
#define N 505
#define M 50005
using namespace std;
int n,F,D,head,tail,list[N<<],tot=,S,T,ans=;
int pre[M],v[M],cap[M],now[N],deep[N];
queue<int>q;
int read()
{
int x=,f=; char ch;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
return x*f;
}
void ins(int a,int b,int c){
++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b; cap[tot]=c;
++tot; pre[tot]=now[b]; now[b]=tot; v[tot]=a; cap[tot]=;
}
void init_build()
{
n=read(); F=read(); D=read();
S=; T=n*+F+D+;
for (int i=; i<=F; i++) ins(S,i,);
for (int i=F+n*+; i<=F+n*+D; i++) ins(i,T,);
for (int i=; i<=n; i++)
{
int A=read(),B=read();
for (int j=; j<=A; j++) {int x=read(); ins(x,F+i,);}
for (int j=; j<=B; j++) {int x=read(); ins(F+n+i,F+n*+x,);}
}
for (int i=;i<=n;i++) ins(F+i,F+i+n,);
}
bool bfs()
{
for (int i=S;i<=T;i++) deep[i]=-;
deep[S]=; head=,tail=,list[]=S;
while (head<tail)
{
int x=list[++head];
for (int p=now[x]; p; p=pre[p])
{
int son=v[p];
if (cap[p] && deep[son]==-)
{
deep[son]=deep[x]+;
if (son==T) return ;
list[++tail]=son;
}
}
}
return ;
}
int find(int x,int tmpflow)
{
int temp,re;
if (x==T) return tmpflow;
re=temp=;
for (int p=now[x]; p; p=pre[p])
{
int son=v[p];
if (cap[p] && deep[son]==deep[x]+)
{
temp=find(son,min(tmpflow,cap[p]));
cap[p]-=temp;
cap[p^]+=temp;
re+=temp;
tmpflow-=temp;
if (tmpflow==) break;
}
}
deep[x]=-;
return re;
}
void dinic()
{
ans=;
while (bfs())
{
ans+=find(S,inf);
}
}
int main()
{
tot=;
init_build();
dinic();
printf("%d\n",ans);
return ;
} BZOJ #include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,r,ans=;
int read(){
int x=,f=; char ch;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
return x*f;
}
struct data{
int l,r,val;
}a[];
int f[];
bool cmp(data a,data b)
{
return a.l==b.l?a.r<b.r:a.l<b.l;
}
int main()
{
n=read(); m=read()+; r=read();
a[].l=a[].r=-; a[].val=;
for (int i=; i<=m; i++)
{
a[i].l=read(),a[i].r=read()-,a[i].val=read();
}
sort(a+,a+m+,cmp);
for (int i=; i<=m; i++)
{
for (int j=; j<=i-; j++)
{
if (a[j].r+r<a[i].l)
{
f[i]=max(f[i],f[j]+a[i].val);
ans=max(ans,f[i]);
}
}
}
printf("%d\n",ans);
return ;
}
代码集合
2016.11.8
BZOJ1708：背包
BZOJ1690：01分数规划+spfa+二分
BZOJ1669：LIS问题+单调栈
BZOJ #include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define ll long long
using namespace std;
int n,m;
ll f[];
int read()
{
int x=,f=; char ch;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
return x*f;
}
int main()
{
n=read(); m=read(); f[]=;
for (int i=; i<=n; i++)
{
int x=read();
for (int i=x; i<=m; i++) f[i]+=f[i-x];
}
printf("%lld\n",f[m]);
return ;
} BZOJ1690
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define ll long long
#define N 1005
#define M 5005
using namespace std;
int n,m,tot;
int a[N],now[N],pre[M],v[M];
double ans,mid,val[M],value[N],dis[N];
bool vis[N];
int read()
{
int x=,f=; char ch;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
return x*f;
}
void ins(int a,int b,int c){++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b; val[tot]=c;
}
bool spfa(int x)
{
vis[x]=;
for (int p=now[x]; p; p=pre[p])
{
int son=v[p];
if (dis[son]<dis[x]+value[son]-mid*val[p])
{
if (!vis[son])
{
dis[son]=dis[x]+value[son]-mid*val[p];
if (spfa(son)) return ;
}
else return ;
}
}
return vis[x]=;
}
int main()
{
n=read(); m=read();
for (int i=; i<=n; i++) value[i]=read();
for (int i=; i<=m; i++)
{
int a=read(),b=read(),c=read(); ins(a,b,c);
}
double l=,r=,eps=1e-;
while (r-l>eps)
{
memset(dis,,sizeof(dis));
memset(vis,,sizeof(vis));
mid=(l+r)/2.0; dis[]=0.0;
if (spfa()) ans=mid,l=mid; else r=mid;
}
printf("%0.2lf\n",ans);
return ;
} BZOJ1669 #include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define N 5005
#define ll long long
using namespace std;
int n,tot;
int b[N];
int read()
{
int x=,f=; char ch;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
return x*f;
}
int main()
{
int n=read(),tot=;
for (int i=; i<=n; i++)
{
int x=read();
if (x>b[tot])
{
tot++; b[tot]=x;
}
else
{
int l=tot;
while (l>= && b[l]>=x) l--;
//cout<<" "<<l<<endl;
b[l+]=x;
}
}
printf("%d\n",tot);
return ;
}
代码集合
2016.11.7
BZOJ3298：打表找规律
BZOJ3296：并查集
BZOJ1599：模拟
BZOJ1232：最小生成树
BZOJ3298 #include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define ll long long
#define N 1000005
using namespace std;
int n,m,f[N];
int read()
{
int x=,f=; char ch;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
return x*f;
}
int main()
{
n=read()+; m=read()+;
f[]=; int t=;
for (int i=; i<=m; i++)
{
if (f[i]) continue;
t++; f[i]=i+t; if (i+t<=m) f[i+t]=i;
}
int T=read();
while (T--)
{
int x=read()+,y=read()+;
if (f[x]==y) printf("Farmer John\n"); else printf("Bessie\n");
}
return ;
} BZOJ3296 #include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define ll long long
#define N 40005
using namespace std;
int fa[N],id[N],n,m,ans;
int read()
{
int x=,f=; char ch;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
return x*f;
}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main()
{
n=read(); m=read();
for (int i=; i<=n; i++) fa[i]=i;
for (int i=; i<=n; i++)
{
int k=read();
for (int j=; j<=k; j++){int x=read(); if (!id[x]) id[x]=i; else {fa[find(id[x])]=find(i); id[x]=i;}}
}
for (int i=; i<=n; i++) if (find(i)==i) ans++;
printf("%d\n",ans-);
return ;
} BZOJ1599 #include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define ll long long
using namespace std;
int sum[],ans;
int read()
{
int x=,f=; char ch;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
return x*f;
}
int main()
{
int a=read(),b=read(),c=read();
for (int i=; i<=a; i++)
for (int j=; j<=b; j++)
for (int k=; k<=c; k++) sum[i+j+k]++;
sum[]=; ans=; for (int i=; i<=a+b+c; i++) if (sum[i]>sum[ans]) ans=i;
printf("%d\n",ans);
return ;
} BZOJ1232 #include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define ll long long
#define N 100005
using namespace std;
int n,m;
struct data{
int u,v,val;
}a[N];
int c[N],Min=0x7fffffff,ans=,fa[N],cnt=;
int read()
{
int x=,f=; char ch;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
return x*f;
}
bool cmp(data a,data b){return a.val<b.val;
}
int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}
int main()
{
n=read(); m=read();
for (int i=; i<=n; i++) fa[i]=i;
for (int i=; i<=n; i++) c[i]=read();
for (int i=; i<=m; i++) a[i].u=read(),a[i].v=read(),a[i].val=read()*+c[a[i].u]+c[a[i].v];
sort(a+,a+m+,cmp);
for (int i=; i<=m; i++)
{
int u=a[i].u,v=a[i].v,val=a[i].val;
int fu=find(u),fv=find(v);
if (fv!=fu)
{
fa[fv]=fu; Min=min(Min,min(c[u],c[v]));
ans+=val; cnt++; if (cnt==n-) break;
}
}
printf("%d\n",ans+Min);
return ;
}
代码集合