差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:acm_life_from_zero:8.1-8.7 [2020/08/04 22:15]
lak [比赛]
+++ 2020-2021:teams:acm_life_from_zero:8.1-8.7 [2020/08/07 17:00] (当前版本)
kipple
@@ 行 1: / 行 1: @@
-======= 2020/07/25-2020/07/31周报 =======
+======= 2020/08/01-2020/08/07周报 =======
 ====== 团队训练 ======
 ====== 李元恺 ======
 =====题目=====
+CF1383DE（F卡常了）
 =====比赛=====
 [[https://atcoder.jp/contests/abc174|AtCoder Beginner Contest 174]](atcoder) ''pros:6/6/6 rk:536''
@@ 行 11: / 行 11: @@
 ====== 姜维翰 ======
 ===== 比赛 =====
-cf edu 92（码农专场.jpg）
+atcoder abc 174
 ====== 袁熙 ======
-===== 专题 =====
-没有专题
 ===== 比赛 =====
-没有比赛
+cf round 661
-===== 题目 =====
-补题（板子） 牛客第五场B \\ [[https://ac.nowcoder.com/acm/contest/5670|链接]] \\
-题意；给边带权的树，可以连边或删边，要求始终连通且形成的环异或和=0，求最后图的最小权值和\\
-思路：对原图的树，可以把边权用所连点的权值异或和来表示，转化成异或最小生成树\\
-类似的模板题：[[http://codeforces.com/problemset/problem/888/G|链接]]
 ====== 本周推荐 ======
 ====== 李元恺 ======
-[[https://codeforces.com/contest/1383/problem/C|Codeforces Round 659 1C]]
+[[https://codeforces.com/contest/1383/problem/E|Codeforces Round 659 1E]]
-标签：图论、状压dp
+标签：dp
-题意：两个字符串S、T，字符集大小20，每次可以从S中选任意多个相同字符，将他们变成另一个字符，问最小多少次可以将S变成T。
+题意：有一个01串S，长度为n，每次可以选相邻两个数，将这两个数替换为他们的或运算值，求n-1次操作内能够得到多少个不同的串（mod1e9+7）。
-思路：将每个字符作为一个点，如果存在字符$s_i = a$ 且$t_i = b$ 建立一条a->b的有向边，计这个图为$G_1$。
+思路：考虑对于每个合法结果，一定存在一个最小的i使得我们可以通过操作s[1-i]得到这个字符串。令f[i]表示最短匹配为s[1-i]的串数，分别考虑这样的串下一个填0和填1进行转移。
+   设原串为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:这周做的最有意思的题，推荐给大家
+====== 袁熙 ======
+cf 1380e Inverse Genealogy
-   证明：显然每个点都至少要被一条边覆盖，如果不是链状，则一定有两条边指向相同点，此时可以把先操作的边的目标改为后操作的边的起点，重复这样调整，最终会得到一个操作数相同的链状解。
+tag：构造 分治
-、现在我们可以用一个序列{$a_n$}来表示答案，$a_1,a_2,...,a_n$表示依次执行$a_1$->$a_2$,$a_2$->$a_3$,...,$a_{n-1}$->$a_n$，
+题意：对给定的n,k，构造一颗完全二叉树使这棵树的n个节点中，k个点满足其一个儿子所在子树大小是另一个的至少两倍
-序列$a_1,a_2,...,a_n$合法 iff 任意$G_1$中的边u->v，存在i，j满足$i<j$且$a_i = u,a_j = v$
+题解：
-、对于$G_1$的弱联通块$G$,计其无环导出子图中点数最多的为S，计|S|=k，|G|=n，则答案大于等于$2n-k-1$。
+观察一下后可以发现符合题意的树的这些性质：
-   证明：设有一个解的大小为k，考虑向一个空图中依次加入k条边。
+.有奇数个点，且k不大于(n-3)/2
-）若某次操作的两个端点处于同一个联通块中，则对于任意无环导出子图（DAG），其大小最多减1，连通块数不变
-）若不处于同一连通块中，则连通块数-1，所有DAG体积不变。
-   初始状态下有n个连通块，所以最多k-n+1条边被用来减小DAG的体积，最开始我们有一个大小为n的DAG，所以最终最大的DAG体积至少是2*n-k-1。
-、存在一个使答案等于2n-k-1的方案，给出构造：设G(V,E)最大DAG导出子图=S($V_1$,$E_1$),令序列为$V \setminus V_1$,$V_1$,$V \setminus V_1$
+.当且仅当2^x=n+1时，可以有k=0
-、状压dp求出最大DAG导出子图
+.(n,k)可以向(n-2,k-1)转化
-comment:这周做的最有意思的题，推荐给大家
+又可以发现，k=1时，只要n+1≠2^x,按顺序从根向下在每层放满点就可以满足要求，问题变成怎么放点能使(n-2*k+2,1)转变到(n,k)
-====== 袁熙 ======
-CF1372F [[https://codeforces.com/contest/1372/problem/F|题目链接]]\\
-标签：构造 交互\\
+对n-2*k+2≠2^x的情况，我们要在不破坏之前结果的情况下构造。由(n-2*k+2,1)的构造可以知道满足题意的点所在的位置，在维护之前大小关系的情况下放点。
+n-2*k+2=2^x时，不存在(n-2*k+2,1)的构造，可以先提前留下几个点，然后当做上面的情况继续构造，最后将这些点放在不影响结果的位置
-题意：一个长为$n$，不降的序列，由$k$个不同的数组成，每次可以询问$l,r$中的众数（数量相同取更小值），要求在$4k$次询问内确定原序列\\
+comment：有点麻烦的构造题。。没有看到能比较好的做最后一步转化的方法
-思路：考虑如果已知某个数在某个位置$p$，和这个数的总出现次数$f$。那么可以用两次询问$(p,p+f-1),(p-f+1,p)$得到这个数的结果.那么如果能使所有数都出现在查询结果中，就能知道整个序列。\\
-要想构造出上述的查询，我们可以从$(1,n)$开始，用当前区间的最高频率$f$为间隔，每次确认$f,2f,..$这些点的数值，这些数值两两不等，且$(1,n)$查询得到的众数一定在这些数值中。接下来递归地对两边的区间进行询问。这样对于每个数，找到它的一个出现位置+确定它的出现区间+递归时确定它作为众数的区间，共4k次询问。\\
-comment：做法比较多的构造题\\
 ====== 姜维翰 ======
-CF1292C
+cf 1382e mastermind
-tag：dp
-题意：给一棵n个点的树，要求给每条边选择一个0到n-2的数，不可以重复，mex(u,v)表示点u到点v经过的数的mex，求最大化所有点对的mex和，n=3000
+tag：贪心
-解法：可以看到，树上存在一条链，链上包含[0,l]上的所有值，答案只和这个链的位置和链上数的摆法有关
+题意：给n,x,y和一个长n的数组，数组元素的大小为1到n+1间的整数，求另一个数组，元素大小同样在1到n+1，两个数组元素相同的位置有x个，重新排列后两个数组最多有y个相同位置的元素相同
-我们还可以通过贪心，看出链应该是这个样子的：10，8，6，4，2，0，1，3，5，7，9
-于是链的摆法就确定了
-那么我们就f[u][v]来表示链为u到v时的答案
+题解：首先对出现的元素进行计数，显然要把x的指标优先给数量多的元素
-在算答案的时候要把mex求和转化成对mex大于某个值的点对的计数
+这样还剩下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方的时间内完成了
+对于有解的情况就比较简单了，对n-x这部分的元素排序，然后旋转(n-x)/2之后放进去，再把n-y个位置的元素换成不存在过的元素就可以了
-comment：很独特的一道dp题，答案计数方法的转换也很经典
+comment：很妙的题，尤其是对于无解的判断

CVBB ACM Team

用户工具

站点工具

差别

页面工具