2019牛客暑期多校训练营第七场
2019-08-09 / Luo Jinrong   

进度

A B C D E F G H I J K
√ √ √ √ ∅ √

A. String

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define per(i,a,n) for (int i=a;i<n;i++)
#define rep(i,a,n) for (int i=n-1;i>=a;i--)
const int MAXN(2e3+7);
 
int T;
string str;
int len;
int strp[MAXN], endp[MAXN], znm[MAXN], onm[MAXN];
int cntt;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> T;
    while(T--) {
        cin >> str;
        cntt = 0;
        len = str.length();
        per(i, 0, len) {
            if (str[i] == '0') {
                int j = i;
                strp[cntt] = i;
                while (j < len) {
                    if (str[j] == '0') j++;
                    else break;
                }
                if (j == len) {
                    endp[cntt] = j;
                    znm[cntt] = j - i;
                    onm[cntt] = 0;
                    cntt++;
                    i = j - 1;
                } else {
                    znm[cntt] = j - i;
                    while (j < len) {
                        if (str[j] == '1') j++;
                        else break;
                    }
                    endp[cntt] = j;
                    onm[cntt] = j - i - znm[cntt];
                    cntt++;
                    i = j - 1;
                }
            } else {
                int j = i;
                znm[cntt] = 0;
                strp[cntt] = i;
                while (j < len) {
                    if (str[j] == '1') j++;
                    else break;
                }
                onm[cntt] = j - i;
                endp[cntt] = j;
                cntt++;
                i = j - 1;
            }
        }
        per(i, 0, cntt) {
            int flag0=0;
            rep(j, i, cntt) {
                string ptr = str.substr(strp[i], endp[j] - strp[i]);
                string tmp;
                int flag1 = 1;
                per(k, i + 1, j + 1) {
                    tmp = str.substr(strp[k], endp[j] - strp[k]) + str.substr(strp[i], strp[k] - strp[i]);
                    if (tmp < ptr) {
                        flag1 = 0;
                        break;
                    }
                }
                if (flag1) {
                    cout << str.substr(strp[i], endp[j]-strp[i]) << ' ';
                    i = j;
                    break;
                }
            }
        }
        cout << '\n';
    }
 
    return 0;
}

B. Irreducible Polynomial

题意

一个n次多项式，判断其能否在实数范围内因式分解，能分解输出No，否则为Yes。

做法

当n>=3时一定是可以分解的，当n<2时一定是不可以分解的，这时候只要判断n=2的情况，这个时候只需要判断$\delta =b^2-4ac$，如果小于零就不能分解，否则就能分解。

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
#include<bits/stdc++.h>
#define FIN freopen("./B.in","r",stdin)
using namespace std;
typedef long long ll;
const ll maxn(1e2+5);
ll T,n,a[maxn],g;
int main(){
#ifndef ONLINE_JUDGE
	FIN;
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	for(int t=1;t<=T;t++){
		cin>>n;
		for(ll i=1;i<=n+1;i++){
			cin>>a[i];
		}
		if(n>2){
			cout<<"No\n";
		}else if(n<2){
			cout<<"Yes\n";
		}else{
			if(a[2]*a[2]-4*a[1]*a[3]<0){
				cout<<"Yes\n";
			}else{
				cout<<"No\n";
			}
		}
	}
}

C. Governing sand

题意

有n种树，每种树有一个数量p，高度h，砍树花费c。要使高度最高的树的数量严格大于所有树的一半，问砍树的最小花费。

做法

先按树的高度从大到小排序，选择一个树作为高度最高的树（可能有别的树跟他高度一样，也保留），首先要把比这个高度高的树全部砍掉，然后在根据这个高度树的数量确定还需要再砍多少树，因为价格在1-200之间，我们可以根据花费记录比这个高度低的树的数量，然后慢慢从花费最小的开始砍，知道满足要求为止。

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>
using namespace std;
typedef long long ll;
#define per(i,a,n) for (int i=a;i<n;i++)
#define rep(i,a,n) for (int i=n-1;i>=a;i--)
const int MAXN(1e5+7);
 
