octal的XCPC题解

2023南京

I. Counter

【思维】【签到】

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
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
inline void solve()
{
	int n, m;
	cin >> n >> m;
	vector<pii> a(m+5);
	for(int i=1; i<=m; i++)
	{
		int x, y;
		cin >> x >> y;
		a[i] = {x, y};
	}
	a[0] = {0, 0};
	sort(a.begin()+1, a.begin()+1+m);
	for(int i=1; i<=m; i++)
	{
		int t = a[i].first - a[i-1].first;
		if(a[i].second - a[i-1].second != t && a[i].second+1 > t)
		{
			puts("No");
			return;
		}
	}
	puts("Yes");
}
int main()
{
	int t;
	cin >> t;
	while(t--)
		solve();
	return 0;
}

C. Primitive Root

【数学】

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
#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
typedef pair<int, int> pii;
__int128 read()
{
	__int128 res=0;
	char scan[1005];
	scanf("%s",scan);
	for(int i=0;i<strlen(scan);i++)
		res*=10,res+=scan[i]-'0';
	return res;
}
void print(__int128 num)
{
	if(num>9) 
		print(num/10);
	putchar(num%10+'0');
}
inline void solve()
{
    ll p, m;
    p = read();
    m = read();
    ll k = (m-1) / p;
    ll zero = 0;
    ll res = max(zero, k-50);
    for(ll i=max(zero, k-50); i<=k+50; i++)
    {
        ll t = (i*p+1) ^ (p-1);
        if(t <= m) res ++;
    }
    print(res);
    puts("");
}

int main()
{
    /*
    k*p + 1 <= m
    k <= K
    
    */
    int t;
    cin >> t;
    while(t--)
        solve();

    return 0;
}

F. Equivalent Rewriting

【拓扑排序】

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
int n, m;
	cin >> n >> m;
	vector<int> v[m+5];
	for(int i=1; i<=n; i++)
	{
		int p;
		cin >> p;
		while(p--) {
			int b;
			cin >> b;
			v[b].push_back(i);
		}
	}
	vector<int> deg(n+5);
	vector<int> g[n+5];
	set<pii> st;

	for(int i=1; i<=m; i++)
	{
		int sz = v[i].size();
		if(sz <= 1) continue;
		int u = v[i][sz-1];
		for(int j=sz-2; j>=0; j--)
		if(!st.count({u, v[i][j]}))
		{
			st.insert({u, v[i][j]});
			g[u].push_back(v[i][j]);
			deg[v[i][j]] ++;
		}
	}

	priority_queue<int, vector<int>, greater<int>> hp;
	for(int i=1; i<=n; i++)
	if(!deg[i]) hp.push(i);
	vector<int> ans;
	while(!hp.empty()) {
		int u = hp.top();
		hp.pop();
		ans.push_back(u);
		for(int v : g[u]) {
			deg[v] --;
			if(!deg[v]) hp.push(v);;
		}
	}

	for(int i=1; i<=n; i++) {
		if(ans[n-i] != i) {
			puts("Yes");
			while(ans.size()) {
				cout << ans.back() << " ";
				ans.pop_back();
			}
			puts("");
			return;
		}
	}
	puts("No");
}
int main()
{
	int t;
	cin >> t;
	while(t--)
		solve();
	return 0;
}

G. Knapsack

【DP + 贪心】

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;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ll long long
inline void solve()
{
	int n, W, K;
	cin >> n >> W >> K;
	vector<pll> a(n+5);
	for(int i=1; i<=n; i++)
	{
		cin >> a[i].first >> a[i].second;
	}
	sort(a.begin()+1, a.begin()+1+n, [](pll x, pii y){
		return x.second < y.second; //按价值从小到大排序
	});
	vector<vector<ll>> dp(n+5, vector<ll>(W+5));
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<a[i].first; j++)
			dp[i][j] = dp[i-1][j];
		for(int j=W; j>=a[i].first; j--)
			dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i].first] + a[i].second);
	}
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=W; j++)
			dp[i][j] = max(dp[i][j], dp[i][j-1]);
	}
	vector<ll> sum(n+5);
	for(int i=n; i>=1; i--) //价值的后缀
		sum[i] = sum[i+1] + a[i].second;

	priority_queue<ll, vector<ll>, greater<ll>> hp;
	for(int i=n; i>=n-K+1; i--) //价值最大的K个的重量加入小根堆
		hp.push(a[i].first);
	ll s = 0, res = 0;
	for(int i=n-K+1; i>=1; i--)
	{
	    if(hp.size() > K) s += hp.top(), hp.pop();
		if(s <= W) res = max(res, dp[i-1][W-s] + sum[i]);
		hp.push(a[i-1].first);
	}
	cout << res << endl;
}
int main()
{
	int t;
	t = 1;
	while(t--)
		solve();
	return 0;
}

A. Cool, It’s Yesterday Four Times More

【BFS】

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
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ll long long

inline void solve()
{
	int n, m;
	cin >> n >> m;
	vector<vector<char>> mp(n+5, vector<char>(m+5));
	vector<pii> a;
	for(int i=1; i<=n; i++)
	for(int j=1; j<=m; j++)
	{
		cin >> mp[i][j];
		if(mp[i][j] == '.')
			a.push_back({i, j}); 
	}
	auto check = [&](int x, int y) {
		if(x<1 || y<1 || x>n || y>m)
			return true;
		if(mp[x][y] == 'O') 
			return true;
		return false;
	};

	int dx[5] = {0, 1, -1, 0, 0};
	int dy[5] = {0, 0, 0, 1, -1};
	set<pii> st; //使每个点只遍历一次
	auto bfs = [&](int x, int y) {
		queue<pii> q;
		vector<pii> dxy;
		st.insert({x, y});
		q.push({x, y});
		int tot = 1;
		while(!q.empty()) {
			auto u = q.front();
			int ux = u.first;
			int uy = u.second;
			q.pop();
			for(int i=1; i<=4; i++)
			{
				int vx = ux + dx[i];
				int vy = uy + dy[i];
				if(check(vx, vy)) continue;
				if(st.count({vx, vy})) continue;
				st.insert({vx, vy});
				tot ++;
				dxy.push_back({vx - x, vy - y});
				q.push({vx, vy});
			}
		}
		
		for(auto t : a) {
			if(t.first != x || t.second != y) {
				bool ok = 0;
				for(pii p : dxy) {
					if(check(t.first+p.first, t.second+p.second))
					{
						ok = 1;
						break;
					}
				}
				if(!ok) return 0; //这一个集合的点都不满足
			}
		}
		return tot;
	};

	int res = 0;
	for(auto t : a) 
	if(!st.count({t.first, t.second}))
	{
		res += bfs(t.first, t.second);
	}
	cout << res << endl;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--)
		solve();
	return 0;
}