「HAOI2015」树上染色
题意
有一棵点数为 \(N\) 的树,树边有边权。给你一个在 \(0 \sim N\) 之内的正整数 \(K\),你要在这棵树中选择 \(K\) 个点,将其染成黑色,并将其他的 \(N-K\) 个点染成白色。将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。
问收益最大值是多少。
\(N \leq 2000, \ 0 \leq K \leq N\)
题解
树上距离,我们要么考虑差分深度,要么考虑一条边对于多少个点对进行贡献。
前者显然是不好考虑的,可以考虑后者。
令 \(f_{i, j}\) 为 \(i\) 子树内有 \(j\) 个黑点的最优答案。不难发现这个直接做一个树上背包即可,背包的权值就是这条边被多少对同色点对穿过乘上这条边的权值。
由于树上两点在 \(lca\) 贡献一次复杂度,那么复杂度是 \(\mathcal O(n ^ 2)\) 的。
代码
#include <bits/stdc++.h>
#define For(i, l, r) for (register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for (register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Rep(i, r) for (register int i = (0), i##end = (int)(r); i < i##end; ++i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl
using namespace std;
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }
inline int read() {
int x(0), sgn(1); char ch(getchar());
for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
return x * sgn;
}
void File() {
#ifdef zjp_shadow
freopen ("2124.in", "r", stdin);
freopen ("2124.out", "w", stdout);
#endif
}
const int N = 2010, M = N << 1;
using ll = long long;
int n, K;
ll dp[N][N], tmp[N];
int Head[N], Next[M], to[M], val[M], e = 0;
inline void add_edge(int u, int v, int w) {
to[++ e] = v; Next[e] = Head[u]; val[e] = w; Head[u] = e;
}
int sz[N];
void Dfs(int u, int fa = 0) {
for (int i = Head[u], v = to[i]; i; v = to[i = Next[i]])
if (v != fa) {
Dfs(v, u); Set(tmp, 0);
For (j, 0, min(K, sz[u])) For (k, 0, min(K, sz[v])) {
int Pair = k * (K - k) +
(sz[v] - k) * ((n - K) - (sz[v] - k));
chkmax(tmp[j + k], dp[u][j] + dp[v][k] + 1ll * Pair * val[i]);
}
Cpy(dp[u], tmp); sz[u] += sz[v];
}
Fordown (i, min(K, ++ sz[u]), 0)
dp[u][i] = max(i ? dp[u][i - 1] : 0ll, dp[u][i]);
}
int main () {
File();
n = read(); K = read();
For (i, 1, n - 1) {
int u = read(), v = read(), w = read();
add_edge(u, v, w); add_edge(v, u, w);
}
Dfs(1);
printf ("%lld\n", dp[1][K]);
return 0;
}
「HAOI2015」树上操作
题意
有一棵点数为 \(N\) 的树,以点 \(1\) 为根,且树有点权。然后有 \(M\) 个操作,分为三种:
- 把某个节点 \(x\) 的点权增加 \(a\) 。
- 把某个节点 \(x\) 为根的子树中所有点的点权都增加 \(a\) 。
- 询问某个节点 \(x\) 到根的路径中所有点的点权和。
\(N,M \leq 10^5\)
题解
树剖裸题,没什么好说的,复杂度是 \(\mathcal O(n \log^2 n)\) 。
代码
#include <bits/stdc++.h>
#define For(i, l, r) for (register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for (register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Rep(i, r) for (register int i = (0), i##end = (int)(r); i < i##end; ++i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl
using namespace std;
using ll = long long;
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }
inline int read() {
int x(0), sgn(1); char ch(getchar());
for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
return x * sgn;
}
void File() {
#ifdef zjp_shadow
freopen ("2125.in", "r", stdin);
freopen ("2125.out", "w", stdout);
#endif
}
const int N = 2e5 + 1e3;
int n;
#define lowbit(x) (x & -x)
template<int Maxn>
struct Fenwick_Tree {
ll sum1[Maxn], sum2[Maxn];
inline void Add(int pos, int uv) {
for (int tmp = pos; pos <= n; pos += lowbit(pos))
sum1[pos] += uv, sum2[pos] += 1ll * tmp * uv;
}
ll Sum(int pos) {
ll res = 0;
for (int tmp = pos; pos; pos -= lowbit(pos))
res += 1ll * (tmp + 1) * sum1[pos] - sum2[pos];
return res;
}
inline void Update(int ul, int ur, int val) {
Add(ul, val); if (ur < n) Add(ur + 1, -val);
}
inline ll Query(int ql, int qr) {
return Sum(qr) - Sum(ql - 1);
}
};
Fenwick_Tree<N> T;
int dep[N], fa[N]; vector<int> G[N];
int son[N], sz[N];
void Dfs_Init(int u, int from) {
sz[u] = 1;
dep[u] = dep[fa[u] = from] + 1;
for (int v : G[u]) if (v != from) {
Dfs_Init(v, u); sz[u] += sz[v];
if (sz[v] > sz[son[u]]) son[u] = v;
}
}
int dfn[N], efn[N], top[N];
void Dfs_Part(int u) {
static int clk = 0; dfn[u] = ++ clk;
top[u] = son[fa[u]] == u ? top[fa[u]] : u;
if (son[u]) Dfs_Part(son[u]);
for (int v : G[u]) if (v != son[u] && v != fa[u]) Dfs_Part(v);
efn[u] = clk;
}
int val[N];
int main () {
File();
n = read(); int m = read();
For (i, 1, n) val[i] = read();
For (i, 1, n - 1) {
int u = read(), v = read();
G[u].push_back(v); G[v].push_back(u);
}
Dfs_Init(1, 0); Dfs_Part(1);
For (i, 1, n) T.Update(dfn[i], dfn[i], val[i]);
For (i, 1, m) {
int opt = read(), x = read();
if (opt <= 2)
T.Update(dfn[x], opt == 1 ? dfn[x] : efn[x], read());
if (opt == 3) {
ll ans = 0;
for (int u = x; u; u = fa[top[u]])
ans += T.Query(dfn[top[u]], dfn[u]);
printf ("%lld\n", ans);
}
}
return 0;
}
「HAOI2015」数组游戏
题意
有一个长度为 \(N\) 的数组,甲乙两人在上面进行这样一个游戏:首先,数组上有一些格子是白的,有一些是黑的。然后两人轮流进行操作。每次操作选择一个白色的格子,假设它的下标为 \(x\) 。接着,选择一个大小在 \(1 \sim n / x\) 之间的整数 \(k\),然后将下标为 \(x\)、\(2x\)、...、\(kx\) 的格子都进行颜色翻转。不能操作的人输。
现在甲(先手)有一些询问。每次他会给你一个数组的初始状态,你要求出对于这种初始状态他是否有必胜策略。
\(N \leq 1000000000\),\(K,W \leq 100\)
题解
这是个经典的翻硬币游戏,可以参考一下 Candy? 的博客 。
每一个硬币可以看成独立的子游戏,所以:
局面的 \(SG\) 值为局面中每个正面朝上的棋子单一存在时的 \(SG\) 值的异或和。
令 \(SG(x)\) 为第 \(x\) 位为白的时候的 \(SG\) 值,那么有
\]
这个直接暴力做是 \(\mathcal O(n \ln n)\) 的。
\(SG\) 函数通常考虑的优化就是找规律,打打表,不难发现:
\(\forall i, j\) 如果有 \(\displaystyle \lfloor \frac{n}{i} \rfloor = \lfloor \frac{n}{j} \rfloor\) 那么有 \(SG(i) = SG(j)\) 。
这个直接上整除分块就好了,然后枚举倍数的时候只需要枚举在分的块中的数,复杂度好像是 \(\mathcal O(n^{3/ 4})\) 的。
总结
翻硬币问题是一种经典的 nim
问题,可以设 \(SG\) 函数。
代码
#include <bits/stdc++.h>
#define For(i, l, r) for (register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for (register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Rep(i, r) for (register int i = (0), i##end = (int)(r); i < i##end; ++i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl
using namespace std;
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }
inline int read() {
int x(0), sgn(1); char ch(getchar());
for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
return x * sgn;
}
void File() {
#ifdef zjp_shadow
freopen ("2126.in", "r", stdin);
freopen ("2126.out", "w", stdout);
#endif
}
const int N = 1e5 + 1e3;
int n, d, k, sg[N], App[N];
int id1[N], id2[N], clk = 0;
#define id(x) (x <= d ? id1[x] : id2[n / (x)])
int main () {
File();
n = read();
d = sqrt(n + .5);
for (int i = 1; i <= n; i = n / (n / i) + 1) {
int x = n / i, v = 0; id(n / i) = App[0] = ++ clk;
for (int j = x << 1, nextj; j <= n; j = nextj + x) {
nextj = (n / (n / j)) / x * x;
App[v ^ sg[id(j)]] = clk;
if (((nextj - j) / x + 1) & 1) v ^= sg[id(j)];
}
while (App[sg[id(x)]] == clk) ++ sg[id(x)];
}
int cases = read();
while (cases --) {
int res = 0;
For (i, 1, read()) {
int x = read(); res ^= sg[id(x)];
}
puts(res ? "Yes" : "No");
}
return 0;
}
「HAOI2015」按位或
题意
刚开始你有一个数字 \(0\),每一秒钟你会随机选择一个 \([0,2^n-1]\) 的数字,与你手上的数字进行或操作。选择数字 \(i\) 的概率是 \(p[i]\) 问期望多少秒后,你手上的数字变成 \(2^n-1\)。
\(n \le 20\) 。
题解
似乎有强行推式子的做法。。。但是我好像不会 QAQ
但类似于这种无限期望,每个时刻会随机出现其中一些元素,到所有元素都出现的期望计算一般都可以用 \(\min-\max\) 容斥做。
即原问题是求集合中最晚的元素的期望,利用最值反演就变成求集合中最早元素的期望,即
\]
然后有
\]
我们就只需要对于每个 \(S\) 求 \(\sum_{T \cap S \not = \varnothing} P[T]\) 了。
这个直接取补集,考虑补集的子集和就行了,即
\]
利用 \(\text{FMT}\) 就可以做到 $\mathcal O(n \times 2^n) $ 的复杂度。
总结
把 \(\min - \max\) 当做一个黑箱来用比较好。
代码
一开始蠢了,那个补集子集和没想到,利用容斥求得并不为空的贡献。。。
#include <bits/stdc++.h>
#define For(i, l, r) for (register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for (register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Rep(i, r) for (register int i = (0), i##end = (int)(r); i < i##end; ++i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl
using namespace std;
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }
inline int read() {
int x(0), sgn(1); char ch(getchar());
for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
return x * sgn;
}
void File() {
#ifdef zjp_shadow
freopen ("2127.in", "r", stdin);
freopen ("2127.out", "w", stdout);
#endif
}
const int N = 1 << 20;
const double eps = 1e-8;
int n, maxsta; double p[N], prob[N], sum[N];
void FMT(double *f) {
Rep (j, n) Rep (i, maxsta)
if (i >> j & 1) f[i] += f[i ^ (1 << j)];
}
int main () {
File();
n = read(); maxsta = 1 << n; int all = maxsta - 1;
int cur = 0;
Rep (i, maxsta) {
scanf ("%lf", &p[i]);
if (p[i] > eps) cur |= i;
}
if (cur != maxsta - 1) return puts("INF"), 0;
Rep (i, maxsta) sum[i] = p[all ^ i]; FMT(sum);
Rep (i, maxsta) if (i)
prob[i] = sum[all ^ i] * (__builtin_popcount(i) & 1 ? 1 : -1);
FMT(prob);
double ans = .0;
Rep (i, maxsta) if (i)
ans += (__builtin_popcount(i) & 1 ? 1 : -1) / prob[i];
printf ("%.7lf\n", ans);
return 0;
}
「HAOI2015」数字串拆分
题意
你有一个长度为 \(n\) 的数字串。定义 \(f(S)\) 为将 \(S\) 拆分成若干个 \(1\sim m\) 的数的和的方案数。
你可以将这个数字串分割成若干个数字(允许前导 \(0\) ),将他们加起来,求 \(f\) 的和。已知字符串和 \(m\) 后求答案,对 \(998244353\) 取模。
字符串长度不超过 \(500\),\(m \leq 5\)
题解
首先要解决的问题就是给定一个字符串 \(S\) 如何快速求 \(f(S)\) ,注意到 \(m\) 很小,而 \(S\) 很大,不难想到矩阵快速幂。
转移是很显然的 \(f(S) = \sum_{i = 1}^m f(S - i)\) ,搞个矩阵作为转移系数。
然后令 \(dp_i\) 为以 \(i\) 结尾的答案矩阵,转移显然 \(dp_i = \sum_{j < i} dp_j \times trans_{j \sim i}\) 。
我们唯一要处理的就是 \(trans_{j \sim i}\) ,可以利用二进制下矩阵快速幂解决,但显然高精度十进制转二进制很不方便。可以考虑直接预处理关于十进制的矩阵幂就行了。
复杂度是 \(\mathcal O(|S|^2m^3)\) 的。
总结
有时候不一定要纠结着二进制,可能没有那么好解决,十进制是一种不错的方案。
代码
#include <bits/stdc++.h>
#define For(i, l, r) for (register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for (register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Rep(i, r) for (register int i = (0), i##end = (int)(r); i < i##end; ++i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl
using namespace std;
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }
inline int read() {
int x(0), sgn(1); char ch(getchar());
for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
return x * sgn;
}
void File() {
#ifdef zjp_shadow
freopen ("2128.in", "r", stdin);
freopen ("2128.out", "w", stdout);
#endif
}
const int N = 510, M = 7, Mod = 998244353;
char str[N]; int m;
struct Matrix {
int a[M][M];
Matrix() { Set(a, 0); }
void Unit() { For (i, 1, m) a[i][i] = 1; }
inline Matrix friend operator * (const Matrix &lhs, const Matrix &rhs) {
Matrix res;
For (i, 1, m) For (k, 1, m) For (j, 1, m)
res.a[i][k] = (res.a[i][k] + 1ll * lhs.a[i][j] * rhs.a[j][k]) % Mod;
return res;
}
inline Matrix friend operator + (const Matrix &lhs, const Matrix &rhs) {
Matrix res;
For (i, 1, m) For (j, 1, m)
res.a[i][j] = (lhs.a[i][j] + rhs.a[i][j]) % Mod;
return res;
}
};
Matrix trans[N][10], Base, f[N];
int dp[N];
int main () {
File();
scanf ("%s", str + 1); m = read();
int n = strlen(str + 1);
For (i, 1, m - 1) Base.a[i][i + 1] = 1;
For (i, 1, m) Base.a[m][i] = 1;
trans[0][0].Unit(); trans[0][1] = Base;
For (i, 2, 9) trans[0][i] = trans[0][i - 1] * Base;
For (i, 1, n) {
trans[i][0].Unit();
trans[i][1] = trans[i - 1][1] * trans[i - 1][9];
For (j, 2, 9) trans[i][j] = trans[i][j - 1] * trans[i][1];
}
dp[0] = 1;
For (i, 1, 10) For (j, 1, min(i, m)) dp[i] += dp[i - j];
For (i, 1, m) f[0].a[i][1] = dp[i - 1];
For (i, 1, n) {
Matrix now; now.Unit();
Fordown (j, i, 1) {
now = now * trans[i - j][str[j] ^ 48];
f[i] = f[i] + now * f[j - 1];
}
}
printf ("%d\n", f[n].a[1][1]);
return 0;
}
HAOI2015 简要题解的更多相关文章
-
Noip 2014酱油记+简要题解
好吧,day2T1把d默认为1也是醉了,现在只能期待数据弱然后怒卡一等线吧QAQ Day0 第一次下午出发啊真是不错,才2小时左右就到了233,在车上把sao和fate补掉就到了= = 然后到宾馆之后 ...
-
Tsinghua 2018 DSA PA2简要题解
反正没时间写,先把简要题解(嘴巴A题)都给他写了记录一下. upd:任务倒是完成了,我也自闭了. CST2018 2-1 Meteorites: 乘法版的石子合并,堆 + 高精度. 写起来有点烦貌似. ...
-
Codeforces 863 简要题解
文章目录 A题 B题 C题 D题 E题 F题 G题 传送门 简要题解?因为最后一题太毒不想写了所以其实是部分题解... A题 传送门 题意简述:给你一个数,问你能不能通过加前导000使其成为一个回文数 ...
-
HNOI2018简要题解
HNOI2018简要题解 D1T1 寻宝游戏 题意 某大学每年都会有一次 Mystery Hunt 的活动,玩家需要根据设置的线索解谜,找到宝藏的位置,前一年获胜的队伍可以获得这一年出题的机会. 作为 ...
-
JXOI2018简要题解
JXOI2018简要题解 T1 排序问题 题意 九条可怜是一个热爱思考的女孩子. 九条可怜最近正在研究各种排序的性质,她发现了一种很有趣的排序方法: Gobo sort ! Gobo sort 的算法 ...
-
BJOI2018简要题解
BJOI2018简要题解 D1T1 二进制 题意 pupil 发现对于一个十进制数,无论怎么将其的数字重新排列,均不影响其是不是 \(3\) 的倍数.他想研究对于二进制,是否也有类似的性质. 于是他生 ...
-
CQOI2018简要题解
CQOI2018简要题解 D1T1 破解 D-H 协议 题意 Diffie-Hellman 密钥交换协议是一种简单有效的密钥交换方法.它可以让通讯双方在没有事先约定密钥(密码)的情况下,通过不安全的信 ...
-
AtCoder ExaWizards 2019 简要题解
AtCoder ExaWizards 2019 简要题解 Tags:题解 link:https://atcoder.jp/contests/exawizards2019 很水的一场ARC啊,随随便便就 ...
-
Comet OJ - Contest #2 简要题解
Comet OJ - Contest #2 简要题解 cometoj A 模拟,复杂度是对数级的. code B 易知\(p\in[l,r]\),且最终的利润关于\(p\)的表达式为\(\frac{( ...
随机推荐
-
asp.net gridview动态添加列,并获取其数据;
1,绑定数据前先动态添加列,见方法CreateGridColumn(只在第一次加载动态添加): 2,gvlist_RowDataBound为对应列添加控件: 前台代码: <%@ Page Lan ...
-
第六十九篇、OC_录制语音和播放语音功能的实现
录制: 1.设置全局属性 NSURL *recordedFile;//存放路径 AVAudioPlayer *player;//播放 AVAudioRecorder *recorder;//录制 NS ...
-
HashMap 与HashTable的区别
我们先看2个类的定义 public class Hashtable extends Dictionary implements Map, Cloneable, java.io.Serializable ...
-
Java项目打包工具安装失败解决方法
在学习Java的时候我们打包项目但遇到例如以下情况:(提示没有找到java的执行环境! ) 网上眼下有两中的解决方式: (1)选择本地jdk环境; (2)下载Download 可是第一种选择本地老是失 ...
-
弹性布局EM的计算方法
文章来源: http://www.w3cplus.com/css/px-to-em 总结: 1.浏览器默认的字体大小为16PX,即1em 2.EM可以指定小数点的后三位 3.元素自身没有设置字体大小, ...
-
Python学习--Python运算符
什么是运算符? 举个简单的例子 4 + 5 = 9 . 例子中,4 和 5 被称为操作数,"+" 称为运算符. Python语言支持以下类型的运算符: 算数运算符 比较(关系)运算 ...
-
win8系统电脑自动关机怎么取消
在使用win8系统的用户会遇到电脑自动关机的情况,这是win8自带的自动关机功能,如果想取消这个功能,只需要通过执行一个命令即可实现.下面小编来为大家讲解一下具体步骤. 1.组合键:win+R,然后在 ...
-
结巴分词和自然语言处理HanLP处理手记
手记实用系列文章: 1 结巴分词和自然语言处理HanLP处理手记 2 Python中文语料批量预处理手记 3 自然语言处理手记 4 Python中调用自然语言处理工具HanLP手记 5 Python中 ...
-
springMVC工程使用jreloader实现热部署
springMVC工程使用jreloader实现热部署applicationContext - ContextLoaderListener重新加载DispatcherServlet 重新加载提高开发效 ...
-
探索Java语言与JVM中的Lambda表达式
Lambda表达式是自Java SE 5引入泛型以来最重大的Java语言新特性,本文是2012年度最后一期Java Magazine中的一篇文章,它介绍了Lamdba的设计初衷,应用场景与基本语法.( ...