Menu

第十八次CCF计算机软件能力认证

发表于 16 Dec 2019 总计 6023字 阅读时间 21分
CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~

UPDATE：成绩单出了，看排名似乎考的没那么差 hh，原来不是我一个人觉得后两题难…

成绩单

两年前打过第十三次 CSP 认证，当时觉得比赛挺水的就没继续打了…

两年后抱着（以为）自己进步一点的心态重新参赛，结果疯狂白给，100+100+100+60+25…特么还没两年前打得好。后两题完全只会暴力，字符串处理也是令人呕吐…

报数

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

// INFO BEGIN
//
// User = 201911505159(吴坎)
// Group = C/C++
// Problem = 报数
// Language = CPP11
// SubmitTime = 2019-12-15 13:53:06
//
// INFO END

#include <cstdio>
using namespace std;
const int N = 1e5 + 9;
int n, a[N];
int seven(int k)
{
	if (k % 7 == 0)
		return 1;
	for (; k; k /= 10)
		if (k % 10 == 7)
			return 1;
	return 0;
}
int main()
{
	scanf("%d", &n);
	for (int i = 0, k = 1; i < n; ++k)
	{
		if (seven(k))
			++a[(k - 1) % 4];
		else
			++i;
	}
	for (int i = 0; i < 4; ++i)
		printf("%d\n", a[i]);
	return 0;
}

回收站选址

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

// INFO BEGIN
//
// User = 201911505159(吴坎)
// Group = C/C++
// Problem = 回收站选址
// Language = CPP11
// SubmitTime = 2019-12-15 13:51:03
//
// INFO END

#include <cstdio>
#include <set>
#include <vector>
using namespace std;
int n, cnt[5];
set<pair<int, int>> se;
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
	{
		pair<int, int> p;
		scanf("%d%d", &p.first, &p.second);
		se.insert(p);
	}
	for (auto p : se)
	{
		vector<pair<int, int>> v(4, p);
		--v[0].first, ++v[1].first, --v[2].second, ++v[3].second;
		if (se.count(v[0]) && se.count(v[1]) && se.count(v[2]) && se.count(v[3]))
		{
			--v[0].second;
			++v[1].second;
			++v[2].first;
			--v[3].first;
			int score = 0;
			for (int i = 0; i < 4; ++i)
				if (se.count(v[i]))
					++score;
			++cnt[score];
		}
	}
	for (int i = 0; i < 5; ++i)
		printf("%d\n", cnt[i]);
	return 0;
}

化学方程式

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

// INFO BEGIN
//
// User = 201911505159(吴坎)
// Group = C/C++
// Problem = 化学方程式
// Language = CPP11
// SubmitTime = 2019-12-15 15:01:15
//
// INFO END

