A Knight
留坑。
B Tree
思路：两次树形DP，但是要考虑0没有逆元
可以用前缀后缀做
#include <bits/stdc++.h>
using namespace std; #define N 1000010
#define ll long long const ll MOD = (ll)1e9 + ; int n;
ll dp[N], dp2[N];
ll prefix[N], suffix[N];
vector <int> G[N]; void Init()
{
for (int i = ; i <= n; ++i) dp[i] = , dp2[i] = , G[i].clear();
} void DFS(int u, int fa)
{
for (auto v : G[u])
{
if (v == fa) continue;
DFS(v, u);
dp[u] = dp[u] * (dp[v] + ) % MOD;
}
} void DFS2(int u, int fa)
{
prefix[] = ;
suffix[G[u].size() + ] = ;
int len = G[u].size();
for (int i = ; i < len; ++i)
{
int v = G[u][i];
if (v == fa) prefix[i + ] = prefix[i];
else prefix[i + ] = prefix[i] * (dp[G[u][i]] + ) % MOD;
}
for (int i = len - ; i >= ; --i)
{
int v = G[u][i];
if (v == fa) suffix[i + ] = suffix[i + ];
else suffix[i + ] = suffix[i + ] * (dp[G[u][i]] + ) % MOD; }
for (int i = ; i < len; ++i)
{
int v = G[u][i];
if (v == fa) continue;
dp2[v] = prefix[i] % MOD * suffix[i + ] % MOD * (dp2[u] + ) % MOD;
}
for (auto v : G[u])
{
if (v == fa) continue;
DFS2(v, u);
}
} void Run()
{
while (scanf("%d", &n) != EOF)
{
Init();
for (int i = , u, v; i < n; ++i)
{
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
DFS(, ); DFS2(, );
for (int i = ; i <= n; ++i) printf("%lld\n", dp[i] * (dp2[i] + ) % MOD);
}
} int main()
{
#ifdef LOCAL
freopen("Test.in", "r", stdin);
#endif Run();
return ;
}
C Two Graphs
留坑。
D Shopping
贪心即可。
#include <bits/stdc++.h>
using namespace std; #define N 1010 int t, n, m;
int arr[N], res; int main()
{
scanf("%d", &t);
while (t--)
{
res = ;
scanf("%d%d", &n, &m);
for (int i = , b; i <= n; ++i)
{
scanf("%d%d", arr + i, &b);
if (b) ++res;
}
sort(arr + , arr + + n);
res = min(res, m);
double ans = ;
for (int i = n; i >= ; --i, --res)
ans += res > ? arr[i] * 1.0 / : arr[i];
printf("%.1f\n", ans);
}
return ;
}
E Trophies
留坑。
F Palindrome
留坑。
G Stones
留坑。
H Travel
思路：隔板法，一条边相当于划成两个区域。
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 100010 const ll MOD = (ll)1e9 + ; ll fac[N]; void Init()
{
fac[] = ;
for (int i = ; i < N; ++i) fac[i] = fac[i - ] * i % MOD;
} ll qpow(ll base, ll n)
{
ll res = ;
while (n)
{
if (n & ) res = res * base % MOD;
base = base * base % MOD;
n >>= ;
}
return res;
} ll C(ll n, ll m)
{
if (m > n) return ;
return fac[n] * qpow(fac[m] * fac[n - m] % MOD, MOD - ) % MOD;
} int t, n, m; int main()
{
Init();
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &m);
for (int i = , a, b; i < n; ++i) scanf("%d%d", &a, &b);
printf("%lld\n", C(n - , m - ) * fac[m] % MOD);
}
return ;
}
I Metropolis
思路：将所有大都会都放到最短路去跑多源最短路，记录每个点的最短路是由哪个点扩展而来
显然，如果一个点源点i扩展到一个点j， 而点j又已经被点k扩展了，那么就没有必要扩展下去
我们在枚举每一条边，更新答案
#include <bits/stdc++.h>
using namespace std; #define N 200010
#define ll long long
#define INFLL 0x3f3f3f3f3f3f3f3f struct Edge
{
int to, nx; ll w;
Edge() {}
Edge(int to, int nx, ll w) : to(to), nx(nx), w(w) {}
}edge[N << ]; int n, m, p;
int head[N], pos;
int x[N], Belong[N];
ll dis[N], ans[N]; void addedge(int u, int v, ll w)
{
edge[++pos] = Edge(v, head[u], w); head[u] = pos;
} struct node
{
ll w; int u, v;
node() {}
node(int u, int v, ll w) : u(u), v(v), w(w) {}
bool operator < (const node &r) const
{
return w > r.w;
}
}; priority_queue <node> q; void Init()
{
memset(head, -, sizeof head);
pos = ;
while (!q.empty()) q.pop();
memset(Belong, , sizeof Belong);
memset(ans, 0x3f, sizeof ans);
} void Dijkstra()
{
while (!q.empty())
{
node top = q.top(); q.pop();
if (Belong[top.v]) continue;
Belong[top.v] = top.u;
dis[top.v] = top.w;
for (int it = head[top.v]; ~it; it = edge[it].nx)
{
int v = edge[it].to;
q.emplace(top.u, v, top.w + edge[it].w);
}
}
} void Run()
{
while (scanf("%d%d%d", &n, &m, &p) != EOF)
{
Init();
for (int i = ; i <= p; ++i)
{
scanf("%d", x + i);
q.emplace(x[i], x[i], );
}
for (int i = , u, v, w; i <= m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
addedge(u, v, w);
addedge(v, u, w);
}
Dijkstra();
for (int u = ; u <= n; ++u)
{
for (int it = head[u]; ~it; it = edge[it].nx)
{
int v = edge[it].to;
ll w = edge[it].w;
if (Belong[u] == Belong[v]) continue;
ans[Belong[u]] = min(ans[Belong[u]], dis[u] + dis[v] + w);
ans[Belong[v]] = min(ans[Belong[v]], dis[u] + dis[v] + w);
}
}
for (int i = ; i <= p; ++i) printf("%lld%c", ans[x[i]], " \n"[i == p]);
}
} int main()
{
#ifdef LOCAL
freopen("Test.in", "r", stdin);
#endif Run();
return ;
}
J Graph Coloring I
思路：对于一张图，如果没有奇圈，那么肯定可以用两种颜色进行染色，那么肯定有解
只要去找奇圈即可。
#include <bits/stdc++.h>
using namespace std; #define N 300010 int n, m;
vector <int> G[N], ans;
int deep[N], fa[N];
bool flag; void DFS(int u)
{
if (flag) return;
for (auto v : G[u])
{
if (flag) return;
if (v == fa[u]) continue;
if (fa[v] != - && !flag)
{
if ((deep[u] - deep[v]) % == )
{
ans.push_back(u);
while (u != v)
{
u = fa[u];
ans.push_back(u);
}
flag = true;
return;
}
}
else
{
fa[v] = u;
deep[v] = deep[u] + ;
DFS(v);
}
}
} void Init()
{
for (int i = ; i <= n; ++i) G[i].clear();
ans.clear();
memset(fa, -, sizeof fa);
deep[] = ;
flag = false;
} int main()
{
while (scanf("%d%d", &n, &m) != EOF)
{
Init();
for (int i = , u, v; i <= m; ++i)
{
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
DFS();
if (flag)
{
printf("%d\n", (int)ans.size());
for (int i = , len = ans.size(); i < len; ++i) printf("%d%c", ans[i], " \n"[i == len - ]);
}
else
{
puts("");
for (int i = ; i <= n; ++i) printf("%d%c", deep[i] & , " \n"[i == n]);
}
}
return ;
}
K Graph Coloring II
留坑。