第十七届中国计量大学程序设计竞赛（同步赛）

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

总结：

  • 第一次满员一起打比赛，也还没什么配合，还没有特别明确的分工，就是谁先读懂题意谁先来做。
  • 不要只有一个人懂某块知识。当队友在某道题陷进去之后，需要另一个人来帮忙debug或者是提供测试数据都行，千万别让他一个人陷进去出不来。
  • K题。这个单独写出来，实在是因为温哥哥做太久了，留给温哥哥自己反思。

比赛链接

A A Party for You Started

solved by Sstee1XD

题意： 给你一棵树，每次操作先询问单点权值，然后增加一点权值，同时它所有的子节点也增加相同的权值。

题解： 看题意很容易想到单点修改，区间求和或者区间修改，查询单点问题。为了把节点和它的子节点放在一个区间内，要用dfs序去处理。当时写了一个树状数组去区间求和，比较麻烦。赛后发现区间修改，查询单点简单很多，可以用线段树写。这里以树状数组维护差分数组，查询单点为例。

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>
#define bug cout << "bug********************************\n"

using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-7;
const int maxn = 2e4 + 7;

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;
}

int n, m, fa, num, rt;
vector<int> G[maxn];
int id[maxn], to[maxn];
ll sum[maxn];
int lowbit(int x) {
	return x & -x;
}

void add(int i, ll x) {
	while (i <= n) {
		sum[i] += x;
		i += lowbit(i);
	}
}

ll query(int i) {
	ll res = 0;
	while (i > 0) {
		res += sum[i];
		i -= lowbit(i);
	}
	return res;
}

void dfs(int u, int fa) {
	id[u] = ++num;
	for (auto v : G[u]) {
    if (v != fa) dfs(v, u);
	}
  to[u] = num;
}

void run(){
	for (int i = 1;i <= n; ++i) {
		fa = read();
		G[fa].push_back(i);
	}
	rt = G[0][0];
	dfs(rt, -1);
	int u, v;
	ll x;
	while (m--) {
		scanf("%d %lld %d", &u, &x, &v);
		printf("%lld\n", query(id[v]));
		add(id[u], x);
    	add(to[u] + 1, -x);
	}
}

int main(){
	n = read();
	m = read();
	run();
	return 0;
}

B Broken Pad

solved by lllllan

题意： 每组数据含有两个数组a、b，数组由0和1组成。要求你通过一些翻转使得数组a变成数组b。操作要求为：当翻转第i个数字的时候，第i以及他之后的所有数字都将由1变成0或由0变成1。特别的，可以在第一步时，将整个数组重置为全0数组。找出翻转次数最少的操作方案，并输出每次翻转的数字的下标。（如一开始将数组a重置为0，则需要首位输出0）。

题解： 定义一个翻转标记p来记录前一位的翻转对后一位的影响，需要分别去统计一般情况下需要翻转的次数，和重置之后需要翻转的次数，比较之后输出次数较少的即可。

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
#include<bits/stdc++.h>
using namespace std;

int _T;
void run(){
	int q = 0, p = 0;
	string a, b;
	vector<int> ans, res;
	ans.push_back(0);	//ans中记录重置之后的翻转情况，需要先插入0
	cin >> a >> b;
	for(int i = 0; i < a.length(); i++){
		if((q + b[i]) % 2)	ans.push_back(i + 1), q++;
		if((p + a[i] + b[i]) % 2)	res.push_back(i + 1), p++;
	}
	if(ans.size() >= res.size())
		for(int i = 0; i < res.size(); i++)	cout << res[i] << " ";
	else
		for(int i = 0; i < ans.size(); i++)	cout << ans[i] << " ";
	cout << endl;
}

int main(){
	scanf("%d", &_T);
	while(_T--) run();
	return 0;
}

C Cook Steak

solved by lllllan

