WEEK201205

AGC010C

先找个非叶子作为根,(把 \(n=2\) 判掉),然后考虑一个等效次数 \(f(u)\),就是相当于一个节点和儿子必须满足方程:\(\exists\,x:f(u)=a[u]-x=sum-2x\) ,其中 \(x\) 是对当前节点的等效情形的操作次数。这样对于每个经过 \(u\) 的路径就可以合理地分配给各个儿子,从而分配到最后的叶子。于是 dfs 一遍判每个节点的解 \(x\) 是否存在就做完了。

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
// 静かな海
#include <bits/stdc++.h>
#define dbg(x, y...) fprintf(stderr, x, y)
#define pline() (dbg("Passing Line #%d in Func [%s]", __LINE__, __FUNCTION__))
using namespace std;

inline int rd() {
int x=0,c,f=1;while(!isdigit(c=getchar()))if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=x*10+c-'0';return x*f;
}
const int N = 1e5+3;
#define int long long

int n, a[N], f[N], d[N];
vector<int> G[N];

void dfs(int u, int fa) {
if (d[u] == 1) return void(f[u] = a[u]);

int sum = 0, mx = 0;
for (int v:G[u]) if (v^fa) {
dfs(v, u);
sum += f[v], mx = max(mx, f[v]);
}

f[u] = 2*a[u] - sum;
if (a[u] > sum || a[u] < mx || f[u] < 0)
puts("NO"), exit(0);
}

signed main() {
n = rd();
for (int i=1; i<=n; i++) a[i] = rd();
if (n == 2) return 0 * puts(a[1] == a[2] ? "YES" : "NO");
for (int i=1; i<n; i++) {
int u = rd(), v = rd();
G[u].push_back(v), G[v].push_back(u);
d[u]++, d[v]++;
}

int rt;
for (int i=1; i<=n; i++)
if (d[i] > 1) { rt = i; break; }

dfs(rt, 0);

puts(f[rt] ? "NO" : "YES");
}

AGC011D

有点水,推一推或者直接打表都可以发现每次要么第一个数取反要么整体左移并取反, 以至于很快尾部出现 BABA 型循环节,最后把所有数字顶掉,形成 1~2 周期的循环, 于是 bitset 暴力模拟一下即可。

不知道为啥 47 个点就是过不去,WA,就放这儿吧,反正只有我自己看这文章,懒得仔细看了……

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
// 静かな海
#include <bits/stdc++.h>
#define dbg(x, y...) fprintf(stderr, x, y)
#define pline() (dbg("Passing Line #%d in Func [%s]", __LINE__, __FUNCTION__))
using namespace std;

inline int rd() {
int x=0,c,f=1;while(!isdigit(c=getchar()))if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=x*10+c-'0';return x*f;
}
const int N = 1e5+3;

int n, k;
bitset<200000> b;

signed main() {
n = rd(), k = rd();
for (int i=0; i<n; i++)
b[i] = getchar() == 'B';

int tg = 0;
for (int i=1; i<=k && i<=2*n+1; i++) {
if (b[0] ^ tg) b>>=1, tg ^= 1, b[n-1] = tg;
else b[0].flip();
}

if (2*n+1 < k) {
int rem = k - 2*n - 1;
if (!(b[0] ^ tg)) tg ^= rem & 1;
}

for (int i=0; i<n; i++)
putchar((b[i]^tg) ? 'B' : 'A');

putchar('\n');
}

Over

一个国家有 \(N\) 个村庄,第 \(i\) 个村庄有一个奇妙的权值 \(A_i\),以及另一个奇妙的权值 \(B_i\)。 其中 \(B_i=\sum_j^i A_j\)。 我们保证 \(B_N=0\)

现在要从任意一个村庄出发,遍历除起点外任意不少于\(1\)个村庄,之后回到起始村庄。当从第\(i\)个村庄走到第\(j\)个村庄的时候,贡献是\(\dfrac{(A_i−A_j)B_iB_j}{2A_iA_j}\)

假设遍历顺序是 \(P_1,P_2,P_3,...,P_k,P_{k+1}\)(当然,由于起始位置必须相同,这里 \(P_{k+1}=P_1\)),他希望存在一个 \(2\le i\le k\),使得对于任意 \(j<i\), 都满足 \(B_{P_j}\le B_{P_{j+1}}\);而对于任意 \(k\ge j\ge i\), 都满足\(B_{P_j}\ge B_{P_{j+1}}\)

换句话说,\(B\) 权值在到达某个村庄之前是单调不降的,而之后又是单调不增的。在这个限制下最大化贡献和。


\[ \frac{(A_i−A_j)B_iB_j}{2A_iA_j}=\frac12\left(B_i\frac{B_j}{A_j}-B_j\frac{B_i}{A_i}\right) \]

于是求凸包面积即可

1
// gugu

评论和共享

WEEK201129

HDU6438 Buy and Resell

这个题目挺有意思的,值得记录下来。和以前一道CF一样。它们都是考虑一种“不关心具体方案”时的修改,即利用式子来进行“反悔”。

