OI

20170116 AHSDFZ day3 NOI 模拟赛解题报告

graph

题目大意：

给出一个n个点m条边的无向图，边有边权。你要求一个含有点数最少的正环，输出该环长度。n<=300，保证无重边自环

考场上这道题弃疗了…我一想 环 就想简单环 然后就不会做了。。

赛后lt跟我讲一个非简单环一定不是答案，考虑一个非简单环 由至少两个子环构成 那么他们其中一个权值大于等于0，一个小于等于0，这样非常不好，我们干脆不要小于的那部分，剩下的还可以更优是不是。。

正解：

考虑动态规划 令dp[i][j][k]表示从i到j走了k步的最长路。求答案的时候枚举k 看看dp[i][i][k]是否大于0.

然后这样状态是n^3，转移n 总复杂度n^4爆炸。

我们发现一个一个转移k不妙，于是用倍增的思想来做。

dp[i][j][k]表示从i到j走了2^k步的最长路

然后计算答案的时候怎么做呢？

（这里YY了好久。。感谢lt和sqc大神的指点。。）

假设当前走了step步，走完之后每个点对i,j之间的最长路都已经记录下来了，用f[i][j]来表示走step步后i,j最长路长度。

考虑我们dp出来的东西的贡献。

枚举一个k，然后转移，f->g。g为走了step+2^k步之后点对最长路。

如果g里面存在g[i][i] > 0 显然已经有一个从i->i的正环了，GG 我们不走2^k步 我们试试2^(k-1)步（类似于lca的思想）

这样我们就找出了环最短的长度，答案要求输出点的个数，我们让ans+1即可。

注意不要瞎开long long，否则会有4这个常数。。。。

代码：

 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

#include <cstdio>
#include <algorithm>
using namespace std;
typedef int LL;
int n, m, ans;
int f[9][301][301], cur[301][301], tmp[301][301];
const LL INF = 1000000007;
bool check(int k) {
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            tmp[i][j] = f[k][i][j];
    for (int l = 1; l <= n; ++l)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                tmp[i][j] = max(tmp[i][j], max(cur[i][l] + f[k][l][j], f[k][i][l] + cur[l][j]));
    for (int i = 1; i <= n; ++i)
        if (tmp[i][i] > 0) return true;
    return false;
}
int main() {
    freopen("graph.in", "r", stdin);
    freopen("graph.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for (int i = 0; i <= 300; ++i)
        for (int j = 0; j <= 300; ++j)
            for (int k = 0; k <= 8; ++k)
                f[k][i][j] = -INF;
    for (int i = 0; i <= 300; ++i)
        f[0][i][i] = 0;
    int x, y;
    for (int i = 1; i <= m; ++i) {
        scanf("%d %d", &x, &y);
        scanf("%d %d", &f[0][x][y], &f[0][y][x]);
    }
    for (int k = 1; k <= 8; ++k)
        for (int l = 1; l <= n; ++l)
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j)
                    f[k][i][j] = max(f[k-1][i][l] + f[k-1][l][j], f[k][i][j]);
    ans = 0;
    for (int i = 1; i <= n; ++i)
        cur[i][i] = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            cur[i][j] = -INF;
    for (int k = 8; k >= 0; --k) {
        if (!check(k)) {
            ans += (1<<k);
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j)
                    cur[i][j] = tmp[i][j];
        }
    }
    if (ans == 0) puts("0");
    else printf("%d", ans + 1);
}

tree

题目大意

给你一棵n个点的树，给你平面上n个点，要求你完成树上的点到平面上的点的映射，要求映射完后对于任意两条树上的边，在平面中对应的两对点的连线不相交。保证有解，重合不算相交。

正解

首先有解这个很显然，关键看怎么构造。

令solve(i,S)表示现在dfs处理到了i这个点，i以及其子树对应点的集合为S

我们先在S中找到最左下角的点，钦定i对应的就是这个点。

我们把剩下的点按照到i的极角排个序

然后对于i的子树j 一定对应着这排好序中的某一段，递归处理solve(j,S’)即可

证明：我们不妨将对应的一段看成平面中的一个扇形，首先两两子树之间不相交（这个显然，两个扇形之间肯定不重合），然后对于他的子树中的边，我们如果递归着搞肯定也有这个性质。

