2026夏组队训练赛第二场

A. Attracting Attendees

图搜索
队列

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define debug(x) cout << #x << '=' << x << ' ';
#define DL cout << '\n';

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m, c;
	cin >> n >> m >> c;

	vector<vector<int>> g(m + 1);
	vector<vector<int>> f(n + 1);
	vector<int> sz(m + 1), cur(m + 1), szf(n + 1), rm(m + 1), rmf(n + 1);

	for (int i = 1; i <= m; i ++) {
		cin >> sz[i];
		for (int j = 1; j <= sz[i]; j ++) {
			int x;
			cin >> x;
			g[i].push_back(x);
			f[x].push_back(i);
		}
	}
	for (int i = 1; i <= n; i ++) szf[i] = f[i].size();
	for (int i = 1; i <= m; i ++) cur[i] = sz[i];

	queue<int> q;//乐队
	queue<int> q2;

	for (int i = 1; i <= n; i ++) {
		if (szf[i] < c) {
			rmf[i] = 1;
			q.push(i);
		}
	}

	while (!q.empty()) {
		int u = q.front();
		q.pop();

		for (int v : f[u]) if (!rm[v]) {
			cur[v] --;
			if (cur[v] < (sz[v] + 1) / 2) {
				rm[v] = 1;
				q2.push(v);
			}
		}

		while (!q2.empty()) {
			int u2 = q2.front();
			q2.pop();

			for (int v2 : g[u2]) if (!rmf[v2]) {
				szf[v2] --;
				if (szf[v2] < c) {
					rmf[v2] = 1;
					q.push(v2);
				}
			}
		}
	}

	vector<int> ans;
	for (int i = 1; i <= n; i ++) {
		if (!rmf[i]) ans.push_back(i);	
	}
	if (ans.empty()) cout << "impossible\n";
	else {
		cout << "possible\n";
		cout << size(ans) << '\n';
		for (auto i : ans) cout << i << ' ';
	}
}

B. Bye Bye Bilbo

深度优先搜索
树
贪心

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define debug(x) cout << #x << '=' << x << ' ';
#define DL cout << '\n';

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
		
	int n, k;
	cin >> n >> k;

	vector<vector<int>> g(n + 1);

	for (int i = 2; i <= n; i ++) {
		int x;
		cin >> x;
		g[x].push_back(i);
	}

	vector<int> d(n + 1), ans;

	auto dfs = [&](auto self, int u, int fa) -> void {
		d[u] = 1;
		for (auto v : g[u]) if (v != fa) {
			self(self, v, u);
			d[u] = max(d[u], d[v] + 1);
		}
		if (d[u] == k) ans.push_back(u), d[u] = 0;
	};

	dfs(dfs, 1, 0);
	if (ans.empty() || ans.back() != 1) ans.push_back(1);

	cout << size(ans) << '\n';
	for (auto i : ans) cout << i << ' ';
}

C. Crosses and Circles

博弈论
几何

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define debug(x) cout << #x << '=' << x << ' ';
#define DL cout << '\n';

int vis[100][100];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cout << 20 << ' ' << 20 << endl;
	int x, y;
	cin >> x >> y;
	vis[x][y] = 1;

	if (x == 20 && y == 22) {
		cout << 20 << ' ' << 19 << endl;
		cin >> x >> y;
		vis[x][y] = 1;
		if (vis[20][21]) cout << 20 << ' ' << 18 << endl;
		else cout << 20 << ' ' << 21 << endl;
		return 0;
	}

	if (abs(x - 20) + abs(y - 20) == 1) {
		cout << 21 << ' ' << 21 << endl;
		cin >> x >> y;
		vis[x][y] = 1;
		if (vis[19][19]) cout << 22 << ' ' << 22 << endl;
		else cout << 19 << ' ' << 19 << endl;
	} else {
		cout << 20 << ' ' << 21 << endl;
		cin >> x >> y;
		vis[x][y] = 1;
		if (vis[20][19]) cout << 20 << ' ' << 22 << endl;
		else cout << 20 << ' ' << 19 << endl;
	}
}

E. Egocentric Expedition

数学
几何

cpp

