Preface
貌似CF的Div1/Div2分场就有1900的分界线，大号打不了Div2就很难受
同时我对自己的水平有清晰的认知，现在打这种纯Div1的场肯定就是纯被虐，所以也不敢去Div1
所以索性开了个小号去Div2划水了，结果又是写的又慢又烂，2h50min才堪堪写了5题，最后D还FST了
后来看了下原来是一个初值赋太小了，有点可惜的说
嘛不过实话实说这场题目质量很高，做起来感觉就很舒服，狠狠地好评一波
A. Likes
简单贪心处理即可，最大的情况就是把点赞的全部放在前面，最小的情况就是点一个赞消一个赞
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int t,n,x,gr,le;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),gr=0,i=1;i<=n;++i) scanf("%d",&x),gr+=x>0; le=n-gr;
for (i=1;i<=n;++i) printf("%d%c",i<=gr?i:gr-(i-gr)," \n"[i==n]);
for (i=1;i<=2*le;++i) printf("%d%c",i&1?1:0," \n"[i==n]);
for (i=2*le+1;i<=n;++i) printf("%d%c",i-2*le," \n"[i==n]);
}
return 0;
}
B. Settlement of Guinea Pigs
考虑记录下每个时刻确定了性别的猪的个数sure和未确定性别的个数unkn
不难发现一次检查操作就可以把所有的unkn的猪都变成sure，那么我们只要考虑对于unkn只未确定性别的猪，最少需要多少个笼子
通过简单的手玩我们发现这部分的贡献就是\(\lfloor\frac{unkn}{2}\rfloor+1\)，但是要注意当\(unkn=0\)时不产生贡献要特判一下
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int t,n,x,ans,sure,unkn;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),ans=sure=unkn=0,i=1;i<=n;++i)
{
if (scanf("%d",&x),x==1) ++unkn; else sure+=unkn,unkn=0;
ans=max(ans,(sure?(sure/2+1):0)+unkn);
}
printf("%d\n",ans);
}
return 0;
}
C. The Very Beautiful Blanket
构造怪题，刚开始走错了好几个方向，但最后还是堪堪乱搞出来了一个很怪异的做法
首先数的种类数肯定是\(n\times m\)，考虑如何构造出使达到这个上界
前面通过手玩加观察样例以为是要第一行每个数和第二行每个数异或起来都相同，然后其它行和列也是类推，不过最后浪费了好多时间最后不了了之
本来都准备弃疗了，但是突然想到一个很怪的做法，遂起死回生，先上个我构造方法的图：
大致思路就是先随便给前四个格子填数，然后考虑设置一个横向的增量\(A\)和一个纵向的增量\(B\)，每次增量跳两格
乍一看感觉不太清楚，看一下上面那个图就豁然开朗了
然后我们发现这么构造之后对于任意的\(2\times 2\)的子矩阵，如果我们可以把重复的\(A,B\)消除掉，那么它们的异或值就都是\(X\oplus Y\oplus P\oplus Q\)
那么怎么样才能让\(A,B\)消除呢，考虑我们做的操作是异或，因此如果\(X,Y,P,Q\)和\(A,B\)的值有绝对差距的话就可以用异或消除掉\(A,B\)且对前面部分没有影响
乍一听又很抽象，再举个例子，比如说我们令\(A=2^{59},B=2^{60},C=2^{61},D=2^{62}\)，此时如果让\(A=1,B=2\)，则此时每个\(2\times 2\)的格子在异或的时候就可以消除掉\(A,B\)的影响了
但是如果直接按上面的方法做又会有一个问题，有些格子的值可能会相同，这是由于\(A,B\)的线性组合\(x_1\times A+y_1\times B=x_2\times A+y_2\times B\)在\(x_1\ne x_2,y_1\ne y_2\)时仍然会有解
要解决这个问题也很简单，我们只要让\(A,B\)也相差一个数量级即可，比如令\(A=1,B=2^{30}\)，此时就可以避免上面的那种情况
综上用这种奇奇怪怪的方法堪堪搞过了这道有趣的构造题（比赛的时候怕挂还手写了下check）
#include<cstdio>
#include<iostream>
#include<set>
#define RI register int
#define CI const int&
using namespace std;
typedef long long LL;
const int N=205;
const LL st[2][2]={{1LL<<59,1LL<<60},{1LL<<61,1LL<<62}},A=1,B=1LL<<30;
int t,n,m; LL a[N][N]; set <LL> s;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=2;++i) for (j=1;j<=2;++j) a[i][j]=st[i-1][j-1];
for (i=1;i<=2;++i) for (j=3;j<=m;++j) a[i][j]=a[i][j-2]+A;
for (j=1;j<=m;++j) for (i=3;i<=n;++i) a[i][j]=a[i-2][j]+B;
/*for (s.clear(),i=1;i<=n;++i) for (j=1;j<=m;++j)
if (s.count(a[i][j])) return puts("WRONG"),0; else s.insert(a[i][j]);
for (i=1;i+3<=n;++i) for (j=1;j+3<=m;++j)
{
LL x1=a[i][j]^a[i+1][j]^a[i][j+1]^a[i+1][j+1];
LL x2=a[i+2][j+2]^a[i+3][j+2]^a[i+2][j+3]^a[i+3][j+3];
LL y1=a[i+2][j]^a[i+3][j]^a[i+2][j+1]^a[i+3][j+1];
LL y2=a[i][j+2]^a[i+1][j+2]^a[i][j+3]^a[i+1][j+3];
if (x1!=x2||y1!=y2) return puts("WRONG!"),0;
}*/
for (printf("%d\n",n*m),i=1;i<=n;++i) for (j=1;j<=m;++j)
printf("%lld%c",a[i][j]," \n"[j==m]);
}
return 0;
}
D. Buying gifts
这题的思路就很trivial啊，不过我写挂了好多地方也确实菜
首先考虑把所有礼物按照\(a_i\)排序，然后考虑从后往前枚举\(k\)，假设送给第一个人的最贵的礼物就是\(a_k\)
此时显然后面的礼物都必须是选给第二个人的，那么我们设\(tmx=\max_{j=k+1}^n b_i\)，然后分情况讨论：
- 若\(tmx\ge a_k\)，则直接用\(tmx-a_k\)更新答案，前面的默认都选择第一个人显然是最优的
- 若\(tmx<a_k\)，此时我们在前\(k-1\)个礼物中找出数值与\(a_k\)最接近的\(b_{pre},b_{nxt}\)（就是在\(b\)构成的集合里找\(a_k\)的前驱后继），然后在\(tmx,a_{pre},a_{nxt}\)里面找一个和\(a_k\)最接近的更新答案即可
然后我写的时候在集合里插入一个极大值防止越界的时候扔了个\(10^9\)进去，最后就FST了，改成\(2\times 10^9\)就行了
#include<cstdio>
#include<iostream>
#include<set>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
typedef set <int>::iterator SI;
const int N=500005,INF=2e9;
struct Data
{
int x,y;
friend inline bool operator < (const Data& A,const Data& B)
{
return A.x!=B.x?A.x<B.x:A.y>B.y;
}
}a[N]; int t,n,ans; multiset <int> s;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),s.clear(),ans=0,i=1;i<=n;++i)
scanf("%d%d",&a[i].x,&a[i].y),ans=max(ans,max(a[i].x,a[i].y)),s.insert(a[i].y);
int tmx=-INF; for (s.insert(-INF),s.insert(INF),sort(a+1,a+n+1),i=n;i;--i)
{
if (s.erase(s.find(a[i].y)),tmx<a[i].x)
{
SI it=s.lower_bound(a[i].x); int nxt=*it,pre=*(--it);
ans=min(ans,min(a[i].x-max(pre,tmx),nxt-a[i].x));
} else ans=min(ans,tmx-a[i].x); tmx=max(tmx,a[i].y);
}
printf("%d\n",ans);
}
return 0;
}
E. Music Festival
刚开始以为是那种在sort的cmp上做文章的题目，WA了一发后感觉不对立马跑路Rush出了正解
首先我们先把每个唱片里没用的元素剔除掉，即维护一个递增的序列\(v_{i,1},v_{i,2},\cdots,v_{i,k}\)
考虑当某个唱片\(j\)放在另一个唱片\(i\)之后时，新产生的贡献就是以唱片\(i\)结束时的贡献再加上\(v_j\)中大于\(v_{i,k}\)的数个数
因此我们发现每个唱片可能产生贡献的一定是\(v\)中的一段后缀，同时一个唱片对它后面的影响只取决于它最后一个元素的值
那么我们考虑把所有唱片按照\(v\)的最后一个元素排序，不难发现此时最终产生贡献的唱片序列一定是升序的，因为把后面的排到前面去一定不会变优
同时我们维护下以唱片\(i\)结束时的答案\(f_i\)，然后考虑在处理第\(j\)张唱片时，从后往前枚举每一段后缀，设此时这段后缀的开头是\(t\)
我们就要找出所有之前的满足\(v_{i,k}<t\)的最大的\(f_i\)的值，这个显然可以用树状数组维护
因此这题就做完了，复杂度\(O(n\log n+\sum k\log |a_{i,j}|)\)
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,m,x,f[N],ans,mx; vector <int> v[N];
inline bool cmp(const vector <int>& A,const vector <int>& B)
{
return A.back()<B.back();
}
class Tree_Array
{
private:
int bit[N];
public:
#define lowbit(x) (x&-x)
inline void add(RI x,CI y)
{
for (;x<=mx;x+=lowbit(x)) bit[x]=max(bit[x],y);
}
inline void clear(RI x)
{
for (;x<=mx;x+=lowbit(x)) bit[x]=0;
}
inline int get(RI x,int ret=0)
{
for (;x;x-=lowbit(x)) ret=max(ret,bit[x]); return ret;
}
#undef lowbit
}T;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j; for (scanf("%d",&n),mx=0,i=1;i<=n;++i)
{
for (v[i].clear(),scanf("%d%d",&m,&x),mx=max(mx,x),v[i].push_back(x),j=2;j<=m;++j)
if (scanf("%d",&x),mx=max(mx,x),x>v[i].back()) v[i].push_back(x);
}
for (sort(v+1,v+n+1,cmp),ans=0,i=1;i<=n;++i)
{
for (f[i]=v[i].size(),j=v[i].size()-1;~j;--j)
f[i]=max(f[i],T.get(v[i][j]-1)+((int)v[i].size()-j));
T.add(v[i].back(),f[i]); ans=max(ans,f[i]);
}
for (printf("%d\n",ans),i=1;i<=n;++i) T.clear(v[i].back());
}
return 0;
}