分类目录归档：acm

[POJ 3422]

费用流。

好久没写网络流的题目了，敲了很久，不过还是1A了。

这题和以前qoshi推荐的DP是同类题目，但这超过了DP能求解的规模，所以只能用费用流来做了。思路是把矩阵每个元素拆点为ui和vi，并根据费用流算法的需要进行建图。然后重复k次增广操作即可。增广用的是基于栈的spfa。g++下跑了938ms。

#include<cstdio>
#include<cstring>

#define inf 0x0fffffff

int n,m,hd[5000],el,b[5000],f[5000],p[5000],sm,ed;
int stk[5000],sl;

struct E
{
    int u,v,c,f,p;
}e[50000];

inline void adde(int u,int v,int c,int f)
{
    e[el].u=u; e[el].v=v; e[el].c=c; e[el].f=f;
    e[el].p=hd[u]; hd[u]=el++;
}

void sa(int ui,int uj,int f)
{
    int i,j,k,l;
    i=(ui*n+uj)*2;
    j=i+1;
    adde(i,j,1,f);
    adde(j,i,0,-f);
    adde(i,j,inf,0);
    adde(j,i,0,0);
    if(ui<n-1)
    {
        k=i+2*n;
        adde(j,k,inf,0);
        adde(k,j,0,0);
    }
    if(uj<n-1)
    {
        k=i+2;
        adde(j,k,inf,0);
        adde(k,j,0,0);
    }
}

void init()
{
    int i,j,k,l;
    el=sm=0;
    memset(hd,-1,sizeof hd);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            scanf("%d",&k);
            sa(i,j,k);
        }
    ed=((n-1)*n+n-1)*2+1;
}