int T;
struct nd{
    ll H, C, P;
}Tr[MAXN];
int n;
ll sumC[400];
ll outt, nowcost, precost, sumP, nowP;
int l1, r1;
ll shdbecut;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    while(cin >> n) {
        sumP = 0;
        outt = 2e18+7;
        per(i, 1, 201) sumC[i]=0;
        per(i, 0, n) {
            cin >> Tr[i].H >> Tr[i].C >> Tr[i].P;
            sumC[Tr[i].C]+=Tr[i].P;
            sumP += Tr[i].P;
        }
        sort(Tr, Tr+n, [](const nd& a, const nd& b) { return a.H>b.H; });
        l1 = r1 = 0;
        precost = 0;
        while(l1<n) {
            nowP = 0;
            nowcost = precost;
            while(r1<n && Tr[r1].H==Tr[l1].H) { nowP+=Tr[r1].P; sumC[Tr[r1].C]-=Tr[r1].P; r1++; }
            sumP -= nowP;
            shdbecut = sumP-nowP+1;
            if(shdbecut>0) {
                per(i, 1, 201) {
                    if (sumC[i] < shdbecut) {
                        nowcost += sumC[i] * i;
                        shdbecut -= sumC[i];
                    } else {
                        nowcost += shdbecut * i;
                        break;
                    }
                }
            }
            outt = min(outt, nowcost);
            while(l1<r1) {precost+=Tr[l1].C*Tr[l1].P;l1++;}
        }
        cout << outt << '\n';
    }
 
    return 0;
}

D. Number

题意

给两个整数n，p，找到一个n位的p的倍数。找不到输出T_T。

做法

首先判断p的位数，如果比n大则找不到，否则先输出p，再往后补0直到有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
#include<bits/stdc++.h>
#define FIN freopen("./D.in","r",stdin)
using namespace std;
typedef long long ll;
const ll maxn(1e5+5);
ll p_t,p,n,len;
int main(){
#ifndef ONLINE_JUDGE
	FIN;
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>p;
    p_t=p;
	while(p_t){
		p_t/=10;
		len++;
	}
	if(n<len){
		cout<<"T_T\n";
	}else{
		cout<<p;
		for(int i=len;i<n;i++){
			cout<<0;
		}
		cout<<"\n";
	}
}

E. Find the median

题意

有N次操作，每次操作往数列里加入l-r的数，每次求这个数列的中位数（长度为奇数时取中间的，否则取中间两个数的最小值）。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define per(i,a,n) for (int i=a;i<n;i++)
#define rep(i,a,n) for (int i=n-1;i>=a;i--)
const int MAXN(5e6+7);
 
int N;
ll X[MAXN], Y[MAXN], A1,B1,C1,M1,A2,B2,C2,M2;
struct nd{
    ll L, R;
}ope[MAXN];
ll qp[2*MAXN];
ll lnm[2*MAXN];
int cntt=9;
 
