Codeforces Round#602(Div 2)解题报告

ACM 阅读量

依旧是赛后补题的一场，依旧是舔我超哥的一天，感谢 $qsc$ 的视频讲解，与他的算法讲堂！

题目链接

A.Math Problem

题意

给你 $n$ 个线段，让你找到一个最短的线段使得该线段与输入的所有线段均有交点

题解

维护一个 $L$,$R$。分别代表找到的线段最左端能到哪里,以及该线段最右端的最小值
即

  • $L = min(L,r)$
  • $R = max(R,l)$

描述不清，很好理解吧

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5+7;
const int INF = 0x3f3f3f3f;
int main(){
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        int L = INF,R = 0;
        for(int i = 1;i <= n;i++){
            int l,r;
            cin >> l >> r;
            L = min(L,r);
            R = max(R,l);
        }
        if(n == 1)
        	cout << 0 << endl;
        else
        	cout << max(R - L,0) << endl;
    }
    return 0;
}

B.Box

题意

给你一个 $n$ 代表有 $1$ 到 $n$ 个数，给你一个长为 $n$ 的序列， $a[i] = max(a[i]~a[1])$,问能否构造出来一个序列满足题中给的前缀最大值序列(不包括 $0$)。

题解

第一遍没想到，想到了裸的暴力，一直 $T$，我真菜。后来被提醒，可以直接从小到大开始填，如果这个数没填过，就直接填进去，否则从小往大找一个能填的即可。可是我还是一直 $T$，不知道为何，把 $cin,cout,vector$ 都去掉了才过，可能写的是真丑吧

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e6+7;
int a[MAXN],vis[MAXN];
int ans[MAXN];
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,cnt = 0;
        scanf("%d",&n);
        for(int i = 1;i <= n;i++)
            scanf("%d",&a[i]);
		int mi = 1;
        bool flag = false;
        for(int i = 1;i <= n;i++){
        	if(!vis[a[i]])
				ans[++cnt] = a[i];
			else {
				if(mi < a[i]){
					ans[++cnt] = mi;
				} else {
					flag  = true;
					break;
				}
			}
			vis[ans[cnt]] = 1;
			while(vis[mi]) mi++;
            
        }
        if(flag)
            printf("-1");
        else
            for(int i = 1;i <= n;i++)
                printf("%d ",ans[i]);
        printf("\n");
        for(int i = 1;i <= n;i++)
            vis[i] = 0;
    }
    return 0;
}

C.Messy

题意

给你一个长为 $n$ (保证偶数)的字符串只包含 $($ 与 $)$，你可以执行 不超过$n$次 的区间翻转即对 $[l…r]$ 翻转，则变成 $[r…l]$，问你能否构造一个序列使得，字符串的所有前缀中只包含 $k$ 个正则表达式的括号。输出翻转的次数与每次翻转的位置。注意只要小于 $n$ 即可，不需要最小。题目保证有解。

正则表达式括号: $()$, $(())$,诸如此类。

题解

他能翻转 $n$ 次意味着，可以得到这个字串的任何形式，至此开始构造。先 构造$k-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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int MAXN = 1e6+7;
vector<P> ans;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(false),cout.tie(false);
    int T;
    cin >> T;
    while(T--){
    	string s,ans_s;
        int n,k;
        cin >> n >> k;
        cin >> s;
        int len = s.size();
        for(int i = 0;i < k-1;i++)
            ans_s += "()";
        int len1 = len - ans_s.size();
        
        for(int i = 0;i < len1/2;i++)
            ans_s += "(";
        for(int i = 0; i < len1/2;i++)
            ans_s += ")";
        for(int i = 0;i < len;i++){
            if(ans_s[i] != s[i]){
                for(int j = i+1;j < len;j++){
                    if(ans_s[i] == s[j]){
                        int x = i,y = j;
                        while(x < y){
                            swap(s[x],s[y]);
                            x++,y--;
                        }
                        ans.push_back(P(i+1,j+1));
                        break;
                    }
                }
            }
        }
        int sz = ans.size();
        cout << sz << '\n';
        for(int i = 0;i < sz;i++){
            cout << ans[i].first << " " << ans[i].second << '\n';
        }
        ans.clear();
    }
    return 0;
}

