Codeforces Global Round 15
E. Colors and Intervals
题目描述
点此看题
\(n\) 种颜色，每种颜色恰好有 \(k\) 个，他们排成一个长度为 \(n\times k\) 的颜色序列 \(a\)
每种颜色需要选两个端点，这两个点会构成一个区间，试构造方案使得每个点最多被覆盖 \(\lceil\frac{n}{k-1}\rceil\) 次。
\(n,k\leq 100\)
解法
不难转化题意：每 \(k-1\) 个颜色分成一组，要求每一组的区间最多覆盖每个点一次。
再观察每种颜色 \(k\) 个端点，那么 \(k-2\) 个端点会被浪费，可以猜想每种颜色的匹配最多浪费其他颜色的一个端点。
我们取出这一组所有有关的端点，然后从左往右扫，如果这种颜色没有左端点那么记录左端点，如果这种颜色有左端点那么把这个位置当成右端点，然后把其它颜色的左端点往右移直接不交，不难发现其他颜色最多移动一次，因为如果移动多次那么先匹配的就是它了。
总结
和次数相关的构造题一定要找次数的现实意义，除法可以联想到分组，当然如果题目给的是具体数字我们要猜这个数字是怎么来的。
其实我觉得第二步构造是很难的，但是从感觉上说我们想把距离近的点匹配到一起，所以本题的顺序扫描法是很有可能的，我一开始想的时候想的是归纳构造法但是走不通，有时候整体和局部的构造方法都值得去想一想。
#include
#include
#include
using namespace std;
const int M = 100005;
#define pii pair
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,k,a[M],b[M],nxt[M];pii ans[M];
signed main()
{
n=read();k=read();
for(int i=1;i<=n*k;i++)
a[i]=read();
for(int l=1;l<=n;l+=k-1)
{
int r=min(n,l+k-2);vector g;
for(int i=1;i<=n*k;i++)
if(l<=a[i] && a[i]<=r)
g.push_back(i);
for(int i=0;i G. A Serious Referee
题目描述
点此看题
哥哥 \(\tt zxy\) 设计了一种排序方法，这个排序操作有 \(k\) 步，每次选择一个子序列将其内部升序排列。
天下第一妹的 \(\tt jzm\) 要审核这个排序方法，所以她想知道这种排序方法适用于所有长度为 \(n\) 的序列。
\(n\leq 40,k\leq 10\)
解法
\(\tt zero-one\ principle\)：对于任何的排序方式，长度为 \(n\) 的序列能排好序当且仅当长度为 \(n\) 的 \(0/1\) 序列能排好序，必要性显然，下证充分性：
不妨设原序列为排列，对于所有 \(1\leq s\leq n\)，我们把小于等于 \(s\) 的元素设置为 \(0\)，大于 \(s\) 的元素设置为 \(1\)，然后把这个 \(0/1\) 序列排序，我们可以得到下列信息：
- 排序后小于等于 \(s\) 的元素在前 \(s\) 个位置上。
那么可以依次推出最小的元素在第一个位置，次小的元素在第二个位置\(...\)充分性得证
那么我们只需要考虑对所有 \(01\) 序列是否能排好序即可，暴力枚举 \(O(2^{40})\) 受不了，而折半搜索又不行。
现在排序之后状态量会减少，那么我们按操作来考虑，考虑到第 \(i\) 个操作时只记录前 \(i\) 个操作涉及到的位置的状态。我们考虑怎么扩展状态，每次我们考虑新增的位置的状态，但是因为要排序我们只需要枚举新增的位置有多少个 \(1\) 就可以得到新的状态了。
因为新增位置的总数是 \(n\)，而最多新增 \(k\) 次，设每次新增了 \(s_i\) 个：
\[(s_1+1)(s_2+1)...(s_k+1)\leq (\frac{n+k}{k})^k=O(5^k) \]然后就可以开始卡常了，判断一个 \(01\) 序列是否排好序的方法：找出 \(0\) 的个数，然后看前这么多位是否全是 \(0\) 即可。因为这道题范围是 \(\tt ll\)，你要用 __builtin_popcountll(x)，这是针对 \(\tt ll\) 统计二进制有多少个 \(1\) 的函数。
总结
像这种有很奇怪数据范围的题，一定注意减少状态量即可，思考按什么顺序考虑状态会少一些。
#pragma GCC optimize(2)
#include
#include
#include
using namespace std;
const int M = 105;
const int N = 10000005;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,k,b[M],x[M],w[N],h[N],st[M];
signed main()
{
n=read();k=read();w[m=1]=0;
for(int i=1;i<=n;i++)
st[i]=st[i-1]|(1ll<