2020牛客国庆集训派对day7

字数统计: 1.2k字   |   阅读时长: 6分
训练题解
solved A B C D E F G H I J K
3 / 11 · O · · · · · · Ø O !
  • O：比赛时通过
  • Ø：赛后通过
  • !：比赛时尝试了未通过
  • ·：比赛时未尝试

比赛链接

B Abbreviation

solved by Sstee1XD. 1:55(+1)

题意 ： 找到一行字符串中连续数量大于1的，有且仅有首字母为大写，中间用一个空格分隔的单词组，将他们的首字母组合输出后，再用括号装饰原单词组后输出，其余不变输出。

题解 ： 每次check一整个单词，返回单词尾的位置，将符合条件的位置记录下来。

AC代码 
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
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;

int len, flag;
char s[211];
int l[200], r[200], f;
int check(int i) {
	if (!isalpha(s[i])) {
		flag = 0;
		return i;
	}
	if (!isupper(s[i])) flag = 0;
	else flag = 1;
	i++;
	int num = 0;
	while (isalpha(s[i]) && i < len) {
		if (isupper(s[i])) flag = 0;
		i++;
		num++;
	}
	if (!num) flag = 0;
	if (flag) r[f] = i - 1;
	
	return i;
}

int main() {
	while (gets(s)) {
		f = 0;
		len = strlen(s);
		flag = 0;
		for (int i = 0; i < len; ++i) {
			l[f] = i;
			i = check(i);
			int num = 0;
			while (flag) {
				if (i >= len || s[i] != ' ') break;
				i++;
				i = check(i);
				num+= flag;
			}
			if (num >= 1) f++;
		}
		int tmp = 0;
		for (int i = 0; i < len; ++i) {
			if (tmp < f && l[tmp] == i) {
				for (int j = l[tmp]; j <= r[tmp]; ++j) if(isupper(s[j])) printf("%c", s[j]);
				printf(" (");
				while (i <= r[tmp]) printf("%c", s[i++]);
				printf(")");
				i--;
				tmp++;
			}
			else printf("%c", s[i]);
		}
		puts("");
	}
	return 0;
}

I Bowlstack

题意 ： 给出n个碗个高度，底面圆半径和上底圆半径，求这n个碗堆在一起的最小高度。

题解 ： 因为给出的n最大只有9，所以可以暴力一下枚举每种情况，情况数最多只有9！次，所以不会超时。思路就是每次放置一个碗，计算这个碗底的高度，算到最后时再加上当前碗的高度。

AC代码 
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
#include<bits/stdc++.h>
using namespace std;    
const double pi = acos((double)(-1));
#define inf 0x3f3f3f3f
#define ll long long
#define eps 1e-10
const int maxn = 210;
const int mod = 1e9 + 7;
struct Wan {
    double h, r, R;
};
int flag = 0;
int t,n,id[15];
double high[15];
double getHigh(Wan A, Wan B) {
    if (A.r > B.R)
        return B.h;
    if (A.R < B.r)
        return 0;
    if ((A.R - A.r) * B.h <= (B.R - B.r) * A.h) {
        if (A.r <= B.r) return 0;
        return B.h * (A.r - B.r) / (B.R - B.r);
    }
    if (A.R > B.R)
        return max(0.0, B.h - A.h * (B.R - A.r) / (A.R - A.r));
    return max(0.0,B.h * (A.R - B.r) / (B.R - B.r) - A.h);
}
int p(Wan A,Wan B){
    if(B.r <= A.r && B.R <= A.R) flag = 1;
    return flag;
}
 
int main() {
    Wan a[10];
    cin>>t;
    int pre = 0;
    while(t--) {
        cin>>n;
        for(int i = 1; i <= n; i++) {cin>>a[i].h>>a[i].r>>a[i].R, id[i] = i;}
        double ans = inf,res = 0;
        do{
            res = 0;
            for(int i = 1; i <= n; i++){
                high[i] = 0;
                for(int j = 1; j < i; j++)
                    high[i] = max(high[i], high[j] + getHigh(a[id[i]],a[id[j]]));
                res = max(high[i] + a[id[i]].h,res);
            }
            ans = min(ans,res);
        }while(next_permutation(id + 1, id + 1 + n));
        cout<< (int)ans<<endl;
    }      
    return 0;
}

J Adjustment Office

题意： 有一个有n*n个单元格的正方形，每个单元的值为下标之和（x+y）。有q次询问，每次询问有两种央视“R r”和“C c”，分别表示询问第r行或第c列的总和，并将询问过的单元格的值清零。

AC代码 
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;

#define endl "\n"
#define dbg(x...)             \
    do {                      \
        cout << #x << " -> "; \
        err(x);               \
    } while (0)

void err() {	cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' ';
    err(args...);
}

inline int read() {
   int s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}

const int N = 1e6 + 10;
int n, q, k;
char c;
set<int> R, C;
ll Row, Col;
void run() {
	cin >> c >> k;
	if(c == 'R') {
		if(R.find(k) != R.end()) {
			cout << 0 << endl;
			return ;
		} else {
			ll ans = (ll)(1 + n + 2 * k) * n / 2;
			ans -= (ll)(Col + C.size() * k);
			cout << ans << endl;
			Row += k;
			R.insert(k);
		}
	} else {
		if(C.find(k) != C.end()) {
			cout << 0 << endl;
			return ;
		} else {
			ll ans = (ll)(1 + n + 2 * k) * n / 2;
			ans -= (ll)(Row + R.size() * k);
			cout << ans << endl;
			Col += k;
			C.insert(k);
		}
	}
}

int main() {
	ios :: sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin >> n >> q;
	while(q--) run();
	return 0;
}
文章目录
  1. B Abbreviation
  2. I Bowlstack
  3. J Adjustment Office
|