CTime_Pup_314

不能再颓废了

0%

10809102 AGC006

发表于 更新于 分类于 阅读次数： Valine：

Median Pyramid Easy

给定一个数字三角形，最底下一层的值为一个长度为 \(2n-1\) 排列，其余方格中填写的整数是方格正下方,左下方和右下方方格中所写整数的中位数，给定 \(n\) 和 \(x\) 求最终构造出三角形顶端为 \(x\) 的方案

一开始想的是每一层的值比下一层的值少了下一层的最大值和最小值以及满足比周围 \(4\) 个方格的树都小或都大的数，所以我们需要要计算好中位数偏移量，将左侧每 \(3\) 个数将需要删除的数移进去即可，得到的结论是 \(|n-x|\le\lfloor\frac{n}{3}\rfloor\) 时 \(x\) 可以构造出来，这个构造意外的骗了很多分 然而，正确的结论是 \(x\) 可以为 \(1\) 或 \(2n-1\) 的任何数，我们可以发现当最倒数第二层出现两个相邻的相同数字时，这两个数字会一直向上沿伸，最后的答案为里对称轴最近的满足上述条件的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 2e5+5;
int n, x, q, ans;
int p[N], vis[N];
int main()
{
    scanf("%d%d", &n, &x);
    if(x == 1||x == 2*n-1) return puts("No"), 0;
    puts("Yes"); 
    p[n] = x, p[n-1] = x == 2?x+1:x-1, p[n+1] = x == 2?x-1:x+1, p[n+2] = x == 2?x+2:x-2;
    vis[x] = vis[x+1] = vis[x-1] = vis[x == 2?x+2:x-2] = 1;
    for(int i = 1, j = 1; i <= 2*n-1; ++i)
    {
        if(p[i]) continue; while(vis[j]) ++j;
        p[i] = j, vis[j] = 1;
    }
    for(int i = 1; i <= 2*n-1; ++i) printf("%d ", p[i]);
    return 0;
}

Rabbit Exercise

有 \(n\) 只兔子站在数轴上，第 \(i\) 只兔子的初始位置为 \(a_i\)，现在这些兔子会按照下面的规则做若干次移动，每一次\(m\) 次跳跃组成，在第 \(j\)次跳跃的时候，第 \(c_j\) 只兔子会等概率随机选择第 \(c_j-1\) 和 \(c_j+1\) 只兔子中的一只跳到对称点，求 \(k\) 次动作之后，每一只兔子最终位置坐标的期望值

