Dreagonm's BLOG
0%

Codeforces Round#810 (Div. 2) 解题报告

发表于 分类于
CF1711 A-E题题解

A Perfect Permutation

题意简述

对于一个排列$P_{1\dots n}$，定义其权重为排列中满足$i$能够整除$P_i$的$i$的数量
输入n，构造一个长度为n的排列使其权重在所有长为n的排列中最小。
若有多解，任意输出。

思路

对于任意的$i$，$i\not=1$时，$i$均不能整除$i+1$，故很容易得出在$i$位置填$i\%n+1$这一种构造方法，该构造方法的权重为1，由于位置1一定会产生1的权重，故这样构造的排列权重最小。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
void work(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        printf("%d ",i+1);
    }
    printf("%d\n",1);
    return;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--)
        work();
    return 0;
}

B Party

题意简述

要举行一个派对，共有n个可以被邀请的成员，如果第i个人没有被邀请，则会产生$a_i$的不愉快值
这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
58
59
60
61
62
63
64
65
66
67
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define int long long
using namespace std;
int a[100100],d[100100];
vector<pair<int,int> > V;
void work(){
    memset(d,0,sizeof(d));
    V.clear();
    int n,m;
    int sum = 0;
    scanf("%lld %lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        sum += a[i];
    }
    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%lld %lld",&a,&b);
        d[a]++;
        d[b]++;
        V.push_back(make_pair(a,b));
    }
    int sumt = 0;
    for(int i=1;i<=n;i++){
        if(d[i]==0){
            sumt += a[i];
        }
    }
    long long minx2 = sum;
    for(int i=1;i<=m;i++){
        if(( d[V[i-1].first] + d[V[i-1].second] )%2 == 0){
            minx2 = min(minx2,a[V[i-1].first]+a[V[i-1].second]);
        }
    }
    long long minx = sum;
    int minans = 0;
    for(int i=1;i<=n;i++){
        if(d[i]%2==1 && a[i]<minx){
            minx = a[i];
            minans = i;
        }
    }
    if(m%2==0){
        printf("0\n");
        return;
    }
    else{
        if(minx == sum){
            printf("%lld\n",minx2);
        }
        else{
            int tmp = min(a[minans],minx2);
            printf("%lld\n",tmp);
        }
    }
}
signed main(){
    int T;
    scanf("%lld",&T);
    while(T--){
        work();
    }
    return 0;
}

C Color the Picture

题意简述

要对一个由$n \times m$个块组成的矩形涂色，总共有k种颜色，第i种颜色有$a_i$种。
当对矩形每个块，都有至少三个邻接块和该块同色时，认为这是一个合法矩形。

邻接块的定义是满足模n意义下，$y_1 = y_2 \wedge x_1 - x_2 \equiv 1$ 或 $x_1 = x_2 \wedge y_1 - y_2 \equiv 1$的两个方块。

思路

参照样例，容易得出结论。

将每种颜色排成宽至少两列的一个色带，能排成就说明可行。

由于宽两列的色带恰能使其中的每个方块都有三个邻接块同色，如果少于两列，可以证明至少有一个位置不合法。

对应模拟即可。

代码

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
int a[100100],b[100100];
bool cmp(int a,int b){
    return a>b;
}
bool Judge(int n,int m,int k){
    for(int i=1;i<=k;i++){
        b[i] = a[i];
        if(b[i] >= 1LL*n*m)
            return true;
    }
    bool has1 = 0;
    sort(b+1,b+k+1,cmp);
    int cur = 0;
    for(int i=1;i<=k;i++){
        int tmp = a[i] / n;
        if(tmp >= 2){
            if(tmp>2){
                has1 = 1;
            }
            cur += tmp;
        } 
    }
    if(m%2 == 0){
        if(cur >= m)
            return true;
        else
            return false;
    }
    else{
        if(cur >= m){
            if(has1){
                return true;
            }
            else{
                return false;
            }
        }
        else{
            return false;
        }
    }
}
void work(){
    int n,m,k;
    scanf("%lld %lld %lld",&n,&m,&k);
    for(int i=1;i<=k;i++){
        scanf("%lld",&a[i]);
    }
    printf("%s\n",(Judge(n,m,k)||Judge(m,n,k))?"Yes":"No");    
}
signed main(){
    int T;
    scanf("%lld",&T);
    while(T--){
        work();
    }
    return 0;
}

D Rain

题意简述