ll ans[MAXN << 2], lazy[MAXN << 2];
inline void PushUp(int rt) {
    ans[rt] = ans[rt << 1] + ans[rt << 1 | 1];
}
inline void Build(int l, int r, int rt) {
    if (l == r) {
        ans[rt] = 0;
        return;
    }
    int mid = (l + r) >> 1;
    Build(l, mid, rt << 1);
    Build(mid + 1, r, rt << 1 | 1);
    PushUp(rt);
}
inline void PushDown(int rt, ll ln, ll rn) {
    if (lazy[rt]) {
        lazy[rt << 1] += lazy[rt];
        lazy[rt << 1 | 1] += lazy[rt];
        ans[rt << 1] += lazy[rt] * ln;
        ans[rt << 1 | 1] += lazy[rt] * rn;
        lazy[rt] = 0;
    }
}
inline void Update(int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R) {
        ans[rt] += (qp[r+1] - qp[l]);
        lazy[rt] ++;
        return;
    }
    int mid = (l + r) >> 1;
    PushDown(rt, qp[mid+1] - qp[l], qp[r+1] - qp[mid+1]);
    if (L <= mid) { Update(L, R, l, mid, rt << 1); }
    if (R > mid) { Update(L, R, mid + 1, r, rt << 1 | 1); }
    PushUp(rt);
}
inline ll Query(ll C, int l, int r, int rt) {   //查询第C个数字
    if(l==r) {
        C = (C-1)/(ans[rt]/(qp[l+1]-qp[l]))+1;
        return qp[l]+C-1;
    }
    int mid = (l + r) >> 1;
    PushDown(rt, qp[mid+1] - qp[l], qp[r+1] - qp[mid+1]);
    if (C <= ans[rt<<1]) { return Query(C, l, mid, rt << 1); }
    else { return Query(C-ans[rt<<1], mid + 1, r, rt << 1 | 1); }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    //input+离散化
    cin >> N;
    cin >> X[1] >> X[2] >> A1 >> B1 >> C1 >> M1 >> Y[1] >> Y[2] >> A2 >> B2 >> C2 >> M2;
    ope[1].L = min(X[1], Y[1])+1; ope[1].R = max(X[1], Y[1])+1;
    ope[2].L = min(X[2], Y[2])+1; ope[2].R = max(X[2], Y[2])+1;
    qp[1] = ope[1].L; qp[2] = ope[1].R; qp[3] = ope[2].L; qp[4] = ope[2].R;
    qp[5] = ope[1].L+1; qp[6] = ope[1].R+1; qp[7] = ope[2].L+1; qp[8] = ope[2].R+1;
    per(i, 3, N+1) {
        X[i] = (A1*X[i-1]%M1 + B1*X[i-2]%M1 + C1)%M1;
        Y[i] = (A2*Y[i-1]%M2 + B2*Y[i-2]%M2 + C2)%M2;
        ope[i].L = min(X[i], Y[i])+1;
        ope[i].R = max(X[i], Y[i])+1;
        qp[cntt++] = ope[i].L;
        qp[cntt++] = ope[i].L+1;
        qp[cntt++] = ope[i].R;
        qp[cntt++] = ope[i].R+1;
    }
    sort(qp+1, qp+cntt);
    cntt = unique(qp+1, qp+cntt)-qp;
    //end
 
    //映射
    per(i, 1, cntt) { lnm[i] = qp[i+1]-qp[i]; }     //[qp[i-1], qp[i]), 最后加一段 [qp[cntt-1], qp[cntt-1]+1)
    per(i, 1, N+1) {
        ope[i].L = lower_bound(qp, qp+cntt, ope[i].L)-qp;
        ope[i].R = lower_bound(qp, qp+cntt, ope[i].R)-qp;
    }
    //end
 
    //建树
    cntt--;
    ll sumpt=0;
    Build(1, cntt, 1);
    per(i, 1, N+1) {
        sumpt += (qp[ope[i].R+1]-qp[ope[i].L]);
        Update(ope[i].L, ope[i].R, 1, cntt, 1);
        cout << Query((sumpt+1)/2, 1, cntt, 1) << endl;
    }
 
    return 0;
}

J. A+B problem

题意

给两个数A，B，将A，B反转再相加再反转输出。

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
#include<bits/stdc++.h>
#define FIN freopen("./J.in","r",stdin)
using namespace std;
typedef long long ll;
const ll maxn(1e5+5);
ll T,a,b,ra,rb,ans,rans;
int main(){
#ifndef ONLINE_JUDGE
	FIN;
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	for(int t=1;t<=T;t++){
		ra=rb=rans=0;
		cin>>a>>b;
		while(a){
			ra=ra*10+a%10;
			a/=10;
		}
		while(b){
			rb=rb*10+b%10;
			b/=10;
		}
		ans=ra+rb;
		while(ans){
			rans=rans*10+ans%10;
			ans/=10;
		}
		cout<<rans<<"\n";
	}
}

return 0;

本文链接：
https://luojinrong.github.io/2019/08/09/2019牛客暑期多校训练营第七场/