2020-2021:teams:legal_string:jxm2001:contest:cf_global_15
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
2020-2021:teams:legal_string:jxm2001:contest:cf_global_15 [2021/07/26 10:05] jxm2001 创建 |
2020-2021:teams:legal_string:jxm2001:contest:cf_global_15 [2021/07/26 20:02] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 54: | 行 54: | ||
| enter(ans); | enter(ans); | ||
| } | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== E. Colors and Intervals ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定 $n\times k$ 的序列，第 $i$ 个元素颜色为 $c_i$，其中 $1\le c_i\le n$，且每种颜色恰好出现 $k$ 次。 | ||
| + | |||
| + | 要求选择 $n$ 条线段，其中第 $i$ 条线段左右两端点颜色均为 $i$，且序列中任意一点最多被 $\lfloor \frac n{k-1}\rfloor$ 条线段覆盖。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 首先设颜色 $i$ 的出现位置为 $c(i,1),c(i,2)\cdots c(i,k)$，则不难发现最优方案一定是取 $[c(i,j),c(i,j+1)](1\le j\lt k)$ 的线段。 | ||
| + | |||
| + | 考虑将所有颜色先按 $c(i,2)$ 排序从小到大排序，取走前 $\lfloor \frac n{k-1}\rfloor$ 个颜色的 $[c(i,1),c(i,2)]$，然后删除该颜色，再依次考虑 $c(i,3)\cdots c(i,k)$。 | ||
| + | |||
| + | 这样操作轮数为 $k-1$，最多可以取走 $(k-1)\lfloor \frac n{k-1}\rfloor\ge n$ 种颜色，因此可以保证每个颜色都被选取。 | ||
| + | |||
| + | 另外第 $i$ 轮操作后考虑当前取走的颜色 $a$ 和剩下的颜色 $b$，一定有 $c(a,i)\lt c(b,i)$。 | ||
| + | |||
| + | 然后接下来第 $j$ 轮中取颜色 $b$ 的线段 $[c(b,j-1),c(b,j)]$ 时一定有 $c(a,i)\lt c(b,i)\le c(b,j-1)$。 | ||
| + | |||
| + | 所以 $[c(a,i-1),c(a,i)]$ 与 $[c(b,j-1),c(b,j)]$ 一定不相交。进一步，即任意两轮之中取的线段都不相交。 | ||
| + | |||
| + | 而同一轮的线段最多只有 $\lfloor \frac n{k-1}\rfloor$ 条，所以对任意一个点最多覆盖 $\lfloor \frac n{k-1}\rfloor$ 次。 | ||
| + | |||
| + | 于是上述构造满足题目约束，时间复杂度 $O(nk\log n)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=105; | ||
| + | vector<int> c[MAXN]; | ||
| + | bool vis[MAXN]; | ||
| + | pair<int,int> ans[MAXN]; | ||
| + | int main(){ | ||
| + | int n=read_int(),k=read_int(),bound=(n+k-2)/(k-1); | ||
| + | _rep(i,1,n*k) | ||
| + | c[read_int()].push_back(i); | ||
| + | vector<int> vec; | ||
| + | _for(i,1,k){ | ||
| + | vec.clear(); | ||
| + | _rep(j,1,n){ | ||
| + | if(!vis[j]) | ||
| + | vec.push_back(j); | ||
| + | } | ||
| + | sort(vec.begin(),vec.end(),[&](int a,int b){ | ||
| + | return c[a][i]<c[b][i]; | ||
| + | }); | ||
| + | _for(j,0,min((int)vec.size(),bound)){ | ||
| + | vis[vec[j]]=true; | ||
| + | ans[vec[j]]=make_pair(c[vec[j]][i-1],c[vec[j]][i]); | ||
| + | } | ||
| + | } | ||
| + | _rep(i,1,n) | ||
| + | printf("%d %d\n",ans[i].first,ans[i].second); | ||
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/contest/cf_global_15.1627265118.txt.gz · 最后更改: 2021/07/26 10:05 由 jxm2001
