Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

CF题目乱做

Posted on Edited on

这段时间天天降智，于是开始刷CF了。

CF1710A Color the Picture

伞兵构造。

不难发现可行的图形的颜色块一定是矩形，对于所有颜色放置的底边是$n$还是$m$进行分类讨论，直接算即可。

贴一下代码，之前vp挂惨了。

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
#include<bits/stdc++.h>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0; bool flag = 0;
    char c = getchar();
    while('0' > c || c > '9') { if(c == '-') flag = 1; c = getchar();}
    while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if(flag) res = -res;
}
template <class T, class ...Arg>
inline void read(T &res, Arg &...com){ read(res), read(com...);}
template <class T>
void out(T res)
{
    if(res > 9) out(res / 10);
    putchar(res % 10 + '0');
}
template <class T>
inline void write(T res)
{
    if(res < 0) putchar('-'), res = -res;
    out(res), putchar('\n');
}
const int N = 1e5 + 5;
int n, m, k, T;
int a[N], b[N];
inline bool check1(int n, int m)
{
    if(n > m) swap(n, m);
    queue<int> q;
    for(int i = k, cnt;i >= 1;i --)
    {
        cnt = a[i] / n;
        if(cnt == 1) cnt = 0;
        q.push(cnt);
    }
    int u = 0, ans = 0;
    while(!q.empty())
    {
        u += 2;
        ans += q.front(), q.pop();
        if(ans >= m && u <= m) return true;
    }
    return false;
}
inline bool check2(int n, int m)
{
    if(n < m) swap(n, m);
    queue<int> q;
    for(int i = k, cnt;i >= 1;i --)
    {
        cnt = a[i] / n;
        if(cnt == 1) cnt = 0;
        q.push(cnt);
    }
    int u = 0, ans = 0;
    while(!q.empty())
    {
        u += 2;
        ans += q.front(), q.pop();
        if(ans >= m && u <= m) return true;
    }
    return false;
}
inline void work()
{
    read(n, m, k);
    for(int i = 1;i <= k;i ++) read(a[i]);
    sort(a + 1, a + k + 1);
    if(!check1(n, m) && !check2(n, m)) return puts("No"), void();
    puts("Yes");
}
signed main()
{
    read(T);
    while(T --) work();
    return 0;
}

CF1710B rain

离散化，数学。

神秘题（没见过），首先有一个结论：水量最大的点一定是降雨点。

证明： 对于任意相邻的降雨点$x,y ,\ x < y$，对于他们之间的任意点$pos$，显然$pos$水量最大时$x$和$y$都必须要对$pos$有贡献，那么：
$$
val_{pos}=val[x] - pos + x + val[y] + y - pos = val[x] + val[y] + y - x
$$
显然等于降雨点的水量。

于是我们考虑首先处理出所有降雨点的水量，降雨的式子是个一次函数，我们考虑用差分来计算，最后考虑如何验证每个点，我们考虑转化，我们重新定义一张图，这张图上的所有点的水量都是$m$，我们在原图上撤去降雨就等价于在新图上降水，而当新图和$x$轴所形成的图形可以完全将原图和$x$轴形成的图形覆盖掉，则撤去这个点就是合法的，否则不行。

然后我们考虑几何法，将图形画出来时，可以发现每个最高点到左右的两条线的斜率的绝对值都是$1$，所以我们用截距表示点，预处理出原图的截距的并的范围，如果新图的截距的范围覆盖了原图，则可行，反之不行。

注：计算原图截距的并的时候只用计算点值大于$m$的，正确性显然。

