HK2016训练赛总结

编程入门行业动态更新时间:2024-10-09 16:25:27

HK2016<a href=https://www.elefans.com/category/jswz/34/1758418.html style= 训练赛总结"/>

HK2016训练赛总结

HK2016训练赛

C

by ?49min

想想\(k>1\)且\(k<n-2\)时，答案是啥？
\(k=0,k=n-1\)时，非常简单。
\(k=1\)or\(k=n-1\)时，对a``b分别维护前缀，后缀最大值最小值。然后枚举哪个元素比较孤傲即可。

B

by?66min

求一些点到直线距离取min

D

by?130min

dp[i][j][k]: 使得前i栋楼，上升序列长度为j，第i栋楼高度为k的最小耗费。
然后显然，我们应该对高度离散化。因为这里要求严格递增，所以我们先h[i]+=i,然后再离散化，这样就变成非严格单增问题了。

K

by?187min

把每个集合当成一个节点。如果集合S是T1,T2,T3...的并。那么我们把T1,T2,T3...当成集合S的儿子。
关于怎么建树，我们考虑元素x,如果x被集合set1,set2,set3...包含。那我们对set1,set2,...按照从小到大的顺序排序，然后，第i个集合的爸爸是第i+1个集合。

J

by?220min

把所有串插入AC自动机。
如果某个状态包含了某个禁止的串，那么这个状态我们删掉。对于剩下的状态，我们建图。
如果建出来的图成环，那么输出-1
否则DAG上求最长路即可。

A

by?290min

我们可以在200步操作内，将u,v交换颜色，或者将v的颜色变成u的颜色。
我们先通过交换，使得每种颜色至少有一个节点，走到正确位置。
然后对于每种颜色，我们拿着那个位置正确的点，修改掉其他位置不正确的点的颜色即可。

补题

H

从大到小，依次加边。加边的同时，进行并查集合并。
枚举最大割边的权值上界\(w\)，要最小化slim值，就是要让两个集合的size尽可能的接近。
权值\(\leq w\)的边，会把\(n\)个点，分成很多个联通块，大小为\(k\)的联通块，相当于体积为\(k\)的物品，为了让两个集合size接近，我们选择一些物品，使得体积和最接近\(n/2\)

两个做法

做法1：

体积为\(k\)的物品，可以看成多项式\(1+x^k\)
添加一个物品，可以看成乘上\((1+x^k)\)
弃置一个物品，可以看成乘上\((1+x^k)^{-1}\)
我们先添加\(n\)个，大小为1的物品。
合并两个大小为\(k_1,k_2\)的物品，就相当于弃二摸一啦。
然后每次乘法的复杂度是\(O(n)\)的。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MOD = 1e9 + 7;
const int N = 30000+10;
int n,m,par[N],sz[N];
struct Edge{int u,v,w;bool operator < (const Edge & o) const {return w > o.w;}
} edge[N];
int find(int x){return par[x]==x?x:par[x]=find(par[x]);
}
int dp[N];
void ItemUPD(int val,int on) {//printf("val=%d, on=%d\n", val, on);if(on==+1) {for(int i=n;i>=val;i--) dp[i]=(dp[i]+dp[i-val])%MOD;}if(on==-1) {for(int i=val;i<=n;i++) dp[i]=(dp[i]-dp[i-val]+MOD)%MOD;}
}
int main(){scanf("%d%d",&n,&m);for(int i=0;i<=n;i++) par[i]=i,sz[i]=1;dp[0]=1;for(int i=1;i<=m;i++){scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);edge[i].u++, edge[i].v++;}sort(edge+1,edge+1+m);double ans = 1e12;for(int i=1;i<=n;i++) ItemUPD(1,+1);for(int i=1;i<=m;i++) {        int u=edge[i].u;int v=edge[i].v;if(find(u)==find(v)) continue;for(int j=n/2;j>=1;j--){if(dp[j]) {ans=min(ans, 1.0*edge[i].w/j);break;}}ItemUPD(sz[find(u)], -1);ItemUPD(sz[find(v)], -1);sz[find(v)]+=sz[find(u)];par[find(u)]=find(v);ItemUPD(sz[find(v)], +1);}printf("%.12f\n", ans);
}

做法2：时间魔术！CDQ分治

我们来施展时间魔术！每秒钟加入一条边。
然后每个物品都会有个出现的时间，有个消失的时间。那么每个物品存在的时间都是一个区间
我们尝试着拿一个bitset维护，哪些体积是能够凑出来的。
该怎么算时间\([L,R]\)内，的答案呢？
考虑体积为\(V\),对应的区间\([x,y]\)的物品。
- 如果\([x,y]\)包含\([L,R]\)。那么此物品，对于\([L,R]\)的每个时间点，都既可以拿，也可以不拿。我们直接更新bitset啦，\(B=B|(B<<V)\)
- 否则的话，令\(mid=(L+R)/2\)
  - 如果\(y\geq mid+1\),那么这个物品会影响\([mid+1,R]\)，我们把这样的物品放入【垃圾桶A】
  - 如果\(x \leq mid\)，那么这个物品会影响\([L,mid]\)，我们把这样的物品放入【垃圾桶B】
- 递归地，拿垃圾桶A去，更新\([L,mid]\),拿垃圾桶B去更新\([mid+1,R]\)
注意，与dfs的弹栈类似，处理完一个区间后，应该将bitset，还原到刚开始处理这个区间的状态。

从题目风格来看，这套题和国内画风不太一致。

国内的硬核数学题，计算几何题，数据结构题在区域赛上出现得相当之多。一旦遇到这种题，团队配合很容易脱节。前几日的CCPC吉林，最后两个小时，?卡在一个数据结构上，?卡在一个模拟上，?和?基本上被分割到了战场的两侧，无法形成任何呼应。?后期的存在感也相当淡薄。这种局势显然是极度不利的。

但从这套题来看，“重意识，轻操作”是一个很大的特点。也是说，不需要多深的数学底蕴，亦不需多高超的操作技巧，合理的想法所及之处，便是AC。从我方特点来看.......操作真的很烂很烂了。