D.Optimal Subsequences

题意

给定一个长度为 $n$ 的数组，$m$ 次询问，每次询问一个 $k$,一个 $pos$ ，代表在原序列中找到一个长为 $k$ 的子序列，使得这个子序列的和是所有长为 $k$ 的子序列中最大的，如果有和相同的，则选择字典序最小的，然后输出这个子序列的第 $pos$ 位置的值。

题解

D1数据范围100，可以直接贪心暴力。

首先对原序列进行排序，因为要取和最大，可以优先按照值排序，值相同的按照字典序排序。

线段树的解法:
对询问进行离线处理。针对每一个询问有一个规律， $k = i$ 一定是由 $k = i-1$ 得到的，由此我们可以对询问进行排序，按照 $k$ 由小到大进行排序，然后建立权值线段树，维护原序列的坐标，然后二分线段树的边界，找到 $1-K$ 中能包含 $pos$ 个数的最大右边界。
具体看代码把，表达能力不清，难搞

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 7;
const int INF = 0x3f3f3f3f;
int n,m,ans[MAXN];
struct Node{
    int l,r,val;
    int mid(){
        return (l + r) >> 1;
    }
}tree[MAXN << 2];

struct Ans{
    int val,id;
}a[MAXN],b[MAXN];

struct node{
    int k,pos,id;
}q[MAXN];

void PushUp(int rt){
    tree[rt].val = tree[rt << 1].val + tree[rt << 1|1].val;
}

void Build(int l,int r,int rt){
    tree[rt].l = l,tree[rt].r = r;
    if(l == r){
        return ;
    }
    int mid = tree[rt].mid();
    Build(l,mid,rt << 1);
    Build(mid+1,r,rt << 1|1);
    PushUp(rt);
}

void Update(int rt,int pos){
    if(pos == tree[rt].l && pos == tree[rt].r){
        tree[rt].val++;
        return ;
    }
    int mid = tree[rt].mid();
    if(pos <= mid){
        Update(rt << 1,pos);
    } else {
        Update(rt << 1|1,pos);
    }
    PushUp(rt);
}

int Query(int rt,int pos){
    if(pos >= tree[rt].r)
        return tree[rt].val;
    int mid = tree[rt].mid();
    int ret = 0;
    ret += Query(rt << 1,pos);
    if(pos > mid)
        ret += Query(rt << 1|1,pos);
    return ret;
}

bool cmp1(Ans aa,Ans bb){
    if(aa.val != bb.val)
        return aa.val > bb.val;
    return aa.id < bb.id;
}

bool cmp2(node aa,node bb){
    return aa.k < bb.k;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    cin >> n;
    Build(1,n,1); 
    for(int i = 1;i <= n;i++){
        cin >> a[i].val;
        a[i].id = i;
        b[i] = a[i];
    }
    sort(b+1,b+1+n,cmp1); //贪心排序
    cin >> m;
    for(int i = 1;i <= m;i++){ //对询问进行离线处理
        cin >> q[i].k >> q[i].pos;
        q[i].id = i;
    }
    sort(q+1,q+1+m,cmp2);
    int now = 1;
    for(int i = 1;i <= m;i++){
        for(int j = now;j <= q[i].k;j++)
            Update(1,b[j].id);
        now = q[i].k + 1;
        int l = 1,r = n,tk;
        while(l <= r){ //二分确定最小的包含区间
            int mid = (l + r) >> 1;
            if(Query(1,mid) < q[i].pos)
                l = mid+1;
            else {
                r = mid - 1;
                tk = mid;
            }
        }
        ans[q[i].id] = a[tk].val;
    }
    for(int i = 1;i <= m;i++)
        cout << ans[i] << endl;
    return 0;
}