现在有n场大雨，第i场大雨中心在$x_i$，强度为$p_i$
第i场大雨在位置j的积水量是$max(0,p_i-|x_i-j|)$
如果某个位置积水量大于m，就会出现洪水。
询问对i从1到n，如果你能够移除第i次下雨，是否不会出现洪水。

思路

对于不是下雨中心的点。

如果其处于一个大雨的影响范围中，其积水量一定小于该大雨的中心点位置。

如果其处于两个大雨的影响范围当中，设两个大雨中心点之间区间的长度为$L$，区间中任一点的积水量都是$p_l+p_r-L$

更多的影响可以分拆成前两种情况。

故得到结论，某次大雨影响下的积水量极值点一定是某次降雨的中心点。

这样的关键点一共有$O(n)$个

对于每次降水，实际上是加上了一个一次函数。

可以利用差分维护一次函数的斜率和截距，求出所有关键点n次大雨后的积水量，设为$a$。

对于移除第i次积水，将绝对值去掉，得，

对于$[x_i-p_i,x_i]$的$j$点，影响是$a_j-p_i+x_i-j$，对$[x_i,x_i+p_i]$的$j$点，影响是$a_j-p_i+j-x_j$，

于是可以维护$a_j-j$，$a_j+j$，$a_j$的最大值，每次查询即可。

复杂度为$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
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
138
139
140
141
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
#define int long long
int x[200200],p[200200],x2[200200];
pair<int,int> rain[200200];
vector<pair<int,int> > a,b,a2,b2;
int n,m;
int ST1[200200][22],ST2[200200][22],ST3[200200][22]; // 2**21
int lg[200200];
void build(){
    lg[1] = 0;
    for(int i=2;i<=200000;i++)
        lg[i] = lg[i>>1] + 1;
    int tmpn = lg[n];
    for(int i=1;i<=tmpn;i++){
        for(int j=1;j<=n;j++){
            ST1[j][i] = max(ST1[j][i-1],ST1[min(j+(1<<(i-1)),n)][i-1]);
            ST2[j][i] = max(ST2[j][i-1],ST2[min(j+(1<<(i-1)),n)][i-1]);
            ST3[j][i] = max(ST3[j][i-1],ST3[min(j+(1<<(i-1)),n)][i-1]); 
        }
    }
}
const int INF = 0x3f3f3f3f3f3f3f3f;
int query1(int l,int r){
    if(r<l)
        return -INF;
    int tmp = lg[r-l+1];
    return max(ST1[l][tmp],ST1[max(1ll,r-(1<<tmp)+1)][tmp]);
}
int query2(int l,int r){
    if(r<l)
        return -INF;
    int tmp = lg[r-l+1];
    return max(ST2[l][tmp],ST2[max(1ll,r-(1<<tmp)+1)][tmp]);
}
int query3(int l,int r){
    if(r<l)
        return -INF;
    int tmp = lg[r-l+1];
    return max(ST3[l][tmp],ST3[max(1ll,r-(1<<tmp)+1)][tmp]);
}
 
