牛客小白月赛39

2023-12-03 19:53:04

牛客小白月赛39

A.憧憬

签到，\(O(n^2)\)枚举即可。

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 5e5 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

int n;
struct Node{
	int x1,y1,x2,y2;
}e[N];

int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d %d %d %d",&e[i].x1,&e[i].y1,&e[i].x2,&e[i].y2);
	}
	int a,b,c,d;
	scanf("%d %d %d %d",&a,&b,&c,&d);
	int res1=c-a,res2=d-b;
	int D=gcd(res1,res2);
	res1=res1/D;
	res2=res2/D;
	for(int i=1;i<=n;++i){
		for(int j=i+1;j<=n;++j){
			int _1=e[i].x1+e[j].x1;
			int _2=e[i].x2+e[j].x2;
			int _3=e[i].y1+e[j].y1;
			int _4=e[i].y2+e[j].y2;
			int ans1=(_2-_1);
			int ans2=(_4-_3);
			D=gcd(ans1,ans2);
			ans1=ans1/D;
			ans2=ans2/D;
			if(ans1==res1 && ans2==res2){
				puts("YES");
				return 0;
			}
		}
	}
	puts("NO");
	return 0;
}

B. 欢欣

签到

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

char s[N];

int main() {
	scanf("%s",s);
	int n=strlen(s);
	for(int i=0;i<n-2;++i){
		if(s[i]=='Q' && s[i+1]=='A' && s[i+2]=='Q'){
			printf("%d",i+1);
			return 0;
		}
	}
	return 0;
}

C. 奋发

可以将题意模拟成两个板子不断往上跑的过程，然后判断一下当前在最下面的板子和上一个在最上面的板子是否相交，计算贡献即可。

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 4e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

int n;
int a[N],b[N    ];
ll ans;

int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d %d",&a[i],&b[i]);
		ll mx=max(a[i-1],b[i-1]);
		ll mi=min(a[i],b[i]);
		if(mx<=mi) ans+=mi-mx+1;
		if(a[i-1]==b[i-1]) ans--;
	}
	printf("%lld\n",ans);
	return 0;
}

根据题意，\(x=0\)，啥也没发生，如果\(x>1\)那么，\([l,r]\)内质数个数直接清零，\(x=1\)时，对\(l=1\)先单独讨论一下，然后在看\([2,r]\)，此时的操作为对\(a[i]\)乘上\(i\)，那么如果\(a[i]>1\)，必然为合数，如果\(a[i]=1\)，那么我们看\(i\)是否为质数，当且仅当第一次操作时可以将\(a[i]\)变成质数，那么这个过程我们可以用线段树来维护区间质数个数和\(a[i]=1\)并且\(i\)为质数的个数，然后标记\(x=1\)时的操作总次数即可。

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

int n,m;
int a[N];
int prime[N],cnt;
bool vis[N];
struct Node{
	int l,r;
	int tag;
	int cnt;
	int cnt1;
}tr[N<<4];


void get_prime(int n){
	for(int i=2;i<=n;++i){
		if(!vis[i]) prime[cnt++]=i;
		for(int j=0;j<cnt && prime[j]<=n/i;++j){
			vis[i*prime[j]]=true;
			if(i%prime[j]==0) break;
		}
	}
}

void push_up(int u){
	tr[u].cnt=tr[u<<1].cnt+tr[u<<1|1].cnt;
	tr[u].cnt1=tr[u<<1].cnt1+tr[u<<1|1].cnt1;
}

void push_down(int u){
	if(tr[u].tag){
		tr[u<<1].tag+=tr[u].tag;
		tr[u<<1|1].tag+=tr[u].tag;
		if(tr[u].tag==1){
			tr[u<<1].cnt=tr[u<<1].cnt1;
			tr[u<<1|1].cnt=tr[u<<1|1].cnt1;
			tr[u<<1].cnt1=tr[u<<1|1].cnt1=0;
		}
		else{
			tr[u<<1].cnt=tr[u<<1].cnt1=0;
			tr[u<<1|1].cnt=tr[u<<1|1].cnt1=0;
		}
		tr[u].tag=0;
	}
}

void build(int u,int l,int r){
	if(l==r){
		int res1,res2;
		if(!vis[a[l]]) res1=1;
		else res1=0;
		if(a[l]==1 && !vis[l]) res2=1;
		else res2=0;
		tr[u]={l,r,0,res1,res2};
		return;
	}
	tr[u]={l,r,0};
	int mid=(l+r)>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	push_up(u);
}

void update(int u,int L,int R,int k){
	if(tr[u].l>=L && tr[u].r<=R){
		if(k==1){
			tr[u].cnt=tr[u].cnt1;
			tr[u].cnt1=0;
		}
		else{
			tr[u].cnt=0;
			tr[u].cnt1=0;
		}
		tr[u].tag+=k;
		return;
	}
	int mid=(tr[u].l+tr[u].r)>>1;
	push_down(u);
	if(!tr[u].cnt1 && !tr[u].cnt) return;
	if(L<=mid) update(u<<1,L,R,k);
	if(R>mid) update(u<<1|1,L,R,k);
	push_up(u);
}

