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;
}
BZOJ3301: [USACO2011 Feb] Cow Line
Aug 18, 2015 07:34:33 PM
题目大意:
(1)给定一个排列,问排列的序号.
(2)给定一个序号,要求构造出给定序号的排列.
题解:
首先要知道怎么得出排列的序号.
假如序列的长度为$n$,且第$i$个元素为$P_i$.
则序号为:$\sum_{i=1}^{n}(n-i)!\sum_{j=i+1}^{n}[P_i>P_j]$
这样的话可以$O(n^2)$算出排列的序号.
构造序列的话也是一个道理,我是暴力的,没管复杂度...
代码:
#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
typedef unsigned long long llu;
int a[21],ans[21];
llu fac[21];
bool ok[21];
int main(){
int n,Q,i,j;
char s[10];
cin>>n>>Q;
llu x;
for(fac[0]=i=1;i<=20;++i)
fac[i]=fac[i-1]*i;
int temp;
while(Q--){
scanf("%s",s);
if(s[0]=='P'){
cin>>x;
--x;
for(i=1;i<=n;++i)
a[i]=x/fac[n-i],x-=a[i]*fac[n-i];
memset(ok,1,sizeof ok);
for(i=1;i<=n;++i){
temp=0;
for(j=1;j<=n;++j){
if((temp+=ok[j])==a[i]+1)
break;
}
ok[ans[i]=j]=0;
}
for(i=1;i<=n;++i){
if(i!=1)
putchar(' ');
printf("%d",ans[i]);
}
puts("");
}
else{
for(i=1;i<=n;++i)
scanf("%d",&a[i]);
for(x=0,i=1;i<=n;++i){
for(temp=0,j=i+1;j<=n;++j)
temp+=(a[i]>a[j]);
x+=fac[n-i]*temp;
}
cout<<x+1<<endl;
}
}
return 0;
}
BZOJ3884: 上帝与集合的正确用法 数论
Feb 28, 2015 07:25:17 PM
首先我们知道欧拉定理:
\[a^{\phi(p)}=1(mod~p)((a,p)=1)\]
那么看起来这道题有点能做了.
可惜如果\(p\)是偶数又怎么办?
我们有\(cx%cy=c(x%y)\)这条神奇的性质.也很容易证明.
这样,我们就可以将问题递归处理了.
对于\(\phi\)函数的不断迭代是\(log\)级别的,然后我们每次\(O(\sqrt{n}logn)\)求\(\phi\).因此时间复杂度为\(O(\sqrt{n}logn)\).
还有另外一种不用讨论的方法:
有公式:\(a^x=a^{x\%\phi(p)+\phi(p)}(mod~p)(x>=\phi(p))\)
这样就能更加自然地递归下去了.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
inline int getphi(int x){
int re=x,t=x;
for(int i=2;i*i<=x;++i){
if(t%i==0){
re=(LL)re*(i-1)/i;
while(t%i==0)t/=i;
}
}if(t!=1)re=(LL)re*(t-1)/t;
return re;
}
inline int ksm(int x,int y,int p){
int re=1,t=x;for(;y;y>>=1,t=(LL)t*t%p)if(y&1)re=(LL)re*t%p;return re;
}
inline int calc(int p){
if(p==1)return 0;
else{
int phi=getphi(p),re=calc(phi);
return ksm(2,re+phi,p);
}
}
int main(){
int T,p;scanf("%d",&T);
while(T--){
scanf("%d",&p);
printf("%d\n",calc(p));
}
return 0;
}
BZOJ2956:模积和 数学
Feb 10, 2015 06:48:39 PM
思路:
其实是一道简单题.关键是要注意到题目中的一个条件:\(i\not=j\)!!!
我们考虑用所有的情况减去\(i=j\)的情况.
所有的情况就很好求了.令\(f(n)=\sum_{i=1}^{n}n\%i\),则所有的情况为\(f(n)*{f(m)}\).
这玩意很容易分块求.
然后\(i=j\)的情况的贡献是:
\((n\%i)*(m\%i)=(n-i*\frac{n}{i})*(m-i*\frac{m}{i})=nm+i^2\frac{n}{i}\frac{m}{i}-n*i\frac{m}{i}-m*i\frac{n}{i}\)
这样发现分开之后都可以分块求.
于是就\(O(\sqrt{n})\)水过.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
static const int mod=19940417,rev2=(mod+1)>>1,rev6=3323403;
inline void mul(int&x,int y){x=(LL)x*y%mod;}
inline void inc(int&x,int y){if((x+=y)>=mod)x-=mod;}
inline void dec(int&x,int y){x=x<y?x+mod-y:x-y;}
inline int calc(int n){//return sigma i^2
int res=n;mul(res,(LL)(n+1)*(2*n+1)%mod),mul(res,rev6);return res;
}
inline int cal(int l,int r){
int cl=calc(l-1),cr=calc(r);
return cr<cl?cr+mod-cl:cr-cl;
}
inline int solve1(int n,int lim){//return sigma i*(n/i)
int lst,t,res=0;
for(int i=1;i<=lim;i=lst+1){
lst=min(lim,n/(n/i));
mul(t=n/i,(LL)(i+lst)*(lst-i+1)%mod),mul(t,rev2);
inc(res,t);
}return res;
}
inline int solve2(int n){//return sigma n%i
return ((LL)n*n%mod+mod-solve1(n,n))%mod;
}
inline int solve3(int n,int m,int lim){//return sigma i^2(n/i)(m/i)
int lst,t,res=0;
for(int i=1;i<=lim;i=lst+1){
lst=min(n/(n/i),m/(m/i)),lst=min(lst,lim);
mul(t=(LL)(n/i)*(m/i)%mod,cal(i,lst));
inc(res,t);
}return res;
}
int main(){
int n,m;scanf("%d%d",&n,&m);register int i,j;
int res=(LL)solve2(n)*solve2(m)%mod;
dec(res,(LL)min(n,m)*n%mod*m%mod);
inc(res,(LL)solve1(n,min(n,m))*m%mod);
inc(res,(LL)solve1(m,min(n,m))*n%mod);
dec(res,solve3(n,m,min(n,m)));
printf("%d",res);
return 0;
}