专栏文章

AC源Day2模拟赛复盘

MMarkLikeFlorr
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miokcnb5
此快照首次捕获于
2025/12/02 20:37
3 个月前
此快照最后确认于
2025/12/02 20:37
3 个月前
查看原文

单击此处添加标题

T1（30 WA）

签到题，套公式+快速幂可解（不知道为什么写了快速幂但只有30分 后记：~其实是公式打错了~，下面的是满分代码）
CPP
#include<bits/stdc++.h>
#define mod 200907
#define int unsigned long long
using namespace std;

int a,b,c,x,m,k;
int ksm(int u,int p){
	if(p==0) return 1;
	int tmp=u,cnt=1;
	while(p>0){
		if(p%2){
			cnt*=tmp;
			cnt%=mod;
		}
		p>>=1;
		tmp*=tmp;
		tmp%=mod;
	}
	return cnt;
}

signed main(){
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// freopen("seq.in","r",stdin);
	// freopen("seq.out","w",stdout);
 	
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>a>>b>>c>>x;
		if(b-a==c-b){
			k=b-a;
			k%=mod,a%=mod,x%=mod;
			// cout<<k<<" "<<a<<" "<<x<<"\n";
			cout<<(a+(k*(x-1))%mod)%mod<<"\n";
		}
		else{
			k=b/a;
			a%=mod,k%=mod;
			// cout<<k<<" "<<a<<" "<<x<<"\n";
			cout<<(a*ksm(k,x-1))%mod<<"\n";
			
		}
	}
	return 0;
}

T2（100 AC）

对偶数u进行分割，最后会得到lowbit(u)份，O(n)就可以拆完（我暴力拆然后线段树查询过的 ~然而在洛谷评测时MLE了~）
CPP
#include<bits/stdc++.h>
#define int unsigned long long
#define N 200005
using namespace std;

int n,m,cnt=0,sum[4*N];
struct www{
	int num,cnt;
} a[N];
void upd(int u){
	sum[u]=sum[u*2]+sum[u*2+1];
}
void dfs(int u,int l,int r){
	if(l==r){
		sum[u]=a[l].cnt;
		return;
	}
	int mid=(l+r)>>1;
	dfs(u*2,l,mid);
	dfs(u*2+1,mid+1,r);
	upd(u);
}
int query(int x,int u,int l,int r){
	if(l==r) return a[l].num;
	int mid=(l+r)>>1;
	if(x>sum[u*2]) return query(x-sum[u*2],u*2+1,mid+1,r);
	else return query(x,u*2,l,mid);
}

signed main(){
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	freopen("cake.in","r",stdin);
	freopen("cake.out","w",stdout);
	
	cin>>n;
	for(int i=1;i<=n;i++){
		int u;
		cin>>u;
		a[i].num=u;
		a[i].cnt++;
	}
	for(int i=1;i<=n;i++){
		while(a[i].num%2==0){
			a[i].num>>=1;
			a[i].cnt<<=1;
		}
	}
	dfs(1,1,n);
	cin>>m;
	for(int i=1;i<=m;i++){
		int u;
		cin>>u;
		cout<<query(u,1,1,n)<<"\n";
	}
	return 0;
}

T3（没写）

二分最小值，相当于有M*N课时时间，注意只能选最多M次Ai（一周只有一节课），贪心选课程/自习

T4（没写）

按左端点排序然后搜索线思想，贪心优先往左填，同左端点区间长度小的优先填，填不了了就cout<<"No"。
CPP
#include<bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;

int m,n,u,r;
struct www{
	int l,r;
	friend bool operator < (www x,www y){
		return x.r>y.r;
	}
} a[N];
bool cmp(www x,www y){
	return x.l<y.l;
}

signed main(){
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i].l>>a[i].r;
		}
		sort(a+1,a+n+1,cmp);
		bool nf=0;
		r=1,u=a[r].l;
		priority_queue<www> q;
		a[n+1].l=0,a[n+1].r=0;
		while(r<=n){
			while(r<=n&&a[r].l<=u){
				q.push(a[r]);
				r++;
			}
			if(q.empty()){
				if(r>n) break;
				u=a[r].l;
				q.push(a[r]);
				r++;
			}
			if(q.top().r<u){
				nf=1;
				break;
			}
			else{
				u++;
				q.pop();
			}
		}
		while(!q.empty()){
			if(q.top().r<u){
				nf=1;
				break;
			}
			else{
				u++;
				q.pop();
			}
		}
		if(nf) cout<<"No\n";
		else cout<<"Yes\n";
	}
	return 0;
}

T5（0 WA）

先考虑无环情况：前缀和的绝对值之和就是答案，再考虑有环：复制一遍消环，滑动窗口取小的（30分），观察转化问题为数轴选点使所有点与其距离最小，结论知选中位数（我写了贪心）

T6（没写）

二分最小值，将区间挂在端点上，遇到要加的数就从大根堆（维护区间长度）取出一个

总结：

  • ~骗分过样例，打表出奇迹~
  • 遇到最大值最小，最小值最大问题优先考虑二分答案
  • 搜索线思想很重要
OIer啊，要多想。
想了以后呢？
我只能告诉你在那之前要多想。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...