526互联

Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2)

发布时间 2023-08-28 15:18:52作者: 空気力学の詩

Preface

因为不清空E题调了好久才过，没时间看后面的题了遂2h下机，赛后感觉F还是可做的

这周三和周四的CF因为第二天有课可能都要开另一个小号随便打打了，毕竟有早八还打到两点钟实在是顶不住的说

A. Increasing and Decreasing

从后往前贪心地确定每个数，最后检验下即可

#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<ctime>
#include<limits.h>
#include<functional>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=1005;
int t,x,y,n,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; scanf("%d%d%d",&x,&y,&n); a[1]=x; a[n]=y;
		int dlt=1; for (i=n-1;i>1;--i) a[i]=a[i+1]-dlt,++dlt;
		if (a[2]-a[1]<=a[3]-a[2]) puts("-1"); else
		for (i=1;i<=n;++i) printf("%d%c",a[i]," \n"[i==n]);
	}
	return 0;
}

B. Swap and Reverse

注意到如果仅有第一个操作那么所有奇偶性相同的位置间会产生交换

同时若\(k\)为奇数那么也是同上，否则若\(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>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<functional>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=100005;
int t,n,k; char s[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; scanf("%d%d%s",&n,&k,s+1);
		if (k&1)
		{
			deque <char> v[2];
			for (i=1;i<=n;++i) v[i&1].push_back(s[i]);
			sort(v[0].begin(),v[0].end());
			sort(v[1].begin(),v[1].end());
			for (i=1;i<=n;++i) putchar(v[i&1].front()),v[i&1].pop_front();
			putchar('\n');
		} else
		{
			deque <char> v;
			for (i=1;i<=n;++i) v.push_back(s[i]);
			sort(v.begin(),v.end());
			for (i=1;i<=n;++i) putchar(v.front()),v.pop_front();
			putchar('\n');
		}
	}
	return 0;
}

C. Divisor Chain

正难则反，考虑倒着处理，对于某个数\(x\)，不难发现它能推出的最大的数就是\(2x\)，我们不妨从\(1\)开始先倍增找到最大且小于等于\(n\)的数\(y\)

然后考虑对\(n-y\)进行二进制分解，将剩下的需要补上的二的若干次幂从大到小接在后面即可

比如对于\(n=14\)，有（因为\(14-8=6=4+2\)，所以先加\(4\)后加\(2\)）：

\[1\to 2\to 4\to 8\to 12\to 14 \]

不难发现这样不仅每个差值最多出现两次，而且操作次数也是\(O(\log 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>
#include<ctime>
#include<limits.h>
#include<functional>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=1005;
int t,x,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; scanf("%d",&x); int y=1,cnt=1; a[1]=1;
		while (y<=x) a[++cnt]=(y*=2); y=x-a[--cnt];
		for (i=30;i>=0;--i) if (y>=(1<<i))
		a[cnt+1]=a[cnt]+(1<<i),++cnt,y-=(1<<i);
		for (printf("%d\n",cnt),i=cnt;i>=1;--i) printf("%d%c",a[i]," \n"[i==1]);
	}
	return 0;
}

D. Matrix Cascade

首先我们发现对于第一行的所有\(1\)的位置，都必须要进行操作，因为其它的操作都不能影响到它

同理我们这样做完第一行后，就是要对第二行的所有\(1\)的位置进行操作，依此类推直到处理完整个矩阵

因此这题的难点就在于怎么优化这个操作的过程，这里可以考虑用差分

考虑对于某个位置，会对它的值产生影响的操作的位置是一个倒三角的形状，我们不妨直接记录以某个点为倒三角下顶点时的操作次数

考虑\((x,y)\)的答案可以从\((x-1,y)\)的答案，再加上两条斜线的答案转移过来，因此分别维护这些信息即可

代码非常好写，复杂度\(O(n^2)\)

#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<ctime>
#include<limits.h>
#include<functional>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=3005;
int t,n,a[N][N],b[N][N],c[N][N]; char s[N][N];
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),i=1;i<=n;++i) scanf("%s",s[i]+1);
		int ans=0; for (i=1;i<=n;++i) for (j=1;j<=n;++j)
		{
			int cur=a[i-1][j]^b[i-1][j-1]^c[i-1][j+1]^(s[i][j]-'0');
			ans+=cur; a[i][j]=a[i-1][j]^b[i-1][j-1]^c[i-1][j+1]^cur;
			b[i][j]=b[i-1][j-1]^cur; c[i][j]=c[i-1][j+1]^cur;
		}
		printf("%d\n",ans);
	}
	return 0;
}