HDU6439 Congruence equation

记对参数 \(m\),这样的数列 \(\{C_k\}\) 的个数为 \(f(m)\)

  • 长度为 \(k\)
  • 对某些位置限制了必须为某值,而其它位置可以在有限域 \(F_m\) 中任选
  • \(\sum_{1\le i\le k}C_ix_i\equiv1\pmod m\),其中 \(x_i\) 是自由变量,这个方程要有整数解

你要计算 \(\sum_{m=1}^nf(m)\)

\(T\le100,k\le50,n\le10^9\),但最多对\(10\)组数据有 \(n\ge10^6\)


首先入手点当然是那个不定方程了,同余不用怕,多加一个系数为 \(m\) 的变量之后就变成普通不定方程了。

所以有解等价于 \(\gcd(C,m)=1\)\(C\) 是数列中所有数字的简记法。

但是还有一些位置已经定了值,我们不妨把它们先拉出来,把它们的 \(\gcd\) 设为 \(q\)。并且令 \(k\to\text{the number of free var }c_i\)

其实想到到这里应该就知道自己做完了这个不难的题目了,然而我却sb了,看到 \(\gcd=1\) 还想不到反演……

下面记枚举所有数列中不定的位置求和为 \(\sum_{C}\),实际上是 \(k\) 个求和号,那么答案就是

\[ \begin{aligned} \sum_{1\le m\le n}\sum_{C}[(C,q,m)=1] &=\sum_{1\le m\le n}\sum_{C}\sum_{d|(C,q,m)}\mu(d)\\ &=\sum_{d\le n}\mu(d)\sum_{m\le n}\sum_C[d|(C,q,m)]\\ &=\sum_{d\le n}\mu(d)[d|q]\sum_{m\le n}\left(\prod_{1\le h\le k}\sum_{1\le c_h\le m}[d|c_h]\right)\\ &=\sum_{d|q}\mu(d)\sum_{p\le \left\lfloor\large\frac nd\right\rfloor}p^k\\ \end{aligned} \]

这个式子好办,直接枚举因数,然后对于后面那个自然数幂和,暴力\(\mathcal O(k^2)\)预处理伯努利数即可。由于 \(q\le n\le 10^9\)\(\mathcal O(k^2+k\sqrt q)\) 是可以通过的。

当然,此外还有一种情形更棘手些,对于 \(q=0\) ,也就是没有限制,\(d|0\) 是(要视为)恒成立的,也就是 \(d\)\(1\to n\) 枚举。这个时候我们利用和杜教筛类似的交换和号方法可以直接得到

\[ =\sum_{1\le p\le n}p^k\sum_{dp\le n}\mu(d) \]

后面那个是 \(M\left(\left\lfloor\frac nd\right\rfloor\right)\),可以杜教筛,因为显然杜教筛 \(M(n)\) 时其实就会求出所有的 \(M\left(\left\lfloor\frac nd\right\rfloor\right)\)

口胡一下复杂度 \(\mathcal O(k^2+k\sqrt n+n^{2/3})\)

HDU6440 Dream

这个构造还是有点新奇的,幸好 fz 事构造大师hhh,于是我们的方案是这样的

\[ \forall x,y:x+y=1,x\times y=\min(x,y)+1 \]

其中本来是先想出了乘法,这样对幂就有

\[ a\ne0:a^0=1,\;a^1=1\times a=2,\;a^2=3,\;\cdots,\;a^{a-1}=a,\;a^a=a\cdots \]

HDU6442 GuGu Convolution

\(F(x)=\mathrm{EGF}\langle A^0,A^1,A^2,\cdots\rangle(x),G(x)=\mathrm{EGF}\left\langle 0,\left(\sqrt B\right)^1,0,\left(\sqrt B\right)^3,0,\left(\sqrt B\right)^5,\cdots\right\rangle(x)\),求 \(n![x^n](F\times G)(x)\)


比较水,但是很坑。根据 EGF 卷积,答案就是

\[ \sum_{k\text{ is odd}\atop 0\le k\le n}\binom nkA^{n-k}\left(\sqrt B\right)^{k}=\frac12[(A+\sqrt B)^n-(A-\sqrt B)^n] \]

然后显然可以快速幂,有两个坑点

  • 写矩阵快速幂常数太大容易 T,原因是有很多冗余运算,对 \(0\) 运算的那种。可以改成直接做线性变换,省去矩阵操作。
  • 模数任意,但是只要求 \(2\) 的逆元,写个欧拉定理很不值;有个 trick:可以全程 \(\pmod{2p}\) 然后最后换回去的答案是 \(\left\lfloor\dfrac{\rm ans}{2}\right\rfloor\)

评论和共享

WEEK201121

SRM 545 div1 hard SetAndSet

\(n\le50\) 个数 \(V\le2^{20}\),要分成非空的两组,使得对每组把所有数 \(\And\) 起来结果相同。求方案数。


