黑龙江职业学院校赛第二场题解

前言

由于本人比较菜，只做出了9题，所以下面都是个人见解，如果有问题欢迎在评论区告诉我。总体而言题目偏简单的 比赛链接:https://ac.nowcoder.com/acm/contest/27150

A.龙职院卷怪争霸（暴力枚举） 思路

因为数据范围很小只有100，所以直接暴力枚举二重循环即可，当然也可以用单调栈做，单调栈学习链接：https://blog.csdn.net/m0_46201544/article/details/118891706

代码

#include
using namespace std;
#define ll long long
#define mod 1000000009
#define endl "\n"
#define PII pair
ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 2e6+10;
ll n,a[N],b[N];


int main()
{
	cin>>n;
	for(int i = 1;i >a[i];
		for(int j = i - 1;j >= 1; --j) {
			if(a[i] > a[j]) b[i]++;
		}
	}
	for(int i = 1;i ch,vis[ch] = true;
	coutzn>>qc>>z>>q;
	for(int i = 1;i >a[i],
	for(int i = 1;i >b[i];
	for(int i = 1;i >c[i];
	while(z--) {
		ll u,v;
		scanf("%lld%lld",&u,&v);
		u = find(u);
		v = find(v);
		if(u != v) fa[v] = u;
	}
	for(int i = 1;i s1>>s2;
	if(s1.find(s2) != -1) puts("YES");
	else puts("NO");
	
	return 0;
}

G.求素数（欧拉筛+二分） 思路

因为要求一个素数区间的素数个数，并且这个区间达到了 1 e 8 1e8 1e8，那么我们只能考虑使用欧拉筛（线性筛）将素数放在一个数组或者容器中，然后通过二分查找的方式进行一个 l o g 2 n log_2n log2​n级别的查询。

代码

#include
using namespace std;
#define ll long long
#define mod 1000000009
#define endl "\n"
#define PII pair
ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}


const int N = 100000005; 
int prime[7000000];
bool vis[N];
int cnt = 0;

void get_prime() {
	memset(vis,true,sizeof vis);
	memset(prime,0,sizeof prime);
	vis[0] = vis[1] = false;
	for(int i = 2; i >k;
	if(k%2==0) puts("-1");
	else cout