题意： 需要按顺序煎熟n块牛排，而每块牛排 i 都有它合适的温度范围[li,ril_i,r_i]。温度从0开始，每上升或下降一个单位需要一分钟，到达合适范围之后，煎熟一块牛排需要一分钟。问按顺序煎熟所有的牛排最少需要多少分钟。

题解： 贪心。设一个前驱温度pre，初始为0。按顺序给出n块牛排，如果pre本来在下一块牛排合适的温度范围内，则不做改变。否则，则将温度改变到离pre最近，又在合适范围内的值。最后再算上煎熟n块牛排的时间即答案。

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
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;

int _T, n, l, r;
void run() {
	int pre = 0;
	ll ans = 0;
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		scanf("%d%d", &l, &r);
		if(pre >= l && pre <= r)	continue;
		if(abs(l - pre) < abs(r - pre)) {
			ans += (ll)(abs(l - pre));
			pre = l;
		} else {
			ans += (ll)(abs(r - pre));
			pre = r;
		}
	}
	ans += (ll)n;
	printf("%lld\n", ans);
}

int main() {
	scanf("%d", &_T);
	while(_T--) run();
	return 0;
}

D Dessert Time

solved by Sstee1XD

题意： 给nn个装着一定数量蛋糕的盘子，两个人轮流取一个盘子，每次取的盘子中的蛋糕数量不能少于上一个人取的数量。特殊的，如果剩下的盘子中的蛋糕数量都比上一次少，则取的人会一次性把剩下的盘子都取完，称为兜底。谁先取完谁输，问先手是否能赢，输出第一次取的盘子中的蛋糕数量或者−1-1。

题解： 若所有盘子中的蛋糕数量都一样，若为偶数先手必赢。我们由此向后推，发现若所有相同蛋糕数量的盘子都为偶数时，先手必赢，取蛋糕数量最少的盘子。若出现了奇数，先手为了不让自己兜底，只能取从大到小第一次数量为奇数的盘子。此时若这个盘子中蛋糕数量是最少的，那么先手会取完最后一盘或者兜底，必输；若不是最少的，后手必兜底，先手必胜。

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
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 7;

int n;
int a[maxn];

void solve() {
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    sort(a + 1, a + 1 + n, greater<int>());
    for (int i = 1; i <= n; ++i) {
        int f = 1;
        while (a[i] == a[i + 1] && i <= n) {
            i++;
            f++;
        }
        if (f & 1) {
            if (i == n) {
                puts("-1");
                return;
            }
            printf("%d\n", a[i]);
            return;
        }
    }
    printf("%d\n", a[n]);
}

int _T;

int main() {
    scanf("%d", &_T);
    while (_T--) {
        scanf("%d", &n);
        solve();
    }
    return 0;
}

E Eat Grapes

solved by Sstee1XD

题意： 有一串链式葡萄，每个节点上都有若干颗葡萄。特殊的，对于最后一个节点，会额外连接一颗葡萄，但不算在它给你的数量里（例如有一个节点葡萄数量为00，当它成为最后一个节点时，数量会变成11）。两个人轮流取葡萄，每次可以在最后一个节点上取正整数个葡萄，当最后一个节点的葡萄数为00，则倒数第二个节点就会成为最后一个节点，谁取完谁输，问先手是否能赢。

题解： 当节点上葡萄数为0时，只能直接取，其余情况下，都可以根据情况选择取完，或者取到只剩下一个葡萄让对手取，从而改变接下来会取到的节点的情况。因此谁先取到葡萄数不为0的节点，就能根据接下来的情况选择取法，达到必胜的状态。

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
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 7;

int n, a[maxn];

void solve() {
	scanf("%d", &n);
	int res = 0;
	int m ;
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	for (int i = n; i >= 1; --i) {
		res ^= 1;
		if (a[i]) break;
	}
	if (res) puts("these are sweet grapes");
	else puts("these are sour grapes");
}

int _T;

int main() {
	scanf("%d", &_T);
	while (_T--) solve();
	return 0;
}

