An Olympian Math Problem

#include <stdio.h>
int main()
{
	long long t, n;
	for (scanf("%lld", &t); t--; printf("%lld\n", n - 1))
		scanf("%lld", &n);
}

AC Challenge

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int maxn = 25;
const int maxv = 1 << 22;
const long long inf = -100000000000000;

queue<long long> q[2];
long long f[2][maxv];
bool inq[maxv];
int pre[maxn];
int val[maxn][maxn];
int n, a, b, s, u, V;
long long ans;

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d%d", &a, &b);
		for (int j = 1; j <= n; j++)
			val[i][j] = a * j + b;
		scanf("%d", &s);
		for (int j = 1; j <= s; j++)
		{
			scanf("%d", &u);
			pre[i] += 1 << u;
		}
	}
	V = 1 << n + 1;
	for (int i = 1; i <= n; i++)
		if (pre[i] == 0)
			f[1][1 << i] = val[i][1], q[1].push(1 << i);
	for (int i = 2; i <= n; i++)
	{
		memset(inq, false, sizeof(inq));
		while (!q[(i + 1) % 2].empty())
		{
			int g = q[(i + 1) % 2].front();
			//printf("%d %d\n",i,g);
			q[(i + 1) % 2].pop();
			for (int j = 1; j <= n; j++)
			{
				if ((1 << j) & g)
					continue;
				if ((g & pre[j]) != pre[j])
					continue;
				//	if (f[(i+1)%2][k]+val[j][i]>f[i%2][k+(1<<j)]) printf("%d %d %d\n",j,k,f[(i+1)%2][k]+val[j][i]);
				int nxt = g + (1 << j);
				if (f[(i + 1) % 2][g] + val[j][i] > f[i % 2][nxt])
				{
					f[i % 2][nxt] = f[(i + 1) % 2][g] + val[j][i];
					if (!inq[nxt])
						q[i % 2].push(nxt), inq[nxt] = true;
					ans = max(ans, f[i % 2][nxt]);
				}
			}
			f[(i + 1) % 2][g] = inf;
		}
	}
	printf("%lld", ans);
	return 0;
}

Sum

线性筛处理一下。

#include <cstdio>
#include <vector>
using namespace std;
const int N = 2e7 + 7;
struct EulerSieve
{
	vector<int> p, m, f;
	EulerSieve(int N) : m(N, 0), f(N)
	{
		f[1] = 1;
		for (long long i = 2, k; i < N; ++i)
		{
			if (!m[i])
				p.push_back(m[i] = i), f[i] = 2;
			for (int j = 0; j < p.size() && (k = i * p[j]) < N; ++j)
				if (f[k] = f[i] * 2, (m[k] = p[j]) == m[i])
				{
					f[k] /= 4;
					break;
				}
		}
		for (int i = 0, p3; p3 = p[i] * p[i] * p[i], p3 < N; ++i)
			for (int j = p3; j < N; j += p3)
				f[j] = 0;
	}
} e(N);
long long sum[N];
int t, n;
int main()
{
	for (int i = 1; i < N; ++i)
		sum[i] = sum[i - 1] + e.f[i];
	for (scanf("%d", &t); t--; printf("%lld\n", sum[n]))
		scanf("%d", &n);
}

Magical Girl Haze

居然有 spfa 过的…

#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int N = 12e5, NPOS = -1;
struct Edge
{
	int from, to;
	ll dist;
} e[N << 2];
int ea[N << 2], va[N], es, vs;
void init(int n)
{
	fill(va, va + (vs = n), NPOS);
	es = 0;
}
void add(const Edge &ed)
{
	ea[es] = va[ed.from];
	va[ed.from] = es;
	e[es++] = ed;
}
ll d[N];
void ask(int s)
{
	fill(d, d + vs, INF);
	priority_queue<pair<ll, int>> q;
	for (q.push(make_pair(d[s] = 0, s)); !q.empty();)
	{
		ll dis = -q.top().first;
		int u = q.top().second;
		if (q.pop(), d[u] < dis)
			continue;
		for (int k = va[u], to; k != NPOS; k = ea[k])
			if (to = e[k].to, d[to] > d[u] + e[k].dist)
			{
				d[to] = d[u] + e[k].dist;
				q.push(make_pair(-d[to], to));
			}
	}
}
int main()
{
	int t, n, m, k;
	for (scanf("%d", &t); t--;)
	{
		scanf("%d%d%d", &n, &m, &k);
		init(n * (k + 2));
		for (int i = 0, u, v, c; i < m; ++i)
		{
			scanf("%d%d%d", &u, &v, &c), --u, --v;
			for (int j = 0; j <= k; ++j)
				add({u + j * n, v + j * n, c}), add({u + j * n, v + (j + 1) * n, 0});
		}
		ask(0);
		printf("%lld\n", d[n * (k + 1) - 1]);
	}
}