widsnoy's blog

ZJOI2016 小星星

发表于 2020-10-21 更新于 2023-12-07 分类于题解

题目链接

感觉是第一次入手容斥原理 (?)

小Y是一个心灵手巧的女孩子，她喜欢手工制作一些小饰品。她有$n$颗小星星，用$m$条彩色的细线串了起来，每条细线连着两颗小星星。有一天她发现，她的饰品被破坏了，很多细线都被拆掉了。这个饰品只剩下了$n−1$条细线，但通过这些细线，这颗小星星还是被串在一起，也就是这些小星星通过这些细线形成了树。小Y找到了这个饰品的设计图纸，她想知道现在饰品中的小星星对应着原来图纸上的哪些小星星。如果现在饰品中两颗小星星有细线相连，那么要求对应的小星星原来的图纸上也有细线相连。小Y想知道有多少种可能的对应方式。只有你告诉了她正确的答案，她才会把小饰品做为礼物送给你呢。

抽象化的题意：用$1\sim n$的排列给树上节点编号，有树边$(u,v)$的两个端点编号$p-u,p-v$在原图上也要有一条边。

最暴力的方法是枚举全排列，然后去验证合不合法。

可以把全排列变成枚举子集，树形$dp$暴力合并。

状态设置为$dp[i][j][s]$，数值表示编号的方案数。

第二维是为了满足转移的时候$u,v$直接有边。
第三维是子树中用了的点的编号，目的是保证最后选出的是一个排列

可以用容斥原理去掉第三维。

钦定可以用的点，然后计算方案数，容斥原理得出全集的答案。

阅读全文 »

「LibreOJ β Round

发表于 2020-10-20 更新于 2023-12-07 分类于题解

「LibreOJ β Round #2」DP 一般看规律

感觉题目不是很难，不过代码技巧学习了。

把所有数按颜色插入到$\text{set}$里面，每次合并的时候对于每个数只有前驱或者后缀会产生答案。

所以合并的时候更新下答案就可以了。

这个$\text{map<int,set<int>>}$学到了啊，相当于每个下标都对应了一个$\text{set}$，也就是开了多个$\text{set}$，并且是动态申请的。

#include <bits/stdc++.h>
using namespace std;

map<int, set<int> > m;
int n, q, ans = 2147483647;

void find(int s, int x) {
    auto it = m[s].lower-bound(x);
    if (it != m[s].end()) ans = min(ans, *it - x);
    if (it != m[s].begin()) ans = min(ans, x - *--it);
}

int main() {
    scanf("%d %d", &n, &q);
    for (int i = 1, x; i <= n; i++) {
    	scanf("%d", &x);
    	m[x].insert(i);
    }
    for (; q--; ) {
    	int x, y;
    	scanf("%d %d", &x, &y);
    	if (x == y) printf("%d\n", ans);
    	else {
            for (auto it = m[x].begin(); it != m[x].end(); ++it) {
            	find(y, *it);
            	m[y].insert(*it);
            }
            m[x].clear();
            printf("%d\n", ans);
    	}
    }
    return 0;
}

SUMCUBE 立方和

发表于 2020-10-20 更新于 2023-12-07 分类于题解

题目链接

$k$次方的组合意义是有顺序的选出$k$条边，统计在多少个子图中出现。

k=1

考虑每条边的贡献。

答案显然是$m*2^{n-2}$

k=2

可能选出相同的边，对应$k=1$

有可能不同，考虑三种情况。

上
两条边三个点，$A\rightarrow B\rightarrow C$，枚举一条边$(s,t)$，$(deg-s-1)+(deg-t-1)$
两条边四个点，$A\rightarrow B$,$C\rightarrow D$，总方案数减去上面的，$m^2-①-②$

k=3

阅读全文 »

20联赛集训day7

发表于 2020-10-20 更新于 2023-12-07 分类于测试

rdx是真的牛逼

题面

A. [20联赛集训day7]稻草富翁

看一下转一轮后会不会增加数。

注意一下等于$0$的情况。

#include <bits/stdc++.h>
using namespace std;

int a, b, c, d, e, f;
bool check() {
    if (d == 0) return 0;
    if (c == 0) return 1;
    if (b == 0) return 0;
    if (a == 0) return 1;
    if (f == 0) return 0;
    if (e == 0) return 1;
    return b * 1ll * d * 1ll * f > a * 1ll * c * 1ll * e;
}

int main() {
    int -;
    for (scanf("%d", &-); -; ---) {
    	scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &f);
        bool pd = check();
        if (pd) puts("MEI");
        else puts("FON");
    }
    return 0;
}

B. [20联赛集训day7]序列

区间加就差分，对操作也差分。

