BZOJ2660: [Beijing wc2012]最多的方案
Aug 18, 2015 08:44:05 PM
题解:
首先我们用Fib贪心的找出一组解.
假如我们利用二进制存储得到的那组解.
例如15=13+2
就是(从小到大)010001,分别代表1,2,3,5,8,13.
由于我们知道由于Fib数列的性质,001等价于110.
所以我们需要知道找到的那组解一共能够变换出多少方案.
我们依次考虑得到的那组解中的每个1,令$f[i][0]$表示第$i$个一在变换后的方案中是$0$的方案数,$f[i][1]$同理.
我们首先观察001变换出110的性质,我们不难发现只能变换出这样的形式:
1->110->11010
即如果有$k$个空位,则有$\lfloor\frac{k}{2}\rfloor$种方案,知道了这些就不难dp了.
详情见代码.
代码:
#include<cstdio>
#include<cctype>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll f[90][2];
ll fib[90];
int ins[90],cnt;
int main(){
ll n;
cin>>n;
int i,j;
for(fib[1]=1,fib[2]=2,i=3;i<=88;++i)
fib[i]=fib[i-1]+fib[i-2];
for(i=88;i>=1;--i)
if(n>=fib[i])
n-=fib[ins[++cnt]=i];
f[cnt][1]=1;
f[cnt][0]=(ins[cnt]-1)>>1;
for(i=cnt-1;i>=1;--i){
f[i][1]=f[i+1][0]+f[i+1][1];
f[i][0]=f[i+1][0]*((ins[i]-ins[i+1])>>1)+f[i+1][1]*((ins[i]-ins[i+1]-1)>>1);
}
cout<<f[1][0]+f[1][1]<<endl;
return 0;
}
BZOJ4205: 卡牌配对
Aug 18, 2015 08:39:03 PM
题解:
首先暴力连边匹配肯定是不行的...
由于$200$以内的质数仅有$46$个,我们构造三类点$ab(p_1,p_2),ac(p_1,p_2),bc(p_1,p_2)$分别表示参数1能被$p_1$整除,参数2能被$p_2$整除,剩下的依此类推.
然后对于左侧的点向符合条件的中间点连边.
对于右侧的点从符合条件的中间点连边.
这样做事实上是边分组,很显然是正确的.
直接用dinic玩就行了.
代码:
#include<cstdio>
#include<cctype>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define inf 0x3f3f3f3f
struct Solver{
static const int V=100010;
static const int E=3000010;
int head[V],next[E],flow[E],end[E],ind,d[V];
inline void reset(){
memset(head,-1,sizeof head);
ind=0;
}
inline void addedge(int a,int b,int f){
int q=ind++;
end[q]=b;
next[q]=head[a];
head[a]=q;
flow[q]=f;
}
inline void make(int a,int b,int f){
addedge(a,b,f);
addedge(b,a,0);
}
inline bool bfs(int s,int t){
static int q[V];
int fr=0,ta=0;
memset(d,-1,sizeof d);
d[q[ta++]=s]=0;
while(fr!=ta){
int i=q[fr++];
for(int j=head[i];j!=-1;j=next[j])
if(flow[j]&&d[end[j]]==-1)
d[q[ta++]=end[j]]=d[i]+1;
}
return d[t]!=-1;
}
inline int dinic(int p,int t,int Maxflow){
if(p==t)
return Maxflow;
int last=Maxflow;
for(int j=head[p];j!=-1;j=next[j])
if(flow[j]&&d[end[j]]==d[p]+1){
int to=dinic(end[j],t,flow[j]>last?last:flow[j]);
if(to){
flow[j]-=to;
flow[j^1]+=to;
if(!(last-=to))
return Maxflow;
}
}
d[p]=-1;
return Maxflow-last;
}
inline int Maxflow(int s,int t){
int re=0;
while(bfs(s,t))
re+=dinic(s,t,inf);
return re;
}
}g;
#define N 210
int p[N],cnt;
bool np[N];
inline void pre(){
int i,j;
for(i=2;i<=200;++i){
if(!np[i])
p[++cnt]=i;
for(j=1;j<=cnt&&p[j]*i<=200;++j){
np[i*p[j]]=1;
if(i%p[j]==0)
break;
}
}
}
int a[51][51],b[51][51],c[51][51];
int x[2][30010],y[2][30010],z[2][30010];
vector<int>v[N];
int main(){
pre();
int n,m;
cin>>n>>m;
int i,j,k;
for(i=1;i<=n;++i)
scanf("%d%d%d",&x[0][i],&y[0][i],&z[0][i]);
for(i=1;i<=m;++i)
scanf("%d%d%d",&x[1][i],&y[1][i],&z[1][i]);
for(i=1;i<=200;++i)
for(j=1;j<=cnt;++j)
if(i%p[j]==0)
v[i].push_back(j);
int id=n+m;
for(i=1;i<=cnt;++i)
for(j=1;j<=cnt;++j){
a[i][j]=++id;
b[i][j]=++id;
c[i][j]=++id;
}
int s=0,t=++id;
g.reset();
for(i=1;i<=n;++i)
g.make(s,i,1);
for(i=1;i<=m;++i)
g.make(n+i,t,1);
int p,q;
for(i=1;i<=n;++i){
for(j=0;j<v[x[0][i]].size();++j)
for(k=0;k<v[y[0][i]].size();++k){
p=v[x[0][i]][j];
q=v[y[0][i]][k];
g.make(i,a[p][q],1);
}
for(j=0;j<v[x[0][i]].size();++j)
for(k=0;k<v[z[0][i]].size();++k){
p=v[x[0][i]][j];
q=v[z[0][i]][k];
g.make(i,b[p][q],1);
}
for(j=0;j<v[y[0][i]].size();++j)
for(k=0;k<v[z[0][i]].size();++k){
p=v[y[0][i]][j];
q=v[z[0][i]][k];
g.make(i,c[p][q],1);
}
}
for(i=1;i<=m;++i){
for(j=0;j<v[x[1][i]].size();++j)
for(k=0;k<v[y[1][i]].size();++k){
p=v[x[1][i]][j];
q=v[y[1][i]][k];
g.make(a[p][q],n+i,1);
}
for(j=0;j<v[x[1][i]].size();++j)
for(k=0;k<v[z[1][i]].size();++k){
p=v[x[1][i]][j];
q=v[z[1][i]][k];
g.make(b[p][q],n+i,1);
}
for(j=0;j<v[y[1][i]].size();++j)
for(k=0;k<v[z[1][i]].size();++k){
p=v[y[1][i]][j];
q=v[z[1][i]][k];
g.make(c[p][q],n+i,1);
}
}
cout<<g.Maxflow(s,t)<<endl;
return 0;
}
BZOJ4240: 有趣的家庭菜园
Aug 18, 2015 08:32:43 PM
题解:
首先预处理出$l_i$表示第$i$个数左侧比第$i$个数大的个数,$r_i$右侧同理.
首先脑补出我们应该将序列排成先单调不降,后单调不增的形式.
我们从大到小将数插入序列,考虑插入某个数,比这个数大的已经全部插入完毕了,由于排成那种形式,我们只能将这个数放在当前序列的头或尾.
若放在开头,则带来$l_i$的逆序对;否则带来$r_i$的逆序对.
显然每个数之间都是独立的,我们直接贪心就行了.
时间复杂度$O(nlogn)$.
代码:
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
#define N 300010
int n,_n,a[N],b[N];
inline int getc(){
static const int L=1<<15;
static char buf[L],*S=buf,*T=buf;
if(S==T){
T=(S=buf)+fread(buf,1,L,stdin);
if(S==T)
return EOF;
}
return*S++;
}
inline int getint(){
int c;
while(!isdigit(c=getc()));
int x=c-'0';
while(isdigit(c=getc()))
x=(x<<1)+(x<<3)+c-'0';
return x;
}
int A[N],l[N],r[N];
inline int ask(int x){
int re=0;
for(;x;x-=x&-x)
re+=A[x];
return re;
}
inline void upd(int x){
for(;x<=_n;x+=x&-x)
++A[x];
}
int main(){
n=getint();
int i,j;
for(i=1;i<=n;++i)
a[i]=b[i]=getint();
sort(b+1,b+n+1);
_n=unique(b+1,b+n+1)-b-1;
for(i=1;i<=n;++i)
a[i]=lower_bound(b+1,b+_n+1,a[i])-b;
for(i=1;i<=n;++i){
l[i]=i-1-ask(a[i]);
upd(a[i]);
}
memset(A,0,sizeof A);
for(i=n;i>=1;--i){
r[i]=n-i-ask(a[i]);
upd(a[i]);
}
long long ans=0;
for(i=1;i<=n;++i)
ans+=min(l[i],r[i]);
cout<<ans<<endl;
return 0;
}