复杂度：$O(n \log n)$，瓶颈在离散化上。

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
#include<bits/stdc++.h>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0; bool flag = 0;
    char c = getchar();
    while('0' > c || c > '9') { if(c == '-') flag = 1; c = getchar();}
    while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if(flag) res = -res;
}
template <class T, class ...Arg>
inline void read(T &res, Arg &...com){ read(res), read(com...);}
template <class T>
void out(T res)
{
    if(res > 9) out(res / 10);
    putchar(res % 10 + '0');
}
template <class T>
inline void write(T res)
{
    if(res < 0) putchar('-'), res = -res;
    out(res);
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(const char *s){ while(*s) putchar(*s ++); } 
template <class T, class ...ARC>
inline void write(T res, ARC ...com) { write(res), write(com...); }
const int N = 2e5 + 5;
const LL Inf = 1e18;
int n, m;
map<int, LL> mp;
LL p[N], x[N];
inline void work()
{
    mp.clear();
    read(n, m);
    for(int i = 1;i <= n;i ++) 
    {
        read(x[i], p[i]);
        mp[x[i] - p[i] + 1] ++;
        mp[x[i] + 1] -= 2;
        mp[x[i] + p[i] + 1] ++;
    }
    LL last = 0, cnt = 0, tot = 0, maxn1 = -Inf, maxn2 = -Inf;
    for(auto iter: mp)
    {
        cnt += tot * (iter.first - last);
        tot += iter.second;
        if(cnt > m)
        {
            maxn1 = max(maxn1, cnt - iter.first + 1);
            maxn2 = max(maxn2, cnt + iter.first - 1); // 前面的坐标都加1了，所以这里要减掉
        }
        last = iter.first;
    }
    for(int i = 1;i <= n;i ++)
        write((maxn1 <= m + p[i] - x[i]) && (maxn2 <= m + p[i] + x[i]));
    write('\n');
}
int T;
int main()
{
    read(T);
    while(T --) work();
    return 0;
}

CF1710C XOR Triangle

数位dp，数学。

直接记录此时满足三边都行即可。

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
#include<bits/stdc++.h>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0; bool flag = 0;
    char c = getchar();
    while('0' > c || c > '9') { if(c == '-') flag = 1; c = getchar();}
    while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if(flag) res = -res;
}
template <class T, class ...Arg>
inline void read(T &res, Arg &...com){ read(res), read(com...);}
template <class T>
void out(T res)
{
    if(res > 9) out(res / 10);
    putchar(res % 10 + '0');
}
template <class T>
inline void write(T res)
{
    if(res < 0) putchar('-'), res = -res;
    out(res);
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(const char *s){ while(*s) putchar(*s ++); } 
template <class T, class ...ARC>
inline void write(T res, ARC ...com) { write(res), write(com...); }
const int N = 2e5 + 5, mod = 998244353;
int n, a[N];
char c[N];
int f[N][2][2][2][2][2][2];
int dfs(int pos, int flag1, int flag2, int flag3, int x, int y, int z)
{
    if(!pos) return x && y && z;
    if(f[pos][flag1][flag2][flag3][x][y][z] != -1) return f[pos][flag1][flag2][flag3][x][y][z];
    int res = 0;
    for(int i = 0;i <= (flag1 ? a[pos] : 1);i ++)
        for(int j = 0;j <= (flag2 ? a[pos] : 1);j ++)
            for(int k = 0;k <= (flag3 ? a[pos] : 1);k ++)
            {
                res = (res + dfs(pos - 1, flag1 && (i == a[pos]), flag2 && (j == a[pos]), flag3 && (k == a[pos]), x | ((j ^ k) + (i ^ k) > (j ^ i)), y | ((j ^ i) + (j ^ k) > (i ^ k)), z | ((i ^ k) + (i ^ j) > (j ^ k)))) % mod;
            }
    return f[pos][flag1][flag2][flag3][x][y][z] = res;
}
int main()
{
    scanf("%s", c + 1);
    n = strlen(c + 1);
    reverse(c + 1, c + n + 1);
    for(int i = 1;i <= n;i ++) a[i] = c[i] - '0';
    memset(f, -1, sizeof(f));
    write(dfs(n, 1, 1, 1, 0, 0, 0));
    return 0;
}

CF1628C Grid Xor

比较牛逼的构造题，首先猜想每个a[i][j]对b的异或值只可能贡献，或者非贡献（意思是不可能出现别的值），我们强行构造这样一种矩阵，记c[i][j]为a[i][j]是否贡献，那么由于a[i][j]是由四周贡献来的，所以c[i][j]^c[i-2][j]^c[i-1][j-1]^c[i-1][j+1]=1（a[i][j]一定存在），对于第一行的话由于这是强行构造的，所以直接全赋一就行了。

CF1679A AvtoBus

垃圾题，分讨即可（还爆了两发罚时，菜成狗了）。

CF1679D Toss a Coin to Your Graph

二分，之后验证即可（看来实力也就CF2000左右了）。