F Flag Scramble Competition

solved by Tryna

题意： 没有输入，直接输出题目文本中出现次数最多的字符。

题解： 队友有办法用python快速地找出来，但是因为训练比较随意，我从a试到了e就通过了。

AC代码 
1
2
3
4
5
6
7
#include<iostream>
using namespace std;

int main(){
    printf("e\n");
    return 0;
}

H Happy Time is Always Short

solved by Sstee1XD

题意： 每次进行区间清00，并询问所有数中的最大值。

题解： 线段树区间更新，查询最大值。

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
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
#define bug cout << "bug********************************\n"

using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-7;

const int maxn = 1e5 + 7;

int a[maxn];

struct SEG{
	int t[maxn << 2];
	int lazy[maxn << 2];
	
	void up(int id) {
		t[id] = max(t[id << 1], t[id << 1 | 1]);
	}
	
	void build(int id, int l, int r) {
		t[id] = lazy[id] = 0;
		if (l == r) {
			t[id] = a[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(id << 1, l, mid);
		build(id << 1 | 1, mid + 1, r);
		up(id);
	}
	
	void down(int id) {
		if (lazy[id] == 0) return;
		lazy[id << 1] = lazy[id << 1 | 1] = -1;
		t[id << 1] = t[id << 1 | 1] = 0;
		lazy[id] = 0;
	}
	
	void modify(int id, int l, int r, int ql, int qr) {
		if (ql <= l && qr >= r) {
			t[id] = 0;
			lazy[id] = -1;
			return;
		}
		down(id);
		int mid = (l + r) >> 1;
		if (ql > mid) modify(id << 1 | 1, mid + 1, r, ql, qr);
		else if (qr <= mid) modify(id << 1, l, mid, ql, qr);
		else modify(id << 1, l, mid, ql, qr), modify(id << 1 | 1, mid + 1, r, ql, qr);
		up(id);
	}
	
	int query(int id, int l, int r, int ql, int qr) {
		if (ql <= l && qr >= r) return t[id];
		down(id);
		int mid = (l + r) >> 1;
		if (ql > mid) return query(id << 1 | 1, mid + 1, r, ql, qr);
		else if (qr <= mid) return query(id << 1, l, mid, ql, qr);
		else return max(query(id << 1 | 1, mid + 1, r, ql, qr), query(id << 1, l, mid, ql, qr));
	}
}seg;

int _T, n, m;
int ql, qr;
void run(){
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	seg.build(1, 1, n);
	while (m--) {
		scanf("%d %d", &ql, &qr);
		seg.modify(1, 1, n, ql, qr);
		printf("%d\n", seg.query(1, 1, n, 1, n));
	}
}

int main(){
	scanf("%d", &_T);
	while (_T--) run();
	return 0;
}

I Isolated Pointset

solved by Tryna

题意：给你若干个点，问你是否存在两个点的垂直平分线通过任意一个点

题解：除了1,2不满足，其余情况都存在。

AC代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
#include<ctime>
using namespace std;
const int maxn=10010;
int t,n;
int main(void){
     scanf("%d",&t);
     while(t--){
         scanf("%d",&n);
         if(n==1||n==2) printf("No\n");
         else printf("Yes\n");
     }
}

J Jiufeng’s Football Team

solved by Sstee1XD

题意：给你一张完全无向图，以及mm条边和边权值，没有涉及的边权值为00，把nn个点分成数量可以不相同的两组，问同组内最大边权最小值。

题解：二分边权，然后考虑补图，将大于等于这个权值的边的两个顶点进行染色，找到能将补图染色成功的最小的边权值，答案即为下一个权值大小。注意每次要将第m+1m+1条边的权值设为00，不然二分到最后的时候输出第m+1m+1条边的权值会wawa。

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
75
#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e4 + 7;
const int maxm = 1e5 + 7;

struct Edge{
	int u, v, w;
	bool operator < (const Edge &e) const{
		return w > e.w;
	}
}edge[maxm];

struct G{
	int nxt, v;
}g[maxm << 1];

int cnt, head[maxn];

void addedge(int u, int v) {
	g[cnt] = {head[u], v,};
	head[u] = cnt++;
	g[cnt] = {head[v], u};
	head[v] = cnt++;
}

int n, m, vis[maxn], _T;

int dfs(int u, int c, int fa) {
	if (vis[u]) return vis[u] == c;
	vis[u] = c;
	for (int i = head[u]; ~i; i = g[i].nxt) {
		int v = g[i].v;
		if (v == fa) continue;
		if (!dfs(v, -c, u)) return 0;
	}
	return 1;
}

int work(int rear) {
	memset(vis, 0, sizeof(vis));
	memset(head, -1, sizeof(head));
	cnt = 0;
	for (int i = 1; i <= rear; ++i) {
		addedge(edge[i].u, edge[i].v);
	}
	for (int i = 1; i <= n; ++i) {
		if (vis[i]) continue;
		if (!dfs(i, 1, 0)) return 0;
	}
	return 1;
}

void solve() {
	scanf("%d %d", &n, &m);
	for (int i = 1, u, v, w; i <= m; ++i) {
		scanf("%d %d %d", &u, &v, &w);
		edge[i] = {u, v, w};
	}
	sort(edge + 1, edge + 1 + m);
	int l = 1, r = m, mid;
	edge[m + 1].w = 0;
	while (l <= r) {
		mid = l + r >> 1;
		if (work(mid)) l = mid + 1;
		else r = mid - 1;
	}
	printf("%d\n", edge[l].w);
}

int main() {
	scanf("%d", &_T);
	while (_T--) solve();
}

K Known-Well Palindrome Date-Easy Version

solved by Tryna

题意：一行给你若干串数字，让你判断有多少个回文日期，回文日期必须要满足以下两个条件。1.必须是一个合法的日期，即不能有1月32日这样的数字出现。2.必须满足是一个回文串。

题解：读入一行存进一个string中，从第0个位置暴力遍历到st.size()-7的位置，条件老老实实判断，比赛过程中因为没有判断年份是否合法wa了很多次。早上又想了一下发现其实不用判断闰年，闰年和平年只有2月不一样，如果是二月，那该年份一定是闰年 XX2002XX。

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=210;
int a[20]={0,31,29,31,30,31,30,31,31,30,31,30,31};
string st;
int cnt,ans;
int main(void){
     ios::sync_with_stdio(false);
     cin.tie(0);cout.tie(0);
     while(getline(cin,st)){
          ans = 0;
          if (st == "#") break;
          if (st.size() < 8) {
              cout << 0 << endl;
              continue;
          }
          for(int i = 0; i < st.size() - 7; i++){
             if((st[i] == st[i + 7]) && (st[i + 1] == st[i + 6] )&& (st[i + 2] == st[i + 5]) && (st[i + 3] == st[i + 4])){
                 int y = (st[i]-'0')*1000+(st[i+1]-'0')*100+(st[i+2]-'0')*10+(st[i+3]-'0');
                 int m = (st[i + 4] - '0') * 10 + (st[i + 5] - '0');
                 int d = (st[i + 6] - '0') * 10 + (st[i + 7] - '0');
                 if (y < 1 || y > 9999) continue;
                 if((m >= 1 && m <= 12) && (d >= 1 && d <= a[m])) ans++;
             }
          }
          cout << ans << endl;
    }
     return 0;
}
文章目录
  1. A A Party for You Started
  2. B Broken Pad
  3. C Cook Steak
  4. D Dessert Time
  5. E Eat Grapes
  6. F Flag Scramble Competition
  7. H Happy Time is Always Short
  8. I Isolated Pointset
  9. J Jiufeng’s Football Team
  10. K Known-Well Palindrome Date-Easy Version
|