无非就是要知道某个操作做了多少次，倒着差分就可以了。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 4, MOD = 1e9 + 7;
int n, q, a[N], b[N];

struct data {
	int op, l, r;
} now[N];

int main() {
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= q; i++) scanf("%d %d %d", &now[i].op, &now[i].l, &now[i].r);
    b[q + 1] = 1;
    for (int i = q; i >= 1; i--) {
    	b[i] = (b[i + 1] + b[i]) % MOD;
        if (now[i].op == 1) {
        	a[now[i].l] = (a[now[i].l] + b[i]) % MOD;
        	a[now[i].r + 1] = ((a[now[i].r + 1] - b[i]) % MOD + MOD) % MOD;
        } else {
        	b[now[i].r] = (b[now[i].r] + b[i]) % MOD;
        	b[now[i].l - 1] = ((b[now[i].l - 1] - b[i]) % MOD + MOD) % MOD;
        }
    }
    for (int i = 1; i <= n; i++) {
    	a[i] = (a[i - 1] + a[i]) % MOD;
    	printf("%d ", a[i]);
    }
    return putchar('\n'), 0;
}

阅读全文 »

20联赛集训day6

发表于 2020-10-19 更新于 2023-12-07 分类于测试

莫名其妙的混了一个上午

卷

众所周知，集训队作业一下发，队员们立刻开始了卷卷卷的日子。

qjd 作为国家队的候选人之一，当然要争当卷王。于是他把这一堆集训队作业摆成了一个树状结构，第一天他就打算做一大批集训队作业题。

然而如果做的两个集训队作业题在树上有直接连边（即在树上相邻），那么 qjd 就会感觉非常不爽从而出 $114514$ 个多项式毒瘤题扔给大家做。

小 w 非常不希望这样的事情发生，~~为了拯救世界~~，他主动要求帮助 qjd 选择一些集训队作业题做。可是 qjd 是有要求的，他给每个题目定义了一个难度 $w-i$，小 w 要让选出题的难度之积尽量大。

简要地说，给定一棵树，你需要求出最大乘积独立集。

由于答案很大，你只需要输出答案 $\bmod 10^9+7$ 的结果即可。

此外，你可以认为 $w-i$ 是在给定范围内随机生成的.

最开始抄了个高精度，好像不怎么行...

阅读全文 »

2020.10.17 T3 pig

发表于 2020-10-18 更新于 2023-12-07 分类于测试

题目

小七养了很多头猪，它们分布在 $n$ 行 $m$ 列中，其中第 $i$ 行第 $j$ 列的猪圈养的是第 $w_{i,j}$ 种猪。小七有时会选择一个子矩形范围内的猪圈进行巡视，如果该子矩形包含 $i $行 $j $列 $(1 ≤ i ≤ n, 1 ≤ j ≤ m)$，且子矩形内含有的猪种类编号最大值减去编号最小值恰好为 $i × j-1$ ，则小七会获得 $i × j$ 的愉悦值。

小七想知道，如果他将每个可能的子矩形都巡视一次，总共能获得多少愉悦值呢？你只需要输出答案对 $998244353$ 取模的结果。

分析

考虑判定权值在区间 $[l,r]$ 内的所有数所在的格子是否形成了一个矩形，记这些格子的颜色为黑色，其它的格子颜色为白色。

考虑所有的 $(n + 1) × (m + 1)$ 个 $2 × 2$ 的小正方形 (部分超出边界也算)，则所有黑色格子形成一个矩形，当且仅当恰好有 $4$ 个小正方形内部有 $1$ 个黑色格子，并且没有任何一个小正方形内部有 $3$ 个黑色格子。

从小到大枚举 $r$ ，对每个 $l ≤ r$ ，记 $f(l)$ 表示染黑权值在 $[l,r]$ 内的格子后，有多少小正方形内部有 $1$ 个或 $3$ 个黑色格子。

可以发现有 $f(l) ≥ 4, f(r) = 4 $，于是只需要对每个 $l$ 维护 $f(l)$ 最小值，最小值的数目和取得最小值的所有 $l$ 之和。

每次 $r$ 增加 $1$ 时，会影响到周边的 $4 $个 $2×2$ 的小正方形，在线段树上修改即可。

时间复杂度 $O(nm log nm)$ ，期望得分 $100$ 分。

阅读全文 »

2020.10.17 T2 fight

发表于 2020-10-18 更新于 2023-12-07 分类于测试

题目

小七擅长泰拳，某天他打算与小枣切磋拳技，一共需要进行 $n$ 次比赛。

由于双方拳技难分上下，每场比赛小七获胜或落败的概率都是 $\dfrac{1}{p+2}$ ，平局的概率是 $\dfrac{p}{p+2}$ 。若最后小七获胜场数大于落败场次，且平局次数为$ k$ ，则能获得 $k + 1$ 奖励分。

