Preface

经典秒完SB题然后开始坐牢1h，写了个E的假算法T在24个点就不管了打lol去了

妈的怎么稍微难点的题就是想不到呢

A. Morning Sandwich

签到

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=100005;
int t,b,c,h;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d%d",&b,&c,&h); int t=b-1;
		if (c+h>=t) printf("%d\n",b+t); else printf("%d\n",(c+h)*2+1);
	}
	return 0;
}

B. Monsters

令\(b_i=a_i\bmod k\)，将数按照二元组\((b_i,i)\)排序后输出即可，其中第一维从大到小，第二维从小到大

注意\(b_i=0\)时要转化成\(b_i=k\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=300005;
int t,n,k,a[N],b[N],id[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%d",&n,&k),i=1;i<=n;++i)
		if (scanf("%d",&a[i]),b[i]=a[i]%k,id[i]=i,!b[i]) b[i]=k;
		auto cmp=[&](CI x,CI y)
		{
			return b[x]!=b[y]?b[x]>b[y]:x<y;
		};
		for (sort(id+1,id+n+1,cmp),i=1;i<=n;++i) printf("%d%c",id[i]," \n"[i==n]);
	}
	return 0;
}

C. Binary String Copying

刚开始一眼没思路就直接跳，后面冷静下来感觉可以写个Hash试一波

然后就直接过了，也没啥好说的

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=200005;
const int mod1=998244353,mod2=19260817;
struct Hasher
{
	int x,y;
	inline Hasher(CI X=0,CI Y=0)
	{
		x=X; y=Y;
	}
	inline LL val(void)
	{
		return ((1LL*x)<<31LL)|(1LL*y);
	}
	friend inline bool operator == (const Hasher& A,const Hasher& B)
	{
		return A.x==B.x&&A.y==B.y;
	}
	friend inline Hasher operator + (const Hasher& A,const Hasher& B)
	{
		return Hasher((A.x+B.x)%mod1,(A.y+B.y)%mod2);
	}
	friend inline Hasher operator - (const Hasher& A,const Hasher& B)
	{
		return Hasher((A.x-B.x+mod1)%mod1,(A.y-B.y+mod2)%mod2);
	}
	friend inline Hasher operator * (const Hasher& A,const Hasher& B)
	{
		return Hasher(1LL*A.x*B.x%mod1,1LL*A.y*B.y%mod2);
	}
}h[N],pw[N],one[N];
const Hasher seed=Hasher(31,131);
int t,n,m,l,r,pfx[N]; char s[N]; set <LL> rst;
inline Hasher get(Hasher *h,CI l,CI r)
{
	if (l>r) return Hasher();
	return h[r]-h[l-1]*pw[r-l+1];
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%d%s",&n,&m,s+1),pw[0]=Hasher(1,1),i=1;i<=n;++i)
		pw[i]=pw[i-1]*seed,one[i]=one[i-1]*seed+Hasher(1,1),h[i]=h[i-1]*seed+Hasher(s[i]-'0',s[i]-'0'),pfx[i]=pfx[i-1]+s[i]-'0';
		int num=0; for (rst.clear(),i=1;i<=m;++i)
		{
			scanf("%d%d",&l,&r); int c1=pfx[r]-pfx[l-1];
			Hasher tmp=get(h,1,l-1)*pw[n-l+1]+one[c1]*pw[n-r]+get(h,r+1,n);
			if (!rst.count(tmp.val())) ++num,rst.insert(tmp.val());
		}
		printf("%d\n",num);
	}
	return 0;
}

D. Array Painting

考虑把所有非\(0\)的连续段找出来，显然如果某个段\([l,r]\)内有\(2\)的话那么它一定可以把\([l-1,r+1]\)都涂色

否则如果该段都为\(1\)那么就只能涂\([l-1,r]\)或者\([l,r+1]\)

很容易想到贪心，先把有\(2\)的段全涂了，然后全\(1\)的段优先涂左边那个格，如果已经涂了就涂右边

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=200005;
int n,a[N],c[N],ret;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
	for (i=1;i<=n;++i) if (a[i])
	{
		for (j=i;j<=n&&a[j];++j); ++ret;
		bool flag=0; for (k=i;k<j;++k) if (a[k]==2) flag=1;
		for (k=i;k<j;++k) c[k]=1;
		if (flag==1) c[i-1]=c[j]=1; else
		{
			if (i>1&&!c[i-1]) c[i-1]=1; else c[j]=1;
		}
		i=j-1;
	}
	for (i=1;i<=n;++i) if (!c[i]) ++ret;
	return printf("%d\n",ret),0;
}