代码：

 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

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const double pi = acos(-1);
const double tao = pi*double(2);
typedef pair<pair<int, int>, pair<double, int> > maghsk;
maghsk e[1505];
int n, h[1505], cnte, ans[1505], fa[1505], siz[1505];
struct edge_T {int to, next;} edge[1505*2];
void ins(int x, int y) {edge[++cnte].to = y;edge[cnte].next = h[x];h[x] = cnte;}
bool cmpa(maghsk a, maghsk b) {return a.second.first < b.second.first;}
bool cmpyx(maghsk a, maghsk b) {return a.first.second == b.first.second ? a.first.first < b.first.first : a.first.second < b.first.second;}
int dfs1(int now, int father) {
    fa[now] = father;
    for (int i = h[now]; i; i = edge[i].next) if (edge[i].to != father) siz[now] += dfs1(edge[i].to, now);
    return ++siz[now];
}
void dfs(int now, int l, int r) {
    sort(e+l,e+r,cmpyx);
    ans[e[l].second.second] = now;
    for (int j = l+1; j < r; ++j) e[j].second.first = atan2(e[j].first.second - e[l].first.second, e[j].first.first - e[l].first.first);
    ++l; sort(e+l, e+r, cmpa);
    for (int i = h[now]; i; i = edge[i].next) {
        if (edge[i].to == fa[now]) continue;
        dfs(edge[i].to, l, l + siz[edge[i].to]);
        l += siz[edge[i].to];
    }
}
int x, y;
int main() {
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i < n; ++i) {
        scanf("%d %d", &x, &y);
        ins(x, y); ins(y, x);
    }
    for (int i = 0; i < n; ++i) {
        scanf("%d %d", &e[i].first.first, &e[i].first.second);
        e[i].second.second = i + 1;
    }
    dfs1(1, 0); dfs(1, 0, n);
    for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

matrix

题目大意：

给你一个n*m的01矩阵，q次询问，每次将（x，y）改成1然后询问最大 0-子正方形矩阵。

正解：

离线询问，变成每次把1改成0

考虑如果答案会变大，肯定是包含(x,y)这个的点的正方形出现了，于是我们看一看x这一行的答案是否变动。

对于每个点x,y维护up和down，表示从这个点往上、下最长0的长度。

那么一个边长为a的合法正方形一定满足存在一个点 x, L 使得在x这一行中（此时的up为up[x],down同理） min(up_i) + min(down_i) – 1 >= a, i in [L, L+a)

这个枚举l，对右端点维护单调队列即可O(n)扫完。

改变一个点对up down的贡献更是可以暴力O(n)修改。

于是我们就得到了一个O(q*(n+m))的优秀的算法啦！

代码:

 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

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 2005;
char str[maxn][maxn];
int uq[maxn], dq[maxn], uh, dh, ut, dt, up[maxn][maxn], down[maxn][maxn], qx[maxn], qy[maxn], n, m, q, ANS, ans[maxn];
inline int solve(int x) {
    int *U = up[x], *D = down[x];
    int ptr = 0, ret = 0;
    uh=dh=1; ut=dt=0;
    uq[1] = dq[1] = 0;
    for (int l = 1; l <= m; ++l) {
        if (ptr < l) ptr = l-1;
        while (ptr < m && min(U[ptr+1], U[uq[uh]]) + min(D[ptr+1], D[dq[dh]]) - 1 >= ptr+1 - l + 1) {
            ++ptr;
            while (uh <= ut && U[uq[ut]] >= U[ptr]) --ut; uq[++ut] = ptr;
            while (dh <= dt && D[dq[dt]] >= D[ptr]) --dt; dq[++dt] = ptr;
        }
        ret = max(ret, ptr - l + 1);
        while (uh <= ut && uq[uh] <= l) ++uh;
        while (dh <= dt && dq[dh] <= l) ++dh;
    }
    return ret;
}
inline void pretreat() {
    for (int j = 1; j <= m; ++j) {
        for (int i = 1; i <= n; ++i) up[i][j] = (str[i][j] == '.') ? up[i-1][j]+1 : 0;
        for (int i = n; i >= 1; --i) down[i][j] = (str[i][j] == '.') ? down[i+1][j]+1 : 0;
    }
    for (int i = 1; i <= n; ++i) {up[i][0] = down[i][0] = 1000000007; ANS = max(ANS, solve(i));}
}
inline void recalc(int x, int y) {
    for (int i = 1; i <= n; ++i) up[i][y] = (str[i][y] == '.') ? up[i-1][y]+1 : 0;
    for (int i = n; i >= 1; --i) down[i][y] = (str[i][y] == '.') ? down[i+1][y]+1 : 0;
    ANS = max(ANS, solve(x));
}
int main() {
    freopen("matrix.in", "r", stdin);
    freopen("matrix.out", "w", stdout);
    scanf("%d %d %d", &n, &m, &q);
    for (int i = 1; i <= n; ++i) scanf("%s", str[i]+1);
    for (int i = 1; i <= q; ++i) {
        scanf("%d %d", qx+i, qy+i);
        str[qx[i]][qy[i]] = 'X';
    }
    pretreat();
    ans[q] = ANS;
    for (int i = q; i >= 2; --i) {
        str[qx[i]][qy[i]] = '.';
        recalc(qx[i], qy[i]);
        ans[i-1] = ANS;
    }
    for (int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}