Determine Line

签到题还 WA 了一发…

bitset初始化的时候是 0 扩展而不是符号扩展。

#include <bits/stdc++.h>
using namespace std;
bitset<127> ans(string(127, '1'));
int n;
int main()
{
	scanf("%d", &n);
	for (int i = 0, r, k; i < n; ++i)
	{
		bitset<127> bs;
		for (scanf("%d", &r); r--; bs.set(k))
			scanf("%d", &k);
		ans &= bs;
	}
	for (int i = 0; i < ans.size(); ++i)
		if (ans[i])
			printf("%d ", i);
}

Divide Candies

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, ans, a[1023];
int main()
{
	scanf("%lld%lld", &n, &m);
	fill(a, a + m, n / m);
	for (ll i = n / m * m + 1; i <= n; ++i)
		++a[i % m];
	for (ll i = 0; i < m; ++i)
		for (ll j = 0; j < m; ++j)
			if ((i * i + j * j) % m == 0)
				ans += a[i] * a[j];
	printf("%lld", ans);
}

Pick Heroes

难得一见的交互题，题目本身不难，无脑贪心即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 2047;
int n, m, p[N], a[N], q[N], vis[N];
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= 2 * n; ++i)
		scanf("%d", &p[q[i] = i]);
	for (int i = 0, x, y; i < m; ++i)
		scanf("%d%d", &x, &y), a[a[x] = y] = x;
	sort(q + 1, q + 2 * n + 1, [](int x, int y) -> bool { return a[x] && !a[y] ? 1 : !a[x] && a[y] ? 0 : p[x] > p[y]; });
	scanf("%d", &m);
	if (m == 1)
		printf("%d\n", vis[q[1]] = q[1]), fflush(stdout);
	for (int t = 1;;)
	{
		scanf("%d", &m);
		for (vis[m] = m; vis[q[t]];)
			++t;
		if (t > 2 * n)
			break;
		m = a[m] && !vis[a[m]] ? a[m] : q[t];
		printf("%d\n", vis[m] = m), fflush(stdout);
	}
}

Decorate Apple Tree

就是求叶结点第 k 小的子树上有多少叶结点。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
vector<int> g[N];
int n, a[N];
void dfs(int u)
{
	if (g[u].empty())
		a[u] = 1;
	for (auto v : g[u])
		dfs(v), a[u] += a[v];
}
int main()
{
	scanf("%d", &n);
	for (int i = 2, p; i <= n; ++i)
		scanf("%d", &p), g[p].push_back(i);
	dfs(1);
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; ++i)
		printf("%d ", a[i]);
}

Check Transcription

字符串哈希，卡模数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Mod
{
	const ll M;
	Mod(ll M) : M(M) {}
	ll add(ll a, ll b) const { return ((a + b) % M + M) % M; }
	ll mul(ll a, ll b) const { return a * b % M; }
};
struct HashString : Mod
{
	vector<ll> f, p;
	HashString(const string &s, ll M = 1e9 + 7, ll P = 131) : Mod(M), f(s.size() + 1), p(s.size() + 1, 1)
	{
		for (int i = 0; i < s.size(); ++i)
		{
			f[i + 1] = add(mul(f[i], P), s[i]);
			p[i + 1] = mul(p[i], P);
		}
	}
	ll ask(int pos, int len)
	{
		return add(f[pos + len], -mul(f[pos], p[len]));
	}
};
string s, t;
int c[2], ans;
int main()
{
	cin >> s >> t;
	HashString h(t);
	for (int i = 0; i < s.size(); ++i)
		++c[s[i] - '0'];
	for (int len[2] = {1}; len[0] * c[0] < t.size(); ++len[0])
	{
		len[1] = (t.size() - len[0] * c[0]) / c[1];
		if (len[1] == 0)
			break;
		if (len[0] * c[0] + len[1] * c[1] == t.size())
		{
			ll r[2] = {-1, -2};
			for (int i = 0, j = 0; r[0] != r[1] && i < s.size(); ++i)
			{
				if (r[s[i] - '0'] < 0)
					r[s[i] - '0'] = h.ask(j, len[s[i] - '0']);
				if (r[s[i] - '0'] == h.ask(j, len[s[i] - '0']))
					j += len[s[i] - '0'];
				else
					r[0] = r[1];
			}
			if (r[1] != r[0])
				++ans;
		}
	}
	cout << ans;
}

Write The Contest

#include <bits/stdc++.h>
using namespace std;
const int N = 127, C = 10, INF = 1e9;
pair<double, int> a[N];
double c, t, f[N][N * C];
int n, kase;
int main()
{
	for (scanf("%d", &kase); kase--;)
	{
		scanf("%d%lf%lf", &n, &c, &t);
		int m = 0, ans = 0;
		for (int i = 1; i <= n; ++i)
			scanf("%lf%d", &a[i].first, &a[i].second), m += a[i].second;
		sort(a + 1, a + n + 1, greater<pair<double, int>>());
		for (int i = 0; i <= n; ++i)
			fill(f[i], f[i] + m + 1, INF);
		f[0][0] = 0;
		for (int i = 1; i <= n; ++i)
			for (int j = i; j; --j)
				for (int k = m - a[i].second; ~k; --k)
					f[j][k + a[i].second] = min(f[j][k + a[i].second], f[j - 1][k] + a[i].first / pow(0.9, j));
		for (int j = m; !ans && j; --j)
			for (int i = 0; !ans && i <= n; ++i)
			{
				double x = max(sqrt(c * f[i][j]) - 1, .0) + 1;
				if (x + c * f[i][j] / x - 1 + c * i * 10 <= t * c)
					ans = j;
			}
		printf("%d\n", ans);
	}
}