分类目录归档：acm

面试题一则

有节点数为n的一棵树，每个节点i有一个权值w[i]，节点i到节点j的距离d[i][j]定义为在树上节点i和节点j之间有多少条边。定义f(i) = sum{w[j] * d[i][j] | -1 < j < n}，求min{f(i) | -1 < i < n}。题源来自qoshi。

基本思路还是树型DP，希望能根据相邻节点的f值计算出当前节点的f值。具体的思路是，如果指定了深搜的起点为0，那么每个节点都会将树上的其他节点分为两个部分，一部分是离0点近的（设为A类节点），一部分是离0点远的（设为B类节点）。

具体的状态转移，包括4个矩阵：lw[i]，记录的是某个节点划分出的属于A类节点的权值和；rw[i]记录属于B类节点的权值和；lws[i]记录的是sum{ w[j] * d[i][j] | j属于i划分出的A类节点}；rws[i]记录的是sum{ w[j] * d[i][j] | j属于i划分出的B类节点}。由此f(i) = lws[i] + rws[i]。使用这4个矩阵是因为，沿着某条边走一步后，某个节点的这4个值可以根据相邻节点的信息O(1)地得到。

其中rws[i]，需要从自底向上的构造，也就是用了深搜遍历完所有孩子节点后，再计算父节点的值；而lws[i]，则是自顶向下的计算。

具体的程序如下：

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

#define M 100000

int n, w[M], lw[M], lws[M], rw[M], rws[M], hd[M], el;
int ansi, ans;

struct E {
    int v, p;
}e[M*2];

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++;
}

void init() {
    int i, j, k, l;
    el=0;
    memset(hd, -1, sizeof hd);
    for(i=0; i<n; i++) scanf("%d", w+i);
    for(i=1; i<n ;i++) {
        scanf("%d%d", &j, &k);
        adde(j, k);
    }
    ans=0x7fffffff;
}

void dfsr(int i, int f) {
    int j, k, l;
    rw[i]=rws[i]=0;
    for(l=hd[i]; l!=-1; l=e[l].p) {
        j=e[l].v;
        if(j==f) continue;
        dfsr(j, i);
        rw[i]+=rw[j]+w[j];
        rws[i]+=rws[j]+rw[j]+w[j];
    }
}

void dfsl(int i, int f) {
    int j, k, l;
    if(f==-1) {
        lw[i]=lws[i]=0;
    } else {
        lw[i]=rw[f]+lw[f]-rw[i]-w[i]+w[f];
        lws[i]=rws[f]+lws[f]-rws[i]-rw[i]-w[i]+lw[i];
    }
    for(l=hd[i]; l!=-1; l=e[l].p) {
        j=e[l].v;
        if(j==f) continue;
        dfsl(j, i);
    }
}

void solve() {
    int i;
    dfsr(0, -1);
    dfsl(0, -1);
    for(i=0; i<n; i++) {
        printf("%d: %d + %d = %d\n", i, lws[i], rws[i], lws[i]+rws[i]);
        if(lws[i]+rws[i]<ans) {
            ans=lws[i]+rws[i];
            ansi=i;
        }
    }
    printf("%d %d\n", ansi, ans);
}

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

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define M 100000

int n, w[M], lw[M], lws[M], rw[M], rws[M], hd[M], el;

int ansi, ans;

struct E {

int v, p;

}e[M*2];

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++;

}

void init() {

int i, j, k, l;

el=0;

memset(hd, -1, sizeof hd);

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

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

scanf("%d%d", &j, &k);

adde(j, k);

}

ans=0x7fffffff;

}

void dfsr(int i, int f) {

int j, k, l;

rw[i]=rws[i]=0;

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

j=e[l].v;

if(j==f) continue;

dfsr(j, i);

rw[i]+=rw[j]+w[j];

rws[i]+=rws[j]+rw[j]+w[j];

}

void dfsl(int i, int f) {

int j, k, l;

if(f==-1) {

lw[i]=lws[i]=0;

} else {

lw[i]=rw[f]+lw[f]-rw[i]-w[i]+w[f];

lws[i]=rws[f]+lws[f]-rws[i]-rw[i]-w[i]+lw[i];

}

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

j=e[l].v;

if(j==f) continue;

dfsl(j, i);

}

void solve() {

int i;

dfsr(0, -1);

dfsl(0, -1);

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

printf("%d: %d + %d = %d\n", i, lws[i], rws[i], lws[i]+rws[i]);

if(lws[i]+rws[i]<ans) {

ans=lws[i]+rws[i];

ansi=i;

}

printf("%d %d\n", ansi, ans);

}

int main () {

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

init();

solve();

}

return 0;

}

只有自己做的一些测试数据，没有找到OJ版本的题目：

输入1：

2 3 1 2 4

0 1

1 2

2 3

2 4

输出1：

0: 0 + 23 = 23
1: 2 + 13 = 15
2: 7 + 6 = 13
3: 21 + 0 = 21
4: 17 + 0 = 17
2 13

0: 0 + 23 = 23

1: 2 + 13 = 15

2: 7 + 6 = 13

3: 21 + 0 = 21

4: 17 + 0 = 17

2 13

输入2：

9
5 2 7 6 8 1 4 2 3
0 1
1 2
1 3
3 5
3 6
3 4
4 7
0 8

5 2 7 6 8 1 4 2 3

0 1

1 2

1 3

3 5

3 6

3 4

4 7

0 8

输出2：

0: 0 + 78 = 78
1: 11 + 45 = 56
2: 80 + 0 = 80
3: 35 + 17 = 52
4: 68 + 2 = 70
5: 88 + 0 = 88
6: 82 + 0 = 82
7: 104 + 0 = 104
8: 110 + 0 = 110
3 52

0: 0 + 78 = 78

1: 11 + 45 = 56

2: 80 + 0 = 80

3: 35 + 17 = 52

4: 68 + 2 = 70

5: 88 + 0 = 88

6: 82 + 0 = 82

7: 104 + 0 = 104

8: 110 + 0 = 110

3 52

[HDU 4836]

发表回复

The Query on the Tree

2014年百度之星复赛的第二题，看了官方题解才会做。

个人觉得这题有意思的地方有：
（1）通过记录DFS顺序+树状数组的方式，动态更新每一棵子树的权值和；
（2）树根改变的时候，根据父子关系巧妙地不修改数据求出当前子树权值和。

#include<cstdio>
#include<cstring>

int t,n,m,el,hd[10000],y[10000],f[10000],dl[10000],dr[10000],di;
int tr[20001],yt,rt;
char s[10];

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

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++;
}

void ins(int i,int d)
{
    while(i<di)
    {
        tr[i]+=d;
        i+=i&-i;
    }
}

int qry(int i)
{
    int d=0;
    while(i)
    {
        d+=tr[i];
        i-=i&-i;
    }
    return d;
}

void dfs(int i,int h)
{
    int j,k,l;
    f[i]=h;
    dl[i]=di++;
    for(l=hd[i];l!=-1;l=e[l].p)
    {
        j=e[l].v;
        if(j==h)
            continue;
        dfs(j,i);
    }
    dr[i]=di++;
}

void init()
{
    int i,j,k,l;
    el=0;
    di=1;
    yt=0;
    rt=0;
    memset(hd,-1,sizeof hd);
    memset(tr,0,sizeof tr);
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&j,&k);
        adde(j-1,k-1);
    }
    for(i=0;i<n;i++)
    {
        scanf("%d",y+i);
        yt+=y[i];
    }
    dfs(0,-1);
    for(i=0;i<n;i++)
        ins(dl[i],y[i]);
}

