CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
An Olympian Math Problem
1
2
3
4
5
6
7
#include <stdio.h>
int main()
{
long long t, n;
for (scanf("%lld", &t); t--; printf("%lld\n", n - 1))
scanf("%lld", &n);
}
AC Challenge
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
#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
线性筛处理一下。
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 <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 过的…
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
#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]);
}
}