主席树解法：
貌似和权值线段树一样，维护的是区间下标第 $k$ 小，加上贪心的排序即可

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
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
vector<int>v;
struct node {
    int l,r,s;
} t[N*40];
int rt[N],cnt;
void update(int l,int r,int x,int &y,int pos) {
    y=++cnt;
    t[y]=t[x];
    t[y].s++;
    if(l==r)
        return;
    int m=(l+r)>>1;
    if(pos<=m)
        update(l,m,t[x].l,t[y].l,pos);
    else
        update(m+1,r,t[x].r,t[y].r,pos);
}
int query(int l,int r,int x,int y,int num) {
    if(l==r)
        return l;
    int sum=t[t[y].l].s-t[t[x].l].s;
    int m=(l+r)>>1;
    if(sum>=num)
        return query(l,m,t[x].l,t[y].l,num);
    else
        return query(m+1,r,t[x].r,t[y].r,num-sum);
}
struct Node{
    int x,id;
}a[N],b[N];
map<int,int> M;
bool cmp1(Node aa,Node bb){
    if(aa.x != bb.x)
        return aa.x > bb.x;
    return aa.id < bb.id;
}

int main() {
    int n,m;
    int x,l,r;
    scanf("%d",&n);
    for(int i=1; i<=n; ++i){
        scanf("%d",&a[i].x);
        a[i].id = i;
        b[i] = a[i];
        M[i] = a[i].x;
    }
    sort(b+1,b+1+n,cmp1);
    for(int i=1; i<=n; ++i)
        update(1,n,rt[i-1],rt[i],b[i].id);
    cin >> m;
    for(int i=1; i<=m; ++i) {
        int k,pos;
        cin >> k >> pos;
        int tt = query(1,n,rt[0],rt[k],pos);
        printf("%d\n",M[tt]);
    }
    return 0;
}

E.Arson In Berland Forest

待补

F.Wrong Answer on test 233

题意

给定一个由 $n$ 道题的试卷，每个题由 $k$ 个选项，接着给你 $n$ 个数代表，每道题的正确答案。判题机器有些问题，会把你选择的答案都往前进 $1$ 个位置 如果是第 $n$ 个题则到 第$1$道题。问你有多少种组合方式使得，经过机器错误读入后比错误读入前能多得分的序列个数。

题解

面向题解解题

设 $dp[i][j]$ 代表第 $i$ 个题在交换后得到 $j$ 分的可能。
如果 $h[i] == h[i+1]$ 可以得出，这个题经过交换后，他的分值不变，因为由 $K$ 个选项，任意选则，所以状态转移方程为

dp[i][j] = dp[i-1][j] * k;

如果 $h[i] != h[i+1]$ 分为三种情况

  1. 改前对，改后错
  2. 改前错，改后对
  3. 同对或同错，分值不变

对于前两种情况，只有固定的一种选项，对于最后一种则由 $(k-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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 4005;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
ll n,k,h[MAXN];
ll dp[2005][4005];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    cin >> n >> k;
    for(int i = 1;i <= n;i++)
        cin >> h[i];
    dp[0][2001] = 1;
    for(int i = 1;i <= n;i++){
       for(int j = 1;j <= 4001;j++){
            if(h[i] == h[i%n+1])
                dp[i][j] = dp[i-1][j] * k % mod;
            else
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1] + dp[i-1][j]* (k-2)) % mod;
       		//printf("%d %d %lld\n",i,j,dp[i][j]);
	   }
    }
    ll ans = 0;
    for(int i = 1;i <= n;i++)
        ans = (ans + dp[n][2001+i]) % mod;
    cout << ans << endl;
    return 0;
}

F2 脑子不够了！！！

有问题欢迎联系:QQ:2112370160 ！

Powered by Hexo and Hexo-theme-hiker

Copyright © 2018 - 2020 Never Give Up! All Rights Reserved.

访客数 : | 访问量 :