void work(){
    a.clear();
    b.clear();
    a2.clear();
    b2.clear();
    scanf("%lld %lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld %lld",&x[i],&p[i]);
        x2[i] = x[i];
        rain[i] = make_pair(x[i],-INF);
    }
    for(int i=1;i<=n;i++){
        a.push_back(make_pair(x[i]-p[i],1));
        a.push_back(make_pair(x[i],0));
        a.push_back(make_pair(x[i]+1,-1));
        a.push_back(make_pair(x[i]+1,-1));
        a.push_back(make_pair(x[i]+p[i]+1,1));   
        b.push_back(make_pair(x[i]-p[i],-(x[i]-p[i])));
        b.push_back(make_pair(x[i],0));
        b.push_back(make_pair(x[i]+1,(x[i]-p[i])));
        b.push_back(make_pair(x[i]+1,(x[i]+p[i])));
        b.push_back(make_pair(x[i]+p[i]+1,-(x[i]+p[i])));      
    }
    // printf("Ok1\n");
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    sort(x2+1,x2+n+1);
    sort(rain+1,rain+n+1);
    int lst = -INF;
    for(int i=0;i<a.size();i++){
        if(a[i].first != lst){
            a2.push_back(make_pair(a[i].first,0));
            lst = a[i].first;
        }
        a2[a2.size()-1].second += a[i].second;
    }
    lst = -INF;
    for(int i=0;i<b.size();i++){
        if(b[i].first != lst){
            b2.push_back(make_pair(b[i].first,0));
            lst = b[i].first;
        }
        b2[b2.size()-1].second += b[i].second;
    }
    for(int i=1;i<a2.size();i++){
        a2[i].second += a2[i-1].second;
    }
    for(int i=1;i<b2.size();i++){
        b2[i].second += b2[i-1].second;
    }
    
    // printf("Ok2\n");
    for(int i=1;i<=n;i++){
        int pos = rain[i].first;
        int A = a2[lower_bound(a2.begin(),a2.end(),rain[i])-a2.begin()].second;
        int B = b2[lower_bound(b2.begin(),b2.end(),rain[i])-b2.begin()].second;
        int num = A*pos + B;
        ST1[i][0] = num-pos;
        ST2[i][0] = num+pos;
        ST3[i][0] = num;
    }
    build();
    // printf("Ok3\n");
    if(query3(1,n)<=m){
        for(int i=1;i<=n;i++){
            putchar('1');
        }
        putchar('\n');
    }
    else{
        
        // printf("Ok4\n");
        for(int i=1;i<=n;i++){
            int lbound = lower_bound(x2+1,x2+n+1,x[i]-p[i])-x2;
            // printf("Ok5\n");
            int rbound = upper_bound(x2+1,x2+n+1,x[i]+p[i])-x2-1;
            // printf("Ok6\n");
            int midbound = lower_bound(x2+1,x2+n+1,x[i])-x2;
            int tmp1 = query1(lbound,midbound)-p[i]+x[i];
            int tmp2 = query2(midbound,rbound)-p[i]-x[i];
            int tmp3 = max(query3(1,lbound-1),query3(rbound+1,n));
            if(max(max(tmp1,tmp2),tmp3) > m)
                putchar('0');
            else
                putchar('1');
        }
        putchar('\n');
    }
}
signed main(){
    int T;
    scanf("%lld",&T);
    while(T--)
        work();
    return 0;
}

E XOR Triangle

题意简述

输入n，求满足$0 \le a,b,c \le n$，且$a \oplus b, b \oplus c, c\oplus a$能够组成合法三角形的(a,b,c)三元组组数
模998244353

思路

令$a \oplus b = x,b \oplus c = y,a \oplus c = z$

合法三角形的条件$x+y \gt z$即$x+y \gt x\oplus y$，其他两个不等式同理。

考虑异或的过程是消去$x,y$相同的1，相加的过程相同的1没有被消去，所以$x+y \ge x \oplus y$，当x和y没有相同的1位时等号成立。

所以题目要求(a,b,c)三元组的个数，满足$a\oplus b$，$b\oplus c$，$c \oplus a$两两有相同的1即可。

利用类似数位dp的思路，common表示两两之间是否有相同的1，bound表示是否有上界约束，即可解决。

代码

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
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
char s[200200];
int dp[200200][8][8];
int n;
const int MOD = 998244353;
int dfs(int len,int bound,int common){
    // printf("%d %d %d\n",len,bound,common);
    if(len == n+1){
        return common==7;
    }
    if(dp[len][bound][common] != -1){
        return dp[len][bound][common];
    }
    int uppera=1,upperb=1,upperc=1;
    if(bound&1){ // bound a
        uppera = s[len] - '0';
    }
    if((bound>>1)&1){ // bound b
        upperb = s[len] - '0';
    }
    if((bound>>2)&1){ // bound c
        upperc = s[len] - '0';
    }
    int v = 0;
    for(int i=0;i<=uppera;i++){
        for(int j=0;j<=upperb;j++){
            for(int k=0;k<=upperc;k++){
                int tmpx = i^j;
                int tmpy = j^k;
                int tmpz = i^k;
                int tmpcommon = common;
                if(tmpx & tmpy) 
                    tmpcommon |= 4;
                if(tmpy & tmpz)
                    tmpcommon |= 2;
                if(tmpx & tmpz)
                    tmpcommon |= 1;
                int tmpbound = bound;
                if(i < s[len] - '0')
                    tmpbound &= 6;
                if(j < s[len] - '0')
                    tmpbound &= 5;
                if(k < s[len] - '0')
                    tmpbound &= 3;
                v = (v+dfs(len+1,tmpbound,tmpcommon))%MOD;
            }
        }
    }
    dp[len][bound][common] = v;
    return v;
}
int main(){
    scanf("%s",s+1);
    n = strlen(s+1);
    memset(dp,-1,sizeof(dp));
    printf("%d\n",dfs(1,7,0));
    return 0;
}