CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
Maomao’s candy
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
68
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Mod
{
const ll M;
Mod(ll M) : M(M) {}
ll qadd(ll &a, ll b) const { return a += b, a >= M ? a -= M : a; }
ll add(ll a, ll b) const { return qadd(a = (a + b) % M, M); }
ll mul(ll a, ll b) const { return add(a * b, -M * ll((long double)a / M * b)); }
} M(1025436931);
typedef array<array<ll, 2>, 2> Mat;
Mat operator*(const Mat &a, const Mat &b)
{
Mat r;
for (int i = 0; i < r.size(); ++i)
for (int j = 0; j < r.size(); ++j)
for (int k = r[i][j] = 0; k < r.size(); ++k)
M.qadd(r[i][j], M.mul(a[i][k], b[k][j]));
return r;
}
Mat pow(Mat a, ll b)
{
Mat r;
for (int i = 0; i < r.size(); ++i)
for (int j = 0; j < r[i].size(); ++j)
r[i][j] = i == j;
for (; b; b >>= 1, a = a * a)
if (b & 1)
r = r * a;
return r;
}
int main()
{
int t, n, m, x1, y1, x2, y2;
for (scanf("%d", &t); t--;)
{
scanf("%d%d%d%d%d%d", &n, &m, &x2, &y2, &x1, &y1);
if (x1 > x2)
x1 = n - x1 + 1, x2 = n - x2 + 1;
if (y1 > y2)
y1 = m - y1 + 1, y2 = m - y2 + 1;
if (n < m)
swap(n, m), swap(x1, y1), swap(x2, y2);
int ans = (x2 - 1) + (y2 - 1) - 1, dx = x2 - x1, dy = y2 - y1;
if (m == 1)
ans = (x1 + x2) & 1 ? x2 - 1 : x2 - 2;
else if ((x1 + x2 + y1 + y2) & 1)
ans = -1;
else
{
if (dx > dy)
ans = max(ans, (x2 - 1) + (m - y2) - 1);
if (dy > dx)
ans = max(ans, (n - x2) + (y2 - 1) - 1);
}
if (ans < 0)
printf("countless\n");
else
{
Mat a;
a[0] = {0, 1};
a[1] = {1, 1};
a = pow(a, ans);
printf("%lld\n", M.add(M.add(a[0][1], a[1][1]), M.M - 1));
}
}
}
Dudu’s maze
由于只有一个 magic portal，先把当前所在的连通块的糖果全拿走，之后在第一次遇到敌人的时候使用肯定是最优的。先用并查集将没有敌人的点合并起来，用一个数组存放该连通块所含点的数量（称作权值），再用搜索搜出和起点所在连通块相连的怪物点，把这些怪物点枚举一下，遍历连接这个怪物点的所有边，求边的另一端的连通块的权值（1 这个点所在连通块的权值要改为 0，因为已经拿过了），求和之后再除以与该点相连的边数，取最大值，加上 1 所在连通块的权重即可。因为遇到敌人是随机选择边逃跑，因此遇到重边的时候连通块的权值要累计多次。同时也是除以连接的边数而不是连接的连通块数量或者房间数量。拿到的糖果数量至少是 1 所在连通块的权重值，不论经过哪里，都一定能拿到那些糖果，所以最后答案直接加上即可
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
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;
typedef double lf;
struct Graph
{
struct Vertex
{
vector<int> o;
};
typedef pair<int, int> Edge;
vector<Vertex> v; //点集
vector<Edge> e; //边集
Graph(int n) : v(n) {}
void add(const Edge &ed)
{
v[ed.first].o.push_back(e.size());
e.push_back(ed);
}
};
struct UnionfindSet : vector<int>
{
vector<int> siz;
UnionfindSet(int n) : vector<int>(n), siz(n, 1)
{
for (int i = 0; i < n; ++i)
at(i) = i;
}
void merge(int u, int w)
{
if (w = ask(w), u = ask(u), w != u)
at(w) = u, siz[u] += siz[w];
}
int ask(int u) { return at(u) != u ? at(u) = ask(at(u)) : u; }
};
int main()
{
int t, n, m, k;
for (scanf("%d", &t); t--;)
{
scanf("%d%d%d", &n, &m, &k);
Graph g(n), h(n);
UnionfindSet ufs(n);
vector<int> x(n, 0);
for (int i = 0, a, b; i < m; ++i)
{
scanf("%d%d", &a, &b);
g.add({a - 1, b - 1});
g.add({b - 1, a - 1});
}
for (int i = 0, t; i < k; ++i)
scanf("%d", &t), x[t - 1] = 1;
for (auto e : g.e)
if (!x[e.first] && !x[e.second])
ufs.merge(e.first, e.second);
lf ans = 0;
for (int i = 0, adj; i < n; ++i)
if (x[i])
{
lf sum = adj = 0;
for (auto k : g.v[i].o)
if (!x[g.e[k].second])
{
if (ufs.ask(g.e[k].second) == ufs.ask(0))
adj = 1;
else
sum += ufs.siz[ufs.ask(g.e[k].second)];
}
if (adj)
ans = max(ans, sum / g.v[i].o.size());
}
printf("%.9lf\n", ans + ufs.siz[ufs.ask(0)]);
}
}
Dawn-K’s water
背包搞一搞。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
const int N = 1023, INF = 1e9 + 9;
int main()
{
for (int n, m; ~scanf("%d%d", &n, &m);)
{
vector<int> f(2e4 + 9, INF);
for (int i = f[0] = 0, p, c; i < n; ++i)
{
scanf("%d%d", &p, &c);
for (int j = c; j < f.size(); ++j)
f[j] = min(f[j], f[j - c] + p);
}
pair<int, int> ans(INF, INF);
for (int i = m; i < f.size(); ++i)
ans = min(ans, {f[i], -i});
printf("%d %d\n", ans.first, -ans.second);
}
}
Fish eating fruit
树上 DP 搞一搞。
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Mod
{
const ll M, SM;
Mod(ll M) : M(M), SM(sqrt(M) + 0.5) {}
ll qadd(ll &a, ll b) const { return a += b, a >= M ? a -= M : a; } //假如a和b都已经在同余系内，就不必取模了，取模运算耗时很高
ll add(ll a, ll b) const { return qadd(a = (a + b) % M, M); } //考虑a和b不在同余系内甚至为负数的情况
ll mul(ll a, ll b) const { return add(a * b, M); }
ll inv(ll a) const { return pow(a, M - 2); } //要求M为素数，否则return pow(a, phi(M) - 1);
ll pow(ll a, ll b) const
{
ll r = 1;
for (a = add(a, M); b; b >>= 1, a = mul(a, a))
if (b & 1)
r = mul(r, a);
return r;
}
/*
ll mul(ll a, ll b) const { return add(a * b, -M * ll((long double)a / M * b)); }
ll mul(ll a, ll b) const //无循环快速计算同余乘法，根据a*b是否爆ll替换a*b%M，需要a<M且b<M，可以调用时手动取模
{
ll c = a / SM, d = b / SM;
a %= SM, b %= SM;
ll e = add(add(a * d, b * c), c * d / SM * (SM * SM - M));
return add(add(a * b, e % SM * SM), add(c * d % SM, e / SM) * (SM * SM - M));
}
ll inv(ll a) const
{ //模m下a的乘法逆元，不存在返回-1（m为素数时a不为0必有逆元）
ll x, y, d = gcd(a, M, x, y);
return d == 1 ? add(x, M) : -1;
}
vector<ll> sol(ll a, ll b) const //解同余方程，返回ax=b(mod M)循环节内所有解
{
vector<ll> ans;
ll x, y, d = gcd(a, M, x, y);
if (b % d)
return ans;
ans.push_back(mul((b / d) % (M / d), x));
for (ll i = 1; i < d; ++i)
ans.push_back(add(ans.back(), M / d));
return ans;
}
ll log(ll a, ll b) const
{
unordered_map<ll, ll> x;
for (ll i = 0, e = 1; i <= SM; ++i, e = mul(e, a))
if (!x.count(e))
x[e] = i;
for (ll i = 0, v = inv(pow(a, SM)); i <= SM; ++i, b = mul(b, v))
if (x.count(b))
return i * SM + x[b];
return -1;
}
*/
} M(1e9 + 7);
struct Graph
{
struct Vertex
{
vector<int> o;
vector<ll> ans, sum, cnt;
};
struct Edge
{
int first, second;
ll len; //边长、容量，图论算法使用
};
vector<Vertex> v; //点集
vector<Edge> e; //边集
Graph(int n) : v(n) {}
void add(const Edge &ed)
{
v[ed.first].o.push_back(e.size());
e.push_back(ed);
}
void dp(int u, int fa)
{
v[u].ans.assign(3, 0);
v[u].sum.assign(3, 0);
v[u].cnt.assign(3, 0);
int to;
for (auto k : v[u].o)
if (to = e[k].second, to != fa)
{
dp(to, u);
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
{
M.qadd(v[u].sum[(i + j + e[k].len) % 3], M.mul(v[u].ans[i], v[to].cnt[j]));
M.qadd(v[u].sum[(i + j + e[k].len) % 3], M.mul(v[u].cnt[i], v[to].ans[j]));
M.qadd(v[u].sum[(i + j + e[k].len) % 3], M.mul(M.mul(v[u].cnt[i], v[to].cnt[j]), e[k].len));
}
for (int i = 0; i < 3; ++i)
{
M.qadd(v[u].sum[(i + e[k].len) % 3], v[u].ans[i]);
M.qadd(v[u].sum[(i + e[k].len) % 3], M.mul(v[u].cnt[i], e[k].len));
}
//cerr << v[u].sum[0] << endl;
for (int i = 0; i < 3; ++i)
{
M.qadd(v[u].cnt[(i + e[k].len) % 3], v[to].cnt[i]);
M.qadd(v[u].ans[(i + e[k].len) % 3], v[to].ans[i]);
M.qadd(v[u].ans[(i + e[k].len) % 3], M.mul(e[k].len, v[to].cnt[i]));
}
M.qadd(v[u].cnt[e[k].len % 3], 1);
M.qadd(v[u].ans[e[k].len % 3], e[k].len);
}
/*
for (int i = 0; i < 3; ++i)
for (int j = 0; j < i; ++j)
{
M.qadd(v[u].sum[(i + j) % 3], M.mul(v[u].cnt[j], v[u].ans[i]));
M.qadd(v[u].sum[(i + j) % 3], M.mul(v[u].cnt[i], v[u].ans[j]));
}
*/
/*
for (int i = 0; i < 3; ++i)
cerr << v[u].ans[i] << ',' << v[u].cnt[i] << ',' << v[u].sum[i] << '!';
cerr << u << endl;*/
}
};
int main()
{
for (int n; ~scanf("%d", &n);)
{
Graph g(n);
for (int i = 1, x, y, z; i < n; ++i)
{
scanf("%d%d%d", &x, &y, &z);
g.add({x, y, z});
g.add({y, x, z});
}
g.dp(0, -1);
for (ll i = 0, ans; i < 3; ++i)
{
for (ll j = ans = 0; j < n; ++j)
{
M.qadd(ans, g.v[j].sum[i]);
M.qadd(ans, g.v[j].ans[i]);
}
printf("%lld%c", M.mul(2, ans), " \n"[i == 2]);
}
}
}
Honk’s pool
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
#define ll long long
#define int ll
#define maxn 500005
using namespace std;
int a[maxn];
struct pa
{
int val, num;
} p[maxn], p2[maxn];
int n, k, ct;
int sum[maxn], tt, ct1, ct2, val1, val2;
ll summ, req;
signed main(void)
{
//freopen("qet","r",stdin);
while (~scanf("%lld%lld", &n, &k))
{
req = summ = ct1 = ct2 = tt = val1 = val2 = ct = 0;
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]), summ += a[i];
sort(a + 1, a + n + 1);
if (summ % n == 0)
{
val1 = summ / n;
for (int i = 1; i <= n; i++)
req += abs(val1 - a[i]);
if (req <= 2 * k)
{
printf("0\n");
continue;
}
}
else
{
val1 = summ / n;
val2 = val1 + 1;
ct2 = summ % n;
ct1 = n - ct2;
for (int i = 1; i <= ct1; i++)
req += abs(val1 - a[i]);
for (int i = n; i > ct1; i--)
req += abs(val2 - a[i]);
if (req <= 2 * k)
{
printf("1\n");
continue;
}
}
for (int i = 1; i <= n; i++)
{
if (a[i] == a[i - 1])
p[ct].num++;
else
p[++ct].val = a[i], p[ct].num = 1;
}
for (int i = 1; i <= ct; i++)
{
sum[i] = sum[i - 1] + p[i].num;
}
int ans = a[n] - a[1], pt1 = 1, pt2 = ct, temk = k;
while (k >= sum[pt1])
{
int tem = min(k / sum[pt1], p[pt1 + 1].val - p[pt1].val);
k -= tem * sum[pt1];
ans -= tem;
//cout<<tem<<" "<<k<<" "<<ans<<endl;
pt1++;
}
k = temk;
while (k >= sum[ct] - sum[pt2 - 1])
{
int tem = min(k / (sum[ct] - sum[pt2 - 1]), p[pt2].val - p[pt2 - 1].val);
k -= tem * (sum[ct] - sum[pt2 - 1]);
ans -= tem;
//cout<<tem<<" "<<k<<" "<<ans<<endl;
pt2--;
}
cout << ans << endl;
}
}
Guanguan’s Happy water
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Mod
{
const ll M, SM;
Mod(ll M) : M(M), SM(sqrt(M) + 0.5) {}
ll qadd(ll &a, ll b) const { return a += b, a >= M ? a -= M : a; } //假如a和b都已经在同余系内，就不必取模了，取模运算耗时很高
ll add(ll a, ll b) const { return qadd(a = (a + b) % M, M); } //考虑a和b不在同余系内甚至为负数的情况
ll mul(ll a, ll b) const { return add(a * b, M); }
ll inv(ll a) const { return pow(a, M - 2); } //要求M为素数，否则return pow(a, phi(M) - 1);
ll pow(ll a, ll b) const
{
ll r = 1;
for (a = add(a, M); b; b >>= 1, a = mul(a, a))
if (b & 1)
r = mul(r, a);
return r;
}
/*
ll mul(ll a, ll b) const { return add(a * b, -M * ll((long double)a / M * b)); }
ll mul(ll a, ll b) const //无循环快速计算同余乘法，根据a*b是否爆ll替换a*b%M，需要a<M且b<M，可以调用时手动取模
{
ll c = a / SM, d = b / SM;
a %= SM, b %= SM;
ll e = add(add(a * d, b * c), c * d / SM * (SM * SM - M));
return add(add(a * b, e % SM * SM), add(c * d % SM, e / SM) * (SM * SM - M));
}
ll inv(ll a) const
{ //模m下a的乘法逆元，不存在返回-1（m为素数时a不为0必有逆元）
ll x, y, d = gcd(a, M, x, y);
return d == 1 ? add(x, M) : -1;
}
vector<ll> sol(ll a, ll b) const //解同余方程，返回ax=b(mod M)循环节内所有解
{
vector<ll> ans;
ll x, y, d = gcd(a, M, x, y);
if (b % d)
return ans;
ans.push_back(mul((b / d) % (M / d), x));
for (ll i = 1; i < d; ++i)
ans.push_back(add(ans.back(), M / d));
return ans;
}
ll log(ll a, ll b) const
{
unordered_map<ll, ll> x;
for (ll i = 0, e = 1; i <= SM; ++i, e = mul(e, a))
if (!x.count(e))
x[e] = i;
for (ll i = 0, v = inv(pow(a, SM)); i <= SM; ++i, b = mul(b, v))
if (x.count(b))
return i * SM + x[b];
return -1;
}
*/
} M(1e9 + 7);
ll t, k, n, a[255];
int main()
{
for (scanf("%lld", &t); t--;)
{
scanf("%lld%lld", &k, &n);
for (int i = 0; i < k * 2; ++i)
scanf("%lld", &a[i]);
if (n <= k)
{
ll ans = 0;
for (int i = 0; i < n; ++i)
ans = M.add(ans, a[i]);
printf("%lld\n", ans);
continue;
}
ll ans = 0, sum = 0;
for (int i = 0; i < k; ++i)
ans = M.add(ans, a[i]), sum = M.add(sum, a[i + k]);
M.qadd(ans, M.mul(sum, (n - k) / k % M.M));
n %= k;
for (int i = 0; i < n; ++i)
ans = M.add(ans, a[i + k]);
printf("%lld\n", ans);
}
}