[HDOJ3430 Shuffling]【解一元同余方程组】【例题】

【题目大意】
先有一个1,2,3..n的序列。
给定一个置换群。
然后再给出一个目标状态。
求用置换群置换几次到达目标状态?
【算法分析】
暴力求出各循环节。与错位的次数。
得到p个形如 x = ci (mod mi)的方程。
mi并非两两互质,所以不能使用中国剩余定理。
我们可以通过类似中国剩余定理的方法求解。
今天我在HDU比赛时最后一直在推这个同余方程组怎么求。。。
额,以前没写过,于是果断沙茶,大家一起来鄙视我。。。
后来再推了一阵,又看了一下师傅的推导,虽然和我的不大相同,但方向应该没错。
在后来。。。找了个大神的模板过来看。。。我晕,就是有一个地方mod的数打错了。。。
现在记录一下的我的推导过程。
使用类似数学归纳法的思想:
首先,对于同余方程 x = ci (mod mi)的一个解x。那么x + k * mi依然是该方程的一个解。而且同时,这样能取遍该同余方程的所有解。
我们考虑假设已经找到了一个最小自然数解x,满足了前i-1个同余方程。
那么,我们现在要让x满足第i个方程的同时,仍然满足前i-1个方程,那么我们只能取形如这样的数:
x + k * LCM (其中LCM代表(m1,m2,m3…mi-1)的最小公倍数)。
好了,那么新的第i个同余方程变成
(x+k*LCM) = ci (mod mi)    ————————其中x,LCM,ci,mi已知。
于是变成 k * LCM + t * mi = ci-x。这个方程就可以利用拓展欧几里得算法的求解。
具体是调用 ex_gcd(LCM,mi,k,t)得出一个k*LCM+t*mi=gcd(LCM,mi)的解。(关于k,t)
然后k*(ci-x)/gcd(LCM,mi)可以得出真正要求的红色式子中的k。
接着就是将一个适合的k带进红色的式子。
这一步就很容易出错了,我在比赛时就是这里错了。。。= =
考虑我们在exgcd那一步求得的方程:k*LCM+t*mi=gcd(LCM,mi)。
它本质上是: k * (LCM / gcd(LCM,mi)) + t* (mi / gcd(LCM,mi))=1
所以假设(k,t)是一组可行解,那么所有的可行解可以这么表示:
(k + p*mi / gcd(LCM,mi) , t – p*LCM / gcd(LCM,mi) )。(其中p为整数)
于是我们可以将k%( mi / gcd(LCM,mi) )。那么得到的数必然也是一个可行的k。(并且是最小自然数解)
这样的k自然是最合适的,我们把它带进红色式子。
那么得到新的x,然后再更新一下lcm,合并到最后,就得出一个最小整数解x。
【CODE】
#include #include #include #include using namespace std;
const int N=525;
typedef __int64 lld;
int n,cnt;
int next[N],Final[N],v[N];
int L[N],P[N];
lld m[N],c[N];
bool check;

void init(){
check=true;
cnt=0;
memset(v,0,sizeof(v));
for (int St=1;St<=n;St++)
if (!v[St]){
int i=St,Num=0,j,k;
cnt++;
while (!v[i]){
v[i]=1;
L[++Num]=i;
P[Num]=Final[i];
i=next[i];
}
bool Same=false;
for (i=1;i<=Num;i++)
if (P[i]==L[1]){
Same=true;
j=i; k=1;
do{
if (P[j]!=L[k]) Same=false;
j=j%Num+1;
k=k%Num+1;
}while (i!=j);
break;
}
if (!Same) check=false;
m[cnt]=Num;
c[cnt]=(Num-(i-1))%Num;
}
}

lld exgcd(lld a,lld b,lld &x,lld &y){
if (!b){
x=1;
y=0;
return a;
}
else{
lld res=exgcd(b,a%b,x,y);
lld t=x;
x=y;
y=t-(a/b)*y;
return res;
}
}

lld mod(lld x,lld y){
lld res=x%y;
if (res<0) res+=y;
return res;
}