int query(int u,int L,int R){
	if(tr[u].l>=L && tr[u].r<=R){
		return tr[u].cnt;
	}
	int mid=(tr[u].l+tr[u].r)>>1;
	push_down(u);
	int sum=0;
	if(L<=mid) sum+=query(u<<1,L,R);
	if(R>mid) sum+=query(u<<1|1,L,R);
	return sum;
}

int main() {
	scanf("%d %d",&n,&m);
	get_prime(1000000);	
	vis[1]=true;
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	build(1,2,n);
	while(m--){
		int op;
		int l,r;
		scanf("%d %d %d",&op,&l,&r);
		int tmp=0;
		if(l==1){
			if(!vis[a[1]]) tmp++;
			l++;
		}
		if(op==1){
			int x;
			scanf("%d",&x);
			if(x==1) update(1,l,r,1);
			else if(x>1) update(1,l,r,2);
			printf("%d\n",tmp+query(1,l,r));
		}
		else printf("%d\n",tmp+query(1,l,r));
	}
	return 0;
}

E.迷惘

二进制模拟

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 5e5 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

int n;
ll x;

int main() {
	scanf("%d",&n);
	ll res=0;
	for(int i=1;i<=n;++i){
		scanf("%lld",&x);
		if(x==0){
			continue;
		}
		vector<int> v;
		while(x){
			v.pb(x%2);
			x/=2;
		}
		int cur=0;
		while(v[cur]==0){
			cur++;
		}
		ll base=1;
		for(int i=(int)v.size()-1;i>=cur;--i){
			res+=v[i]*base;
			base*=2;
		}
	}
	printf("%lld\n",res);
	return 0;
}

G. 冷静

也就是求所有质因数分解后最小质因子大于等于\(k\)的数的个数，\(n\)最大为\(3e6\)，那么我们将询问离线存下来然后按\(n\)排序，线性的用树桩数组处理每个询问即可。复杂度\(O(q+n)\).

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 4e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

int q;
int n,k;
int prime[N],cnt;
bool vis[N];
int res[N];
struct Node{
	int n,k,id;
}e[N];
int c[N];
int ans[N];

void get_prime(int n){
	for(int i=2;i<=n;++i){
		if(!vis[i]) prime[cnt++]=i,res[i]=i;
		for(int j=0;j<cnt && prime[j]<=n/i;++j){
			vis[i*prime[j]]=true;
			res[i*prime[j]]=prime[j];
			if(i%prime[j]==0) break;
		}
	}
}

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

void update(int i,int k){
	while(i<=3000010){
		c[i]+=k;
		i+=lowbit(i);
	}
}

int query(int i){
	int res=0;
	while(i){
		res+=c[i];
		i-=lowbit(i);
	}
	return res;
}

int main() {
	get_prime(3000010);
	scanf("%d",&q);
	for(int i=1;i<=q;++i){
		scanf("%d %d",&e[i].n,&e[i].k);
		e[i].id=i;
	}
	sort(e+1,e+1+q,[&](Node a,Node b){
			return a.n<b.n;
	});
	int cur=1;
	for(int i=1;i<=q;++i){
		while(cur<e[i].n){
			cur++;
			update(res[cur],1);
		}
		ans[e[i].id]=e[i].n-1-query(e[i].k-1); //e[i].n-1,因为没有1
	}
	for(int i=1;i<=q;++i) printf("%d\n",ans[i]);
	return 0;
}

H.终别

贪心，考虑到第一个位置和最后一个位置我们肯定要选，那么计算一下前缀和后缀的贡献和，再枚举用魔法消灭的两个位置，维护答案的最小值。

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

int n;
int a[N],b[N];
ll l[N],r[N];

int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	for(int i=1;i<=n;++i){
		l[i]=l[i-1]+a[i];
		if(i+1<=n) a[i+1]=max(0,a[i+1]-a[i]);
		if(i+2<=n) a[i+2]=max(0,a[i+2]-a[i]);
	}
	for(int i=n;i>=1;--i){
		r[i]=r[i+1]+b[i];	
		if(i-1>=1) b[i-1]=max(0,b[i-1]-b[i]);
		if(i-2>=1) b[i-2]=max(0,b[i-2]-b[i]);
	}
	ll ans=1e18;
	for(int i=1;i<=n;++i){
		ans=min(ans,l[i-1]+r[i+2]);
	}
	printf("%lld\n",ans);
	return 0;
}

码农公寓

牛客小白月赛39

牛客小白月赛39

A.憧憬

B. 欢欣

C. 奋发

D.绝望

E.迷惘

G. 冷静

H.终别

码农公寓

牛客小白月赛39

A.憧憬

B. 欢欣

C. 奋发

D.绝望

E.迷惘

G. 冷静

H.终别

相关文章