NOIP提高组模拟赛夜间版2
没想到这个系列还能再更新
A. 装饰
这种题就需要大胆猜测打表验证
反正就是推出来了，式子变化一下就是题解式子，就是有亿点不简洁
我是这么想的（大概）
先排序，两个较小的颜色可以看成一个，这样只用考虑两种颜色，取法只有\(1-2\)
令两种颜色数量为\(a,b(a
-
\(a*2<=b\)显然按照\(a\)取\(1\)，b取\(2\)后\(b\)有剩余，答案是\(a\)
-
\(a*2>b\)，那么每次操作可以令两种颜色数量差\(-1\)，可以推一下，然后写出一个简单式子，实际上这样的结果是剩下的数量一定为\(0-0,1-0,0-1,1-1,0-2,2-0\)，实际上就是\((a+b+c)%3\)，那么答案其实就是\((a+b+c)/3\),当然也可以写一堆恶心式子
code
#include
#include
#include
using namespace std;
typedef long long ll;
ll a[4];
ll work(){
ll ans=0;
a[2]+=a[1];
if(a[3] B. 凉宫春日的消失
感谢数据，让我水了\(65pts\)
发现一定有解，跟\(dfs\)序有关，然后就莽了个按照\(dfs\)序排序
实际上离正解只有一步之遥
我们先让点集里的点按\(dfs\)序排序，然后相邻的两点都进行配对，第一个再和最后一个配对，这样我们把每个点配了两对
想一想深搜的路径，发现此时最多每条边经过两次
也就是说\(\sum_{i=1}^{cnt}path<=2(n-1)\)
我们只需要两两配对，那么只需要保留一半的路径，\(1,3,5....\)或者\(2,4,6....\)
他们有一个一定\(<=n-1\)
简单判断一下一种方案是否可行即可
code
#include
#include
#include
using namespace std;
const int maxn=200005;
struct edge{int net,to;}e[maxn<<1|1];
int head[maxn],tot;
void add(int u,int v){
e[++tot].net=head[u];
head[u]=tot;
e[tot].to=v;
}
int f[maxn][21],dfn[maxn],tim,dep[maxn],ls[maxn];
bool cmp(int x,int y){
return dfn[x]dep[x]){x^=y;y^=x;x^=y;}
for(int i=20;i>=0;--i)if(dep[x]-dep[y]>=(1<=0;--i)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
return f[x][0];
}
bool check(int s,int n){
if(s&1)return false;
int sum=0;
for(int i=1;i<=s;i+=2){
int lca=LCA(ls[i],ls[i+1]);
sum+=dep[ls[i]]-dep[lca]+dep[ls[i+1]]-dep[lca];
if(sum>n)return false;
}
return true;
}
int main(){
freopen("kieru.in","r",stdin);
freopen("kieru.out","w",stdout);
int n;scanf("%d",&n);
for(int i=1;i