void solve(){
n=cnt;
check=true;
lld ans=c[1],LCM=m[1],x,y,g,mm;
for (int i=2;i<=n;i++){
g=exgcd(LCM,m[i],x,y);
if ((c[i]-ans)%g) {check=false; return;}
ans=mod( ans + LCM * mod( (c[i]-ans)/g*x, m[i]/g ) , LCM/g*m[i]);
LCM=LCM/g*m[i];
}
printf("%I64dn",ans);
}

int main(){
while (1){
scanf("%d",&n); if (!n) break;
for (int i=1;i<=n;i++) scanf("%d",&next[i]);
for (int i=1;i<=n;i++) scanf("%d",&Final[i]);
init();
if (!check) puts("-1");
else{
solve();
if (!check) puts("-1");
}
}
}

[ZSUCPC2009pre Problem F : N Queens Puzzle]【300皇后】【随机构造】【贪心调整】

【题目大意】
输入n<=300和k<=20。
要求输出n皇后的k个可行解,并且这k个可行解互不相同。
每个方案以一个1~n的排列为格式输出来。
Special Judge
【算法分析】
搜索显然不可行。
于是乱搞。
我们设斜行里冲突的对数为估价函数f(state)
先随机一个1~n的排列。
然后算出估价函数f(state)。
如果函数值不为0,那么用爬山法。
具体就是交换两个皇后,看估价函数值是否下降,下降的话就接受。
如果到达一个情况,怎么交换函数值都不减少。。。那么就是陷进局部最优解了。我们就重新随机一个排列再搞。。。
【其它】
复杂度不好算= =。。。1TLE,1Y。
TLE是因为算估价函数过于暴力。
后来利用数组把一个O(n^2)的统计变成O(1)。于是AC。
最终通过所有数据的时间用clock函数测得是343MS。
【输入数据】
10
8 2
9 3
20 5
50 5
100 10
150 10
200 10
250 10
280 20
300 20
【CODE】
#include #include #include #include using namespace std;
const int N=305;
int n,Times,done;
int save[25][N];
int a[N],v[N],Num1[N*2],Num2[N*2];
bool change;

