【纪中】Day10+

【C】
题意:求无向图中两点之间的路径数。
水题。由于每个点只在一个简单环上,所以缩点以后图就变成一颗树了,而只要进过一个环,就有两条路。
于是用tarjin缩点再跑lca即可。缩点也可以用dfs,写完tarjin结果忘了无向图怎么处理,只好改dfs。。。
【棋盘游戏】
题意:从一个点走到(0,0),一步可往左、下、左下三个方向走任意步,询问先手的输赢情况。
明显的博弈论,正解是威佐夫博弈,公式很简单:
记w=(int)[((sqrt(5)+1)/2)*z ];
若w=x,则先手必败,否则先手必胜。
来讲讲部分分的做法。
30%:显然,若起点为(0,0)则先手必输,那么,从(0,0)右、上、右上的点便是先手必胜。接着,从(0,0)开始一层一层地找,若没有被标记过先手必胜,则就是先手必败。
60%:既然可以从上述方法得知输赢情况,那么,可以发现先手必败的情况特别少,打表发现,每一个必败点(x, y),(x - 1)(y - 2)、(x - 2)(y - 3)其中一个一定是必败点,可以找规律求解(反正我没找到)。
【偷窃】
题意:在一堆正方体中拿走最多的数量,并且使其三视图不改变。
正解是二分图匹配,对于行和列的最高点建边,再分别连向源点和汇点,流量是其最大值的数值,跑网络流求最大匹配。
但是,水水就能过去的题为什么要打网络流。要使三视图不改变,只要最高的不少,其余的全搬走只剩一个即可。那么,对于列上的最大值,去找行上有没有与其想等的,如果有,在一个位置就可满足行列的要求,如果没有,就随便找一个比它大的放。
代码如下:

【C】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>

using namespace std;

const int N = 2e5 + 10, M = 1e9 + 7;

struct io  {
    io()  {
        freopen("C.in", "r", stdin);
        freopen("C.out", "w", stdout);
    }
    ~io()  {
        fclose(stdin);
        fclose(stdout);
    }
}txt;

int Read()  {
    int val = 0, opt = 1;
    char ch;
    while (!isdigit(ch = getchar() ) || ch == '-');
    if (ch == '-') opt = -1;
    else val = ch - '0';
    while (isdigit( ch = getchar() )) (val *= 10) += ch - '0';
    return val * opt;
}

int nxt[2 * N], beg[N], gt[2 * N], vis[N], New[N], Num[N], sta[N], In[N];
int Time, tot, n, m, que, fa[N][25], val[N], dis[N], dep[N];

void add(int u, int v)  {
    nxt[++tot] = beg[u], beg[u] = tot, gt[tot] = v;
}

void dfs(int t, int fa)  {
    sta[++tot] = t;
    In[t] = vis[t] = 1;
    int Nxt;
    for (int e = beg[t]; e ;e = nxt[e])  {
        Nxt = gt[e];
        if (vis[Nxt] && In[Nxt] && Nxt != fa)  {
            ++New[0];
            val[New[0]] = 1;
            while (In[Nxt])  {
                New[sta[tot]] = New[0];
                In[sta[tot--]] = 0;
            }
        }
        if (!vis[Nxt])  {
            dfs(Nxt, t);
        }
    }
    if (In[t])  {
        --tot;
        In[t] = 0;
        New[t] = ++New[0];
        val[New[0]] = 0;
    }
}

queue<int> q;

void build()  {
    int Now, Nxt, t, NewNxt;
    for (int i = 1;i <= n; i++)
        if (New[i] == New[1])  {
            q.push(i);
            In[i] = 1;
        }
    vis[New[1]] = 1;
    dis[New[1]] = val[New[1]];
    dep[New[1]] = 1;
    while (!q.empty())  {
        t = q.front();
        Now = New[t];
        for (int e = beg[t]; e; e = nxt[e])  {
            Nxt = gt[e];
            NewNxt = New[Nxt];
            if (!In[Nxt])  {
                q.push(Nxt);
                In[Nxt] = 1;
            }
            if (!vis[NewNxt])  {
                vis[NewNxt] = 1;
                dis[NewNxt] = dis[Now] + val[NewNxt];
                dep[NewNxt] = dep[Now] + 1;
                fa[NewNxt][0] = Now;
                for (int i = 1;i <= 20; i++) fa[NewNxt][i] = fa[fa[NewNxt][i - 1]][i - 1];
            }
        }
        q.pop();
    }
}