#include <bits/stdc++.h>
using namespace std;
using ld = long double;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;

    while (t--) {
        cout << "? 1 0" << endl;
        ld d1;
        cin >> d1;
        cout << "? 1 1" << endl;
        ld d2;
        cin >> d2;
        ld p1 = 1.0L / (d1 * d1);
        ld p2 = 1.0L / (d2 * d2);
        ld A = p1 * p1 + p2 * p2;
        ld B = p1 + p2;
        ld x1 = (B + sqrtl(B * B - A)) / (2 * A);
        ld x2 = (B - sqrtl(B * B - A)) / (2 * A);
        ld area = 4 * max(x1, x2);

        cout << "! " << llround(area) << endl;
    }
    return 0;
}

F. Fighting Fraud

哈希集合与映射
模拟

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
#define debug(x) cout << #x << '=' << x << ' ';
#define DL cout << '\n';
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
     
    map<string, int> mp;
 
    int t;
    cin >> t;
     
    int cnt = 0;
 
    for (int i = 1; i <= t; i ++) {
        string op, s;
        cin >> op >> s;
 
        if (op == "pickup") {
            if (mp.count(s)) {
                cout << "no\n";
                return 0;
            }
            cnt ++;
            mp[s] = 1;
        }
        else {
            if (mp[s] == 1) {
                cnt --;
                mp[s] = -1;
            }
            else {
                cout << "no\n";
                return 0;
            }
        }
    }

	if (cnt) cout << "no\n";
	else cout << "yes\n";
}

I. Incremented Itinerary

图论
最短路
Dijkstra

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define debug(x) cout << #x << '=' << x << ' ';
#define DL cout << '\n';

int n, m, s = 1;
const int maxn = 4e5 + 5;
int head[maxn];
int dis[maxn][2];

struct Edge {
	int to, next, w;
} e[maxn << 1];

struct Node {
	int pos, dis;
	bool operator < (const Node& p) const {
		return dis > p.dis;
	}
};

int cnt;
int vis[maxn][2];
void add(int u, int v, int w) {
	e[++cnt].to = v;
	e[cnt].w = w;
	e[cnt].next = head[u];
	head[u] = cnt;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;

	for (int i = 1; i <= m; i ++) {
		int u, v, w;
		cin >> u >> v;
		w = 1;
		add(u, v, w);
		add(v, u, w);
	}

	for (int i = 1; i <= n; i ++) dis[i][1] = dis[i][0] = 1e9;

	dis[s][0] = 0;
	priority_queue<Node> pq;
	pq.push({s, 0});
	
	while (!pq.empty()) {
		auto [pos, d] = pq.top();
		pq.pop();

		int st = d % 2;

		if (vis[pos][st]) continue;
		vis[pos][st] = 1;

		for (int i = head[pos]; i; i = e[i].next) {
			int to = e[i].to;
			if (dis[to][st ^ 1] > d + 1) {
				dis[to][st ^ 1] = d + 1;
				pq.push({to, d + 1});
			}

		}
	}

	//for (int i = 1; i <= n; i ++) cout << dis[i][0] << ' ' << dis[i][1] << endl;
	if (abs(dis[n][0] - dis[n][1]) == 1) cout << "possible";
	else cout << "impossible";
}

K. Keeping Cows

构造
网格图

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define debug(x) cout << #x << '=' << x << ' ';
#define DL cout << '\n';