int Cal(){
int res=0,i,j;
for (i=1;i for (j=i+1;j<=n;j++)
if (i+a[i]==j+a[j] || i-a[i]==j-a[j]) res++;
return res;
}

void Random_List(){
int i,j,cnt,x;
for (i=1;i<=n;i++) v[i]=0;
for (i=n;i>=1;i–){
x=rand()%i+1;
cnt=0;
for (j=1;j<=n;j++)
if (!v[j]){
cnt++;
if (cnt==x){
a[i]=j;
v[j]=1;
break;
}
}
}
}

void Get(){
int now,i,j,tmp;
while (1){
Random_List();
now=Cal();
for (i=1;i<=2*n;i++) Num1[i]=Num2[i]=0;
for (i=1;i<=n;i++){ Num1[a[i]+i]++; Num2[a[i]-i+n]++; }
while (now){
change=false;
for (i=1;i for (j=i+1;j<=n;j++){
tmp=now;
Num1[a[i]+i]–; Num1[a[j]+j]–;
Num2[a[i]-i+n]–; Num2[a[j]-j+n]–;
tmp-=Num1[a[i]+i]; tmp-=Num1[a[j]+j];
tmp-=Num2[a[i]-i+n]; tmp-=Num2[a[j]-j+n];
swap(a[i],a[j]);
tmp+=Num1[a[i]+i]; tmp+=Num1[a[j]+j];
tmp+=Num2[a[i]-i+n]; tmp+=Num2[a[j]-j+n];
Num1[a[i]+i]++; Num1[a[j]+j]++;
Num2[a[i]-i+n]++; Num2[a[j]-j+n]++;
if (tmp now=tmp;
change=true;
}
else{
Num1[a[i]+i]–; Num1[a[j]+j]–;
Num2[a[i]-i+n]–; Num2[a[j]-j+n]–;
swap(a[i],a[j]);
Num1[a[i]+i]++; Num1[a[j]+j]++;
Num2[a[i]-i+n]++; Num2[a[j]-j+n]++;
}
}
if (!change) break;
}
if (!now) break;
}
}

bool check(){
int i,j;
bool res;
for (i=1;i<=done;i++){
res=false;
for (j=1;j<=n;j++)
if (a[j]!=save[i][j]) res=true;
if (!res) return false;
}
return true;
}

void push(){
done++;
for (int i=1;i<=n;i++) save[done][i]=a[i];
}

void output(){
for (int i=1;i<=Times;i++){
for (int j=1;j printf("%dn",save[i][n]);
}
}

int main(){
freopen("queen.in","r",stdin);
freopen("output.txt","w",stdout);
srand(‘e’+’d’+’w’+’a’+’r’+’d’+’_’+’m’+’j’+’n’+’R’+’P’+’+’+’+’);
int Tc,i;
scanf("%d",&Tc);
for (i=0;i scanf("%d%d",&n,&Times);
done=0;
while (done Get();
if (check()) push();
if (done==Times) output();
}
}
return 0;
}

[第33届ACMICPC成都赛区网络赛 Problem H : There is a war]【最小割的一些性质】

【题目大意】
给定一个有向带权图。1为源点,n为汇点。
求加一条权为无穷的边,并且改边的起始点和结束点都1V<=100
E<=V*(V-1)/2
【算法分析】
暴力加边判断肯定不可行。
于是,我们可以弄一个稍微不暴力的方法。
先对这个图求一次最大流。得到一个最小割。
我们加的边一定是这样的:起始点在源集合,结束点在汇集合。
那么dfs求出源集。
设加的边是然后我们将发现,加了边以后,新的增广路必然是这样的:S->p1->p2….->a->b->p3…->T。
于是我们可以从a->b这里截断两边分别求解。
就是在一开始最小割的残余网络中,
若i∈源集,那么FF[i]=maxFlow (S->i)
若i∈汇集,那么FF[i]=maxFlow (i->T)
最终答案将是Max ( Min(FF[i],FF[j]) + initFlow ) 其中i∈源集,j∈汇集。initFlow为原图最小割。
【其它】1Y。
【CODE】
#include #include #include #include using namespace std;
const int N=105;
struct edge{int x,y,c,next;}g[N*N],tg[N*N];
int n,m,e,S,T,Flow;
int ls[N],d[N],fa[N],cur[N],num[N],v[N],FF[N];

void addedge(int x,int y,int c){
g[++e].x=x; g[e].y=y; g[e].c=c; g[e].next=ls[x]; ls[x]=e;
g[++e].x=y; g[e].y=x; g[e].c=0; g[e].next=ls[y]; ls[y]=e;
}

void init(){
e=1; memset(ls,0,sizeof(ls));
scanf("%d%d",&n,&m);
int x,y,c,i;
for (i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&c);
addedge(x,y,c);
}
}

void relabel(int k){
cur[k]=ls[k];
int mm=n;
for (int t=ls[k];t;t=g[t].next)
if (g[t].c && d[g[t].y] mm=d[g[t].y];
d[k]=mm+1;
}

void change(){
int nf=0x7FFFFFFF;
for (int i=T;i!=S;i=g[fa[i]].x)
if (g[fa[i]].c for (int i=T;i!=S;i=g[fa[i]].x){
g[fa[i]].c-=nf;
g[fa[i]^1].c+=nf;
}
Flow+=nf;
}

void sap(){
int i;
for (i=1;i<=n;i++){
num[i]=0;
d[i]=0;
cur[i]=ls[i];
}
num[0]=n;
i=S;
while (d[S] int &t=cur[i];
for (;t;t=g[t].next)
if (g[t].c && d[g[t].y]+1==d[g[t].x]) break;
if (t){
fa[g[t].y]=t;
i=g[t].y;
if (i==T){
change();
i=S;
}
}
else{
if (!–num[d[i]]) break;
relabel(i);
++num[d[i]];
if (i!=S) i=g[fa[i]].x;
}
}
}

void dfs(int p){
v[p]=1;
for (int t=ls[p];t;t=g[t].next)
if (g[t].c && !v[g[t].y]) dfs(g[t].y);
}

void solve(){
memset(v,0,sizeof(v));
dfs(1);
for (int i=2;i<=e;i++) tg[i]=g[i];
int initFlow=Flow,ans=Flow;
for (int i=2;i if (v[i]){
S=1; T=i;
Flow=0;
for (int j=2;j<=e;j++) g[j]=tg[j];
sap();
FF[i]=Flow;
}
else{
S=i; T=n;
Flow=0;
for (int j=2;j<=e;j++) g[j]=tg[j];
sap();
FF[i]=Flow;
}
for (int i=2;i for (int j=2;j if (v[i] && !v[j] && min(FF[i],FF[j])+initFlow>ans)
ans=min(FF[i],FF[j])+initFlow;
printf("%dn",ans);
}

int main(){
freopen("war.in","r",stdin);
freopen("war.out","w",stdout);
int Tc,i;
scanf("%d",&Tc);
for (i=0;i init();
S=1; T=n; Flow=0;
sap();
solve();
}
return 0;
}

[方格取数]【二分图最大点权独立集】【最小割】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1475
【算法分析】
就是求一个二分图的最大点权独立集。
首先我们对图黑白染色,然后白的放X部,黑的放Y部。
再次假设我们取到所有格子上的权。
然后我们尝试最小割的一般构造方法。
对于X部点,如果属于割中源的那一边。那么就当做取这个点。如果属于汇的那一边,则不取。
对于Y部点,如果属于割中源的那一边。那么就当做不取这个点。如果属于汇的那一边,则取。
于是对应地连边。
对于i∈X部,那么连边S->i,容量应当是Wi。
对于i∈Y部,那么连边i->T,容量应当是Wi。
那么相邻的格子连边容量为INF.
对于割,证明命题:如果两点相邻,那么他们不会同时取。
先假设他们同时取了。
对于X部点,被割在了源那一边。
对于Y部点,被割在了汇那一边。
那么:这两点之间那条边,就成了割边!
又由于它是容量为INF的。那么不可能成为割边。
于是反证得上面的命题成立。
最后本题用最小割完美解决。
【其它】1Y。
【CODE】
#include #include #include const int N=35;
const int INF=0x7FFFFFFF;
struct edge{int x,y,c;edge *next,*op;}g[205555],*ls[N*N],*cur[N*N],*fa[N*N];
int n,S,T,e,Flow,Sum;
int color[N][N],num[N*N],d[N*N];

int pos(int x,int y){
if (x<1 || x>n || y<1 || y>n) return -100000;
return (x-1)*n+y;
}

void addedge(int x,int y,int c){
if (x<0 || y<0) return;
g[++e].x=x; g[e].y=y; g[e].c=c; g[e].next=ls[x]; ls[x]=&g[e]; g[e].op=&g[e+1];
g[++e].x=y; g[e].y=x; g[e].c=0; g[e].next=ls[y]; ls[y]=&g[e]; g[e].op=&g[e-1];
}

void init(){
scanf("%d",&n);
S=0; T=n*n+1;
e=0; memset(ls,0,sizeof(ls));
Sum=0;
for (int i=1;i<=n;i++)
for (int w,j=1;j<=n;j++){
if (j==1) color[i][j]=1-color[i-1][j];
else color[i][j]=1-color[i][j-1];
scanf("%d",&w);
Sum+=w;
if (color[i][j]){
addedge(S,pos(i,j),w);
addedge(pos(i,j),pos(i-1,j),INF);
addedge(pos(i,j),pos(i+1,j),INF);
addedge(pos(i,j),pos(i,j-1),INF);
addedge(pos(i,j),pos(i,j+1),INF);
}
else addedge(pos(i,j),T,w);
}
}

void relabel(int p){
cur[p]=ls[p];
int mm=T;
for (edge *t=ls[p];t;t=t->next)
if (t->c && d[t->y] d[p]=mm+1;
}

void change(){
int nf=INF;
for (int i=T;i!=S;i=fa[i]->x)
if (fa[i]->c Flow+=nf;
for (int i=T;i!=S;i=fa[i]->x){
fa[i]->c-=nf;
fa[i]->op->c+=nf;
}
}

void sap(){
int i;
Flow=0;
for (i=S;i<=T;i++){
d[i]=num[i]=0;
cur[i]=ls[i];
}
i=S;
while (d[S]<=T){
edge *&t=cur[i];
for (;t;t=t->next)
if (t->c && d[t->y]+1==d[t->x]) break;
if (t){
fa[t->y]=t;
i=t->y;
if (i==T){
change();
i=S;
}
}else{
if (!–num[d[i]]) break;
relabel(i);
++num[d[i]];
if (i!=S) i=fa[i]->x;
}
}
}

int main(){
init();
sap();
printf("%dn",Sum-Flow);
}