首先暴力的 \(DP\) 方程很好写，\(f'_{c_i}=\frac{2f_{c_i-1}+2f_{c_i+1}-2f_{c_i}}{2}=f_{c_i-1}+f_{c_i+1}-f_{c_i}\)

然而，复杂度为 \(O(mk)\)，遇到转移问题发现难以转移就想一想差分，考虑 \(d_i\ =\ f_i-f_{i-1}\)

那么差分后的转移就变为

\[ d'_{c_i}=f'_{c_i}-f_{c_i-1}=f_{c_i+1}-f_{c_i}=d_{c_i+1} \]

\[ d'_{c_i+1}=f_{c_i+1}-f'_{c_i}=f_{c_i}-f_{c_i-1}=d_{c_i} \]

发现正好是两者交换了位置，那么我们只有扫一遍操作序列，求出循环节，就可以快速求了

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 <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
typedef long long int64;
using namespace std;
inline int64 read(int f = 1, int64 x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 1e5+5;
int n, m, a[N], f[N], s[N], top, vis[N];
int64 ans[N], k;
int main()
{
    n = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    for(int i = n; i; --i) a[i] -= a[i-1], f[i] = i;
    m = read(), k = read();
    for(int i = 1, p; i <= m; ++i) p = read(), swap(f[p], f[p+1]);
    for(int i = 1; i <= n; ++i, top = 0)
        if(!vis[i])
        {
            for(int j = i; !vis[j]; j = f[j]) vis[j] = 1, s[++top] = j;
            for(int j = 1; j <= top; ++j) ans[s[j]] = a[s[(j+k-1)%top+1]];
        }
    for(int i = 1; i <= n; ++i) printf("%lld\n", ans[i] += ans[i-1]);
    return 0;
}

Median Pyramid Hard

给定一个数字三角形，最底下一层的值为一个长度为 \(2n-1\) 排列，其余方格中填写的整数是方格正下方,左下方和右下方方格中所写整数的中位数，给定 \(n\) 和 最底下一层的排列，求第一层的值

直接求很难求，考虑像猜数字一样二分，每次得到顶端的数与二分值得大小，按照 \(B\) 题的结论，里对称轴最近的长度至少为 \(2\) 的连续段就是顶端的答案，特判不存在这样连续段的情况即可

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
#include <cstring>
#include <algorithm>
#include <cctype>
#include <cstdio>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 2e5+5;
int n, p[N], ans = 2;
bool valid(int mid)
{   
    for(int i = 0; i < n-1; ++i)
        if(max(p[n-i], p[n-i-1]) <= mid||max(p[n+i], p[n+i+1]) <= mid) return true;
        else if(min(p[n-i], p[n-i-1]) > mid||min(p[n+i], p[n+i+1]) > mid) return false;
    return p[1] <= mid;
}
int main()
{
    n = read();
    for(int i = 2*n-1; i; --i) p[i] = read();
    int l = 2, r = 2*n-2;
    while(l <= r)
    {
        int mid = (l+r)>>1;
        if(valid(mid)) r = mid-1, ans = mid;
        else l = mid+1;
    }
    printf("%d\n", ans);
    return 0;
}

Rotate 3x3

我们有一个 \(3\) 行 \(N\) 列的初始矩阵，\((i,\ j)\) 位置的数为 \(i+3j-3\)，我们有一个这样的操作：选择一个 \(3\times3\) 的子矩阵，将这个子矩阵旋转 \(180^\circ\)，给定 \(3\) 行 \(N\) 列的矩阵，矩阵内的数值互不相同，问能否通过若干次上述操作将初始矩阵变为给定的矩阵

先特判掉一定无解的情况

我们注意到每次以 \((i,\ 2)\) 为中心旋转实际上是将 \(i-1\) 列和 \(i+1\) 列交换，并且 \(i\) 及相邻两列的上下颠倒，也就是说每次旋转操作除交换之外将区间 \([i-1,\ i+1]\) 的奇偶性改变，奇数时要上下颠倒，偶数时则不用，初始奇偶性序列为给定矩阵的上下颠倒状态，所以问题就转换为对于给定矩阵经过一系列操作后满足第 \(2\) 层的数值顺序递增，且每个位置奇偶性是否满足要求

考虑我们已经使位置合法了，而现在奇偶性并不满足要求，则当 \(n\ge 4\) 时有如下变化可以在不改边位置的情况下该边奇偶性，我们可以

\[ abcd\to CBAd\to CDab\to Adcb\to ABCD \]

可以发现每次我们可以改变相邻 \(4\) 个状态的奇偶性，而我们还有变化

\[ abcdef\to abcFED\to afCBED\to abcFED\to abcdef \]

此外，上述两者结合，我们只需要把一对需要该边奇列或偶列该边它们的奇偶性，所以答案就变成最终状态的奇数和偶上下颠倒的列个数的奇偶性，若都为偶数则合法，否则不合法

对于最终状态而言，我们只需要求出任意一个方案即可，因为对于一系列操作序列来看，都可以由上述两个操作通过类似于线性组合得到，而每次都是成对变化，不会影响奇偶性

对于求出任意一种可以满足顺序正确的交换方案来说，每次交换会使奇偶性相反数列的列个数奇偶性改变

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 <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 1e5+5;
int n, w[3][N], f[N], h[2];
int main()
{
    n = read();
    for(int i = 0; i < 3; ++i)
        for(int j = 1; j <= n; ++j) 
            w[i][j] = read();
    for(int i = 1; i <= n; ++i)
    {
        int a = w[0][i], b = w[1][i], c = w[2][i];
        if(abs(a-b) > 1||abs(b-c) > 1||b%3 != 2||(b%6&i&1)) return puts("No"), 0;
        f[i] = b/3+1, h[i&1] ^= a > c;
    }
    for(int i = 1; i <= n; ++i)
        while(f[i] != i) h[i&1^1] ^= 1, swap(f[i], f[f[i]]);
    puts(h[0]||h[1]?"No":"Yes");
    return 0;
}

Blackout

给定 \(n\times n\) 的网格，给定坐标序列，这些坐标序列的颜色为黑色，其余为白色，若存在 \((x,\ y)\) 和 \((y,\ z)\) 则会出现一个 \((z,\ x)\) 的黑点，求最终黑点数

很容易把题意转化为图论问题，一般图问题如果不知道怎么做就染色，我们把图染成 \(3\) 种颜色，若染色成功我们会发现不同颜色之间会有边相连，若染色不成功则会成为完全图，若每种颜色不全存在，则为各部分图的边数

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
#include <algorithm>
#include <cstring>
#include <cctype>
#include <cstdio>
using namespace std;
typedef long long int64;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 1e5+5;
struct Edge
{
    int next, to, w;
    Edge(int next = 0, int to = 0, int w = 0):next(next), to(to), w(w) {};
}edge[N<<1];
int tot, head[N];
void add(int x, int y, int z) { edge[++tot] = Edge(head[x], y, z); head[x] = tot; }
int n, m, c[N];
int64 ans, f[3], s;
bool color(int x, int col)
{   
    if(c[x]) return c[x] == col+1;   
    c[x] = col+1, ++f[col];
    bool ret = true;
    for(int i = head[x]; i; i = edge[i].next)
    {
        int y = edge[i].to, z = edge[i].w; s += z == 1;
        if(!color(y, col+z >= 3?col+z-3:col+z)) ret = false;
    }
    return ret;
}
int main()
{
    n = read(), m = read();
    for(int i = 1; i <= m; ++i)
    {
        int x = read(), y = read();
        add(x, y, 1), add(y, x, 2);
    }
    for(int x = 1; x <= n; ++x)
        if(!c[x])
        {
            s = f[0] = f[1] = f[2] = 0;
            if(!color(x, 1)) s = f[0]+f[1]+f[2], ans += s*s;
            else if(f[0]&&f[1]&&f[2]) ans += f[0]*f[1]+f[1]*f[2]+f[0]*f[2];
            else ans += s;
        }
    printf("%lld\n", ans);
    return 0;
}