E. Guess Game

这题的核心其实还是要仔细理解题意，建议把样例看明白点就知道该怎么做了

首先我们发现如果\(a,b\)最高位不同，则所需的回合数就是\(1/2\)，这里先后手会有区别可以自己手玩理解下

而如果\(a,b\)最高位相同，则可以利用一次操作排除掉这一位的情况，递归处理后面的部分即可

然后我就写了个暴力检验了一下这个想法，发现能过样例就考虑优化了

不妨先通过枚举确定\(a\)的值，然后枚举\(b\)和\(a\)在哪一位开始出现不同，此时相当于要查询二进制下由某个前缀开头的数的个数，可以很容易地用0/1Trie来维护

但注意要特判完全相同的情况，这种做法复杂度是\(O(n\log^2 a_i)\)的

#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<ctime>
#include<limits.h>
#include<functional>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005,mod=998244353;
int t,n,a[N],rt;
inline void inc(int& x,CI y)
{
	if ((x+=y)>=mod) x-=mod;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
class Trie
{
	private:
		int ch[N*30][2],num[N*30],tot;
	public:
		inline void insert(int& now,CI x,CI d=30)
		{
			if (!now) now=++tot; ++num[now]; if (!~d) return;
			insert(ch[now][(x>>d)&1],x,d-1);
		}
		inline int query(CI now,CI lim,CI x,CI d=30)
		{
			if (d<lim) return num[now]; return query(ch[now][(x>>d)&1],lim,x,d-1);
		}
		inline void clear(void)
		{
			for (RI i=1;i<=tot;++i) ch[i][0]=ch[i][1]=num[i]=0; tot=rt=0;
		}
}T;
/*inline int calc(CI a,CI b)
{
	int ret=1; for (RI i=30;i>=0;--i)
	{
		int x=(a>>i)&1,y=(b>>i)&1;
		if (x!=y) return ret+x; ret+=x;
	}
	return ret;
}*/
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),i=1;i<=n;++i) scanf("%d",&a[i]),T.insert(rt,a[i]);
		int ans=0; for (i=1;i<=n;++i)
		{
			for (j=30;j>=0;--j) if ((a[i]>>j)&1) break;
			int x=0,k=1,cur=n; for (;j>=0;--j) 
			{
				int c=(a[i]>>j)&1,num=T.query(rt,j,x|((c^1)<<j));
				cur-=num; inc(ans,1LL*num*(k+c)%mod); x|=(c<<j); k+=c;
			}
			int num=T.query(rt,0,x); cur-=num; inc(ans,1LL*num*k%mod);
			inc(ans,cur);
		}
		//int ans=0; for (i=1;i<=n;++i) for (j=1;j<=n;++j) inc(ans,calc(a[i],a[j]));
		printf("%d\n",1LL*ans*quick_pow(1LL*n*n%mod)%mod); T.clear();
	}
	return 0;
}

后面ztc发现其实有一个\(\log\)的做法，就是直接在0/1Trie上DFS，然后直接把每个点的左右儿子配对算贡献即可，代码也相对来说更好写

#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<ctime>
#include<limits.h>
#include<functional>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005,mod=998244353;
int t,n,a[N],ans,rt;
inline void inc(int& x,CI y)
{
	if ((x+=y)>=mod) x-=mod;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
class Trie
{
	private:
		int ch[N*30][2],num[N*30],tot;
	public:
		inline void insert(int& now,CI x,CI d=30)
		{
			if (!now) now=++tot; ++num[now]; if (!~d) return;
			insert(ch[now][(x>>d)&1],x,d-1);
		}
		inline void solve(CI now,CI pre=1,CI d=30)
		{
			if (!now) return; solve(ch[now][0],pre,d-1); solve(ch[now][1],pre+1,d-1);
			inc(ans,1LL*num[ch[now][0]]*num[ch[now][1]]%mod*(2*pre+1)%mod);
			if (d==-1) inc(ans,1LL*num[now]*num[now]%mod*pre%mod);
		}
		inline void clear(void)
		{
			for (RI i=1;i<=tot;++i) ch[i][0]=ch[i][1]=num[i]=0; tot=rt=0;
		}
}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),i=1;i<=n;++i) scanf("%d",&a[i]),T.insert(rt,a[i]);
		ans=0; T.solve(rt); printf("%d\n",1LL*ans*quick_pow(1LL*n*n%mod)%mod); T.clear();
	}
	return 0;
}