#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
const int N = 1023;
char s[N];
int pipei(int p)
{
	for (int c = 0;; ++p)
	{
		if (s[p] == '(')
			++c;
		if (s[p] == ')')
			--c;
		if (!c)
			return p;
	}
}
void element(map<string, int> &mp, int coef, int l, int r)
{
	mp[string(s + l, s + r + 1)] += coef;
}
void term(map<string, int> &mp, int coef, int l, int r)
{
	void formula(map<string, int> & mp, int coef, int l, int r);
	if (s[l] == '(' && s[r] == ')')
	{
		formula(mp, coef, l + 1, r - 1);
		return;
	}
	element(mp, coef, l, r);
}
void term_ceof(map<string, int> &mp, int coef, int l, int r)
{
	if ('0' <= s[r] && s[r] <= '9')
	{
		int pos = r, c = 0;
		while ('0' <= s[pos] && s[pos] <= '9')
			--pos;
		for (int i = pos + 1; i <= r; ++i)
			c = c * 10 + s[i] - '0';
		if (c)
			coef *= c;
		term(mp, coef, l, pos);
		return;
	}
	term(mp, coef, l, r);
}
void formula(map<string, int> &mp, int coef, int l, int r)
{
	for (int i = l; i <= r;)
	{
		if (s[i] == '(')
		{
			int p = pipei(i) + 1;
			if (p > r)
			{
				term_ceof(mp, coef, i, p - 1);
				return;
			}
			while ('0' <= s[p] && s[p] <= '9')
				++p;
			term_ceof(mp, coef, i, p - 1);
			i = p;
		}
		else
		{
			int p = i + 1;
			while (('0' <= s[p] && s[p] <= '9') || ('a' <= s[p] && s[p] <= 'z'))
				++p;
			term_ceof(mp, coef, i, p - 1);
			i = p;
		}
	}
}
void coef_formula(map<string, int> &mp, int l, int r)
{
	if ('0' <= s[l] && s[l] <= '9')
	{
		int coef = 0, pos = l;
		for (; '0' <= s[pos] && s[pos] <= '9'; ++pos)
			coef = coef * 10 + s[pos] - '0';
		formula(mp, coef, pos, r);
		return;
	}
	formula(mp, 1, l, r);
}
map<string, int> expr(int l, int r)
{
	map<string, int> mp;
	int pre = l;
	for (int i = l; i <= r; ++i)
		if (s[i] == '+')
		{
			coef_formula(mp, pre, i - 1);
			pre = i + 1;
		}
	coef_formula(mp, pre, r);
	return mp;
}
int main()
{
	int n;
	for (scanf("%d", &n); n--;)
	{
		scanf("%s", s);
		int eq = find(s, s + N, '=') - s;
		printf(expr(0, eq - 1) == expr(eq + 1, strlen(s) - 1) ? "Y\n" : "N\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

// INFO BEGIN
//
// User = 201911505159(吴坎)
// Group = C/C++
// Problem = 区块链
// Language = CPP11
// SubmitTime = 2019-12-15 17:25:00
//
// INFO END

#include <cstdio>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
const int N = 511;
struct Vertex
{
	vector<int> to, link;
	Vertex() : link(1, 0) {}
} v[N];
typedef tuple<int, vector<int>, int> tivi;
priority_queue<tivi, vector<tivi>, greater<tivi>> q;
char s[N];
int n, m, t, k;
void sync(int b)
{
	if (q.empty() || get<0>(q.top()) > b)
		return;
	tivi u = q.top();
	q.pop();
	for (auto to : v[get<2>(u)].to)
		if ((v[to].link.size() < get<1>(u).size()) ||
			(v[to].link.size() == get<1>(u).size() &&
			 v[to].link.back() > get<1>(u).back()))
			q.push(tivi(get<0>(u) + t, v[to].link = get<1>(u), to));
	sync(b);
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1, x, y; i <= m; ++i)
	{
		scanf("%d%d", &x, &y);
		v[x].to.push_back(y);
		v[y].to.push_back(x);
	}
	scanf("%d%d", &t, &k);
	fgets(s, N, stdin);
	for (int i = 1, a, b, c; i <= k; ++i)
	{
		fgets(s, N, stdin);
		if (sscanf(s, "%d%d%d", &a, &b, &c) == 3)
		{
			sync(b);
			v[a].link.push_back(c);
			q.push(tivi(b + t, v[a].link, a));
		}
		else
		{
			sync(b);
			printf("%d ", (int)v[a].link.size());
			for (int j = 0; j < v[a].link.size(); ++j)
				printf("%d ", v[a].link[j]);
			printf("\n");
		}
	}
	return 0;
}

魔数

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

// INFO BEGIN
//
// User = 201911505159(吴坎)
// Group = C/C++
// Problem = 魔数
// Language = CPP11
// SubmitTime = 2019-12-15 16:09:16
//
// INFO END

#include <cstdio>
using namespace std;
typedef long long ll;
const ll
	N = 1e6 + 9,
	u[5] = {
		314882150829468584,
		427197303358170108,
		1022292690726729920,
		1698479428772363217,
		2006101093849356424},
	fm[2] = {2009731336725594113, 2019};
ll mul(ll a, __int128 b, ll c) { return a * b % c; }
ll f1a[N];
int main()
{
	int n, q;
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; ++i)
		f1a[i] = i;
	for (int i = 1, l, r; i <= q; ++i)
	{
		scanf("%d%d", &l, &r);
		int s = 0;
		for (int j = l; j <= r; ++j)
			s += f1a[j] % fm[1];
		printf("%d\n", s);
		ll ut = u[s % 5];
		for (int j = l; j <= r; ++j)
			f1a[j] = mul(f1a[j], ut, fm[0]);
	}
	return 0;
}