int Find(int x, int y)  {
    if (x == y) return x;
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 20;i >= 0; i--)
        if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
    if (x == y) return x;
    for (int i = 20;i >= 0; i--)
        if (fa[x][i] != fa[y][i])
           x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

long long Pow(long long v, int u)  {
    if (!u) return 1;
    if (u % 2) return v * Pow(v, u - 1) % M;
    return Pow(v * v % M, u / 2);
}

int main(void)  {
    int u , v;
    n = Read(), m =Read();
    for (int i = 1;i <= m; i++)  {
        u = Read(), v = Read();
        add(u, v), add(v, u);
    }
    tot = 0;
    dfs(1, 0);
    memset(vis, 0, sizeof vis);
    memset(In, 0, sizeof In);
    build();
    que = Read();
    for (int i = 1;i <= que; i++)  {
        u = Read(), v = Read();
        int lca = Find(New[u], New[v]);
        int ans = Pow(2, dis[New[u]] + dis[New[v]] - 2 * dis[lca] + val[lca]);
        printf("%d\n", ans);
    }
    return 0;
}

【棋盘游戏】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>

using namespace std;

const int N = 1e3;


int a[N + 10][N + 10], Num[N], tot;
这个是30%的代码:
void fp(int x, int y)  {
    for (int i = 1;i <= N; i++)  {
        if (x + i <= N) a[x + i][y] = 1;
        if (y + i <= N) a[x][y + i] = 1;
        if (x + i <= N && y + i <= N) a[x + i][y + i] = 1;
    }
}

int main(void)  {
    int n, x  = 0, y = 0;
    cin >> n;
    for (int i = 1;i <= n; i++)  {
        cin >> x >> y;
        if (x > y) swap(x, y);
        if (x == (int)((1. + sqrt(5)) / 2. * (y - x)))  cout << "Alphago" << endl;
        else cout << "Amphetamine" << endl;
    }
    return 0;
}

【偷窃】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

const int N = 1e2 + 10;

struct io  {
    io()  {
        freopen("steal.in", "r", stdin);
        freopen("steal.out", "w", stdout);
    }
    ~io()  {
        fclose(stdin);
        fclose(stdout);
    }
}text;

struct Node  {
    long long Max, no, b;
    friend bool operator <(Node a, Node b)  {
        return a.Max < b.Max;
    }
    friend bool operator ==(Node a, Node b)  {
        return a.Max == b.Max;
    }
    void FM(long long x)  {
        Max = max(Max, x);
    }
}R[N], C[N];

long long mp[N][N], sh, r, c;

queue<int> q;

void work()  {
    int t = 1;
    int p;
    for (int i = 1;i <= c; i++)  {
        t = 1;
        while (R[t] < C[i] || (C[i] == R[t] && mp[R[t].no][C[i].no] != -1) || (C[i] == R[t] && R[t].b))
              t++;
        if (C[i] == R[t])  {
            C[i].b = R[t].b = 1;
            mp[R[t].no][C[i].no] = C[i].Max;
        }
        else q.push(i);
    }
    while (!q.empty())  {
        t = 1;
        p = q.front();
        while ((R[t] < C[p] || mp[R[t].no][C[p].no] != -1) && t < r) ++t;
        mp[R[t].no][C[p].no] = max(C[p].Max, mp[R[t].no][C[p].no]);
        q.pop();
    }
    for (int i = 1;i <= r; i++)
        if (!R[i].b)  {
            int t = 1;
            while ((C[t] < R[i] || mp[R[i].no][C[t].no] != -1) && t < c)
                  t++;
            mp[R[i].no][C[t].no] = max(R[i].Max, mp[R[i].no][C[t].no]);
        }
    for (int i = 1;i <= r; i++)
        for (int j = 1;j <= c; j++)
            sh -= mp[i][j] >= 0?mp[i][j]:1;
    cout << sh;
}

int main(void)   {
    scanf("%lld%lld", &r, &c);
    long long x;
    for (int i = 1;i <= r; i++)
        for (int j = 1;j <= c; j++)  {
            scanf("%lld", &x);
            sh += x;
            if (x == 0) mp[i][j] = 0;
            else mp[i][j] = -1;
            R[i].FM(x);
            C[j].FM(x);
            C[j].no = j;
            R[i].no = i;
        }
    sort(R + 1, R  + 1 + r);
    sort(C + 1, C  + 1 + c);
    if (!sh)  printf("0\n");
    else work();
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注