F. Exotic Queries

比赛时候太困了看了眼题意好长就不想动脑了，后面发现其实也不是很难的说

考虑如果没有\(l,r\)的限制只是要把整个序列变成\(0\)的话该怎么做，不妨先假设答案为\(n\)，然后考虑什么时候能节约掉一些操作

考虑对于两个同样的数出现的临近的位置\(x,y\)，如果\([x+1,y-1]\)中没有\(<a_x=a_y\)的数的话则可以把这两个数合并在一个区间内，从而节省一次操作

现在考虑加入\(l,r\)的限制后该怎么处理，很经典地考虑离线，从小到大加入值为\(i\)的数然后考虑处理所有\(r=i\)的询问

注意由于我们是从小到大加入数的，因此对于每对临近的位置\(x,y\)，它们之间的所有已经加入的数都是小于\(i\)的

不妨设\([x+1,y-1]\)中的最大值为\(t\)，则很显然当\(l\le t\)时这对数就不能一起操作，否则就可以

分别用线段树维护最大值以及用树状数组维护区间修改，单点求值即可

#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<ctime>
#include<limits.h>
#include<functional>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=1e6+5;
int n,q,l,r,a[N],ans[N],c[N]; vector <int> pos[N]; vector <pi> ques[N];
class Tree_Array
{
	private:
		int bit[N];
	public:
		#define lowbit(x) (x&-x)
		inline int get(RI x,int ret=0)
		{
			for (;x<=n;x+=lowbit(x)) ret+=bit[x]; return ret;
		}
		inline void add(RI x)
		{
			for (;x;x-=lowbit(x)) ++bit[x];
		}
		#undef lowbit
}BIT;
class Segment_Tree
{
	private:
		int mx[N<<2];
		inline void pushup(CI now)
		{
			mx[now]=max(mx[now<<1],mx[now<<1|1]);
		}
	public:
		#define TN CI now=1,CI l=1,CI r=n
		#define LS now<<1,l,mid
		#define RS now<<1|1,mid+1,r
		inline void updata(CI pos,CI mv,TN)
		{
			if (l==r) return (void)(mx[now]=mv); int mid=l+r>>1;
			if (pos<=mid) updata(pos,mv,LS); else updata(pos,mv,RS); pushup(now);
		}
		inline int query(CI beg,CI end,TN)
		{
			if (beg<=l&&r<=end) return mx[now]; int mid=l+r>>1,ret=0;
			if (beg<=mid) ret=max(ret,query(beg,end,LS)); if (end>mid) ret=max(ret,query(beg,end,RS)); return ret;
		}
		#undef TN
		#undef LS
		#undef RS
}SEG;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d%d",&n,&q),i=1;i<=n;++i)
	scanf("%d",&a[i]),pos[a[i]].push_back(i);
	for (i=1;i<=q;++i) scanf("%d%d",&l,&r),ques[r].push_back(pi(l,i));
	for (i=1;i<=n;++i)
	{
		c[i]=c[i-1]; if (pos[i].size())
		{
			++c[i]; SEG.updata(pos[i][0],i);
			for (j=1;j<pos[i].size();++j)
			{
				int x=pos[i][j-1]+1,y=pos[i][j]-1;
				if (x<=y) BIT.add(SEG.query(x,y));
				SEG.updata(pos[i][j],i);
			}
		}
		for (auto [l,id]:ques[i]) ans[id]=c[i]-c[l-1]+BIT.get(l);
	}
	for (i=1;i<=q;++i) printf("%d\n",ans[i]);
	return 0;
}

Postscript

开学了得抗压打CF了，虽然会很难集中精力但也算是种修炼吧