首先分位,对于全 \(0/1\) 的位,随便分直接无视。此外就一定有 \(0\) 了,所以必然是两个集合结果都为 \(0\)。(之前居然想半天没想到这一点,反省……)

然后就可以转化成,两个集合必须都要有 \(0\),发现这个不好做,但是反面很好做,所以考虑容斥。

容斥就要对给定的一些位不合法,不合法意味着 \(0\) 全去了某一边。所以在考虑多个位时,就是关于 \(0\) 有交集的两个位都必须一起划分。

然后用 UFS 合并统计就好了。

Gym 101987G Secret Code

实数区间 \([0,S\le1000]\) 上均匀随机三条线段的开始点,长度分别固定是 \(w_1,w_2,w_3\),问:随机后,线段从左到右,第一条和第二条相交,第二条和第三条相交的概率。


反正是实数,就先考虑写个积分的式子看看。

\[ \int_0^S \mathrm dl_1\int_{l_1}^{\min(l_1+w_1,S)}\mathrm dl_2\min(S-l_2-w_2,w_2) \]

额,也不算很复杂……主要是,反正数值积分那么快,我何必操心它到底啥样呢.jpg

当然,这个东西完全是分段线性的,而且形式摆在那儿了,我们不妨想想怎么直接求。

先考虑 \(l_1-l_2\) 平面,添个纵轴 \(l_3\) ,我们看看哪些点是合法的。

对于前俩轴我们先想个范围,也就是这里积分上下限的限制,显然就是一个斜着的梯形。

而第三条线段只需和第二条相交,也就是说只和 \(l_2\) 有关,又是什么形状呢?还是个梯形 =、= 毕竟限制都是类似的。所以本质其实就是求俩四棱柱(底面是梯形,摆放方向互相垂直)的交的体积。

如图所示,右上角是左边立体图的右视图,分别考虑 \(S_1,S_2\) 两块对应的体积。

\(S_1\) 是个平行四边形,很好办,对应的左边棱柱是个直角三棱锥,也就是说关于 \(l_2\) 是线性的,所以我们可以直接底面积乘高除以二,也就是 \(w_1w_2\cdot\frac{w_1}2\) 这项。

\(S_2\) 是个梯形,看上去比较棘手,但是它对应的棱柱是个等高的东西,就是右视图上某一点对应的体积上的最高点和最低点的高度差是一定的,根据基础几何知识我们知道可以直接用这个高度差乘以底面积。底面积可以补成平行四边形减去一个等腰直角三角形,所以这部分贡献就是 \([(S-w_1)w_2-\frac12w_2^2]w_1\) 这项。

整理一下就得到答案是 \(w_1w_2\left(S-\frac{w_1+w_2}{2}\right)\),简单吧!别忘了考虑全排列嗷!可以枚举俩然后乘二计算。

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
// 静かな海
#include <bits/stdc++.h>
#define dbg(x, y...) fprintf(stderr, x, y)
#define pline() (dbg("Passing Line #%d in Func [%s]", __LINE__, __FUNCTION__))
using namespace std;

inline int rd() {
int x=0,c,f=1;while(!isdigit(c=getchar()))if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=x*10+c-'0';return x*f;
}
const int N = 2e6+3;

double w[5];
vector<pair<double, int>> v;

signed main() {
int n = rd();
for (int i=1; i<=n; i++) {
scanf("%lf%lf%lf%lf", w+4, w+1, w+2, w+3);
w[0] = 0;
for (int j=1; j<=3; j++)
for (int k=j+1; k<=3; k++)
w[0] += (2*w[4]-w[j]-w[k])*w[j]*w[k];
v.emplace_back(w[0]/w[4]/w[4]/w[4], i);
}
sort(v.begin(), v.end());
for (auto& x:v) printf("%d ", x.second);
}

易燃易爆杂题

构造一个正整数集合 \(S\subset [4n]:|S|=n\)\(S\) 里每两个元素不互质但不整除。

qwq先想想试试?


= = 假如你和我一样在那里考虑素因子,那就面壁思过去(

\(S=\{2n+2,2n+4,\cdots,4n\}\)

这应该是对于 \(n>1\) 的唯一解。

我太菜了,orzzz易燃

感觉多想一会儿应该能想到的,自己还是太浮躁,而且不擅长应付这类“师出无名”的构造。

什么时候再找 ATC 练练吧。

整点计数 cz_xuyixuan 2019

回来读 19 年集训队论文,没想到发现 xyx 写了以前一个令我印象深刻的题目的超级加强版的命题报告。

关键在于 \(a^2+b^2\) 的高斯整数分解 \((a+b\mathrm i)(a-b\mathrm i)\) ,这样的分解在不考虑乘上一些 \(\omega_4^k\) 的因子的时候是唯一的,于是加法变成了乘法!

咳咳,在 3b1b 找到了这个解法,要看前半部分不如直接看视频吧。

后半部分就是一个积性函数求和,用 \(\min25\) 筛或洲阁筛解决。

评论和共享

  • 第 1 页 共 1 页
作者的图片

7mile

八轨宇宙的七里征途


学生


E-Rev