char g[105][105];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;

	//freopen("out.txt", "w", stdout);

	cout << 100 << ' ' << 100 << '\n';

	int b = 80;
	int c = n / b;
	int left = n % b;

	for (int j = 4; j <= 4 + c - 1; j ++) {
		for (int i = 11; i <= 11 + b - 1; i ++) {
			g[i][j] = '.';
		}
	}
	for (int i = 11; i <= 11 + left - 1; i ++) {
		g[i][4 + c] = '.';
	}

	for (int i = 1; i <= 100; i ++) {
		for (int j = 1; j <= 100; j ++) {
			if (g[i][j] == 0 && g[i - 1][j] == 0 && g[i][j - 1] == 0) {
				if (g[i + 1][j + 1] == '.' || g[i + 1][j] == '.' || g[i - 1][j + 1] == '.')  {
					g[i][j] = 'O';
					g[i - 1][j] = '#';
					g[i][j - 1] = '#';
				}
			}
		}
	}

	for (int i = 1; i <= 100; i ++) {
		for (int j = 1; j <= 100; j ++) {
			if (g[i][j] == 0 && g[i][j + 1] == 0 && g[i - 1][j] == 0) {
				if (g[i + 1][j + 1] == '.' || g[i + 1][j] == '.' || g[i][j - 1] == '.' || g[i - 1][j - 1] == '.')  {
					g[i][j] = 'O';
					g[i - 1][j] = '#';
					g[i][j + 1] = '#';
				}
			}
		}
	}

	for (int i = 1; i <= 100; i ++) {
		for (int j = 1; j <= 100; j ++) {
			if (g[i][j] == 0 && g[i][j + 1] == 0 && g[i + 1][j] == 0) {
				if (g[i - 1][j + 1] == '.' || g[i - 1][j] == '.' || g[i][j - 1] == '.')  {
					g[i][j] = 'O';
					g[i][j + 1] = '#';
					g[i + 1][j] = '#';
				}
			}
		}
	}
	for (int i = 1; i <= 100; i ++) {
		for (int j = 1; j <= 100; j ++) {
			if (g[i][j] == 0 && g[i][j + 1] == 0 && g[i + 1][j] == 0) {
				if (g[i - 1][j + 1] == '.' || g[i - 1][j] == '.' || g[i][j - 1] == '.')  {
					g[i][j] = 'O';
					g[i][j + 1] = '#';
					g[i + 1][j] = '#';
				}
			}
		}
	}

	for (int i = 1; i <= 100; i ++) for (int j = 1; j <= 100; j ++) if (g[i][j] == 0) g[i][j] = '.';

	if (n <= 80 && n % 2) {
		g[11 + n][4] = '#';
		g[11 + n][6] = '.';
	}

	if (n >= 80 && n % 2 && c % 2 == 0) {
		g[91][c + 3] = '#';
		g[91][c + 5] = '.';
	}

	if (n % 80 == 0 && c % 2 == 0) {
		g[91][c + 3] = '#';
		g[91][c + 5] = '.';
	}

	for (int i = 1; i <= 100; i ++) {
		for (int j = 1; j <= 100; j ++) {
			cout << g[i][j];
		}
		cout << '\n';
	}
}

L. Lyrical Leisure

构造
字符串

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define debug(x) cout << #x << '=' << x << ' ';
#define DL cout << '\n';

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, k;
	cin >> n >> k;

	string ans(k, 'a');
	n -= k;
	
	vector<char> c = {'b', 'c', 'd'};
	int pos = 0;
	
	for (int i = 1; i <= n; i ++) {
		ans += c[pos];
		pos ++;
		pos %= 3;
	}
	cout << ans;
}

M. Mirror Magic

几何
凸包
哈希

cpp

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
const int mod = 998244353;
const int INF = 1e18;
const int N = 1e5 + 5;

struct P {
    int x, y, c;
};

i128 cross(P a, P b, P c) {
    return (i128)(b.x - a.x) * (c.y - a.y)
         - (i128)(b.y - a.y) * (c.x - a.x);
}

vector<P> convex(vector<P> a) {
    sort(all(a), [&](P a, P b) {
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    });

    vector<P> h;

    for (auto p : a) {
        while (sz(h) >= 2 &&
               cross(h[sz(h) - 2], h.back(), p) <= 0)
            h.pop_back();
        h.pb(p);
    }

    int k = sz(h);

    for (int i = sz(a) - 2; i >= 0; i--) {
        auto p = a[i];
        while (sz(h) > k &&
               cross(h[sz(h) - 2], h.back(), p) <= 0)
            h.pop_back();
        h.pb(p);
    }

    if (sz(h) > 1)
        h.pop_back();

    return h;
}

struct Hash {
    size_t operator()(const pii& p) const {
        static const ull R =
            chrono::steady_clock::now().time_since_epoch().count();

        auto H = [&](ull x) {
            x += R + 0x9e3779b97f4a7c15ULL;
            x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
            x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
            return x ^ (x >> 31);
        };

        return H(p.f) ^ (H(p.s) << 1);
    }
};