E. Max to the Right of Min

比赛的时候一直想着枚举中间的某个点，发现难算的一比

其实考虑枚举右端点，考虑移动左端点对答案造成的影响

由于要统计区间最大最小，很容易想到开两个单调栈，这样我们可以对每个右端点\(r\)维护出若干个事件\((l,tp=0/1)\)，表示当左端点\(l\)是区间\([l,r]\)最小值（\(tp=0\)），或区间\([l,r]\)最大值（\(tp=1\)）

考虑如何统计答案，将所有事件按照第一维从小到大排序，不难发现对于两个相邻的事件\((l_i,tp_i),(l_{i+1},tp_{i+1})\)，若\(tp_{i+1}=0\)，则左端点为\([l_i+1,l_{i+1}]\)时都是合法的

那么我们就直接维护一个对应的事件集合，由于贡献的添加与删除都是和相邻的元素间产生，因此很好维护

总复杂度\(O(n\log n)\)，据说有用双端队列实现的\(O(n)\)做法，但懒得去看了

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=1e6+5;
int n,a[N],stkmi[N],topmi,stkmx[N],topmx,cur; LL ans; set <pi> s;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
	for (s.insert(pi(0,0)),s.insert(pi(0,1)),i=1;i<=n;++i)
	{
		while (topmi&&a[stkmi[topmi]]>a[i])
		{
			auto it=s.lower_bound(pi(stkmi[topmi],0)),pre=it,nxt=it;
			--pre; ++nxt; cur-=it->fi-pre->fi;
			if (nxt!=s.end()&&nxt->se==0) cur+=nxt->fi-pre->fi;
			s.erase(it); --topmi;
		}
		cur+=i-s.rbegin()->fi; s.insert(pi(i,0)); stkmi[++topmi]=i;
		while (topmx&&a[stkmx[topmx]]<a[i])
		{
			auto it=s.lower_bound(pi(stkmx[topmx],1)),pre=it,nxt=it;
			--pre; ++nxt;
			if (nxt!=s.end()&&nxt->se==0) cur+=it->fi-pre->fi;
			s.erase(it); --topmx;
		}
		s.insert(pi(i,1)); stkmx[++topmx]=i; ans+=cur;
	}
	return printf("%lld",ans-n),0;
}

F. XOR Partition

据说是经典老题，反正我没见过的说

考虑有一个\(n\)个点的图，图中两个点\(x,y\)之间的边权就是\(a_x\oplus a_y\)

由于最大值最小，很容易想到用类似克鲁斯卡尔求MST的思想，每次考虑当前最小的异或对\((x,y)\)，显然我们需要把它们放进不同的集合中才能让答案变优

因此不难发现当我们给这个图跑一遍最小异或生成树后答案就确定了，只要对生成树跑一个黑白染色即可

而这个是一个经典问题了，大致做法就是分治，从高位到低位考虑

很显然高位相同的数一定要在一组内，同时根据抽屉原理如果当前位分组如果数的个数大过\(2\)，那么无论你怎么分这一位在最终答案都是\(0\)

那么这题只要求输出方案的话其实代码就很好写了，每次递归到不能划分的时候暴力处理即可

但如果要求最小异或生成树的边权和的话，就考虑每次将两个集合内部的联通块先连起来，然后考虑要在两个集合中间连一条边

可以把某一个集合的所有数扔进0/1Trie里，然后在另一边查询即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<limits.h>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=200005;
int n,ans[N]; pi a[N];
inline void solve(CI l,CI r,CI d)
{
	if (d<0||l>r) return; int mid=l-1;
	while (mid+1<=r&&((a[mid+1].fi>>d)&1)==0) ++mid;
	if (mid-l+1>=3||r-mid>=3) return solve(l,mid,d-1),solve(mid+1,r,d-1);
	int tot=r-l+1,mx=0,res=0; RI i,j,k;
	for (i=0;i<(1<<tot);++i)
	{
		int cur=INT_MAX; for (j=0;j<tot;++j) for (k=j+1;k<tot;++k)
		if (((i>>j)&1)==((i>>k)&1)) cur=min(cur,a[l+j].fi^a[l+k].fi);
		if (cur>mx) mx=cur,res=i;
	}
	for (i=0;i<tot;++i) if ((res>>i)&1) ans[a[l+i].se]=1;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i].fi),a[i].se=i;
	for (sort(a+1,a+n+1),solve(1,n,30),i=1;i<=n;++i) putchar(ans[i]?'1':'0');
	return 0;
}