void solve()
{
    int i,j,k,l;
    printf("Case #%d:\n",++t);
    scanf("%d",&m);
    while(m--)
    {
        scanf("%s",s);
        if(s[0]=='Q')
        {
            scanf("%d",&i);
            i--;
            if(i==rt)
            {
                printf("%d\n",yt);
            }
            else
            {
                if(dl[rt]>dl[i]&&dr[rt]<dr[i])
                {
                    for(l=rt;f[l]!=i;l=f[l]);
                    printf("%d\n",yt-(qry(dr[l])-qry(dl[l]-1)));
                }
                else
                {
                    printf("%d\n",qry(dr[i])-qry(dl[i]-1));
                }
            }
        }
        else if(s[0]=='C')
        {
            scanf("%d%d",&i,&j);
            i--;
            ins(dl[i],j-y[i]);
            yt+=j-y[i];
            y[i]=j;
        }
        else
        {
            scanf("%d",&rt);
            rt--;
        }
    }
}

int main()
{
    scanf("%*d");
    while(~scanf("%d",&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

128

129

130

131

132

#include<cstdio>

#include<cstring>

int t,n,m,el,hd[10000],y[10000],f[10000],dl[10000],dr[10000],di;

int tr[20001],yt,rt;

char s[10];

struct E

{

int v,p;

}e[20000];

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++;

}

void ins(int i,int d)

{

while(i<di)

{

tr[i]+=d;

i+=i&-i;

}

int qry(int i)

{

int d=0;

while(i)

{

d+=tr[i];

i-=i&-i;

}

return d;

}

void dfs(int i,int h)

{

int j,k,l;

f[i]=h;

dl[i]=di++;

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

{

j=e[l].v;

if(j==h)

continue;

dfs(j,i);

}

dr[i]=di++;

}

void init()

{

int i,j,k,l;

el=0;

di=1;

yt=0;

rt=0;

memset(hd,-1,sizeof hd);

memset(tr,0,sizeof tr);

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

{

scanf("%d%d",&j,&k);

adde(j-1,k-1);

}

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

{

scanf("%d",y+i);

yt+=y[i];

}

dfs(0,-1);

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

ins(dl[i],y[i]);

}

void solve()

{

int i,j,k,l;

printf("Case #%d:\n",++t);

scanf("%d",&m);

while(m--)

{

scanf("%s",s);

if(s[0]=='Q')

{

scanf("%d",&i);

i--;

if(i==rt)

{

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

}

else

{

if(dl[rt]>dl[i]&&dr[rt]<dr[i])

{

for(l=rt;f[l]!=i;l=f[l]);

printf("%d\n",yt-(qry(dr[l])-qry(dl[l]-1)));

}

else

{

printf("%d\n",qry(dr[i])-qry(dl[i]-1));

}

else if(s[0]=='C')

{

scanf("%d%d",&i,&j);

i--;

ins(dl[i],j-y[i]);

yt+=j-y[i];

y[i]=j;

}

else

{

scanf("%d",&rt);

rt--;

}

int main()

{

scanf("%*d");

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

{

init();

solve();

}

return 0;

}

[POJ 3074]

发表回复

Sudoku

题意：求解数独问题。

思路：用DLX解。首先，需要将格盘建模为DLX用到的十字链表。数字之间的互斥关系共有4种，因此可以对”每行每个数字”、”每列每个数字”、”每九宫格每个数字”、”每个格点位置”分别建立一个链表列，也即总共是9*9+9*9+9*9+9*9=324个链表列，十字链表中每一行表示在某格点放置某数，分别与4个对应的链表列相交。

然后，就是正式的深搜了。在深搜的每一层：
1) 在十字链表表头中找出元素最少且非零的一列，将该列以及列中包含的所有行元素从十字链表中移除；
2) 枚举列中的每行（作为解的一部分），将与该行相交的所有其他列以及这些列包含的行元素在十字链表中移除，递归下一层深搜;
3) 递归返回时，需要将2)中移除的相应列和行添加回十字链表；
4) 所有行枚举完毕时，需要将1)中移除的相应列和行添加回十字链表。

注意，对链表进行增删操作时，需要以相反的顺序修改各结点。同时，也需要动态维护表头的元素数。

#include<cstdio>
#include<cstring>
#define M 10000

int s[9][9],sl;
int hd,el,tag;
char t[82],r[9][10],c[9][10],b[9][10];

struct E
{
    int l,r,u,d,c,s;
    int ri,ci,bi,v;
}e[M];

void adde(int ei,int ri,int ci,int bi,int v)
{
    e[ei].s++;
    e[el].u=ei;
    e[el].d=e[ei].d;
    e[e[ei].d].u=el;
    e[ei].d=el;
    e[el].c=ei;
    e[el].ri=ri;
    e[el].ci=ci;
    e[el].bi=bi;
    e[el].v=v;
    el++;
}

void addr(int ri,int ci,int bi,int v)
{
    int i,j,k,l;
    adde(1+ri*9+v-1,ri,ci,bi,v);
    adde(1+81+ci*9+v-1,ri,ci,bi,v);
    adde(1+81+81+bi*9+v-1,ri,ci,bi,v);
    adde(1+81+81+81+ri*9+ci,ri,ci,bi,v);
    for(i=0;i<4;i++)
    {
        j=(i+3)%4;
        k=(i+1)%4;
        e[el-4+i].l=el-4+j;
        e[el-4+i].r=el-4+k;
    }
}

void init()
{
    int i,j,k,l,tl;
    hd=el=tag=0;
    sl=81;
    memset(r,0,sizeof r);
    memset(c,0,sizeof c);
    memset(b,0,sizeof b);
    for(i=tl=0;i<9;i++)
    {
        for(j=0;j<9;j++)
        {
            if(t[tl]=='.')
                k=0;
            else
                k=t[tl]-'0';
            if(k)
                sl--;
            r[i][k]=1;
            c[j][k]=1;
            s[i][j]=k;
            l=i/3*3+j/3;
            b[l][k]=1;
            tl++;
        }
    }
    e[el].l=e[el].r=el;
    el++;
    for(i=0;i<324;i++)
    {
        e[el].l=hd;
        e[el].r=e[hd].r;
        e[e[hd].r].l=el;
        e[hd].r=el;
        e[el].u=e[el].d=e[el].c=el;
        e[el].s=0;
        el++;
    }
    for(i=0;i<9;i++)
    {
        for(j=0;j<9;j++)
        {
            if(s[i][j])
                continue;
            l=i/3*3+j/3;
            for(k=1;k<10;k++)
            {
                if(r[i][k]||c[j][k]||b[l][k])
                    continue;
                addr(i,j,l,k);
            }
        }
    }
}

void pnt()
{
    int i,j,tl;
    for(i=tl=0;i<9;i++)
        for(j=0;j<9;j++)
            t[tl++]='0'+s[i][j];
    puts(t);
}

void dfs(int si)
{
    if(si==sl)
    {
        tag=1;
        pnt();
        return;
    }
    int i,j,k,l;
    int ii,jj,kk;
    int ri,ci,bi,v;
    for(i=e[hd].r,j=0x7fffffff;i!=hd;i=e[i].r)
    {
        if(e[i].s&&e[i].s<j)
        {
            j=e[i].s;
            k=i;
        }
        if(j==1)
            break;
    }
    if(j==0x7fffffff)
        return;
    e[e[k].l].r=e[k].r;
    e[e[k].r].l=e[k].l;
    for(i=e[k].d;i!=k;i=e[i].d)
    {
        for(j=e[i].r;j!=i;j=e[j].r)
        {
            e[e[j].c].s--;
            e[e[j].u].d=e[j].d;
            e[e[j].d].u=e[j].u;
        }
    }
    for(i=e[k].d;i!=k;i=e[i].d)
    {
        ri=e[i].ri; ci=e[i].ci; bi=e[i].bi; v=e[i].v;
        for(j=e[i].r;j!=i;j=e[j].r)
        {
            kk=e[j].c;
            e[e[kk].l].r=e[kk].r;
            e[e[kk].r].l=e[kk].l;
            for(ii=e[kk].d;ii!=kk;ii=e[ii].d)
            {
                for(jj=e[ii].r;jj!=ii;jj=e[jj].r)
                {
                    e[e[jj].c].s--;
                    e[e[jj].u].d=e[jj].d;
                    e[e[jj].d].u=e[jj].u;
                }
            }
        }
        s[ri][ci]=v;
        dfs(si+1);
        if(tag)
            return;
        for(j=e[i].l;j!=i;j=e[j].l)
        {
            kk=e[j].c;
            e[e[kk].l].r=kk;
            e[e[kk].r].l=kk;
            for(ii=e[kk].u;ii!=kk;ii=e[ii].u)
            {
                for(jj=e[ii].l;jj!=ii;jj=e[jj].l)
                {
                    e[e[jj].u].d=jj;
                    e[e[jj].d].u=jj;
                    e[e[jj].c].s++;
                }
            }
        }
    }
    for(i=e[k].u;i!=k;i=e[i].u)
    {
        for(j=e[i].l;j!=i;j=e[j].l)
        {
            e[e[j].u].d=j;
            e[e[j].d].u=j;
            e[e[j].c].s++;
        }
    }
    e[e[k].l].r=k;
    e[e[k].r].l=k;
}

void solve()
{
    dfs(0);
}

int main()
{
    while(scanf("%s",t)&&t[0]!='e')
    {
        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

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

#include<cstdio>

#include<cstring>

#define M 10000

int s[9][9],sl;

int hd,el,tag;

char t[82],r[9][10],c[9][10],b[9][10];

struct E

{

int l,r,u,d,c,s;

int ri,ci,bi,v;

}e[M];

void adde(int ei,int ri,int ci,int bi,int v)

{

e[ei].s++;

e[el].u=ei;

e[el].d=e[ei].d;

e[e[ei].d].u=el;

e[ei].d=el;

e[el].c=ei;

e[el].ri=ri;

e[el].ci=ci;

e[el].bi=bi;

e[el].v=v;

el++;

}

void addr(int ri,int ci,int bi,int v)

{

int i,j,k,l;

adde(1+ri*9+v-1,ri,ci,bi,v);

adde(1+81+ci*9+v-1,ri,ci,bi,v);

adde(1+81+81+bi*9+v-1,ri,ci,bi,v);

adde(1+81+81+81+ri*9+ci,ri,ci,bi,v);

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

{

j=(i+3)%4;

k=(i+1)%4;

e[el-4+i].l=el-4+j;

e[el-4+i].r=el-4+k;

}

void init()

{

int i,j,k,l,tl;

hd=el=tag=0;

sl=81;

memset(r,0,sizeof r);

memset(c,0,sizeof c);

memset(b,0,sizeof b);

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

{

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

{

if(t[tl]=='.')

k=0;

else

k=t[tl]-'0';

if(k)

sl--;

r[i][k]=1;

c[j][k]=1;

s[i][j]=k;

l=i/3*3+j/3;

b[l][k]=1;

tl++;

}

e[el].l=e[el].r=el;

el++;

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

{

e[el].l=hd;

e[el].r=e[hd].r;

e[e[hd].r].l=el;

e[hd].r=el;

e[el].u=e[el].d=e[el].c=el;

e[el].s=0;

el++;

}

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

{

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

{

if(s[i][j])

continue;

l=i/3*3+j/3;

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

{

if(r[i][k]||c[j][k]||b[l][k])

continue;

addr(i,j,l,k);

}

void pnt()

{

int i,j,tl;

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

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

t[tl++]='0'+s[i][j];

puts(t);

}

void dfs(int si)

{

if(si==sl)

{

tag=1;

pnt();

return;

}

int i,j,k,l;

int ii,jj,kk;

int ri,ci,bi,v;

for(i=e[hd].r,j=0x7fffffff;i!=hd;i=e[i].r)

{

if(e[i].s&&e[i].s<j)

{

j=e[i].s;

k=i;

}

if(j==1)

break;

}

if(j==0x7fffffff)

return;

e[e[k].l].r=e[k].r;

e[e[k].r].l=e[k].l;

for(i=e[k].d;i!=k;i=e[i].d)

{

for(j=e[i].r;j!=i;j=e[j].r)

{

e[e[j].c].s--;

e[e[j].u].d=e[j].d;

e[e[j].d].u=e[j].u;

}

for(i=e[k].d;i!=k;i=e[i].d)

{

ri=e[i].ri; ci=e[i].ci; bi=e[i].bi; v=e[i].v;

for(j=e[i].r;j!=i;j=e[j].r)

{

kk=e[j].c;

e[e[kk].l].r=e[kk].r;

e[e[kk].r].l=e[kk].l;

for(ii=e[kk].d;ii!=kk;ii=e[ii].d)

{

for(jj=e[ii].r;jj!=ii;jj=e[jj].r)

{

e[e[jj].c].s--;

e[e[jj].u].d=e[jj].d;

e[e[jj].d].u=e[jj].u;

}

s[ri][ci]=v;

dfs(si+1);

if(tag)

return;

for(j=e[i].l;j!=i;j=e[j].l)

{

kk=e[j].c;

e[e[kk].l].r=kk;

e[e[kk].r].l=kk;

for(ii=e[kk].u;ii!=kk;ii=e[ii].u)

{

for(jj=e[ii].l;jj!=ii;jj=e[jj].l)

{

e[e[jj].u].d=jj;

e[e[jj].d].u=jj;

e[e[jj].c].s++;

}

for(i=e[k].u;i!=k;i=e[i].u)

{

for(j=e[i].l;j!=i;j=e[j].l)

{

e[e[j].u].d=j;

e[e[j].d].u=j;

e[e[j].c].s++;

}

e[e[k].l].r=k;

e[e[k].r].l=k;

}

void solve()

{

dfs(0);

}

int main()

{

while(scanf("%s",t)&&t[0]!='e')

{

init();

solve();

}

return 0;

}

没有想出太好的优化。c++下跑了188ms。

ps：
记得最早是11年寒假时，和Arios一起留校做MCM时听他提到，当时那道建模题可以用Dancing Links解。一晃眼，3年多过去了，我这才开始读Knuth的这篇论文。

文章本身的算法不算难懂，因为深搜的优化是很多问题都要用到的。之前做题的时候，确实也有考虑过对链表进行动态调整，但发现无法根本上降低时间复杂度（依然是指数时间）后，也没有深究了。而Knuth这篇论文里介绍的DLX，通过对十字链表进行动态调整从而尽量保持搜索树最优，可以说是在通常情况下将深搜优化到了极致。

做这题数独时，在链表建模那一步想了大概一整天时间。主要是数独问题元素间的互斥情况比较复杂。一开始只用了前3种互斥关系，发现表头记录的元素数无法正确维护，每次暴力重算并加了些优化后竟然勉强过了。然后就一直在想正解。想出应该增加第4种互斥关系后，又用了很长时间才推出要移除与当前行元素互斥的所有行。最后对链表的修改要比一开始想的要复杂得多。

查了下status，Arios在5年前作出的时间是32ms，并且是1A 47ms过的。实在是很强。

[SRM 621]

发表回复

第一场TC。

很好的开局。继续努力。

[SPOJ 2832]

发表回复

Find The Determinant III

数论

题意：输入一个最多200*200的行列式a和一个正整数p，求|a|%p。

分析：集训队论文集里《欧几里得算法的应用》的第一道例题。非常巧妙，用GCD思想作模系统下的高斯消元。实现的时候大致要注意以下几点：
（1）尽量减少辗转相除的次数；
（2）尽量少用模运算；
（3）消元过程中算出答案为0提前结束；
（4）尽量避免整行swap；
（5）手动解释输入；
（6）尽量不用long long。

TLE了一整晚后，成功刷入第一版。

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

#define ll long long

int n,p,d[200][200];
ll ans;

int gi()
{
    char c;
    while((c=getchar())!='-'&&(c<'0'||c>'9'));
    int d,e=1;
    if(c=='-')
    {
        e=-1;
        c=getchar();
    }
    d=c-'0';
    while((c=getchar())>='0'&&c<='9')
        d=d*10+c-'0';
    return d*e;
}

void init()
{
    ll i,j;
    ans=1;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            d[i][j]=gi();
            if(abs(d[i][j])>=p)
                d[i][j]%=p;
            if(d[i][j]<0)
                d[i][j]+=p;
        }
    }
}

void calc(int h,int i,int j)
{
    int k;
    ll a,e;
    if(d[i][h]<d[j][h])
        swap(i,j);
    while(d[j][h])
    {
        a=d[i][h]/d[j][h];
        for(k=h;k<n;k++)
        {
            e=d[i][k]-a*d[j][k];
            if(abs(e)>=p)
                e%=p;
            if(e<0)
                e+=p;
            d[i][k]=e;
        }
        if(d[i][h]<d[j][h])
            swap(i,j);
    }
}

void solve()
{
    int i,j,k,l;
    for(i=0;i<n;i++)
    {
        for(j=i;j<n&&!d[j][i];j++);
        if(j==n)
        {
            puts("0");
            return;
        }
        if(j>i)
        {
            for(l=i;l<n;l++)
                swap(d[i][l],d[j][l]);
            ans=-ans;
        }
        for(l=i,j=l+1;j<n;j++)
        {
            calc(i,j,l);
            if(!d[l][i])
                l=j;
        }
        if(l>i)
        {
            ans=-ans;
            for(k=i;k<n;k++)
                swap(d[i][k],d[l][k]);
        }
    }
    for(i=0;i<n;i++)
        ans=ans*d[i][i]%p;
    printf("%lldn",(ans%p+p)%p);
}

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

100

101

102

103

104

105

106

107

108

109

110

111

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

int n,p,d[200][200];

ll ans;

int gi()

{

char c;

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

int d,e=1;

if(c=='-')

{

e=-1;

c=getchar();

}

d=c-'0';

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

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

return d*e;

}

void init()

{

ll i,j;

ans=1;

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

{

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

{

d[i][j]=gi();

if(abs(d[i][j])>=p)

d[i][j]%=p;

if(d[i][j]<0)

d[i][j]+=p;

}

void calc(int h,int i,int j)

{

int k;

ll a,e;

if(d[i][h]<d[j][h])

swap(i,j);

while(d[j][h])

{

a=d[i][h]/d[j][h];

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

{

e=d[i][k]-a*d[j][k];

if(abs(e)>=p)

e%=p;

if(e<0)

e+=p;

d[i][k]=e;

}

if(d[i][h]<d[j][h])

swap(i,j);

}

void solve()

{

int i,j,k,l;

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

{

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

if(j==n)

{

puts("0");

return;

}

if(j>i)

{

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

swap(d[i][l],d[j][l]);

ans=-ans;

}

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

{

calc(i,j,l);

if(!d[l][i])

l=j;

}

if(l>i)

{

ans=-ans;

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

swap(d[i][k],d[l][k]);

}

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

ans=ans*d[i][i]%p;

printf("%lldn",(ans%p+p)%p);

}

int main()

{

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

{

init();

solve();

}

return 0;

}

[POJ 1379]

发表回复

Run Away

模拟退火

题意：在最大10000*10000平面的上有最多1000个洞，求平面上的某个点，使得其离所有洞的最近距离最大化。输出精度为小数点后1位。

分析：按照模拟退火的思想，在平面上随机取10个点，将单次移动的步长设为算法中的温度，移动方向随机。初始温度设为矩形对角线长的一半，每轮迭代后温度降为之前的0.8。每轮迭代时，对于每个点，按照当前步长尝试移动50次，如果目标点更优则更新位置，否则维持原位。当温度降低到0.001以下时，终止算法，并取10个点中的最优值输出。

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

#define eps 1e-3
#define its 50
#define pl 10
#define pi 3.141592653589793

int n;
double r,c,x[1000],y[1000];
double xp[pl],yp[pl],dp[pl];

double calc(double xv,double yv)
{
    int i;
    double d=1e30;
    for(i=0;i<n;i++)
        d=min(d,pow(x[i]-xv,2)+pow(y[i]-yv,2));
    return d;
}

bool chk(double xu,double yu)
{
    return xu>0&&xu<r&&yu>0&&yu<c;
}

void init()
{
    int i;
    for(i=0;i<n;i++)
        scanf("%lf%lf",x+i,y+i);
    for(i=0;i<pl;i++)
    {
        xp[i]=r*0.001*(rand()%1000);
        yp[i]=c*0.001*(rand()%1000);
        dp[i]=calc(xp[i],yp[i]);
    }
}

void solve()
{
    int i,j,k,l;
    double a,g,xv,yv,vd,xu,yu,ud;
    srand(time(0));
    for(l=0;l<pl;l++)
    {
        xv=xp[l];
        yv=yp[l];
        vd=dp[l];
        for(g=sqrt(r*r+c*c)*0.5;g>eps;g*=0.8)
        {
            for(i=0;i<its;i++)
            {
                a=2*pi*0.001*(rand()%1000);
                xu=xv+g*cos(a);
                yu=yv+g*sin(a);
                if(!chk(xu,yu))
                    continue;
                ud=calc(xu,yu);
                if(ud>vd)
                {
                    xv=xu;
                    yv=yu;
                    vd=ud;
                }
            }
        }
        xp[l]=xv;
        yp[l]=yv;
        dp[l]=vd;
    }
    for(l=0,ud=0;l<pl;l++)
    {
        if(dp[l]>ud)
        {
            ud=dp[l];
            xv=xp[l];
            yv=yp[l];
        }
    }
    printf("The safest point is (%.1f, %.1f).\n",xv,yv);
}

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

#include<ctime>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define eps 1e-3

#define its 50

#define pl 10

#define pi 3.141592653589793

int n;

double r,c,x[1000],y[1000];

double xp[pl],yp[pl],dp[pl];

double calc(double xv,double yv)

{

int i;

double d=1e30;

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

d=min(d,pow(x[i]-xv,2)+pow(y[i]-yv,2));

return d;

}

bool chk(double xu,double yu)

{

return xu>0&&xu<r&&yu>0&&yu<c;

}

void init()

{

int i;

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

scanf("%lf%lf",x+i,y+i);

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

{

xp[i]=r*0.001*(rand()%1000);

yp[i]=c*0.001*(rand()%1000);

dp[i]=calc(xp[i],yp[i]);

}

void solve()

{

int i,j,k,l;

double a,g,xv,yv,vd,xu,yu,ud;

srand(time(0));

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

{

xv=xp[l];

yv=yp[l];

vd=dp[l];

for(g=sqrt(r*r+c*c)*0.5;g>eps;g*=0.8)

{

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

{

a=2*pi*0.001*(rand()%1000);

xu=xv+g*cos(a);

yu=yv+g*sin(a);

if(!chk(xu,yu))

continue;

ud=calc(xu,yu);

if(ud>vd)

{

xv=xu;

yv=yu;

vd=ud;

}

xp[l]=xv;

yp[l]=yv;

dp[l]=vd;

}

for(l=0,ud=0;l<pl;l++)

{

if(dp[l]>ud)

{

ud=dp[l];

xv=xp[l];

yv=yp[l];

}

printf("The safest point is (%.1f, %.1f).\n",xv,yv);

}

int main()

{

scanf("%*d");

while(~scanf("%lf%lf%d",&r,&c,&n))

{

init();

solve();

}

return 0;

}

ps：非常山寨的实现方式，没有考虑目标位置并非更优时仍进行移动的方案。本题的数据也是很松，只要控制好初始点数，温度下降幅度以及迭代次数，时限范围内很易求得最优位置。

[POJ 1263]

发表回复

Reflections

计算几何

题意：给出二维平面上一个起始点和光线方向，以及平面上最多25个反射球面，问光线每次反射时击中的球编号。当不再击中球面或是反射了超过10次后终止计算。题目保证起始点不在球内，且不会沿切线方向击中球。

分析：由于数据量不大，可以每次计算出光线方向上与每个球的交点，按距离排序后取最近的一个点，根据入射角和切点算出反射角。迭代以上过程10次即可。

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

#define eps 1e-8

int t,n,pl;
double x,y,xd,yd,a,b,c;

struct S
{
    double x,y,r;
}s[25];

struct P
{
    int si;
    double d,x,y;
    bool operator < (const P& p) const
    {
        return d<p.d;
    }
}p[50];

void init()
{
    int i,j,k,l;
    for(i=0;i<n;i++)
        scanf("%lf%lf%lf",&s[i].x,&s[i].y,&s[i].r);
    scanf("%lf%lf%lf%lf",&x,&y,&xd,&yd);
}

void addp(int si,double d,double x,double y)
{
    p[pl].si=si; p[pl].d=d; p[pl].x=x; p[pl].y=y; pl++;
}

void calcp(int si)
{
    double x0=s[si].x,y0=s[si].y,r=s[si].r,x1,y1,x2,y2,d;
    double a0,b0,c0;
    if(fabs(a)<eps)
    {
        y1=y2=-c;
        x1=x0+sqrt(r*r-pow(c+y0,2));
        x2=x0-sqrt(r*r-pow(c+y0,2));
    }
    else
    {
        a0=(b*b)/(a*a)+1;
        b0=2*(b*(c+a*x0)/(a*a)-y0);
        c0=pow(c+a*x0,2)/(a*a)+y0*y0-r*r;
        y1=(-b0+sqrt(b0*b0-4*a0*c0))/(2*a0);
        x1=-(b*y1+c)/a;
        y2=(-b0-sqrt(b0*b0-4*a0*c0))/(2*a0);
        x2=-(b*y2+c)/a;
    }
    if(fabs(xd)>eps)
    {
        if((x1-x)/xd>eps)
        {
            d=sqrt(pow(x1-x,2)+pow(y1-y,2));
            addp(si,d,x1,y1);
        }
        if((x2-x)/xd>eps)
        {
            d=sqrt(pow(x2-x,2)+pow(y2-y,2));
            addp(si,d,x2,y2);
        }
    }
    else
    {
        if((y1-y)/yd>eps)
        {
            d=sqrt(pow(x1-x,2)+pow(y1-y,2));
            addp(si,d,x1,y1);
        }
        if((y2-y)/yd>eps)
        {
            d=sqrt(pow(x2-x,2)+pow(y2-y,2));
            addp(si,d,x2,y2);
        }
    }
}

void xng()
{
    double xs,ys,ad,as;
    xd=-xd;
    yd=-yd;
    ad=atan2(yd,xd);
    x=p[0].x;
    y=p[0].y;
    xs=x-s[p[0].si].x;
    ys=y-s[p[0].si].y;
    as=atan2(ys,xs);
    ad=as-(ad-as);
    xd=cos(ad);
    yd=sin(ad);
}

void solve()
{
    int i,j,k,l;
    printf("Scene %d\n",++t);
    for(l=0;l<11;l++)
    {
        if(l)
            printf(" ");
        if(fabs(yd)<eps)
        {
            a=0;
            b=1;
            c=-y;
        }
        else
        {
            a=1;
            b=-xd/yd;
            c=-x-b*y;
        }
        pl=0;
        for(i=0;i<n;i++)
        {
            if(fabs(a*s[i].x+b*s[i].y+c)/sqrt(a*a+b*b)<s[i].r-eps)
                calcp(i);
        }
        if(!pl)
        {
            puts("inf");
            break;
        }
        else if(l==10)
        {
            puts("...");
            break;
        }
        sort(p,p+pl);
        printf("%d",p[0].si+1);
        xng();
    }
    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

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define eps 1e-8

int t,n,pl;

double x,y,xd,yd,a,b,c;

struct S

{

double x,y,r;

}s[25];

struct P

{

int si;

double d,x,y;

bool operator < (const P& p) const

{

return d<p.d;

}

}p[50];

void init()

{

int i,j,k,l;

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

scanf("%lf%lf%lf",&s[i].x,&s[i].y,&s[i].r);

scanf("%lf%lf%lf%lf",&x,&y,&xd,&yd);

}

void addp(int si,double d,double x,double y)

{

p[pl].si=si; p[pl].d=d; p[pl].x=x; p[pl].y=y; pl++;

}

void calcp(int si)

{

double x0=s[si].x,y0=s[si].y,r=s[si].r,x1,y1,x2,y2,d;

double a0,b0,c0;

if(fabs(a)<eps)

{

y1=y2=-c;

x1=x0+sqrt(r*r-pow(c+y0,2));

x2=x0-sqrt(r*r-pow(c+y0,2));

}

else

{

a0=(b*b)/(a*a)+1;

b0=2*(b*(c+a*x0)/(a*a)-y0);

c0=pow(c+a*x0,2)/(a*a)+y0*y0-r*r;

y1=(-b0+sqrt(b0*b0-4*a0*c0))/(2*a0);

x1=-(b*y1+c)/a;

y2=(-b0-sqrt(b0*b0-4*a0*c0))/(2*a0);

x2=-(b*y2+c)/a;

}

if(fabs(xd)>eps)

{

if((x1-x)/xd>eps)

{

d=sqrt(pow(x1-x,2)+pow(y1-y,2));

addp(si,d,x1,y1);

}

if((x2-x)/xd>eps)

{

d=sqrt(pow(x2-x,2)+pow(y2-y,2));

addp(si,d,x2,y2);

}

else

{

if((y1-y)/yd>eps)

{

d=sqrt(pow(x1-x,2)+pow(y1-y,2));

addp(si,d,x1,y1);

}

if((y2-y)/yd>eps)

{

d=sqrt(pow(x2-x,2)+pow(y2-y,2));

addp(si,d,x2,y2);

}

void xng()

{

double xs,ys,ad,as;

xd=-xd;

yd=-yd;

ad=atan2(yd,xd);

x=p[0].x;

y=p[0].y;

xs=x-s[p[0].si].x;

ys=y-s[p[0].si].y;

as=atan2(ys,xs);

ad=as-(ad-as);

xd=cos(ad);

yd=sin(ad);

}

void solve()

{

int i,j,k,l;

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

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

{

if(l)

printf(" ");

if(fabs(yd)<eps)

{

a=0;

b=1;

c=-y;

}

else

{

a=1;

b=-xd/yd;

c=-x-b*y;

}

pl=0;

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

{

if(fabs(a*s[i].x+b*s[i].y+c)/sqrt(a*a+b*b)<s[i].r-eps)

calcp(i);

}

if(!pl)

{

puts("inf");

break;

}

else if(l==10)

{

puts("...");

break;

}

sort(p,p+pl);

printf("%d",p[0].si+1);

xng();

}

puts("");

}

int main()

{

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

{

init();

solve();

}

return 0;

}

ps：分类表最后一题了。还差得远，继续努力。

[POJ 3336]

发表回复

ACM Underground

计算几何

题意：给出一个起点和终点坐标，以及最多100条线段和3000个黑点，问从起点出发是否能到达终点。移动过程中存在以下限制：只能沿线段移动，如果遇到交点，可以转移到另一条线段上。如果移动过程中遇到黑点：若黑点在交点处，则无法转移到其他线段；否则无法跨越黑点继续沿线段移动。

分析：数据范围很小，可以首先枚举出所有的点，并对每条线段计算出所有在其上的点，排序，对所有相邻可达点连边，最后从起点出发深搜即可。这里的关键在于，处理某条线上的点时，若在相同位置遇到了黑点和白点，那么需要在后续处理中忽略所有该位置上的点。每次仅当两个相邻点都为白点时才连边，这样可以确保仅能通过有效交点转移到其他线段，且不会越过在单一线段上的黑点。

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

#define M 20000
#define eps 1e-8

int n,m,hd[M],el,pl,ql,S,E;
double xs,ys,xe,ye;
int stk[M],sl,b[M];

struct O
{
    double x1,y1,x2,y2;
    double a,b,c;
}o[100];

struct P
{
    int b;
    double x,y;
    bool operator < (const P& p) const
    {
        if(x<p.x-eps)
            return 1;
        if(x>p.x+eps)
            return 0;
        if(y<p.y-eps)
            return 1;
        if(y>p.y+eps)
            return 0;
        return b<p.b;
    }
}p[M];

struct Q
{
    int pi;
    double d;
    bool operator < (const Q& p) const
    {
        return d<p.d;
    }
}q[M];

struct E
{
    int v,p;
}e[M*10];

void addp(int b,double x,double y)
{
    p[pl].b=b; p[pl].x=x; p[pl].y=y; pl++;
}

void addq(int pi,double d)
{
    q[ql].pi=pi; q[ql].d=d; ql++;
}

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++;
}

double crs(double x1,double y1,double x2,double y2)
{
    return x1*y2-x2*y1;
}

bool its(int i,int j)
{
    double x1=o[i].x1,y1=o[i].y1,x2=o[i].x2,y2=o[i].y2;
    double x3=o[j].x1,y3=o[j].y1,x4=o[j].x2,y4=o[j].y2;
    double v;
    v=crs(x3-x1,y3-y1,x2-x1,y2-y1)*crs(x2-x1,y2-y1,x4-x1,y4-y1);
    if(v<-eps)
        return 0;
    v=crs(x1-x3,y1-y3,x4-x3,y4-y3)*crs(x4-x3,y4-y3,x2-x3,y2-y3);
    if(v<-eps)
        return 0;
    return 1;
}

void calc(int i,int j,double &x,double &y)
{
    double a1=o[i].a,b1=o[i].b,c1=o[i].c;
    double a2=o[j].a,b2=o[j].b,c2=o[j].c;
    if(fabs(a1)<eps)
    {
        y=-c1/b1;
        x=-(b2*y+c2)/a2;
    }
    else
    {
        y=(a2*c1-a1*c2)/(a1*b2-a2*b1);
        x=-(b1*y+c1)/a1;
    }
}

bool on(int oi,int pi)
{
    double x1=o[oi].x1,y1=o[oi].y1,x2=o[oi].x2,y2=o[oi].y2;
    double x=p[pi].x,y=p[pi].y;
    double d=sqrt(pow(x1-x2,2)+pow(y1-y2,2));
    double d1=sqrt(pow(x-x1,2)+pow(y-y1,2));
    double d2=sqrt(pow(x-x2,2)+pow(y-y2,2));
    return abs(d-d1-d2)<eps;
}

void init()
{
    int i,j,k,l;
    double x,y;
    el=pl=0;
    memset(hd,-1,sizeof hd);
    scanf("%lf%lf%lf%lf",&xs,&ys,&xe,&ye);
    addp(0,xs,ys);
    addp(0,xe,ye);
    for(i=0;i<n;i++)
    {
        scanf("%lf%lf%lf%lf",&o[i].x1,&o[i].y1,&o[i].x2,&o[i].y2);
        if(fabs(o[i].y1-o[i].y2)<eps)
        {
            o[i].a=0;
            o[i].b=1;
            o[i].c=-o[i].y1;
        }
        else
        {
            o[i].a=1;
            o[i].b=(o[i].x2-o[i].x1)/(o[i].y1-o[i].y2);
            o[i].c=-o[i].x1-o[i].b*o[i].y1;
        }
    }
    for(i=0;i<m;i++)
    {
        scanf("%lf%lf",&x,&y);
        addp(1,x,y);
    }
    for(i=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if(its(i,j))
            {
                calc(i,j,x,y);
                addp(0,x,y);
            }
        }
    }
    sort(p,p+pl);
    for(i=1;i<pl;i++)
    {
        if(fabs(p[i].x-p[i-1].x)<eps&&fabs(p[i].y-p[i-1].y)<eps)
        {
            if(p[i-1].b==2)
            {
                p[i].b=2;
                continue;
            }
            if(p[i-1].b!=p[i].b)
            {
                for(l=i;l>-1;l--)
                {
                    if(fabs(p[i].x-p[l].x)>eps
                            ||fabs(p[i].y-p[l].y)>eps)
                        break;
                    p[l].b=2;
                }
            }
        }
    }
    for(i=0;i<pl;i++)
    {
        if(fabs(p[i].x-xs)<eps&&fabs(p[i].y-ys)<eps)
            S=i;
        if(fabs(p[i].x-xe)<eps&&fabs(p[i].y-ye)<eps)
            E=i;
    }
    for(i=0;i<n;i++)
    {
        ql=0;
        for(l=0;l<pl;l++)
        {
            if(p[l].b!=2&&on(i,l))
                addq(l,(p[l].x-o[i].x1)*(p[l].x-o[i].x1)
                        +(p[l].y-o[i].y1)*(p[l].y-o[i].y1));
        }
        sort(q,q+ql);
        for(l=0;l<ql-1;l++)
        {
            if(p[q[l].pi].b==0&&p[q[l+1].pi].b==0)
                adde(q[l].pi,q[l+1].pi);
        }
    }
}

void solve()
{
    int i,j,k,l;
    if(S==E)
    {
        puts("YES");
        return;
    }
    if(p[S].b==2||p[E].b==2)
    {
        puts("NO");
        return;
    }
    memset(b,0,sizeof b);
    sl=0;
    b[S]=1;
    stk[sl++]=S;
    while(sl&&!b[E])
    {
        i=stk[--sl];
        for(l=hd[i];l!=-1;l=e[l].p)
        {
            j=e[l].v;
            if(b[j])
                continue;
            b[j]=1;
            stk[sl++]=j;
        }
    }
    puts(b[E]?"YES":"NO");
}

int main()
{
    scanf("%*d");
    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

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

#include<set>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define M 20000

#define eps 1e-8

int n,m,hd[M],el,pl,ql,S,E;

double xs,ys,xe,ye;

int stk[M],sl,b[M];

struct O

{

double x1,y1,x2,y2;

double a,b,c;

}o[100];

struct P

{

int b;

double x,y;

bool operator < (const P& p) const

{

if(x<p.x-eps)

return 1;

if(x>p.x+eps)

return 0;

if(y<p.y-eps)

return 1;

if(y>p.y+eps)

return 0;

return b<p.b;

}

}p[M];

struct Q

{

int pi;

double d;

bool operator < (const Q& p) const

{

return d<p.d;

}

}q[M];

struct E

{

int v,p;

}e[M*10];

void addp(int b,double x,double y)

{

p[pl].b=b; p[pl].x=x; p[pl].y=y; pl++;

}

void addq(int pi,double d)

{

q[ql].pi=pi; q[ql].d=d; ql++;

}

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++;

}

double crs(double x1,double y1,double x2,double y2)

{

return x1*y2-x2*y1;

}

bool its(int i,int j)

{

double x1=o[i].x1,y1=o[i].y1,x2=o[i].x2,y2=o[i].y2;

double x3=o[j].x1,y3=o[j].y1,x4=o[j].x2,y4=o[j].y2;

double v;

v=crs(x3-x1,y3-y1,x2-x1,y2-y1)*crs(x2-x1,y2-y1,x4-x1,y4-y1);

if(v<-eps)

return 0;

v=crs(x1-x3,y1-y3,x4-x3,y4-y3)*crs(x4-x3,y4-y3,x2-x3,y2-y3);

if(v<-eps)

return 0;

return 1;

}

void calc(int i,int j,double &x,double &y)

{

double a1=o[i].a,b1=o[i].b,c1=o[i].c;

double a2=o[j].a,b2=o[j].b,c2=o[j].c;

if(fabs(a1)<eps)

{

y=-c1/b1;

x=-(b2*y+c2)/a2;

}

else

{

y=(a2*c1-a1*c2)/(a1*b2-a2*b1);

x=-(b1*y+c1)/a1;

}

bool on(int oi,int pi)

{

double x1=o[oi].x1,y1=o[oi].y1,x2=o[oi].x2,y2=o[oi].y2;

double x=p[pi].x,y=p[pi].y;

double d=sqrt(pow(x1-x2,2)+pow(y1-y2,2));

double d1=sqrt(pow(x-x1,2)+pow(y-y1,2));

double d2=sqrt(pow(x-x2,2)+pow(y-y2,2));

return abs(d-d1-d2)<eps;

}

void init()

{

int i,j,k,l;

double x,y;

el=pl=0;

memset(hd,-1,sizeof hd);

scanf("%lf%lf%lf%lf",&xs,&ys,&xe,&ye);

addp(0,xs,ys);

addp(0,xe,ye);

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

{

scanf("%lf%lf%lf%lf",&o[i].x1,&o[i].y1,&o[i].x2,&o[i].y2);

if(fabs(o[i].y1-o[i].y2)<eps)

{

o[i].a=0;

o[i].b=1;

o[i].c=-o[i].y1;

}

else

{

o[i].a=1;

o[i].b=(o[i].x2-o[i].x1)/(o[i].y1-o[i].y2);

o[i].c=-o[i].x1-o[i].b*o[i].y1;

}

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

{

scanf("%lf%lf",&x,&y);

addp(1,x,y);

}

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

{

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

{

if(its(i,j))

{

calc(i,j,x,y);

addp(0,x,y);

}

sort(p,p+pl);

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

{

if(fabs(p[i].x-p[i-1].x)<eps&&fabs(p[i].y-p[i-1].y)<eps)

{

if(p[i-1].b==2)

{

p[i].b=2;

continue;

}

if(p[i-1].b!=p[i].b)

{

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

{

if(fabs(p[i].x-p[l].x)>eps

||fabs(p[i].y-p[l].y)>eps)

break;

p[l].b=2;

}

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

{

if(fabs(p[i].x-xs)<eps&&fabs(p[i].y-ys)<eps)

S=i;

if(fabs(p[i].x-xe)<eps&&fabs(p[i].y-ye)<eps)

E=i;

}

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

{

ql=0;

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

{

if(p[l].b!=2&&on(i,l))

addq(l,(p[l].x-o[i].x1)*(p[l].x-o[i].x1)

+(p[l].y-o[i].y1)*(p[l].y-o[i].y1));

}

sort(q,q+ql);

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

{

if(p[q[l].pi].b==0&&p[q[l+1].pi].b==0)

adde(q[l].pi,q[l+1].pi);

}

void solve()

{

int i,j,k,l;

if(S==E)

{

puts("YES");

return;

}

if(p[S].b==2||p[E].b==2)

{

puts("NO");

return;

}

memset(b,0,sizeof b);

sl=0;

b[S]=1;

stk[sl++]=S;

while(sl&&!b[E])

{

i=stk[--sl];

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

{

j=e[l].v;

if(b[j])

continue;

b[j]=1;

stk[sl++]=j;

}

puts(b[E]?"YES":"NO");

}

int main()

{

scanf("%*d");

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

{

init();

solve();

}

return 0;

}

[POJ 2975] & [POJ 2960]

发表回复

Nim

博弈

题意：Nim问题的必胜策略为，取当前各堆石子数的异或和，若为0则为必败局面；否则取走部分石子使得异或和变为0，便可使对方陷入必败局面。问题为，给出一个局面，问有多少种不同的必胜策略。

分析：很简单，既然必胜策略已知，那么可以算出需要改变那些位才能转化为必败局面。由于，每次只允许改变一堆石子的数目，目标石子数小于等于当前石子数时对应一种必胜策略。最后算一算有多少个堆满足该条件即可。

#include<cstdio>

int n,a[1000],ans;

void solve()
{
    int i,j;
    ans=0;
    for(i=j=0;i<n;i++)
    {
        scanf("%d",a+i);
        j^=a[i];
    }
    if(!j)
    {
        puts("0");
        return;
    }
    for(i=0;i<n;i++)
    {
        if((a[i]^j)<=a[i])
            ans++;
    }
    printf("%d\n",ans);
}

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

#include<cstdio>

int n,a[1000],ans;

void solve()

{

int i,j;

ans=0;

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

{

scanf("%d",a+i);

j^=a[i];

}

if(!j)

{

puts("0");

return;

}

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

{

if((a[i]^j)<=a[i])

ans++;

}

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

}

int main()

{

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

solve();

return 0;

}

稍微增加难度的话，就是下面这题：

S-Nim

博弈

题意：对于基本的Nim问题，增加如下限制：每次取走的石子数必须在集合S中，若剩余石子不足则可以全部取走。问题是，对于某局面，是否存在必胜策略。

分析：对于给定的S集，考虑将剩余石子的数目划分类别。具体来说，将剩余为0或无法一步到达第0类的石子数设为第0类，可以一步到达第0类（但无法到达第1类）的设为第1类，并依次类推：可以一步到达第0…i-1类且无法到达第i类的设为第i类。这样分类之后，便可以将第i类堆与原Nim问题中的堆石子数为i对应起来。其依据在于，第i类总是能一步到达更低的类别，但无法保持当前状态（或者到达更高类别时会在下一步（由对手操作）回到该类）。由此，便可以对当前各堆的类别数取异或和，并按照结果是否为0来判定是否为必败局面。

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

int n,m,a[100],b[10001],c[10001];

void init()
{
    int i,j,k,l;
    for(i=0;i<n;i++)
        scanf("%d",a+i);
    sort(a,a+n);
    b[0]=0;
    for(i=1;i<10001;i++)
    {
        memset(c,0,sizeof c);
        for(l=0;l<n&&i>=a[l];l++)
            c[b[i-a[l]]]++;
        for(l=0;c[l];l++);
        b[i]=l;
    }
}

void solve()
{
    int i,j,k,l;
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d",&l);
        j=0;
        while(l--)
        {
            scanf("%d",&i);
            j^=b[i];
        }
        printf("%c",j?'W':'L');
    }
    puts("");
}

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

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,m,a[100],b[10001],c[10001];

void init()

{

int i,j,k,l;

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

scanf("%d",a+i);

sort(a,a+n);

b[0]=0;

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

{

memset(c,0,sizeof c);

for(l=0;l<n&&i>=a[l];l++)

c[b[i-a[l]]]++;

for(l=0;c[l];l++);

b[i]=l;

}

void solve()

{

int i,j,k,l;

scanf("%d",&m);

while(m--)

{

scanf("%d",&l);

j=0;

while(l--)

{

scanf("%d",&i);

j^=b[i];

}

printf("%c",j?'W':'L');

}

puts("");

}

int main()

{

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

{

init();

solve();

}

return 0;

}

[POJ 1478]

发表回复

Island of Logic

枚举

题意：有一个岛上有3种（仅从外观无法分辨的）生物：神（只说真话）、人（白天说真话，晚上说谎话）、鬼（只说谎话）。给你一段长为n的聊天记录，要求尽量推断出更多的事实。聊天记录中最多涉及5个生物。

分析：事实分为两种，（1）生物的种族、（2）当前时间。基本思路是，可以枚举出所有的事实组合，并根据聊天记录来判断可行性。如果可行，则记录该事实组合。记录时，对于各个生物以及时间分别使用一个位相量，以逻辑或的形式记录其所有可能的取值。最后，仅存在唯一可能取值的位相量即为“事实”。

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

int t,n,ti,r[5],rl,rv[5],tag;
int at,ar[5];
char s[100],ri[128],rc[5];

struct E
{
    int tp;
    int u,v,w;
}e[50];

void init()
{
    int i,j,k,l;
    rl=0;
    tag=0;
    at=0;
    memset(ri,-1,sizeof ri);
    memset(ar,0,sizeof ar);
    for(i=0;i<n;i++)
    {
        scanf("%s",s);
        if(ri[s[0]]==-1)
        {
            ri[s[0]]=rl;
            rc[rl]=s[0];
            rl++;
        }
        j=ri[s[0]];
        e[i].u=j;
        scanf("%s",s);
        if(!strcmp(s,"It"))
        {
            e[i].tp=2;
            scanf("%*s%s",s);
            if(s[0]=='d')
                e[i].w=1;
            else
                e[i].w=2;
        }
        else
        {
            if(s[0]=='I')
                k=j;
            else
            {
                if(ri[s[0]]==-1)
                {
                    ri[s[0]]=rl;
                    rc[rl]=s[0];
                    rl++;
                }
                k=ri[s[0]];
            }
            e[i].v=k;
            scanf("%*s%s",s);
            if(s[0]=='n')
            {
                l=1;
                scanf("%s",s);
            }
            else
                l=0;
            if(s[0]=='l')
            {
                e[i].tp=1;
                e[i].w=2-l;
            }
            else
            {
                e[i].tp=0;
                if(s[0]=='d')
                    e[i].w=1;
                else if(s[0]=='h')
                    e[i].w=2;
                else if(s[0]=='e')
                    e[i].w=4;
                if(l)
                    e[i].w^=7;
            }
        }
    }
}

void mkv()
{
    int i;
    for(i=0;i<rl;i++)
    {
        if(r[i]==1)
        {
            rv[i]=1;
        }
        else if(r[i]==2)
        {
            if(ti==1)
                rv[i]=1;
            else
                rv[i]=2;
        }
        else if(r[i]==4)
        {
            rv[i]=2;
        }
    }
}

bool chk()
{
    int i;
    for(i=0;i<n;i++)
    {
        if(e[i].tp==0)
        {
            if(rv[e[i].u]==1)
            {
                if((r[e[i].v]&e[i].w)==0)
                    return 0;
            }
            else
            {
                if(r[e[i].v]&e[i].w)
                    return 0;
            }
        }
        else if(e[i].tp==1)
        {
            if(rv[e[i].u]==1)
            {
                if((rv[e[i].v]&e[i].w)==0)
                    return 0;
            }
            else
            {
                if(rv[e[i].v]&e[i].w)
                    return 0;
            }
        }
        else if(e[i].tp==2)
        {
            if(rv[e[i].u]==1)
            {
                if((ti&e[i].w)==0)
                    return 0;
            }
            else
            {
                if(ti&e[i].w)
                    return 0;
            }
        }
    }
    return 1;
}

void dfs(int i)
{
    if(i==rl)
    {
        ti=1;
        mkv();
        if(chk())
        {
            for(i=0;i<rl;i++)
                ar[i]|=r[i];
            at|=ti;
        }
        ti=2;
        mkv();
        if(chk())
        {
            for(i=0;i<rl;i++)
                ar[i]|=r[i];
            at|=ti;
        }
        return;
    }
    r[i]=1;
    dfs(i+1);
    r[i]=2;
    dfs(i+1);
    r[i]=4;
    dfs(i+1);
}

void solve()
{
    int i,j,k,l;
    dfs(0);
    for(i=0;i<rl;i++)
    {
        if(ar[i])
        {
            for(j=ar[i],k=0;j;j-=j&-j,k++);
            if(k>1)
                tag=max(tag,1);
            else
                tag=max(tag,2);
        }
    }
    if(at==3)
        tag=max(tag,1);
    else if(at)
        tag=max(tag,2);
    printf("Conversation #%d\n",++t);
    if(!tag)
        puts("This is impossible.\n");
    else if(tag==1)
        puts("No facts are deducible.\n");
    else
    {
        for(i='A';i<'F';i++)
        {
            if(ri[i]==-1)
                continue;
            j=ri[i];
            if(ar[j]==1)
                printf("%c is divine.\n",rc[j]);
            else if(ar[j]==2)
                printf("%c is human.\n",rc[j]);
            else if(ar[j]==4)
                printf("%c is evil.\n",rc[j]);
        }
        if(at==1)
            puts("It is day.");
        else if(at==2)
            puts("It is night.");
        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

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int t,n,ti,r[5],rl,rv[5],tag;

int at,ar[5];

char s[100],ri[128],rc[5];

struct E

{

int tp;

int u,v,w;

}e[50];

void init()

{

int i,j,k,l;

rl=0;

tag=0;

at=0;

memset(ri,-1,sizeof ri);

memset(ar,0,sizeof ar);

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

{

scanf("%s",s);

if(ri[s[0]]==-1)

{

ri[s[0]]=rl;

rc[rl]=s[0];

rl++;

}

j=ri[s[0]];

e[i].u=j;

scanf("%s",s);

if(!strcmp(s,"It"))

{

e[i].tp=2;

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

if(s[0]=='d')

e[i].w=1;

else

e[i].w=2;

}

else

{

if(s[0]=='I')

k=j;

else

{

if(ri[s[0]]==-1)

{

ri[s[0]]=rl;

rc[rl]=s[0];

rl++;

}

k=ri[s[0]];

}

e[i].v=k;

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

if(s[0]=='n')

{

l=1;

scanf("%s",s);

}

else

l=0;

if(s[0]=='l')

{

e[i].tp=1;

e[i].w=2-l;

}

else

{

e[i].tp=0;

if(s[0]=='d')

e[i].w=1;

else if(s[0]=='h')

e[i].w=2;

else if(s[0]=='e')

e[i].w=4;

if(l)

e[i].w^=7;

}

void mkv()

{

int i;

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

{

if(r[i]==1)

{

rv[i]=1;

}

else if(r[i]==2)

{

if(ti==1)

rv[i]=1;

else

rv[i]=2;

}

else if(r[i]==4)

{

rv[i]=2;

}

bool chk()

{

int i;

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

{

if(e[i].tp==0)

{

if(rv[e[i].u]==1)

{

if((r[e[i].v]&e[i].w)==0)

return 0;

}

else

{

if(r[e[i].v]&e[i].w)

return 0;

}

else if(e[i].tp==1)

{

if(rv[e[i].u]==1)

{

if((rv[e[i].v]&e[i].w)==0)

return 0;

}

else

{

if(rv[e[i].v]&e[i].w)

return 0;

}

else if(e[i].tp==2)

{

if(rv[e[i].u]==1)

{

if((ti&e[i].w)==0)

return 0;

}

else

{

if(ti&e[i].w)

return 0;

}

return 1;

}

void dfs(int i)

{

if(i==rl)

{

ti=1;

mkv();

if(chk())

{

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

ar[i]|=r[i];

at|=ti;

}

ti=2;

mkv();

if(chk())

{

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

ar[i]|=r[i];

at|=ti;

}

return;

}

r[i]=1;

dfs(i+1);

r[i]=2;

dfs(i+1);

r[i]=4;

dfs(i+1);

}

void solve()

{

int i,j,k,l;

dfs(0);

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

{

if(ar[i])

{

for(j=ar[i],k=0;j;j-=j&-j,k++);

if(k>1)

tag=max(tag,1);

else

tag=max(tag,2);

}

if(at==3)

tag=max(tag,1);

else if(at)

tag=max(tag,2);

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

if(!tag)

puts("This is impossible.\n");

else if(tag==1)

puts("No facts are deducible.\n");

else

{

for(i='A';i<'F';i++)

{

if(ri[i]==-1)

continue;

j=ri[i];

if(ar[j]==1)

printf("%c is divine.\n",rc[j]);

else if(ar[j]==2)

printf("%c is human.\n",rc[j]);

else if(ar[j]==4)

printf("%c is evil.\n",rc[j]);

}

if(at==1)

puts("It is day.");

else if(at==2)

puts("It is night.");

puts("");

}

int main()

{

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

{

init();

solve();

}

return 0;

}

ps：350题了。每做一题在poj上排名都会略微提升，有种在尸体堆里穿行的感觉。（前辈们失敬了）