【题目】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1001
【题目大意】给出一个矩阵型的图，求左上角到右下角的最小割。边都是无向的。
【算法分析】把面看成图，然后可以通过跨越边的方式到达另外一端，跨过边就相当于去这条边为割集的一部分，最后求右上角这个面，到最下角这个面的最短路即可
【其它】NWA，注意N=1 OR M=1的情况请特判。
【CODE】
#include
分类存档：默认分类
[衡阳八中OJ 1093]强连通分量、DP、拓扑排序
【题目大意】
中文的，自己看吧。。。
http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1093
【算法分析】
先缩点，然后topsort。
很容易知道，必须是一条长链才可以成为一个半连通分量。
如果有分叉，那么分叉的两端不能互相到达（已缩环），除非他们仍然可以表述为一条长链。
【其它】2WA，1A，居然有个地方漏写了,Orz
9420 edward_mj 1093 Accepted 15136K 2777MS G++ 2.98K 2010-02-12 23:57:46
【CODE】
#include
[线性规划与网络流之20]最大费用最大流
【题目大意】和K取方格数差不多，不过源和汇的连边有点改变。
【算法】最大费用最大流
【其它】1A
【CODE】
#include
const int N=600;
const int inf=0x7FFFFFFF/2-10;
struct gtp{int x,y,next,op,c,w;}g[100000];
int s,n,m,sn,en,e,S,T,cost;
int ls[N],d[N],fa[N],list[N],v[N],wz[N][N];
inline void add(int x,int y,int c,int w){
e++;
g[e].x=x; g[e].y=y; g[e].c=c; g[e].op=e+1; g[e].w=w;
g[e].next=ls[x]; ls[x]=e;
e++;
g[e].x=y; g[e].y=x; g[e].c=0; g[e].op=e-1; g[e].w=-w;
g[e].next=ls[y]; ls[y]=e;
}
void init(){
memset(ls,0,sizeof(ls));
scanf("%d%d%d%d",&sn,&en,&n,&m);
int tot=0;
for (int j=0;j<=n;j++)
for (int i=0;i<=m;i++) wz[i][j]=++tot;
S=(n+1)*(m+1)+1;
T=S+1;
for (int i=0;i<=n;i++)
for (int j=1;j<=m;j++){
int x;
scanf("%d",&x);
add(wz[j-1][i],wz[j][i],1,x);
add(wz[j-1][i],wz[j][i],inf,0);
}
for (int j=0;j<=m;j++)
for (int i=1;i<=n;i++){
int x;
scanf("%d",&x);
add(wz[j][i-1],wz[j][i],1,x);
add(wz[j][i-1],wz[j][i],inf,0);
}
for (int i=1;i<=sn;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(S,wz[z][y],x,0);
}
for (int i=1;i<=en;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(wz[z][y],T,x,0);
}
}
bool spfa(){
for (int i=0;i<=T;i++) d[i]=-inf;
memset(v,0,sizeof(v));
int head=0,tail=1;
list[1]=S; v[S]=1; d[S]=0;
while (head!=tail){
head++; if (head>=N) head=0;
for (int t=ls[list[head]];t;t=g[t].next)
if (g[t].c && d[g[t].x]+g[t].w>d[g[t].y]){
d[g[t].y]=d[g[t].x]+g[t].w;
fa[g[t].y]=t;
if (!v[g[t].y]){
v[g[t].y]=1;
tail++; if (tail>=N) tail=0;
list[tail]=g[t].y;
}
}
v[list[head]]=0;
}
if (d[T]==-inf) return false;
return true;
}
void change(){
int nf=inf,i=T;
nf=0x7FFFFFFF;
for (;i!=S;i=g[fa[i]].x)
if (g[fa[i]].c
g[fa[i]].c-=nf;
g[g[fa[i]].op].c+=nf;
}
cost+=nf*d[T];
}
void maxflow(){
cost=0;
while (spfa())
change();
}
int main(){
freopen("robo0.in","r",stdin);
freopen("robo0.ans","w",stdout);
init();
maxflow();
printf("%dn",cost);
return 0;
}
[NANKAI 2080]质因数分解、dfs构造数
【题目大意】
给定x和a0的最大公约数是a1
x和b0的最小公倍数是b1
求存在多少个符合条件的x
【算法分析】
哎，NOIP第2题，当时只拿50分。。。
在景润后人的指导下，发现原来这么简单。。。原来我当时捉错方向了。
题目相当于给出两个条件：
根据第一个条件去构造的话，只能根据x=k*a0直接枚举。极限数据的话这必然TLE。
然后如果根据第二个条件去构造的话，就可以根据质因子来dfs，虽然也比较暴力，但是明显比上面那个好很多。。。
于是我们可以对b0质因数分解，枚举构造b0/gcd(b0,x)的这个部分，然后再用b1得到x，再判定就行了。
【其它】TLE多次，最终分解质因数那里改了一下，终于AC。
YM best user 景润后人 AekdyCoin
95562 AekdyCoin 2080 Accepted GNU C++ 1.46k 40ms 1312KB 2009-11-22 14:39:10 95729 xiaotian 2080 Accepted Free Pascal 3.39k 60ms 416KB 2009-11-24 13:31:02 96022 nehzilrz(2) 2080 Accepted GNU C++ 1.10k 60ms 768KB 2009-11-28 11:08:08 99216 edward 2080 Accepted GNU C++ 1.36k 60ms 1536KB 2010-02-12 18:22:38
【CODE】
#include
int ss[N],a0,a1,b0,b1,ssl[N],sst;
int sl[N],num[N],len,ans;
int gcd(int x,int y){
if (y==0) return x;
return gcd(y,x%y);
}
void makess(){
sst=0;
ss[1]=1;
for (int i=2;i*i<=N;i++) if (!ss[i])
for (int j=i;i*j<=N;j++)
ss[i*j]=1;
for (int i=1;i<=N;i++)
if (ss[i]==0){
sst++;
ssl[sst]=i;
}
}
void fenjie(int n){
len=0;
for (int i=1;n!=1 && n>=ssl[i] && i<=sst;i++)
if (n%ssl[i]==0){
len++;
sl[len]=ssl[i];
num[len]=0;
while (n%ssl[i]==0){
n/=ssl[i];
num[len]++;
}
}
if (n!=1){
len++;
sl[len]=n;
num[len]=1;
}
}
void dfs(int i,int now){
if (i>len){
int x=b1/now;
int t=gcd(x,b0),tmp=x/t*b0;
if (gcd(x,a0)!=a1 || x/gcd(x,b0)*b0!=b1) return;
ans++;
return;
}
dfs(i+1,now);
for (int k=1;k<=num[i];k++){
now*=sl[i];
dfs(i+1,now);
}
}
int main(){
makess();
int tc;
scanf("%d",&tc);
for (int i=1;i<=tc;i++){
scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
fenjie(b0);
ans=0;
dfs(1,1);
printf("%dn",ans);
}
}
[HDU 3307 Description has only two Sentences]数论、素论、取余的性质
【题目大意】
an = X*an-1 + Y 保证 y mod (x-1)=0
求最小的Ak mod a0=0
【算法分析】
先用等比数列求和公式得到通项。
最后推导出求x^k = 1 (mod a0)，然后再利用欧拉函数求解。
具体看这里吧http://hi.baidu.com/aekdycoin/blog/item/e5224da98d6c2fbaca130c67.html
后面的欧拉函数部分还不是很懂。。。
【CODE】
#include
__int64 x,y,a0;
__int64 phi(__int64 a){
__int64 r=a;
for (__int64 i=2;i<=a/i;i++)
if(a%i==0){
r-=r/i;
while(a%i==0)
a/=i;
}
return a<2?r:r-r/a;
}
__int64 gcd(__int64 a,__int64 b){
if (b==0) return a;
return gcd(b,a%b);
}
__int64 mod(__int64 a,__int64 b,__int64 c){
__int64 r=1%c;
while(b){
if(b&1)r=r*a%c;
a=a*a%c;
b=b/2;
}
return r;
}
void solve(){
__int64 c=y/(x-1),g=gcd(c,a0);
if (c%a0==0){
printf("1n");
return;
}
a0/=g;
if (gcd(a0,x)>1){
printf("Impossible!n");
return;
}
__int64 times=phi(a0),ans=0x7FFFFFFF;
for (__int64 i=1;i<=times/i;i++)
if (times % i==0){
if (mod(x,i,a0)==1) ans=min(ans,i);
if (mod(x,times/i,a0)==1) ans=min(ans,times/i);
}
if (ans==0x7FFFFFFF) printf("Impossible!n");
else printf("%I64dn",ans);
}
int main(){
while (scanf("%I64d%I64d%I64d",&x,&y,&a0)!=EOF){
solve();
}
return 0;
}