小七想知道，他能获得的奖励分的期望是多少呢？为了避免精度误差，你需要输出答案在模 $998244353$ 意义下的结果。

分析

为了方便，可以假定胜，负各有 $1$ 种方案，平局有 $p$ 种方案，最后将答案乘上$(p + 2)^{-n} $即可。

枚举有 $i$ 次胜或负，有 $n-i$ 场平局，此时胜场大于负场的方案数是 $(x + x^{-1})^i$展开后次数 $> 0$ 的项系数之和，即 $(x^2 + 1)^i$ 展开后次数$ > i$ 的项系数之和。

将 $(x^2 + 1)^i$ 用二项式定理直接展开并计算答案，时间复杂度 $O(n^2)$ ，期望得分$40$ 分。

考虑优化计算 $(x^2 + 1)^i$ 展开后次数 $> i$ 的项系数之和，记其为 $t(i)$。

阅读全文 »

HAOI2018 奇怪的背包

发表于 2020-10-18 更新于 2023-12-07 分类于题解

「HAOI2018」奇怪的背包

其实这题和背包一点关系都没有。

题目要求解方程的解数，

\[\sum x-ia-i\equiv w\pmod p\]

根据裴蜀定理，方程有解当且仅当$\gcd(a-1,a-2,\cdots,a-n,p)\mid w$

于是设$f[i][j]$表示前$i$个数的与$p$的最大公约数是$j$时的方案数，转移只需要枚举当前这个选不选，不需要考虑具体选了多少个。

因为$p$的约数个数不多，我们应该开一个数组映射一下$p$的约数作为转移状态的第二维。

如果两个物体和$p$的$\gcd$相等的话，我们可以把它们一起转移，只需要乘上一个非空子集个数的系数就可以了。

最后统计答案，其实我们要统计的是$\sum_{i\mid w}f[m][i]$，$m$是$p$约数个数

即$i\mid p \wedge i\mid w$，相当于$i\mid \gcd(p,w)$

阅读全文 »

整数分解为2的幂

发表于 2020-10-18 更新于 2023-12-07 分类于题解

题号是$\text{51nod}$ 1383和1048

$n\le 10^6$

这档分$O(n\log n)$或者$O(n)$都可以。

$\log$的是用$2$的幂跑一次完全背包

线性的考虑每个数从为空的序列开始是通过$+1$或者集体$\times 2$得到的。

$f[i]=(i\&1)?0:f[i/2]+f[i-1]$

$n\le 10^{30}$

我们先考虑每个二的整数幂有多少种方法凑出来。

$f[i][j]$表示最大数是$2^j$的数凑出$2^i$的方案数。

如果$f[i][j]=\sum_{k=0}^jf[i-1][k]\times f[i-1][j]$

阅读全文 »

Amount of Degrees

发表于 2020-10-14 更新于 2023-12-07 分类于题解

Amount of Degrees
这篇博客是来贴代码的，真正的题解看这里

#include <bits/stdc++.h>
using namespace std;

const int N = 32;
int f[N][N], k, b, l, r, a[N];

int solve(int x) {
	int ans = 0, tot = 0;
	for (int i = 31; i; i--) {
		if (x & (1 << i)) {
            tot++;
            if (tot > k) break;
            x ^= (1 << i);
		}
		if (x >= (1 << (i - 1))) ans += f[i - 1][k - tot];
	}
	if (tot + x == k) ans++;
	return ans;
}

int calc(int x, int b) {
	int cnt = 0;
	while (x) {
		a[cnt++] = x % b;
		x /= b;
	}
	int res = 0;
	for (int i = cnt - 1; i + 1; i--) {
        if (a[i] > 1) {
            for (int j = i; j + 1; j--) res |= (1 << j);
        } else res |= (a[i] << i);
	}
	return res;
}

int main() {
    scanf("%d %d %d %d", &l, &r, &k, &b);
    f[0][0] = 1;
    for (int i = 1; i < N; i++) {
    	f[i][0] = 1;
    	for (int j = 1; j <= i; j++) f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
    }
    printf("%d\n", solve(calc(r, b)) - solve(calc(l - 1, b)));
    return 0;
}

widsnoy's blog

ZJOI2016 小星星

「LibreOJ β Round

SUMCUBE 立方和

k=1

k=2

k=3

20联赛集训day7

A. [20联赛集训day7]稻草富翁

B. [20联赛集训day7]序列

20联赛集训day6

卷

2020.10.17 T3 pig

题目

分析

2020.10.17 T2 fight

题目

分析

HAOI2018 奇怪的背包

整数分解为2的幂

\(n\le 10^6\)

\(n\le 10^{30}\)

Amount of Degrees