void solve()
{
    int i,j,k,l;
    while(m--)
    {
        sl=0;
        memset(b,0,sizeof b);
        memset(f,-1,sizeof f);
        stk[sl++]=0;
        b[0]=1;
        f[0]=0;
        while(sl)
        {
            i=stk[--sl];
            b[i]=0;
            for(l=hd[i];l!=-1;l=e[l].p)
            {
                if(e[l].c==0) continue;
                j=e[l].v;
                if(f[i]+e[l].f>f[j])
                {
                    f[j]=f[i]+e[l].f;
                    p[j]=l;
                    if(!b[j])
                    {
                        b[j]=1;
                        stk[sl++]=j;
                    }
                }
            }
        }
        sm+=f[ed];
        for(i=ed;i;i=j)
        {
            l=p[i];
            j=e[l].u;
            e[l].c--;
            e[l^1].c++;
        }
    }
    printf("%d\n",sm);
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

#include<cstdio>

#include<cstring>

#define inf 0x0fffffff

int n,m,hd[5000],el,b[5000],f[5000],p[5000],sm,ed;

int stk[5000],sl;

struct E

{

int u,v,c,f,p;

}e[50000];

inline void adde(int u,int v,int c,int f)

{

e[el].u=u; e[el].v=v; e[el].c=c; e[el].f=f;

e[el].p=hd[u]; hd[u]=el++;

}

void sa(int ui,int uj,int f)

{

int i,j,k,l;

i=(ui*n+uj)*2;

j=i+1;

adde(i,j,1,f);

adde(j,i,0,-f);

adde(i,j,inf,0);

adde(j,i,0,0);

if(ui<n-1)

{

k=i+2*n;

adde(j,k,inf,0);

adde(k,j,0,0);

}

if(uj<n-1)

{

k=i+2;

adde(j,k,inf,0);

adde(k,j,0,0);

}

void init()

{

int i,j,k,l;

el=sm=0;

memset(hd,-1,sizeof hd);

for(i=0;i<n;i++)

for(j=0;j<n;j++)

{

scanf("%d",&k);

sa(i,j,k);

}

ed=((n-1)*n+n-1)*2+1;

}

void solve()

{

int i,j,k,l;

while(m--)

{

sl=0;

memset(b,0,sizeof b);

memset(f,-1,sizeof f);

stk[sl++]=0;

b[0]=1;

f[0]=0;

while(sl)

{

i=stk[--sl];

b[i]=0;

for(l=hd[i];l!=-1;l=e[l].p)

{

if(e[l].c==0) continue;

j=e[l].v;

if(f[i]+e[l].f>f[j])

{

f[j]=f[i]+e[l].f;

p[j]=l;

if(!b[j])

{

b[j]=1;

stk[sl++]=j;

}

sm+=f[ed];

for(i=ed;i;i=j)

{

l=p[i];

j=e[l].u;

e[l].c--;

e[l^1].c++;

}

printf("%d\n",sm);

}

int main()

{

while(~scanf("%d%d",&n,&m))

{

init();

solve();

}

return 0;

}

[POJ 3150]

发表回复

Cellular Automaton

矩阵运算。

题意抽象出来，即是求A^k*x(mod m)，其中A是n*n的循环矩阵，x是n维列向量。

很直接的思路是O(n^3*lgk)，但这里n最大500，TLE的。如果利用A是循环矩阵的性质，那么其实每次只要计算第一行就可以了，其他行都可以由第一行移位得到。这样就可以O(n^2*lgk)，实现出来最快500ms。

#include<cstdio>
#include<cstring>

#define ll long long
#define size n<<3

ll n,m,d,e,a[500],b[500],t[500],x[500],y[500];

void init()
{
    ll i,j,k,l;
    for(i=0;i<n;i++)
        scanf("%lld",x+i);
    memset(a,0,size);
    memset(b,0,size);
    memset(y,0,size);
    b[0]=1;
    for(i=j=0,k=0;k<=d;k++)
    {
        a[i]=1;
        ++i;
        if(i==n) i=0;
        a[j]=1;
        --j;
        if(j==-1) j=n-1;
    }
}

void mul(ll b[],ll a[])
{
    ll i,j,k,l;
    memset(t,0,size);
    for(i=0;i<=n/2;i++)
    {
        for(j=0,k=i;j<n;j++)
        {
            t[i]+=b[j]*a[k];
            ++k;
            if(k==n) k=0;
        }
        t[i]%=m;
    }
    for(i=1;i<=n/2;i++)
        t[n-i]=t[i];
    memcpy(b,t,size);
}

void solve()
{
    ll i,j,k,l;
    for(i=1;i<=e;i<<=1);
    for(i>>=1;i;i>>=1)
    {
        mul(b,b);
        if(i&e)
            mul(b,a);
    }
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            y[i]=(y[i]+b[j]*x[(i+j)%n])%m;
    for(i=0;i<n-1;i++)
        printf("%lld ",y[i]);
    printf("%lld\n",y[n-1]);
}

int main()
{
    while(~scanf("%lld%lld%lld%lld",&n,&m,&d,&e))
    {
        init();
        solve();
    }
    return 0;
}

#include<cstdio>

#include<cstring>

#define ll long long

#define size n<<3

ll n,m,d,e,a[500],b[500],t[500],x[500],y[500];

void init()

{

ll i,j,k,l;

for(i=0;i<n;i++)

scanf("%lld",x+i);

memset(a,0,size);

memset(b,0,size);

memset(y,0,size);

b[0]=1;

for(i=j=0,k=0;k<=d;k++)

{

a[i]=1;

++i;

if(i==n) i=0;

a[j]=1;

--j;

if(j==-1) j=n-1;

}

void mul(ll b[],ll a[])

{

ll i,j,k,l;

memset(t,0,size);

for(i=0;i<=n/2;i++)

{

for(j=0,k=i;j<n;j++)

{

t[i]+=b[j]*a[k];

++k;

if(k==n) k=0;

}

t[i]%=m;

}

for(i=1;i<=n/2;i++)

t[n-i]=t[i];

memcpy(b,t,size);

}

void solve()

{

ll i,j,k,l;

for(i=1;i<=e;i<<=1);

for(i>>=1;i;i>>=1)

{

mul(b,b);

if(i&e)

mul(b,a);

}

for(i=0;i<n;i++)

for(j=0;j<n;j++)

y[i]=(y[i]+b[j]*x[(i+j)%n])%m;

for(i=0;i<n-1;i++)

printf("%lld ",y[i]);

printf("%lld\n",y[n-1]);

}

int main()

{

while(~scanf("%lld%lld%lld%lld",&n,&m,&d,&e))

{

init();

solve();

}

return 0;

}

看评论还有一种O(n*lgn*lgk)的算法……但是想了一早上也没明白怎么弄，饿得不行吃饭先了……

[POJ 3159]

发表回复

Candies

差分约束系统。

偶尔发现的很好的题目，对最短路径算法的优化要求较高。

敲了一个SPFA+SLF。其中双端循环队列是手写的，int读入用了getchar处理以节省时间，作了去重边处理。但即使这样也才250ms(g++)。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,m,hd[30000],el,eel,b[30000],d[30000];

class DQ
{
#define MAXL 50000
public:
    int a[MAXL],h,t;
    inline void init()
    {
        t=0;
        h=1;
    }
    inline void push_front(int b)
    {
        a[h++]=b;
        if(h==MAXL) h=0;
    }
    inline void push_back(int b)
    {
        a[t--]=b;
        if(t==-1) t=MAXL-1;
    }
    inline int front()
    {
        if(h==0) return a[MAXL-1];
        return a[h-1];
    }
    inline void pop_front()
    {
        if(h==0) h=MAXL-1;
        else h--;
    }
    inline int empty()
    {
        if(t==MAXL-1&&h==0) return 1;
        return t==h-1;
    }
}dq;

struct EE
{
    int u,v,d;
    bool operator < (const EE &p) const
    {
        if(u<p.u) return 0;
        if(u>p.u) return 1;
        if(v<p.v) return 0;
        if(v>p.v) return 1;
        return d<p.d;
    }
}ee[150000];

struct E
{
    int v,d,p;
}e[150000];

inline void adde(int u,int v,int d)
{
    e[el].v=v; e[el].d=d; e[el].p=hd[u]; hd[u]=el++;
}

inline int getint()
{
    int d;
    char c;
    while((c=getchar())<'0'||c>'9');
    d=c-'0';
    while((c=getchar())>='0'&&c<='9')
        d=d*10+c-'0';
    return d;
}

void init()
{
    int i,j,k;
    el=eel=0;
    memset(hd,-1,sizeof hd);
    memset(b,0,sizeof b);
    memset(d,-1,sizeof d);
    dq.init();
    while(m--)
    {
        i=getint(); j=getint(); k=getint();
        if(i==j) continue;
        ee[eel].u=i-1;
        ee[eel].v=j-1;
        ee[eel].d=k;
        eel++;
    }
    sort(ee,ee+eel);
    adde(ee[0].u,ee[0].v,ee[0].d);
    for(i=1;i<eel;i++)
    {
        if(ee[i].u==ee[i-1].u&&ee[i].v==ee[i-1].v)
            continue;
        adde(ee[i].u,ee[i].v,ee[i].d);
    }
}

void solve()
{
    int i,j,k,l;
    d[0]=0;
    b[0]=1;
    dq.push_front(0);
    while(!dq.empty())
    {
        i=dq.front(); dq.pop_front();
        b[i]=0;
        for(l=hd[i];l!=-1;l=e[l].p)
        {
            j=e[l].v;
            k=e[l].d;
            if(d[j]==-1||d[i]+k<d[j])
            {
                d[j]=d[i]+k;
                if(!b[j])
                {
                    b[j]=1;
                    if(dq.empty()||d[j]<=d[dq.front()])
                        dq.push_front(j);
                    else
                        dq.push_back(j);
                }
            }
        }
    }
    printf("%d\n",d[n-1]);
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,m,hd[30000],el,eel,b[30000],d[30000];

class DQ

{

#define MAXL 50000

public:

int a[MAXL],h,t;

inline void init()

{

t=0;

h=1;

}

inline void push_front(int b)

{

a[h++]=b;

if(h==MAXL) h=0;

}

inline void push_back(int b)

{

a[t--]=b;

if(t==-1) t=MAXL-1;

}

inline int front()

{

if(h==0) return a[MAXL-1];

return a[h-1];

}

inline void pop_front()

{

if(h==0) h=MAXL-1;

else h--;

}

inline int empty()

{

if(t==MAXL-1&&h==0) return 1;

return t==h-1;

}

}dq;

struct EE

{

int u,v,d;

bool operator < (const EE &p) const

{

if(u<p.u) return 0;

if(u>p.u) return 1;

if(v<p.v) return 0;

if(v>p.v) return 1;

return d<p.d;

}

}ee[150000];

struct E

{

int v,d,p;

}e[150000];

inline void adde(int u,int v,int d)

{

e[el].v=v; e[el].d=d; e[el].p=hd[u]; hd[u]=el++;

}

inline int getint()

{

int d;

char c;

while((c=getchar())<'0'||c>'9');

d=c-'0';

while((c=getchar())>='0'&&c<='9')

d=d*10+c-'0';

return d;

}

void init()

{

int i,j,k;

el=eel=0;

memset(hd,-1,sizeof hd);

memset(b,0,sizeof b);

memset(d,-1,sizeof d);

dq.init();

while(m--)

{

i=getint(); j=getint(); k=getint();

if(i==j) continue;

ee[eel].u=i-1;

ee[eel].v=j-1;

ee[eel].d=k;

eel++;

}

sort(ee,ee+eel);

adde(ee[0].u,ee[0].v,ee[0].d);

for(i=1;i<eel;i++)

{

if(ee[i].u==ee[i-1].u&&ee[i].v==ee[i-1].v)

continue;

adde(ee[i].u,ee[i].v,ee[i].d);

}

void solve()

{

int i,j,k,l;

d[0]=0;

b[0]=1;

dq.push_front(0);

while(!dq.empty())

{

i=dq.front(); dq.pop_front();

b[i]=0;

for(l=hd[i];l!=-1;l=e[l].p)

{

j=e[l].v;

k=e[l].d;

if(d[j]==-1||d[i]+k<d[j])

{

d[j]=d[i]+k;

if(!b[j])

{

b[j]=1;

if(dq.empty()||d[j]<=d[dq.front()])

dq.push_front(j);

else

dq.push_back(j);

}

printf("%d\n",d[n-1]);

}

int main()

{

while(~scanf("%d%d",&n,&m))

{

init();

solve();

}

return 0;

}

之后又考虑了用dijkstra。没有优化过直接交果然TLE了。然后开始考虑改进。直接用最小堆来实现最优的dijkstra不太好写，而折中地每次将可能更新最短路径值的点全部push进优先队列的做法是相对比较好实现的，也不会耗损太多时间。第一次写这样的dijkstra，调试了挺久。最后在g++下235ms，c++下1297ms。

#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

#define maxml 30000000

int n,m,hd[30000],el,eel,b[30000],d[30000],ml;

struct EE
{
    int u,v,d;
    bool operator < (const EE &p) const
    {
        if(u<p.u) return 0;
        if(u>p.u) return 1;
        if(v<p.v) return 0;
        if(v>p.v) return 1;
        return d<p.d;
    }
}ee[150000];

struct E
{
    int v,d,p;
}e[150000];

struct F
{
    int d,i;
}mem[maxml];

struct CP
{
    bool operator ()(const F *p,const F *q) const
    {
        return p->d>q->d;
    }
};

inline void adde(int u,int v,int d)
{
    e[el].v=v; e[el].d=d; e[el].p=hd[u]; hd[u]=el++;
}

inline int getint()
{
    int d;
    char c;
    while((c=getchar())<'0'||c>'9');
    d=c-'0';
    while((c=getchar())>='0'&&c<='9')
        d=d*10+c-'0';
    return d;
}

void init()
{
    int i,j,k;
    el=eel=ml=0;
    memset(hd,-1,sizeof hd);
    memset(b,0,sizeof b);
    memset(d,-1,sizeof d);
    while(m--)
    {
        i=getint(); j=getint(); k=getint();
        if(i==j) continue;
        ee[eel].u=i-1;
        ee[eel].v=j-1;
        ee[eel].d=k;
        eel++;
    }
    sort(ee,ee+eel);
    adde(ee[0].u,ee[0].v,ee[0].d);
    for(i=1;i<eel;i++)
    {
        if(ee[i].u==ee[i-1].u&&ee[i].v==ee[i-1].v)
            continue;
        adde(ee[i].u,ee[i].v,ee[i].d);
    }
}

void solve()
{
    int i,j,k,l;
    d[0]=0;
    b[0]=1;
    priority_queue<F*,vector<F*>,CP>pq;
    F* p;
    for(l=hd[0];l!=-1;l=e[l].p)
    {
        p=&mem[ml++];
        d[e[l].v]=p->d=e[l].d;
        p->i=e[l].v;
        pq.push(p);
    }
    while(!b[n-1])
    {
        while(b[i=pq.top()->i])
            pq.pop();
        b[i]=1;
        pq.pop();
        for(l=hd[i];l!=-1;l=e[l].p)
        {
            j=e[l].v;
            k=e[l].d;
            if(b[j]||d[j]!=-1&&d[i]+k>=d[j]) continue;
            p=&mem[ml++];
            d[j]=p->d=d[i]+k;
            p->i=j;
            pq.push(p);
        }
    }
    printf("%d\n",d[n-1]);
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

#include<cstdio>

#include<cstring>

#include<queue>

#include<vector>

#include<algorithm>

using namespace std;

#define maxml 30000000

int n,m,hd[30000],el,eel,b[30000],d[30000],ml;

struct EE

{

int u,v,d;

bool operator < (const EE &p) const

{

if(u<p.u) return 0;

if(u>p.u) return 1;

if(v<p.v) return 0;

if(v>p.v) return 1;

return d<p.d;

}

}ee[150000];

struct E

{

int v,d,p;

}e[150000];

struct F

{

int d,i;

}mem[maxml];

struct CP

{

bool operator ()(const F *p,const F *q) const

{

return p->d>q->d;

}

};

inline void adde(int u,int v,int d)

{

e[el].v=v; e[el].d=d; e[el].p=hd[u]; hd[u]=el++;

}

inline int getint()

{

int d;

char c;

while((c=getchar())<'0'||c>'9');

d=c-'0';

while((c=getchar())>='0'&&c<='9')

d=d*10+c-'0';

return d;

}

void init()

{

int i,j,k;

el=eel=ml=0;

memset(hd,-1,sizeof hd);

memset(b,0,sizeof b);

memset(d,-1,sizeof d);

while(m--)

{

i=getint(); j=getint(); k=getint();

if(i==j) continue;

ee[eel].u=i-1;

ee[eel].v=j-1;

ee[eel].d=k;

eel++;

}

sort(ee,ee+eel);

adde(ee[0].u,ee[0].v,ee[0].d);

for(i=1;i<eel;i++)

{

if(ee[i].u==ee[i-1].u&&ee[i].v==ee[i-1].v)

continue;

adde(ee[i].u,ee[i].v,ee[i].d);

}

void solve()

{

int i,j,k,l;

d[0]=0;

b[0]=1;

priority_queue<F*,vector<F*>,CP>pq;

F* p;

for(l=hd[0];l!=-1;l=e[l].p)

{

p=&mem[ml++];

d[e[l].v]=p->d=e[l].d;

p->i=e[l].v;

pq.push(p);

}

while(!b[n-1])

{

while(b[i=pq.top()->i])

pq.pop();

b[i]=1;

pq.pop();

for(l=hd[i];l!=-1;l=e[l].p)

{

j=e[l].v;

k=e[l].d;

if(b[j]||d[j]!=-1&&d[i]+k>=d[j]) continue;

p=&mem[ml++];

d[j]=p->d=d[i]+k;

p->i=j;

pq.push(p);

}

printf("%d\n",d[n-1]);

}

int main()

{

while(~scanf("%d%d",&n,&m))

{

init();

solve();

}

return 0;

}

吐个小槽……priority_queue里面自定义仿函数时，若比较用的是<，建出来的竟然是大根堆……直觉上怎样也觉得<对应的应该是最小元素在上的小根堆才对……>__< 后记：第二天过来后被Usozki教育了下，他的代码仅仅是SPFA+栈，没有太多优化……但是直接跑出79ms进入第一版了…… 附POJ 3159 by Usozki：

#include<cstdio>
#include<cstring>

int i,j,k,s,t,d,p,dist[30005],hd[30005],el,n,m,instk[30005], inf=0x7fffffff,stk[30005],top;
struct E
{
    int v,p,d;
} e[150005];
inline void adde(int u,int v,int d)
{
    e[el].v=v,e[el].p=hd[u],e[el].d=d,hd[u]=el++;
}

inline int getint()
{
    int d;
    char c;
    while((c=getchar())<'0'||c>'9');
    d=c-'0';
    while((c=getchar())>='0'&&c<='9')
        d=d*10+c-'0';
    return d;
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        el=0,top=0;
        memset(dist,127,sizeof dist);
        memset(instk,0,sizeof instk);
        memset(hd,-1,sizeof hd);
        for(i=0; i<m; i++)
        {
            s=getint(),t=getint(),d=getint();
            adde(s,t,d);
        }
        dist[1]=0;
        stk[++top]=1;
        while(top)
        {
            p=stk[top--],instk[p]=0;
            for(j=hd[p]; j!=-1; j=e[j].p)
            {
                k=e[j].v;
                if(dist[p]+e[j].d<dist[k])
                {
                    dist[k]=dist[p]+e[j].d;
                    if(instk[k]==0)stk[++top]=k,instk[k]=1;
                }
            }
        }
        printf("%d\n",dist[n]-dist[1]);
    }
    return 0;
}

#include<cstdio>

#include<cstring>

int i,j,k,s,t,d,p,dist[30005],hd[30005],el,n,m,instk[30005], inf=0x7fffffff,stk[30005],top;

struct E

{

int v,p,d;

} e[150005];

inline void adde(int u,int v,int d)

{

e[el].v=v,e[el].p=hd[u],e[el].d=d,hd[u]=el++;

}

inline int getint()

{

int d;

char c;

while((c=getchar())<'0'||c>'9');

d=c-'0';

while((c=getchar())>='0'&&c<='9')

d=d*10+c-'0';

return d;

}

int main()

{

while(~scanf("%d%d",&n,&m))

{

el=0,top=0;

memset(dist,127,sizeof dist);

memset(instk,0,sizeof instk);

memset(hd,-1,sizeof hd);

for(i=0; i<m; i++)

{

s=getint(),t=getint(),d=getint();

adde(s,t,d);

}

dist[1]=0;

stk[++top]=1;

while(top)

{

p=stk[top--],instk[p]=0;

for(j=hd[p]; j!=-1; j=e[j].p)

{

k=e[j].v;

if(dist[p]+e[j].d<dist[k])

{

dist[k]=dist[p]+e[j].d;

if(instk[k]==0)stk[++top]=k,instk[k]=1;

}

printf("%d\n",dist[n]-dist[1]);

}

return 0;

}

[POJ 3101]

发表回复

Astronomy

分类里写的是扩展欧几里德，但完全用不到。倒是被高精度稍微卡了下。

题意是共有n个星体各以vi的速度绕同一中心公转，问所有星体排成一条直线的周期。

这里注意“排成一条直线”，可以是在圆周的一侧或是另一侧。这里可以取速度最快的星作为运动参照物，求其他星体相对该星的速度，并计算各星体(v0-vi)*x可同时被0.5除尽的最小倍数值x。x即为所求周期值。0.5是因为可在圆周的任意一侧。

用题意vi = 1/ti来表示的话，则1/t0 – 1/ti = (ti-t0) / (t0*ti)，那么取所有分母的lcm为nu，所有分子的gcd为de，则nu/(2*de)则是所求的x了。

思路出来之后，还有部分细节，首先就是去重，然后是计算素数表大小和估计高精度数组最大长度，最后每次求出某分数值时要约分到最简。这里所谓的“高精度”比较有意思的是，用质因数分解的方式保存各个值，这样可非常简便地求gcd和lcm。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

#define MAXP 1300
#define MAXT 5000
#define SIZEP 4*MAXP
#define SIZET 4*MAXT

int n,d[1000],p[MAXP]={2,3};
int nu[MAXP],de[MAXP],tnu[MAXP],tde[MAXP];
int t[MAXT];

void gcd(int a[],int b[])
{
    int i;
    for(i=0;i<MAXP;i++)
        t[i]=min(a[i],b[i]);
}

void lcm(int a[],int b[])
{
    int i;
    for(i=0;i<MAXP;i++)
        t[i]=max(a[i],b[i]);
}

void div(int a[],int b[])
{
    int i;
    for(i=0;i<MAXP;i++)
        a[i]-=b[i];
}

void pnt(int a[])
{
    int i,j,k,l;
    memset(t,0,SIZET);
    for(i=0,t[0]=1;i<MAXP;i++)
    {
        if(!a[i]) continue;
        j=1;
        while(a[i]--)
            j*=p[i];
        for(l=0;l<MAXT;l++)
            t[l]*=j;
        for(l=0;l<MAXT-1;l++)
        {
            t[l+1]+=t[l]/10;
            t[l]%=10;
        }
    }
    for(l=MAXT-1;!t[l];l--);
    for(;l>-1;l--)
        printf("%d",t[l]);
}

void calc(int a,int b[])
{
    int i;
    memset(b,0,SIZEP);
    for(i=0;a>1;i++)
    {
        while(a%p[i]==0)
        {
            b[i]++;
            a/=p[i];
        }
    }
}

int main()
{
    int i,j,k,l;
    for(i=2;i<MAXP;i++)
    {
        for(j=p[i-1]+2;1;j+=2)
        {
            for(k=0,l=sqrt(j);p[k]<=l&&j%p[k];k++);
            if(p[k]>l)
            {
                p[i]=j;
                break;
            }
        }
    }
    while(~scanf("%d",&n))
    {
        for(i=0;i<n;i++) scanf("%d",d+i);
        sort(d,d+n);
        for(i=j=1;i<n;i++)
        {
            if(d[i]!=d[i-1])
                d[j++]=d[i];
        }
        n=j;
        calc(d[1]-d[0],nu);
        calc(d[0]*d[1],de);
        gcd(nu,de);
        div(nu,t);
        div(de,t);
        for(i=2;i<n;i++)
        {
            calc(d[i]-d[0],tnu);
            calc(d[0]*d[i],tde);
            gcd(tnu,tde);
            div(tnu,t);
            div(tde,t);
            gcd(nu,tnu);
            memcpy(nu,t,SIZE);
            lcm(de,tde);
            memcpy(de,t,SIZE);
        }
        gcd(nu,de);
        div(nu,t);
        div(de,t);
        if(!de[0])
            nu[0]++;
        else
            de[0]--;
        pnt(de);
        printf(" ");
        pnt(nu);
        puts("");
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define MAXP 1300

#define MAXT 5000

#define SIZEP 4*MAXP

#define SIZET 4*MAXT

int n,d[1000],p[MAXP]={2,3};

int nu[MAXP],de[MAXP],tnu[MAXP],tde[MAXP];

int t[MAXT];

void gcd(int a[],int b[])

{

int i;

for(i=0;i<MAXP;i++)

t[i]=min(a[i],b[i]);

}

void lcm(int a[],int b[])

{

int i;

for(i=0;i<MAXP;i++)

t[i]=max(a[i],b[i]);

}

void div(int a[],int b[])

{

int i;

for(i=0;i<MAXP;i++)

a[i]-=b[i];

}

void pnt(int a[])

{

int i,j,k,l;

memset(t,0,SIZET);

for(i=0,t[0]=1;i<MAXP;i++)

{

if(!a[i]) continue;

j=1;

while(a[i]--)

j*=p[i];

for(l=0;l<MAXT;l++)

t[l]*=j;

for(l=0;l<MAXT-1;l++)

{

t[l+1]+=t[l]/10;

t[l]%=10;

}

for(l=MAXT-1;!t[l];l--);

for(;l>-1;l--)

printf("%d",t[l]);

}

void calc(int a,int b[])

{

int i;

memset(b,0,SIZEP);

for(i=0;a>1;i++)

{

while(a%p[i]==0)

{

b[i]++;

a/=p[i];

}

int main()

{

int i,j,k,l;

for(i=2;i<MAXP;i++)

{

for(j=p[i-1]+2;1;j+=2)

{

for(k=0,l=sqrt(j);p[k]<=l&&j%p[k];k++);

if(p[k]>l)

{

p[i]=j;

break;

}

while(~scanf("%d",&n))

{

for(i=0;i<n;i++) scanf("%d",d+i);

sort(d,d+n);

for(i=j=1;i<n;i++)

{

if(d[i]!=d[i-1])

d[j++]=d[i];

}

n=j;

calc(d[1]-d[0],nu);

calc(d[0]*d[1],de);

gcd(nu,de);

div(nu,t);

div(de,t);

for(i=2;i<n;i++)

{

calc(d[i]-d[0],tnu);

calc(d[0]*d[i],tde);

gcd(tnu,tde);

div(tnu,t);

div(tde,t);

gcd(nu,tnu);

memcpy(nu,t,SIZE);

lcm(de,tde);

memcpy(de,t,SIZE);

}

gcd(nu,de);

div(nu,t);

div(de,t);

if(!de[0])

nu[0]++;

else

de[0]--;

pnt(de);

printf(" ");

pnt(nu);

puts("");

}

return 0;

}

Google Round A China New Grad Test 2014

1条回复

早上做了一场Google的在线笔试。

赛制都很熟悉了，和之前的GCJ一样的。比赛时长3小时，共5题，每题都分small和large两组数据。

Problem A. Read Phone Number

读入两个字符串，根据第二个串给出的分段方式，对第一个串进行分析并输出结果。

写第二个串的读入那部分时卡了很久很久。真是对字符串处理太不熟练了，之前北大校赛的时候也是卡很久在字符串处理上。最后还是借鉴了之前用getchar()代替scanf(“%d”,&d)来读入整数以节省时间的方式来读入了每个串分段长度值。提交大数据时一直报含有非ascii字符，结果发现自己数组越界了，如果不是提示这里也就WA掉了。这题做完时已经整整41分钟了。

Problem C. Sorting

随后很自然的看了下board，看到C题过的人很多。点开发现是大水题，两次排序后重构数组输出即可。

Problem B. Rational Number Tree

C题过了后，心态稳下来了。开始读B，发现也是只需要在树上寻根即可，非常简单的处理。大数据提交前看了眼输出，发现竟然有负数。分析到long long最多是2^63-1，遂改成unsigned long long提交。

Problem D. Cross the maze

到这时候已经完全进入状态了。机器人走迷宫的题目，读完后发现也不需要太复杂的处理。分析完之后可以发现，机器人每一步的走法是确定的，而所需要做的就是模拟它走完10000步，看是否经过终点。这里处理写得很凌乱，因为当时以为只有两个小时敲得比较仓促。但提交完发现竟然还有1小时。。。

Problem E. Spaceship Defence

最后一题了，这是唯一稍微考虑了下复杂度的问题。这里大数据是100个源点，图有80000个点，若是稠图最坏情况O(M*N^2)是会TLE的。过了小数据后想了很久怎么对问题进行抽象，但始终没有太好思路。这个时候时间也不多了，想想大数据有8min时限，下下来碰碰运气好了。结果SPFA没有任何优化，1分钟不到就跑出结果了，遂提交之。

12点封榜的时候，好像是排50名左右吧。。。Arios比我快2分钟，能离伟神这么近我也很满足了。睡过午觉过来一看，发现自己AK了。。。。。。最后排名29。其实题目不难的，但貌似很多ACM神牛都没有来玩，不知为何了。。。

最后的board。

事后马上收到了Google的邮件，恭喜通过笔试云云。

不禁也在问自己，这个时候如果要选择，是继续读完研究生，还是去Google工作？

心里面作出回答只用了10秒。而且非常清楚，自己这一决定，怎样也不后悔。

祝自己好运吧。

[POJ 2065] & [POJ 1166]

发表回复

SETI

The Clocks

两题都是高斯消元法。（也都1A了^^）

两题题面都很有意思，分别描述了确定有唯一解的模运算线性方程组，唯一解是因为前者是范德蒙行列式，后者则是给定了满秩系数矩阵。

两题都没有太大难度的，代码也相近。

2065的：

#include<cstdio>
#include<cstring>

int n,p,ab[100][100],t[100];
char s[100];

int gcd(int a,int b)
{
    if(a%b==0) return b;
    return gcd(b,a%b);
}

void init()
{
    int i,j,k,l;
    n=strlen(s);;
    memset(ab,0,sizeof ab);
    for(i=0,k=1;i<n;i++,k++)
    {
        ab[i][0]=1;
        for(j=1;j<n;j++)
            ab[i][j]=ab[i][j-1]*k%p;
        if(s[i]=='*')
            ab[i][n]=0;
        else ab[i][n]=s[i]-'a'+1;
    }
}

int calc(int a,int b)
{
    int i;
    if(a<0) a+=p;
    if(b<0) b+=p;
    for(i=0;i<p;i++)
        if(a*i%p==b) return i;
}

void solve()
{
    int i,j,k,l,m,g;
    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n&&!ab[j][i];j++);
        if(j!=i+1)
        {
            memcpy(t,ab[i],sizeof t);
            memcpy(ab[i],ab[j],sizeof t);
            memcpy(ab[j],t,sizeof t);
        }
        for(j=i+1;j<n;j++)
        {
            if(!ab[j][i]) continue;
            g=gcd(ab[i][i],ab[j][i]);
            l=ab[i][i]/g;
            m=ab[j][i]/g;
            for(k=0;k<=n;k++)
                ab[j][k]=(ab[j][k]*l-ab[i][k]*m)%p;
        }
    }
    for(i=n-1;i;i--)
    {
        for(j=i-1;j>-1;j--)
        {
            if(!ab[j][i]) continue;
            g=gcd(ab[i][i],ab[j][i]);
            l=ab[i][i]/g;
            m=ab[j][i]/g;
            for(k=0;k<=n;k++)
                ab[j][k]=(ab[j][k]*l-ab[i][k]*m)%p;
        }
    }
    for(i=0;i<n-1;i++)
        printf("%d ",calc(ab[i][i],ab[i][n]));
    printf("%d\n",calc(ab[i][i],ab[i][n]));
}

int main()
{
    scanf("%*d");
    while(~scanf("%d%s",&p,s))
    {
        init();
        solve();
    }
    return 0;
}

#include<cstdio>

#include<cstring>

int n,p,ab[100][100],t[100];

char s[100];

int gcd(int a,int b)

{

if(a%b==0) return b;

return gcd(b,a%b);

}

void init()

{

int i,j,k,l;

n=strlen(s);;

memset(ab,0,sizeof ab);

for(i=0,k=1;i<n;i++,k++)

{

ab[i][0]=1;

for(j=1;j<n;j++)

ab[i][j]=ab[i][j-1]*k%p;

if(s[i]=='*')

ab[i][n]=0;

else ab[i][n]=s[i]-'a'+1;

}

int calc(int a,int b)

{

int i;

if(a<0) a+=p;

if(b<0) b+=p;

for(i=0;i<p;i++)

if(a*i%p==b) return i;

}

void solve()

{

int i,j,k,l,m,g;

for(i=0;i<n;i++)

{

for(j=i+1;j<n&&!ab[j][i];j++);

if(j!=i+1)

{

memcpy(t,ab[i],sizeof t);

memcpy(ab[i],ab[j],sizeof t);

memcpy(ab[j],t,sizeof t);

}

for(j=i+1;j<n;j++)

{

if(!ab[j][i]) continue;

g=gcd(ab[i][i],ab[j][i]);

l=ab[i][i]/g;

m=ab[j][i]/g;

for(k=0;k<=n;k++)

ab[j][k]=(ab[j][k]*l-ab[i][k]*m)%p;

}

for(i=n-1;i;i--)

{

for(j=i-1;j>-1;j--)

{

if(!ab[j][i]) continue;

g=gcd(ab[i][i],ab[j][i]);

l=ab[i][i]/g;

m=ab[j][i]/g;

for(k=0;k<=n;k++)

ab[j][k]=(ab[j][k]*l-ab[i][k]*m)%p;

}

for(i=0;i<n-1;i++)

printf("%d ",calc(ab[i][i],ab[i][n]));

printf("%d\n",calc(ab[i][i],ab[i][n]));

}

int main()

{

scanf("%*d");

while(~scanf("%d%s",&p,s))

{

init();

solve();

}

return 0;

}

1166的：

#include<cstdio>
#include<cstring>

int ab[9][10],t[10],tl,tn[10];
int d[]={1,1,0,1,0,0,0,0,0,0,
         1,1,1,0,1,0,0,0,0,0,
         0,1,1,0,0,1,0,0,0,0,
         1,0,0,1,1,0,1,0,0,0,
         1,0,1,0,1,0,1,0,1,0,
         0,0,1,0,1,1,0,0,1,0,
         0,0,0,1,0,0,1,1,0,0,
         0,0,0,0,1,0,1,1,1,0,
         0,0,0,0,0,1,0,1,1,0};

int gcd(int a,int b)
{
    if(a%b==0) return b;
    return gcd(b,a%b);
}

int init()
{
    int i,j,k,l;
    if(-1==scanf("%d",&k)) return 0;
    memcpy(ab,d,sizeof d);
    ab[0][9]=-k;
    for(i=1;i<9;i++)
    {
        scanf("%d",&k);
        ab[i][9]=-k;
    }
    return 1;
}

int calc(int a,int b)
{
    int i;
    if(a<0) a+=4;
    if(b<0) b+=4;
    for(i=0;i<4;i++)
        if(i*a%4==b) return i;
}

void solve()
{
    int i,j,k,l,m,g;
    for(i=0;i<9;i++)
    {
        for(j=i;j<9&&!ab[j][i];j++);
        if(j!=i)
        {
            memcpy(t,ab[i],sizeof t);
            memcpy(ab[i],ab[j],sizeof t);
            memcpy(ab[j],t,sizeof t);
        }
        for(j=i+1;j<9;j++)
        {
            if(!ab[j][i]) continue;
            g=gcd(ab[i][i],ab[j][i]);
            l=ab[i][i]/g;
            m=ab[j][i]/g;
            for(k=0;k<10;k++)
                ab[j][k]=(ab[j][k]*l-ab[i][k]*m)%4;
        }
    }
    for(i=8;i;i--)
    {
        for(j=i-1;j>-1;j--)
        {
            if(!ab[j][i]) continue;
            g=gcd(ab[i][i],ab[j][i]);
            l=ab[i][i]/g;
            m=ab[j][i]/g;
            for(k=0;k<10;k++)
                ab[j][k]=(ab[j][k]*l-ab[i][k]*m)%4;
        }
    }
    for(i=tl=0;i<9;i++)
    {
        j=calc(ab[i][i],ab[i][9]);
        if(j)
        {
            t[tl]=i+1;
            tn[tl]=j;
            tl++;
        }
    }
    for(i=0;i<tl-1;i++)
        while(tn[i]--) printf("%d ",t[i]);
    while(--tn[i]) printf("%d ",t[i]);
    printf("%d\n",t[i]);
}

int main()
{
    while(init())
        solve();
    return 0;
}

#include<cstdio>

#include<cstring>

int ab[9][10],t[10],tl,tn[10];

int d[]={1,1,0,1,0,0,0,0,0,0,

1,1,1,0,1,0,0,0,0,0,

0,1,1,0,0,1,0,0,0,0,

1,0,0,1,1,0,1,0,0,0,

1,0,1,0,1,0,1,0,1,0,

0,0,1,0,1,1,0,0,1,0,

0,0,0,1,0,0,1,1,0,0,

0,0,0,0,1,0,1,1,1,0,

0,0,0,0,0,1,0,1,1,0};

int gcd(int a,int b)

{

if(a%b==0) return b;

return gcd(b,a%b);

}

int init()

{

int i,j,k,l;

if(-1==scanf("%d",&k)) return 0;

memcpy(ab,d,sizeof d);

ab[0][9]=-k;

for(i=1;i<9;i++)

{

scanf("%d",&k);

ab[i][9]=-k;

}

return 1;

}

int calc(int a,int b)

{

int i;

if(a<0) a+=4;

if(b<0) b+=4;

for(i=0;i<4;i++)

if(i*a%4==b) return i;

}

void solve()

{

int i,j,k,l,m,g;

for(i=0;i<9;i++)

{

for(j=i;j<9&&!ab[j][i];j++);

if(j!=i)

{

memcpy(t,ab[i],sizeof t);

memcpy(ab[i],ab[j],sizeof t);

memcpy(ab[j],t,sizeof t);

}

for(j=i+1;j<9;j++)

{

if(!ab[j][i]) continue;

g=gcd(ab[i][i],ab[j][i]);

l=ab[i][i]/g;

m=ab[j][i]/g;

for(k=0;k<10;k++)

ab[j][k]=(ab[j][k]*l-ab[i][k]*m)%4;

}

for(i=8;i;i--)

{

for(j=i-1;j>-1;j--)

{

if(!ab[j][i]) continue;

g=gcd(ab[i][i],ab[j][i]);

l=ab[i][i]/g;

m=ab[j][i]/g;

for(k=0;k<10;k++)

ab[j][k]=(ab[j][k]*l-ab[i][k]*m)%4;

}

for(i=tl=0;i<9;i++)

{

j=calc(ab[i][i],ab[i][9]);

if(j)

{

t[tl]=i+1;

tn[tl]=j;

tl++;

}

for(i=0;i<tl-1;i++)

while(tn[i]--) printf("%d ",t[i]);

while(--tn[i]) printf("%d ",t[i]);

printf("%d\n",t[i]);

}

int main()

{

while(init())

solve();

return 0;

}

好久没来了……这几天都在看书+帮人折腾VPS。Linode用久了就以为主机商都该是这样的，现在算认识到很多产品还是良萎不齐的（而且还死贵……）

[POJ 3020]

发表回复

Antenna Placement

二分图匹配。

其实是很久以前做的题目了。今天被Usozki问了下这题怎么做，看了他的代码，感觉值得改进的地方不少……便自己着手重做了下这题，希望能讲清边表的写法。由于之前hackerhank出过一题很刁钻的匈牙利，觉得已经把这个算法弄得很透彻了（包括递归改非递归、每轮匈牙利时局部链表指针改全局、每次不重新memste标记数组等等），但这次重写这题还是用了很久。

这里用了一个题目的特点（可以染色成国际象棋棋盘那样的二分图），使得每个匹配的共算了两次；又或者其实可以每次仅从一种颜色的点出发，这样就只算一次匹配。

这是今天写的代码：

#include<cstdio>
#include<cstring>

char s[40][11];

int h,w,bi,hd[400],d[40][10],b[400],f[400],el,si;

struct E
{
    int v,p;
}e[1600];

inline void adde(int u,int v)
{
    e[el].v=v; e[el].p=hd[u]; hd[u]=el++;
    e[el].v=u; e[el].p=hd[v]; hd[v]=el++;
}

int hun(int i)
{
    int j,k,l;
    for(l=hd[i];l!=-1;l=e[l].p)
    {
        j=e[l].v;
        if(b[j]==bi) continue;
        b[j]=bi;
        if(f[j]==-1||hun(f[j]))
        {
            f[j]=i;
            return 1;
        }
    }
    return 0;
}

void init()
{
    int i,j;
    si=el=0;
    memset(hd,-1,sizeof hd);
    memset(d,-1,sizeof d);
    for(i=0;i<h;i++)
    {
        scanf("%s",s[i]);
        for(j=0;j<w;j++)
            if(s[i][j]=='*') d[i][j]=si++;
        if(i)
            for(j=0;j<w;j++)
                if(d[i][j]!=-1&&d[i-1][j]!=-1)
                    adde(d[i][j],d[i-1][j]);
        for(j=1;j<w;j++)
            if(d[i][j]!=-1&&d[i][j-1]!=-1)
                adde(d[i][j],d[i][j-1]);
    }
    memset(b,-1,sizeof b);
    memset(f,-1,sizeof f);
}

void solve()
{
    int c=0;
    for(bi=0;bi<si;bi++)
        c+=hun(bi);
    printf("%d\n",si-c/2);
}

int main()
{
    scanf("%*d");
    while(~scanf("%d%d",&h,&w))
    {
        init();
        solve();
    }
    return 0;
}

#include<cstdio>

#include<cstring>

char s[40][11];

int h,w,bi,hd[400],d[40][10],b[400],f[400],el,si;

struct E

{

int v,p;

}e[1600];

inline void adde(int u,int v)

{

e[el].v=v; e[el].p=hd[u]; hd[u]=el++;

e[el].v=u; e[el].p=hd[v]; hd[v]=el++;

}

int hun(int i)

{

int j,k,l;

for(l=hd[i];l!=-1;l=e[l].p)

{

j=e[l].v;

if(b[j]==bi) continue;

b[j]=bi;

if(f[j]==-1||hun(f[j]))

{

f[j]=i;

return 1;

}

return 0;

}

void init()

{

int i,j;

si=el=0;

memset(hd,-1,sizeof hd);

memset(d,-1,sizeof d);

for(i=0;i<h;i++)

{

scanf("%s",s[i]);

for(j=0;j<w;j++)

if(s[i][j]=='*') d[i][j]=si++;

if(i)

for(j=0;j<w;j++)

if(d[i][j]!=-1&&d[i-1][j]!=-1)

adde(d[i][j],d[i-1][j]);

for(j=1;j<w;j++)

if(d[i][j]!=-1&&d[i][j-1]!=-1)

adde(d[i][j],d[i][j-1]);

}

memset(b,-1,sizeof b);

memset(f,-1,sizeof f);

}

void solve()

{

int c=0;

for(bi=0;bi<si;bi++)

c+=hun(bi);

printf("%d\n",si-c/2);

}

int main()

{

scanf("%*d");

while(~scanf("%d%d",&h,&w))

{

init();

solve();

}

return 0;

}

这里建图是先编号，再检查上方和左方是否存在点，然后加边的。代码里函数功能应该都区分得很明显了。这样写出来的边表，是做很多图论题时必须使用的数据结构（甚至其他类型题目里也经常用到）。无论是时间、空间，还是代码实现难度方面都是很好的。

另外也贴下以前写的，当时不会用边表，但是代码还算是比较齐整了：

#include<stdio.h>
#include<string.h>

int t,n,h,w,a[40][10],b[400],d[400][400],f[400];
char s[40][11];

int dfs(int i)
{
    int j,k,l;
    for(j=0; j<n; j++)
    {
        if(!b[j]&&d[i][j])
        {
            b[j]=1;
            if(f[j]==-1||dfs(f[j]))
            {
                f[j]=i;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    int i,j,k,l;
    scanf("%d",&t);
    while(t--)
    {
        memset(a,-1,sizeof(a));
        memset(d,0,sizeof(d));
        memset(f,-1,sizeof(f));
        n=0;
        scanf("%d%d",&h,&w);
        for(i=0; i<h; i++)
        {
            scanf("%s",s[i]);
            for(j=0; j<w; j++)
                if(s[i][j]=='*') a[i][j]=n++;
        }
        for(i=0; i<h; i++)
        {
            for(j=i&1; j<w; j+=2)
            {
                if(a[i][j]>-1)
                {
                    if(i>0&&a[i-1][j]>-1) d[a[i][j]][a[i-1][j]]=1;
                    if(i<h-1&&a[i+1][j]>-1) d[a[i][j]][a[i+1][j]]=1;
                    if(j>0&&a[i][j-1]>-1) d[a[i][j]][a[i][j-1]]=1;
                    if(j<w-1&&a[i][j+1]>-1) d[a[i][j]][a[i][j+1]]=1;
                }
            }
        }
        for(i=j=0; i<n; i++)
        {
            memset(b,0,sizeof(b));
            j+=dfs(i);
        }
        printf("%d\n",n-j);
    }
    return 0;
}

#include<stdio.h>

#include<string.h>

int t,n,h,w,a[40][10],b[400],d[400][400],f[400];

char s[40][11];

int dfs(int i)

{

int j,k,l;

for(j=0; j<n; j++)

{

if(!b[j]&&d[i][j])

{

b[j]=1;

if(f[j]==-1||dfs(f[j]))

{

f[j]=i;

return 1;

}

return 0;

}

int main()

{

int i,j,k,l;

scanf("%d",&t);

while(t--)

{

memset(a,-1,sizeof(a));

memset(d,0,sizeof(d));

memset(f,-1,sizeof(f));

n=0;

scanf("%d%d",&h,&w);

for(i=0; i<h; i++)

{

scanf("%s",s[i]);

for(j=0; j<w; j++)

if(s[i][j]=='*') a[i][j]=n++;

}

for(i=0; i<h; i++)

{

for(j=i&1; j<w; j+=2)

{

if(a[i][j]>-1)

{

if(i>0&&a[i-1][j]>-1) d[a[i][j]][a[i-1][j]]=1;

if(i<h-1&&a[i+1][j]>-1) d[a[i][j]][a[i+1][j]]=1;

if(j>0&&a[i][j-1]>-1) d[a[i][j]][a[i][j-1]]=1;

if(j<w-1&&a[i][j+1]>-1) d[a[i][j]][a[i][j+1]]=1;

}

for(i=j=0; i<n; i++)

{

memset(b,0,sizeof(b));

j+=dfs(i);

}

printf("%d\n",n-j);

}

return 0;

}

[POJ 1487]

发表回复

Single-Player Games

还是高斯消元法。

这题的特点是输入是用树来表示的，并且需要做类似编译原理那样的词法和语法分析。处理字符的时候小心一点，问题不会太大（但还是被负数的’-‘阴到了。。）。用递归来表示每个括号的匹配情况，符号移到等式右端（取负），数值直接累加，递归返回时每个值除去子树规模再累加到父节点数组上即可。由于输入规模不大，除了字符串处理也没有其他麻烦了。

解线性方程组的时候，注意每个方程已经指定了主元了，如果系数为0即对应变量无解，所有依赖于该变量的其他变量也无解。但其他剩余有解的变量还是要解出来的。这题比之前那题取模的要好处理，方程比较整齐，而且可以直接用浮点数。

#include<cstdio>
#include<cstring>

const double eps=1e-6;

int n,ml,t;
double ab[26][27],m[1000000],d[26];
char c,b[26];

inline double abs(double e)
{
    return e>0?e:-e;
}

int getint()
{
    int d=c-'0';
    while((c=getchar())>='0'&&c<='9')
        d=d*10+c-'0';
    return d;
}

void calc(double *f)
{
    ml+=n+1;
    double *e=&m[ml];
    int i,l=0;
    c=getchar();
    while(1)
    {
        while(c==' ')
            c=getchar();
        if(c==')') break;
        l++;
        if(c=='(') calc(e);
        else if(c=='-'||c>='0'&&c<='9')
        {
            if(c=='-')
            {
                c=getchar();
                e[n]-=getint();
            }
            else e[n]+=getint();
        }
        else if(c>='a'&&c<='z')
        {
            e[c-'a']-=1;
            c=getchar();
        }
    }
    for(i=0;i<=n;i++)
        f[i]+=e[i]/l;
    c=getchar();
}

void init()
{
    int i;
    ml=0;
    memset(ab,0,sizeof ab);
    memset(m,0,sizeof m);
    for(i=0;i<n;i++)
    {
        ab[i][i]=1;
        scanf("%*s%*s");
        while((c=getchar())!='(');
        calc(ab[i]);
    }
}

void solve()
{
    int i,j,k,l;
    double e,f;
    memset(b,0,sizeof b);
    printf("Game %d\n",++t);
    for(i=0;i<n;i++)
    {
        if(abs(ab[i][i])<eps)
        {
            b[i]=-1;
            continue;
        }
        for(j=i+1;j<n;j++)
        {
            if(abs(ab[j][i])<eps) continue;
            e=ab[j][i]/ab[i][i];
            for(k=i;k<=n;k++)
                ab[j][k]-=ab[i][k]*e;
        }
    }
    for(i=n-1;i>-1;i--)
    {
        if(b[i]==-1) continue;
        for(j=0;j<n&&!(abs(ab[i][j])>eps&&b[j]==-1);j++);
        if(j<n)
        {
            b[i]=-1;
            continue;
        }
        d[i]=ab[i][n]/ab[i][i];
        for(j=i-1;j>-1;j--)
        {
            if(abs(ab[j][i])<eps) continue;
            ab[j][n]-=ab[i][n]*ab[j][i]/ab[i][i];
            ab[j][i]=0;
        }
    }
    for(i=0;i<n;i++)
    {
        if(b[i]==-1)
            printf("Expected score for %c undefined\n",'a'+i);
        else
            printf("Expected score for %c = %.3f\n",'a'+i,d[i]);
    }
    puts("");
}

int main()
{
    while(~scanf("%d",&n)&&n)
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

#include<cstdio>

#include<cstring>

const double eps=1e-6;

int n,ml,t;

double ab[26][27],m[1000000],d[26];

char c,b[26];

inline double abs(double e)

{

return e>0?e:-e;

}

int getint()

{

int d=c-'0';

while((c=getchar())>='0'&&c<='9')

d=d*10+c-'0';

return d;

}

void calc(double *f)

{

ml+=n+1;

double *e=&m[ml];

int i,l=0;

c=getchar();

while(1)

{

while(c==' ')

c=getchar();

if(c==')') break;

l++;

if(c=='(') calc(e);

else if(c=='-'||c>='0'&&c<='9')

{

if(c=='-')

{

c=getchar();

e[n]-=getint();

}

else e[n]+=getint();

}

else if(c>='a'&&c<='z')

{

e[c-'a']-=1;

c=getchar();

}

for(i=0;i<=n;i++)

f[i]+=e[i]/l;

c=getchar();

}

void init()

{

int i;

ml=0;

memset(ab,0,sizeof ab);

memset(m,0,sizeof m);

for(i=0;i<n;i++)

{

ab[i][i]=1;

scanf("%*s%*s");

while((c=getchar())!='(');

calc(ab[i]);

}

void solve()

{

int i,j,k,l;

double e,f;

memset(b,0,sizeof b);

printf("Game %d\n",++t);

for(i=0;i<n;i++)

{

if(abs(ab[i][i])<eps)

{

b[i]=-1;

continue;

}

for(j=i+1;j<n;j++)

{

if(abs(ab[j][i])<eps) continue;

e=ab[j][i]/ab[i][i];

for(k=i;k<=n;k++)

ab[j][k]-=ab[i][k]*e;

}

for(i=n-1;i>-1;i--)

{

if(b[i]==-1) continue;

for(j=0;j<n&&!(abs(ab[i][j])>eps&&b[j]==-1);j++);

if(j<n)

{

b[i]=-1;

continue;

}

d[i]=ab[i][n]/ab[i][i];

for(j=i-1;j>-1;j--)

{

if(abs(ab[j][i])<eps) continue;

ab[j][n]-=ab[i][n]*ab[j][i]/ab[i][i];

ab[j][i]=0;

}

for(i=0;i<n;i++)

{

if(b[i]==-1)

printf("Expected score for %c undefined\n",'a'+i);

else

printf("Expected score for %c = %.3f\n",'a'+i,d[i]);

}

puts("");

}

int main()

{

while(~scanf("%d",&n)&&n)

{

init();

solve();

}

return 0;

}

另外这题也是我在POJ上有记录的第200题，貌似里面夹杂的水题不少。。。但还是值得纪念：

[POJ 2947]

发表回复

Widget Factory

高斯消元法。

其实就是线性代数里解线性方程组，但这题还要求等式两边mod7。

解向量中xi的取值范围是[3,9]，共有m个方程，判断是否有解，如果有解，要判断是否有唯一解。

这题一开始走了弯路，想象以前解普通线性方程组那样用浮点数依次选列主元后化成上三角来求解。但发现在这题mod7条件下，行不通。

后来发现可以用一个很差的时间复杂度完全使用整数进行处理。。。由于数据规模不大，发现这样是可行的。每次消元处理后都也要注意各种取模，不然很易RE。

反正最后就是各种暴力。。。就过了。。。

#include<cstdio>
#include<cstring>

int n,m,d[300];
int ab[300][301],t[301];
char s[4],e[4];

int gcd(int a,int b)
{
    if(a%b==0) return b;
    return gcd(b,a%b);
}

int lcm(int a,int b)
{
    if(!a||!b) return 0;
    return a*b/gcd(a,b);
}

int chk(char s[])
{
    if(!strcmp(s,"MON")) return 1;
    if(!strcmp(s,"TUE")) return 2;
    if(!strcmp(s,"WED")) return 3;
    if(!strcmp(s,"THU")) return 4;
    if(!strcmp(s,"FRI")) return 5;
    if(!strcmp(s,"SAT")) return 6;
    return 7;
}

inline int calc(int a,int b)
{
    a=(a%7+7)%7;
    b=(b%7+7)%7;
    for(int d=3;d<=9;d++)
        if(a*d%7==b) return d;
    return -1;
}

void solve()
{
    int i,j,k,l,o,p;
    memset(ab,0,sizeof ab);
    for(i=0;i<m;i++)
    {
        scanf("%d%s%s",&j,s,e);
        k=chk(s);
        l=chk(e);
        ab[i][n]=l-k+1;
        while(j--)
        {
            scanf("%d",&k);
            ab[i][k-1]++;
        }
    }
    for(i=0;i<m;i++)
        for(j=0;j<=n;j++)
            ab[i][j]%=7;
    for(i=l=0;i<n;i++)
    {
        for(j=l;j<m&&!ab[j][i];j++);
        if(j==m) continue;
        if(j>l)
        {
            memcpy(t,ab[j],sizeof t);
            memcpy(ab[j],ab[l],sizeof t);
            memcpy(ab[l],t,sizeof t);
        }
        for(j=l+1;j<m;j++)
        {
            if(!ab[j][i]) continue;
            p=lcm(ab[j][i],ab[l][i])/ab[j][i];
            for(o=i;o<=n;o++)
                ab[j][o]*=p;
            p=ab[j][i]/ab[l][i];
            for(o=i;o<=n;o++)
            {
                ab[j][o]-=ab[l][o]*p;
                ab[j][o]%=7;
            }
        }
        l++;
    }
    for(i=m-1;i>-1;i--)
    {
        for(j=0;j<=n&&!ab[i][j];j++);
        if(j==n)
        {
            puts("Inconsistent data.");
            return;
        }
    }
    memset(d,-1,sizeof d);
    for(i=l-1;i>-1;i--)
    {
        for(j=0;j<n&&!ab[i][j];j++);
        if(j==n) continue;
        for(k=j+1;k<n&&!ab[i][k];k++);
        if(k<n)
        {
            puts("Multiple solutions.");
            return;
        }
        d[j]=calc(ab[i][j],ab[i][n]);
        for(k=i-1;k>-1;k--)
        {
            if(!ab[k][j]) continue;
            p=lcm(ab[i][j],ab[k][j])/ab[k][j];
            for(o=0;o<=n;o++)
                ab[k][o]*=p;
            p=ab[k][j]/ab[i][j];
            for(o=0;o<=n;o++)
            {
                ab[k][o]-=ab[i][o]*p;
                ab[k][o]%=7;
            }
        }
    }
    for(i=0;i<n;i++)
        if(d[i]==-1)
        {
            puts("Multiple solutions.");
            return;
        }
    for(i=0;i<n-1;i++) printf("%d ",d[i]);
    printf("%d\n",d[n-1]);
}

int main()
{
    while(~scanf("%d%d",&n,&m)&&n)
        solve();
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

#include<cstdio>

#include<cstring>

int n,m,d[300];

int ab[300][301],t[301];

char s[4],e[4];

int gcd(int a,int b)

{

if(a%b==0) return b;

return gcd(b,a%b);

}

int lcm(int a,int b)

{

if(!a||!b) return 0;

return a*b/gcd(a,b);

}

int chk(char s[])

{

if(!strcmp(s,"MON")) return 1;

if(!strcmp(s,"TUE")) return 2;

if(!strcmp(s,"WED")) return 3;

if(!strcmp(s,"THU")) return 4;

if(!strcmp(s,"FRI")) return 5;

if(!strcmp(s,"SAT")) return 6;

return 7;

}

inline int calc(int a,int b)

{

a=(a%7+7)%7;

b=(b%7+7)%7;

for(int d=3;d<=9;d++)

if(a*d%7==b) return d;

return -1;

}

void solve()

{

int i,j,k,l,o,p;

memset(ab,0,sizeof ab);

for(i=0;i<m;i++)

{

scanf("%d%s%s",&j,s,e);

k=chk(s);

l=chk(e);

ab[i][n]=l-k+1;

while(j--)

{

scanf("%d",&k);

ab[i][k-1]++;

}

for(i=0;i<m;i++)

for(j=0;j<=n;j++)

ab[i][j]%=7;

for(i=l=0;i<n;i++)

{

for(j=l;j<m&&!ab[j][i];j++);

if(j==m) continue;

if(j>l)

{

memcpy(t,ab[j],sizeof t);

memcpy(ab[j],ab[l],sizeof t);

memcpy(ab[l],t,sizeof t);

}

for(j=l+1;j<m;j++)

{

if(!ab[j][i]) continue;

p=lcm(ab[j][i],ab[l][i])/ab[j][i];

for(o=i;o<=n;o++)

ab[j][o]*=p;

p=ab[j][i]/ab[l][i];

for(o=i;o<=n;o++)

{

ab[j][o]-=ab[l][o]*p;

ab[j][o]%=7;

}

l++;

}

for(i=m-1;i>-1;i--)

{

for(j=0;j<=n&&!ab[i][j];j++);

if(j==n)

{

puts("Inconsistent data.");

return;

}

memset(d,-1,sizeof d);

for(i=l-1;i>-1;i--)

{

for(j=0;j<n&&!ab[i][j];j++);

if(j==n) continue;

for(k=j+1;k<n&&!ab[i][k];k++);

if(k<n)

{

puts("Multiple solutions.");

return;

}

d[j]=calc(ab[i][j],ab[i][n]);

for(k=i-1;k>-1;k--)

{

if(!ab[k][j]) continue;

p=lcm(ab[i][j],ab[k][j])/ab[k][j];

for(o=0;o<=n;o++)

ab[k][o]*=p;

p=ab[k][j]/ab[i][j];

for(o=0;o<=n;o++)

{

ab[k][o]-=ab[i][o]*p;

ab[k][o]%=7;

}

for(i=0;i<n;i++)

if(d[i]==-1)

{

puts("Multiple solutions.");

return;

}

for(i=0;i<n-1;i++) printf("%d ",d[i]);

printf("%d\n",d[n-1]);

}

int main()

{

while(~scanf("%d%d",&n,&m)&&n)

solve();

return 0;

}

[POJ 2348]

发表回复

Euclid’s Game

博弈问题。

输入是两个数A、B（设A>=B），有两个人轮流操作，每轮可以从A中减去B*k，k满足A>=B*k，随后令A’=A-B*k，A=max(A’,B)，B=min(A’,B)，再进行下一轮。先使得B==0的人获胜。

分析题意易得，A、B两数的组合每次的mxk=A/B值决定了当前选手是否拥有主动权：若mxk>1，那么自己可以选择(mxk-1)，对手只能选1，下一轮依然自己先选，若下一轮mxk==1还可以本轮自己全取，依然是主动；但若mxk==1，那么自己这轮就无法选择了。由于这里每轮都是最优操作，那么首先获得主动权的人可以赢得比赛。由此迭代更新A、B，并找到首先不为1的A/B值，此轮的先手就是赢家。

另外，最后一组A、B的值无关紧要，因为此时无论谁先手，都必定全取k=A/B。

#include<cstdio>

int a,b;

int main()
{
    int i,w;
    while(~scanf("%d%d",&a,&b)&&a)
    {
        if(a<b) a^=b^=a^=b;
        for(w=1;a%b&&a/b==1;w^=1,i=a,a=b,b=i%b);
        puts(w?"Stan wins":"Ollie wins");
    }
    return 0;
}

#include<cstdio>

int a,b;

int main()

{

int i,w;

while(~scanf("%d%d",&a,&b)&&a)

{

if(a<b) a^=b^=a^=b;

for(w=1;a%b&&a/b==1;w^=1,i=a,a=b,b=i%b);

puts(w?"Stan wins":"Ollie wins");

}

return 0;

}