2020-2021:teams:acm_life_from_zero:8.8-8.14
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:acm_life_from_zero:8.8-8.14 [2020/08/13 14:37] lak [比赛] |
2020-2021:teams:acm_life_from_zero:8.8-8.14 [2020/08/14 18:12] (当前版本) lak [姜维翰] |
||
|---|---|---|---|
| 行 6: | 行 6: | ||
| =====比赛===== | =====比赛===== | ||
| - | [[http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=892|2020 年百度之星·程序设计大赛 - 复赛]] | + | [[http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=892|2020 年百度之星·程序设计大赛 - 复赛]] ''rk:69 pros:3/6'' |
| + | |||
| + | [[https://codeforces.com/contest/1394|Codeforces Round #664 (Div. 1)]] ''rk:131 pros:2/5'' | ||
| ====== 姜维翰 ====== | ====== 姜维翰 ====== | ||
| - | ===== 比赛 ===== | + | 小学期咕咕咕 |
| - | atcoder abc 174 | + | |
| ====== 袁熙 ====== | ====== 袁熙 ====== | ||
| + | =====比赛===== | ||
| + | [[https://codeforces.com/contest/1395|Codeforces Round #664 (Div. 2)]] \\ | ||
| + | |||
| + | [[https://codeforces.com/contest/1391|Codeforces Round #663 (Div. 2)]] | ||
| - | ===== 比赛 ===== | ||
| - | cf round 661 | ||
| - | |||
| - | |||
| ====== 本周推荐 ====== | ====== 本周推荐 ====== | ||
| ====== 李元恺 ====== | ====== 李元恺 ====== | ||
| - | [[https://codeforces.com/contest/1383/problem/E|Codeforces Round 659 1E]] | + | [[https://codeforces.com/contest/1394/problem/B|CF1394B]] |
| - | 标签：dp | + | tag：图论、搜索 |
| - | 题意：有一个01串S，长度为n，每次可以选相邻两个数，将这两个数替换为他们的或运算值，求n-1次操作内能够得到多少个不同的串（mod1e9+7）。 | + | 题意：一张n点m边有向由边权图（n,m~1e5），每个点最多k条边（$k \leq 9$）,对于一个长度为k的数组{$c_k$}，满足$c_i \leq i$，定义图对其的转移：一个点，若出度为x，则走边权第$c_x$小的出边。求有多少个${c_k}$满足任意一个点出发经过有限步可以返回出发点。 |
| - | 思路：考虑对于每个合法结果，一定存在一个最小的i使得我们可以通过操作s[1-i]得到这个字符串。令f[i]表示最短匹配为s[1-i]的串数，分别考虑这样的串下一个填0和填1进行转移。 | + | 思路：对于一个合法转移，每个点都在一个简单环内，即每个点的入度都必须为1，于是对于每个点的任意两个入边，可以得到一个四元组$(c_i,c_j,v_i,v_j)$表示$c_i = v_i,c_j = v_j$不能同时发生。预处理一下所有的四元组，然后O(k!k)暴搜所有解判断是否合法即可。 |
| - | 设原串为p，则 | + | |
| - | 填1：p+1的最短匹配一定是s[i]向后找的第一个1 | + | |
| - | 填0：若p的最短匹配是s[1-i]，则s[1-i]的末尾0数一定和p相等，因此若s[i+1]是0，则最短匹配的位置是i+1，否则设s[1-i]末尾0数为k，最短匹配是i后面第一个连续k+1个0。 | + | |
| - | 这样就可以O（n）计算f[1-n]，注意并不是所有f[i]都可以作为答案，因为后缀0数不能超过s串的后缀0数 | + | |
| - | comment:这周做的最有意思的题，推荐给大家 | + | comment:一道解法众多的题，上面只是一种可以通过的解法。 |
| ====== 袁熙 ====== | ====== 袁熙 ====== | ||
| - | cf 1380e Inverse Genealogy | + | [[https://codeforces.com/contest/1393/problem/E1|cf1393E Twilight and Ancient Scroll]] |
| - | tag：构造 分治 | + | tag:hash,dp |
| - | 题意：对给定的n,k，构造一颗完全二叉树使这棵树的n个节点中，k个点满足其一个儿子所在子树大小是另一个的至少两倍 | + | 题意：给n个词构成的串，词之间按字典序不降，可以选择对每个词进行一次操作：在某个字母后添加一个字母之后选择某个词。之后，选择一个词，撤销此操作。问操作后可能产生的串的不同版本数量 |
| - | 题解： | + | 思路:考虑dp时，对相邻的两个词$S_1,S_2$，在题意的操作下分别产生$|S_1|+1，|S_2|+1$个子串。如果对子串排序后，对$S_2$的每个子串，可以二分找到合法的$S_1$的子串数量，完成转移。为了在转移时找到合法子串的数量，还需要对每个词hash一下。 |
| - | 观察一下后可以发现符合题意的树的这些性质： | + | comment:补之前的题（ 大概是常规的dp |
| - | + | ||
| - | 1.有奇数个点，且k不大于(n-3)/2 | + | |
| - | + | ||
| - | 2.当且仅当2^x=n+1时，可以有k=0 | + | |
| - | + | ||
| - | 3.(n,k)可以向(n-2,k-1)转化 | + | |
| - | + | ||
| - | 又可以发现，k=1时，只要n+1≠2^x,按顺序从根向下在每层放满点就可以满足要求，问题变成怎么放点能使(n-2*k+2,1)转变到(n,k) | + | |
| - | + | ||
| - | 对n-2*k+2≠2^x的情况，我们要在不破坏之前结果的情况下构造。由(n-2*k+2,1)的构造可以知道满足题意的点所在的位置，在维护之前大小关系的情况下放点。 | + | |
| - | n-2*k+2=2^x时，不存在(n-2*k+2,1)的构造，可以先提前留下几个点，然后当做上面的情况继续构造，最后将这些点放在不影响结果的位置 | + | |
| - | + | ||
| - | comment：有点麻烦的构造题。。没有看到能比较好的做最后一步转化的方法 | + | |
| ====== 姜维翰 ====== | ====== 姜维翰 ====== | ||
| - | cf 1382e mastermind | ||
| - | |||
| - | tag：贪心 | ||
| - | |||
| - | 题意：给n,x,y和一个长n的数组，数组元素的大小为1到n+1间的整数，求另一个数组，元素大小同样在1到n+1，两个数组元素相同的位置有x个，重新排列后两个数组最多有y个相同位置的元素相同 | ||
| - | |||
| - | 题解：首先对出现的元素进行计数，显然要把x的指标优先给数量多的元素 | ||
| - | |||
| - | 这样还剩下n-x个元素，对于这n-x个元素，两个数组在不重新排列前不能有匹配，对于一某种元素c，假设它有k个，如果2*k>n-x，那么必然有一部分元素要变成其它的元素，n个位置有n+1种元素，所以这个用来替换的元素是一定存在的，而如果出现这样的情况，n-x这一部分在重排之后至多能匹配2*(n-x-k)个，也就是要2*(n-x-k)>=y-x，化简得2*n-x-y>=2*k，不满足则无解 | ||
| - | |||
| - | 对于有解的情况就比较简单了，对n-x这部分的元素排序，然后旋转(n-x)/2之后放进去，再把n-y个位置的元素换成不存在过的元素就可以了 | ||
| - | comment：很妙的题，尤其是对于无解的判断 | ||
2020-2021/teams/acm_life_from_zero/8.8-8.14.1597300667.txt.gz · 最后更改: 2020/08/13 14:37 由 lak
