首页 > 其他分享 >Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2)

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

时间：2023-08-28 15:24:56浏览次数：35  
标签：typedef Space int Contest CI long Div include define

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了，虽然会很难集中精力但也算是种修炼吧

标签：typedef,Space,int,Contest,CI,long,Div,include,define
From： https://www.cnblogs.com/cjjsb/p/17662353.html

相关文章

  • java.lang.OutOfMemoryError: Java heap space 解决之道
    使用Java程序从数据库中查询大量的数据时出现异常:java.lang.OutOfMemoryError:Javaheapspace在JVM中如果98%的时间是用于GC且可用的Heapsize不足2%的时候将抛出此异常信息。JVM堆的设置是指java程序运行过程中JVM可以调配使用的内存空间的设置.JVM......
  • PermGen space简介
    PermGenspace简介 PermGenspace的全称是PermanentGenerationspace，是指内存的永久保存区域OutOfMemoryError:PermGenspace从表面上看就是内存益出，解决方法也一定是加大内存。说说为什么会内存益出：（1）这一部分用于存放Class和Meta的信息，Class在被Load的时候被放入PermGensp......
  • Codeforces Round 888 (Div. 3)G. Vlad and the Mountains（数据结构，图论）
    题目链接：https://codeforces.com/contest/1851/problem/G 大致题意： 给出n个点m条边的无向图，每个点有点权h【i】。从点i到点j会消耗h【j】-h【i】的能量，如果小于0，那么就是恢复对应绝对值的能量。 进行q次询问，每次询问包含起点s，终点t，能量e，能量在移动过程中不能小......
  • Codeforces Round 887 (Div. 1)C. Ina of the Mountain（数据结构，反悔贪心）
    题目链接：https://codeforces.com/problemset/problem/1852/C 题意： 给定一个长度为n的序列和正整数k； 每次可以选取任意一个区间，将区间内每个数减1； 如果出现一个数变成0，那么那个数变成k； 问至少操作多少次可以使得每个数变成k； 分析： 将每个数值抽象为对应高度的......
  • Codeforces Round 892 (Div. 2)E. Maximum Monogonosity（动态规划，数学）
    题目链接：https://codeforces.com/contest/1859/problem/E 题意： 有长度为n的a和b俩个序列，定义f【l，r】=abs（a【l】-b【r】）+abs（b【l】-a【r】）； 给正整数k，求 不相交的区间且  所有  区间的长度 的 和 为k的最大值 是多少？ 分析： 这里借鉴一个佬......
  • Educational Codeforces Round 151 (Rated for Div. 2)E. Boxes and Balls（数学，动态规
    题目链接：https://codeforces.com/contest/1845/problem/E 题意： 给定长度为n且只含0和1的数组，你可以进行以下操作： 交换相邻的0和1； 给正整数k，问经过k次操作后，会有多少种本质不同的结果； 分析： 如果1比0多，我们可以把他们取反（让0比1多，结果是一样的） 设计状态dp[i][j......
  • Codeforces Round 885 (Div. 2)E. Vika and Stone Skipping（数学，质因数分解）
    题目链接：https://codeforces.com/problemset/problem/1848/E 大致题意： 打水漂，某人在海岸线以f（正整数）的力量扔出石头，会在f，f+（f-1），f+（f-1）+（f-2），........，f+（f-1）+.....+2+1，的位置接触水面； 现在给出坐标x和q次询问，每次询问给出一个y值，将x=x*y；假设石头在x的位置接触水面，问有多少......
  • Codeforces Round 885 (Div. 2) F. Vika and Wiki（数学，倍增）
    题目链接：https://codeforces.com/problemset/problem/1848/F 大致题意：长度为n（n是2的幂次），每轮让a【i】=a【i】^a【i%n+1】，（^为异或）问需要操作多少次后可以使得每个数为0； 解题思路：我们来观察：第一次相当于：a【i】=a【i】^a【i+1】，a【i+1】=a【i+1】^a【i+2】第二次......
  • Educational Codeforces Round 152 (Rated for Div. 2)E. Max to the Right of Min（数
    题目链接：https://codeforces.com/problemset/problem/1849/E 大致题意： 长度为n的序列，求有多少个区间满足区间最大值在区间最小值的右边？ 解题思路： （此题有使用线段树等其他做法，本处使用的是单调栈做法） 我们先求出每个a【i】的左边的比他小的LMIN，左边比他大的LMAX，右......
  • Codeforces Round 889 (Div. 1)C. Expected Destruction（期望，动态规划）
    题目链接：https://codeforces.com/problemset/problem/1854/C 大致题意： 有一个集合S，和一个上界m； 现在每秒钟可以进行一次如下操作： 1：等概率的选取S中的一个元素x；2：将x从S中移走；3：如果x+1不大于m并且x+1不在S中，那么添加x+1在S里面 问期望多少秒钟后可以使得S为空集（答......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99