CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
======= 2020/07/11-2020/07/17周报 =======
====== 团队训练 ======
2020.7.12 [[牛客多校第一场]] ''pro: 4/4/10'' ''rk: 45''

2020.7.13 [[牛客多校第二场]] ''pro: 4/4/11'' ''rk: 168''
====== 李元恺 ======
CR655C

[[https://codeforces.com/contest/1372/problem/C|链接]]

题意：

一个排列，每次可以任选一个子序列重新排，只需满足每个数都不在原来的位置；

做法：

可以观察到最多只需两次，一次让所有的数都不在正确位置。于是分别验证0次和1次可不可即可

CR655D

[[https://codeforces.com/contest/1372/problem/D|链接]]

题意：2n+1个数排成一圈，每次选三个连续的数消去，并把两侧的两个数之和放在原位，问还剩一个数时最大值。

做法：观察，如果是一条链，最后的和最大值一定是所有奇数位置之和（因为奇偶不同位置永远不能求和）。成环以后一个数可以从两个分别加和，于是可以取一次连续两个位置，然后其他位置隔一选一。证明很显然，显然不能存在连续三个都选，如果存在两个连续两个选的位置，则这两个对中相近的侧的两个数一定先合并，此时剩余三个数一定无法加和。
===== 题目 =====


====== 姜维翰 ======
===== 专题 =====
没有专题
===== 比赛 =====
没有比赛
===== 题目 =====

====== 袁熙 ======

===== 专题 =====
没有专题
===== 比赛 =====
没有比赛
===== 题目 =====
上周atc的F[[https://atcoder.jp/contests/aising2020/tasks/aising2020_f|链接]]\\
题意：给$N\leq 10^9$，要求找5对数$a_i,b_i$满足$0\leq a_i<b_i,\sum_i(a_i+b_i)\leq N$，求所有方案的$\prod_i(b_i-a_i)$\\
做法：拉格朗日拟合，由题意，答案应该是一个十几次的多项式，暴力算几个点拟合一下。由于下面的说明，奇偶是两个不同的多项式，要分开来做。\\
或者排列组合，将$a_i,b_i$转为$\Delta=b_i-a_i，2a_i$，则问题转化为在数量为N的球中插板，并且板之间球的个数有一定要求（偶数）。

====== 本周推荐 ======
====== 李元恺 ======
这周做题比较少，就推荐一下CR655D

CR655D

[[https://codeforces.com/contest/1372/problem/D|链接]]

题意：2n+1个数排成一圈，每次选三个连续的数消去，并把两侧的两个数之和放在原位，问还剩一个数时最大值。\\
tag:找规律\\
做法：观察，如果是一条链，最后的和最大值一定是所有奇数位置之和（因为奇偶不同位置永远不能求和）。成环以后一个数可以从两个分别加和，于是可以取一次连续两个位置，然后其他位置隔一选一。\\
证明:显然不能存在连续三个都选，如果存在两个连续两个选的位置，则这两个对中相近的侧的两个数一定先合并，此时剩余三个数一定无法加和。\\
comment：一道结论一般显然的结论题\\

====== 袁熙 ======
推荐这周div2的F题[[https://atcoder.jp/contests/aising2020/tasks/aising2020_f|链接]]\\
题意：给$N\leq 10^9$，要求找5对数$a_i,b_i$满足$0\leq a_i<b_i,\sum_i(a_i+b_i)\leq N$，求所有方案的$\prod_i(b_i-a_i)$\\
tag:拉格朗日拟合，排列组合\\
做法：拉格朗日拟合，由题意，答案应该是一个十几次的多项式，暴力算几个点拟合一下。由于下面的说明，奇偶是两个不同的多项式，要分开来做。\\
或者排列组合，将$a_i,b_i$转为$\Delta=b_i-a_i，2a_i$，则问题转化为在数量为N的球中插板，并且板之间球的个数有一定要求（偶数）。\\
comment:大概是常规的思维题？
====== 姜维翰 ======
推荐这周牛客第二场的E[[https://ac.nowcoder.com/acm/contest/5667/E|链接]]\\
tag：FWT，位运算\\
题意：从给定集合里选n个数，使得它们的异或值最大，数小于2^18\\
题解：n大于19时可以通过异或的开关性化成小于等于19的情况，小于等于19时用异或卷积(FWT)算答案\\
comment：头一次见到FFT还能这么玩，计划下周详细介绍快速沃尔变换FWT\\
CVBB ACM Team

用户工具

站点工具

页面工具