bool check(
    P u,
    P v,
    const vector<P>& a,
    const vector<P>& b,
    const unordered_set<pii, Hash>& st,
    i128 sx,
    i128 sy,
    int m
) {
    i128 dx = (i128)v.x - u.x;
    i128 dy = (i128)v.y - u.y;

    i128 D = dx * dx + dy * dy;

    i128 d =
        (i128)v.x * v.x + (i128)v.y * v.y
        - (i128)u.x * u.x - (i128)u.y * u.y;

    if (2 * (dx * sx + dy * sy) != (i128)m * d)
        return false;

    int sa = 0, sb = 0;

    for (auto p : a) {
        i128 z = 2 * (dx * p.x + dy * p.y) - d;

        if (z == 0)
            return false;

        int t = z > 0 ? 1 : -1;

        if (!sa)
            sa = t;
        else if (sa != t)
            return false;
    }

    for (auto p : b) {
        i128 z = 2 * (dx * p.x + dy * p.y) - d;

        if (z == 0)
            return false;

        int t = z > 0 ? 1 : -1;

        if (!sb)
            sb = t;
        else if (sb != t)
            return false;
    }

    if (sa == sb)
        return false;

    for (auto p : a) {
        i128 z = 2 * (dx * p.x + dy * p.y) - d;

        i128 nx = (i128)p.x * D - z * dx;
        i128 ny = (i128)p.y * D - z * dy;

        if (nx % D != 0 || ny % D != 0)
            return false;

        int x = nx / D;
        int y = ny / D;

        if (!st.count({x, y}))
            return false;
    }

    return true;
}

void init() {
    
}

void solve() {
    int n;
    cin >> n;

    vector<P> a(n), b(n);
    vector<P> p;
    p.reserve(2 * n);

    i128 sx = 0, sy = 0;

    for (int i = 0; i < n; i++) {
        cin >> a[i].x >> a[i].y;
        a[i].c = 0;

        sx += a[i].x;
        sy += a[i].y;

        p.pb(a[i]);
    }

    unordered_set<pii, Hash> st;
    st.reserve(2 * n + 10);
    st.max_load_factor(0.7);

    for (int i = 0; i < n; i++) {
        cin >> b[i].x >> b[i].y;
        b[i].c = 1;

        sx += b[i].x;
        sy += b[i].y;

        p.pb(b[i]);
        st.insert({b[i].x, b[i].y});
    }

    vector<P> h = convex(p);

    vector<pair<P, P>> cand;

    if (sz(h) == 2) {
        if (h[0].c == h[1].c) {
            cout << "impossible" << endl;
            return;
        }

        cand.pb({h[0], h[1]});
    } else {
        for (int i = 0; i < sz(h); i++) {
            P u = h[i];
            P v = h[(i + 1) % sz(h)];

            if (u.c != v.c)
                cand.pb({u, v});
        }

        if (sz(cand) != 2) {
            cout << "impossible" << endl;
            return;
        }
    }

    for (auto [u, v] : cand) {
        if (check(u, v, a, b, st, sx, sy, 2 * n)) {
            cout << "possible" << endl;
            return;
        }
    }

    cout << "impossible" << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init();

    int t = 1;
    while (t--)
        solve();

    return 0;
}

其他没做的题

Delphi Danger
Garbled Garden
Historical Hits
Junior Joining

2026夏组队训练赛第二场 ​

A. Attracting Attendees ​

B. Bye Bye Bilbo ​

C. Crosses and Circles ​

E. Egocentric Expedition ​

F. Fighting Fraud ​

I. Incremented Itinerary ​

K. Keeping Cows ​

L. Lyrical Leisure ​

M. Mirror Magic ​

2026夏组队训练赛第二场

A. Attracting Attendees

B. Bye Bye Bilbo

C. Crosses and Circles

E. Egocentric Expedition

F. Fighting Fraud

I. Incremented Itinerary

K. Keeping Cows

L. Lyrical Leisure

M. Mirror Magic