CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
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);
}
}