2013-2014 Winter Petrozavodsk Camp, Andrew Stankevich Contest 45 (ASC 45)¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 44/218 | 6 | 6 | 11 |
A¶
solved by YZW
题意¶
构造 \(|A|=|B|=n\) 的集合，使得可重集 \(A+A=B+B\) 且 \(A\neq B\)，或判断无解。
题解¶
不会。凭感觉猜了个结论就过了。
B¶
solved by JLK
题意¶
给定一个\([0,x]\)上的分段线性函数，\(\xi\)是\([0,x]\)上随机变量。
求\(P(L \le \xi \le R|a \le f(\xi) \le b)\ge \alpha\)的最小\(R-L\)的任意一对\(L,R\)。
\(1 \le n \le 10^5\)
题解¶
把函数上满足在\([a,b]\)的区间找出来，显然答案必有一个方案，使\(L,R\)之一在找出来的区间端点上。尺取即可。
注意细节，函数可能是水平线。
\(O(n)\)
C¶
solved by TYB
题意¶
对于序列\(\{a_n\}\)，定义\(A_i=\sum_{i=1}^{n-1}[a_i<a_{i+1}]\)，求满足下列条件的\(\{a_n\}\)个数：
\(\bullet\ a_i\le A_{i-1}+1\)
\(\bullet\) 不存在\(i<j<k\)，使得\(a_k<a_i<a_j\)
\(n\le32\)
题解¶
考虑暴力：\(f[i][j][k][l][S]\)表示填了前\(i\)位，最后一位的数是\(j\)，\(A_i=k\)，前\(i\)个数中满足存在\(i<j,a_i<a_j\)的\(a_i\)中最大的为\(l\)，已经选了的数的集合为\(S\)的方案数。可以发现\(S\)其实不用记录所有数的状态，只需要记录大于等于\(l\)的数的状态即可，这样大大减少了有效状态，可以通过本题。
D¶
solved by TYB
题意¶
构造一个至多\(1000\)个点的有向图，满足以下条件：
\(\bullet\) 除\(n-1\)和\(n\)这两点没有出边外，其他点恰有两条出边。
\(\bullet\) 从\(1\)出发，每次等概率随机选择走一条边，到达\(n-1\)或\(n\)的时候结束，最后到达\(n-1\)的概率恰为\(\frac{p}{q}\)。
可以有重边，自环。
\(1\le p<q\le 100\)
题解¶
建一棵以\(1\)为根，\(255\)个结点的二叉树，则其恰有\(128\)个叶子结点，给他们从\(1\)到\(128\)编号，\(i\)号叶子按照如下规则连边：
\(\bullet\ 1\le i\le p\)：两条边连向\(256\)号节点。
\(\bullet\ p< i\le q\)：两条边连向\(257\)号节点。
\(\bullet\ q< i\le 128\)：两条边连向\(1\)号节点。
显然这样满足题意。
E¶
upsolved by
题意¶
题解¶
F¶
solved by YZW
题意¶
给出一个无向图 \(G=\{V,E\}\)，每个点都与 \(1\) 相连，给每条边分配 \([1,|E|]\) 间互不相同的编号，要求每个点相连边编号之和互不相同。
\(|V|\leq 1000, |E|\leq 100000\)
题解¶
给不与 \(1\) 相连的边任意分配 \([1,|E|-|V|+1]\) 内的编号，再拿 \(1\) 连的边调整使之互不相同即可。
G¶
upsolved by
题意¶
题解¶
H¶
upsolved by
题意¶
题解¶
I¶
upsolved by
题意¶
题解¶
J¶
upsolved by
题意¶
题解¶
K¶
solved by YZW
题意¶
计算几何题。
题解¶
现场写的做法太奇怪了，一堆 case，谢谢 jgg 帮我指点江山。
拿半平面交写似乎更好。
记录¶
开局没有看到特别可做的，JLK先写B，TYB和YZW看ADF。
JLK WA了一次，换TYB先写D，WA一次后AC(1:17)。
JLK又WA了一次，换YZW先写F。然后TYB帮JLK找出bug后B过了(1:30)。
YZW过F(1:33)，然后马上尝试A的结论，过了(1:37)。
YZW写K，JLK和TYB看CEHI。
YZW调了很久，WA一次后被JLK叉掉了，改了后AC(4:12)。
TYB尝试C，最后也过了(4:51)。
总结¶
Dirt¶
B(-2)
C(-1)
D(-1)
K(-1)