edward_mj

[衡阳八中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 using namespace std;
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    for (i=T;i!=S;i=g[fa[i]].x){
        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 #include const int N=50001;
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]数论、素论、取余的性质

【题目大意】

a_n = X*a_n-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 #include #include using namespace std;
__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;
}

[NOI 2008 day1 志愿者招募]最小费用最大流、利用不等式构造等式、利用流量守恒保证可行解**

【题目】

【算法分析】

详细的看这里吧：http://www.byvoid.com/blog/noi-2008-employee/

【其它】最后一个点在我机器上TLE。。。BYV大牛的程序也是。。。算了，都差不了多少秒。

【CODE】

#include #include const int N=1111;
const int M=11111;
const int E=100000;
const int inf=0x7FFFFFFF;
struct gtp{int x,y,next,op,c,w;}g[E];
int n,m,S,T,e,cost,flow,tot;
int need[N],st[M],ed[M],cc[M];
int ls[N],d[N],fa[N],list[N],v[N],zz[N];

void init(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&need[i]);
    for (int i=1;i<=m;i++)
      scanf("%d%d%d",&st[i],&ed[i],&cc[i]);
}

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].w=w; g[e].op=e+1;
    g[e].next=ls[x]; ls[x]=e;
    e++;
    g[e].x=y; g[e].y=x; g[e].c=0; g[e].w=-w; g[e].op=e-1;
    g[e].next=ls[y]; ls[y]=e;
}

void build(){
    S=n+2; T=n+3;
    for (int i=0;i<=n;i++)
      if (need[i]-need[i+1]>0) add(S,i+1,need[i]-need[i+1],0);
                          else add(i+1,T,need[i+1]-need[i],0);
    for (int i=2;i<=n+1;i++) add(i-1,i,inf,0);
    for (int i=1;i<=m;i++)
      add(ed[i]+1,st[i],inf,cc[i]);
}

bool spfa(){
    memset(d,50,sizeof(int)*(T+1));
    tot=0;
    d[S]=0;
    int head=0,tail=1; list[1]=S;
    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].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]!=d[0]) return true;
    return false;
}

void change(){
    int nf=inf;
    for (int i=T;i!=S;i=g[fa[i]].x)
      if (g[fa[i]].c    cost+=nf*d[T];
    flow+=nf;
    for (int i=T;i!=S;i=g[fa[i]].x){
        g[fa[i]].c-=nf;
        g[g[fa[i]].op].c+=nf;
    }
}

void maxflow_mincost(){
    flow=0; cost=0;
    while (spfa())
      change();
    printf("%dn",cost);
}

int main(){
    init();
    build();
    maxflow_mincost();
    return 0;
}