9.22

Posted on Edited on In

  • 透彻pair与map的合理利用来处理重边 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    typedef pair<int, int> pr;
    map<pr, bool>existd;

    for (i = 1; i <= m; ++ i)
    {
        x = read(), y = read();
        if (existd[pr(x, y)] == true) continue;
        if (x == y) continue;
        add_edge(x, y), add_edge(y, x);
        
        existd[pr(x, y)] = true;
    }

  • 割点

割点不需要判断什么儿子父亲

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inline void tarjan(int x)
{
    int flag(0), i, y;
    dfn[x] = low[x] = ++ num;
    for (i = head[x]; i; i = nex[i])
    {
        y = ver[i];
        if (! dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
            if (low[y] >= dfn[x])
            {
                ++ flag;
                if (x != root || flag > 1) cut[x] = true;
            }
        }
        else low[x] = min(low[x], dfn[y]);
    }
    return;
}

if (x != root || flag > 1) cut[x] = true;

很巧妙的一句话，考虑if不成立的条件，x不为root，并且flag大于1

  • 割边

需要来判断另一条边

令cnt从2开始计数

2 XOR 1 = 3，3 XOR 1 = 2

  • 曾经做过的一道原题，见7.30

其中t数组的运用太niub了

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
inline void fuck()
{
    int i, j, l, r, tot;
    
    for (i = 1; i <= n; ++ i) f[i] = g[i] = 0;
    for (i = 1; i <= n; ++ i)
    {
        for (j = 1; j <= n; ++ j)
        {
            sum[i][j] = a[i][j];
            sum[i][j] += sum[i][j - 1];
        }
    }
    
    for (l = 1; l <= n; ++ l)
    {
        for (r = l; r <= n; ++ r)
        {
            tot = 0;
            
            for (i = 1; i < p; ++ i) t[i] = -1;
            for (i = 1; i <= n; ++ i)
            {
                tot += sum[i][r] - sum[i][l - 1];
                tot %= p;
                
                if (t[tot] != -1)
                {
                    f[r] = max(f[r], (r - l + 1) * (i - t[tot]));
                    g[l] = max(g[l], (r - l + 1) * (i - t[tot]));
                }
                else t[tot] = i;
            }
        }
    }
    
    for (i = n - 1; i >= 1; -- i) g[i] = max(g[i], g[i + 1]);
    for (i = 1; i <= n - 1; ++ i) res = max(res, f[i] + g[i + 1]);
    
    return;	
}

关于旋转矩形那里，直接swap就得了

  • 考试题

大致题意： 每次可以选择一行或者一列加上1，令3，6，9，12为好数，问最多可以有多少个好数？

一道考试题的暴力思路

首先对所有数字mod3，因为我们只需要知道这个数字变为3的倍数需要加上几最后对这个矩阵扫一遍，统计零的个数就是答案

对同一个数字在某一行或者某一列记录他出现的次数，对于出现最多次数的数字，判断其与当前行（或者列）零出现的次数

如果比零出现的次数多，说明使得这一行（或者列）出现次数最多的数字变为0（也就是成为3的倍数）之后，得到的0比原来更多 反之就不操作

do_while什么时候结束？就是当所有行或者列里面，零出现的次数都是最多的，也就意味着再进行操作就不优了

这种做法在数值属于[1,12]期间的时候，是可以AC的

但是他的数值可以变为负数，可以大于12

正解是搜索

  • 另一道考试题目

在维护最大值的时候

多考虑优先队列大根堆

其中如果需要查找前后值的话，考虑链表

其中维护链表的时候，总之务必搞清楚先nex还是pre