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)