专栏文章

国庆集训Day1

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

文章操作

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

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

123

比赛

重载运算符

CPP
struct node{
	int x,y;
	friend bool operator < (node p,node q){
		if(p.x!=q.x)return p.x<q.x;
		return p.y<q.y 
	}
	friend bool operator > (node p,node q){
		if(p.x!=q.x)return p.x>q.x;
		return p.y>q.y 
	}
};

[蓝桥杯 2015 国 B] 密文搜索

CPP
#include<bits/stdc++.h>
using namespace std;
string s;
map <string,int> m;
int t,ans; 
signed main(){
	cin>>s>>t;
	while(t--){
		string a;
		cin>>a;
		sort(a.begin(),a.end());
		m[a]++;
	}
	for(int i=0;i+7<=(int)s.size();i++){
		string b=s.substr(i,8);
		sort(b.begin(),b.end());
		ans+=m[b];
	}
	printf("%d",ans);
	return 0;
}
/*
1 ≤n ≤1000
*/
  • 思路就是分类，然后根据字典序排序后的字符串判相等

[蓝桥杯 2018 省 B] 日志统计

CPP
#include<bits/stdc++.h>
#define pb push_back
#define int long long//好习惯 
using namespace std;
int n,d,k,mx;
vector <int> v[100005];
signed main(){
	scanf("%lld%lld%lld",&n,&d,&k);
	for(int i=1;i<=n;i++){
		int ts,id;
		scanf("%lld%lld",&ts,&id);
		v[id].pb(ts);
		mx=max(mx,id);
	}
	for(int i=0;i<=mx;i++){
		sort(v[i].begin(),v[i].end());
		int l=0,r=k-1;
		bool fl=0;
		while(!fl&&r<v[i].size()){
			if(v[i][r]<d+v[i][l]){
				fl=1;
				printf("%lld\n",i);
			}
			l++;
			r++;
		}
	}
	return 0;
}
/*
id =0 
数组 1e5 
感觉 1e5*1e5 要用龙龙 
*/
  • 依旧分组

Cross Explosion

CPP
#include<bits/stdc++.h>
#define lb lower_bound
#define ub upper_bound 
const int inf=1e9+7;
using namespace std;
set <int> n[400005];
set <int> m[400005];
int h,w,q,ans;
void de(int x,int y){
	if(x==-inf||x==inf||y==-inf||y==inf)return;
	n[x].erase(y);
	m[y].erase(x);
	return ;
}
signed main(){
	cin>>h>>w>>q; 
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			n[i].insert(j);
		}
		n[i].insert(-inf);
		n[i].insert(inf);
	}
	for(int i=1;i<=w;i++){
		
		for(int j=1;j<=h;j++){
			m[i].insert(j);
		}
		m[i].insert(-inf);
		m[i].insert(inf);
	}
	while(q--){
		int x,y;
		cin>>x>>y;
		if(n[x].count(y)){//删过 
			de(x,y);
		} 
		else{//没删过 
			//左
			auto it=n[x].ub(y);
			auto it2=it;
			it--;
			de(x,*it);
			de(x,*it2);
			//上!!
			it=m[y].ub(x);
			it2=it;it--;
			de(*it,y);
			//下 
			it++;
			de(*it2,y);
		}
	}
	for(int i=1;i<=h;i++){
		ans+=(int)n[i].size()-2;
	}
	cout<<ans;
	return 0;
}
/*
 
*/
  • 这道题要注意的是二分查找删除处，不能用一个指针删完第一个在减一，因为删完第一个后元素位置会变，再减一就不是我们想要的值了，卡了我一天啊

Buildings

CPP
#include<bits/stdc++.h>
using namespace std;
int n;
int a[200005];
int f[200005];
priority_queue <int,vector<int>,greater<int> > q;
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	q.push(a[n]);
	for(int i=n-1;i>=1;i--){
		f[i]=q.size();
		while(q.top()<a[i]&&!q.empty()){
			q.pop();
		}
		q.push(a[i]);
	}
	for(int i=1;i<=n;i++){
		printf("%d ",f[i]);
	}
	return 0;
}
/*

*/
  • 也是拿到123第94500次测评了
  • 我们先维护一个容器(不知道是干啥的)，然后最后的一个值放进去，再找第二个放进去(最后两个肯定会去 [1,0][1,0] )，到第三个的时候……会发现，很多值是无效的，因为前面还有比他大的值，所以遍历到每个点的时候，就把比这个点小的删掉，这时候值的数量就是答案

Max × SumE

CPP
#include<bits/stdc++.h>
#define int long long 
using namespace std;
struct node{
	int a,b;
}s[200005];
int t;
bool cmp(node x,node y){
	return x.a<y.a;
}
signed main(){
	scanf("%lld",&t);
	while(t--){
		int n,k;
		scanf("%lld%lld",&n,&k);
		for(int i=1;i<=n;i++){
			scanf("%lld",&s[i].a);
		}
		for(int i=1;i<=n;i++){
			scanf("%lld",&s[i].b);
		}
		sort(s+1,s+n+1,cmp);
		priority_queue <int> q;
		int sum=0;
		int ans=0x7fffffffffff;
		for(int i=1;i<=k;i++){
			q.push(s[i].b);
			sum+=s[i].b;
		}
		ans=sum*s[k].a;
		for(int i=k+1;i<=n;i++){
			if(s[i].b>q.top()) continue;
			sum-=q.top();
			sum+=s[i].b;
			q.pop();
			q.push(s[i].b);
			ans=min(ans,sum*s[i].a);
		}
		printf("%lld\n",ans);
	}
	return 0;
}
/*
不开long long见祖宗 
*/
  • 遇到求乘积最小值时，我们只看一个因子变小，另一些因子变大的情况
  • 我们可以根据 aa 从小到大排序，然后不断枚举最大值，如果新加进来的 bb 不能让 sumsum 变小（即不比上一个答案的值中的任何一个大），就没有必要记录答案了（因为两个因子都变大，积肯定变大）

凌乱的yyy / 线段覆盖

CPP
#include<bits/stdc++.h>
using namespace std;
int n,ans;
struct node{
	int be,la;
}a[1000006];
bool cmp(node x,node y){
	if(x.la==y.la) return x.be>y.be;
	return x.la<y.la;
}
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i].be,&a[i].la);
	}
	sort(a+1,a+n+1,cmp);
	int l=a[1].la;
	ans++;
	for(int i=2;i<=n;i++){
		if(l<=a[i].be){
			ans++;
			l=a[i].la;
		}
	}
	printf("%d",ans);
	return 0;
}
/*
数组：1e6
 
*/
  • 比较模版的贪心

区间选点

CPP
#include<bits/stdc++.h>
using namespace std;
int n,ans;
struct node{
	int be,la;
}a[100006];
bool cmp(node x,node y){
	if(x.la==y.la) return x.be>y.be;
	return x.la<y.la;
}
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i].be,&a[i].la);
	}
	sort(a+1,a+n+1,cmp);
	int l=a[1].la;
	ans++;
	for(int i=2;i<=n;i++){
		if(l<a[i].be){
			ans++;
			l=a[i].la;
		}
	}
	printf("%d",ans);
	return 0;
}
/*
数组：1e5
*/
  • 蓝桥的题
  • 贪心，如果上一次选的数能覆盖就不管，否则就选最右侧的(影响更多的区间，当时咋没想出来)

区间分组

CPP
#include<bits/stdc++.h>
using namespace std;
int n,ans,now;
map <int,int> m;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		m[l]++;
		m[r+1]--;
	}
	for(auto i:m){
		now+=i.second;
		ans=max(ans,now);
	}
	printf("%d",ans);
	return 0;

}
/*
数组：1e5 
*/
  • 其实就是看某一时间点最多有多少个区间重叠，在安吉做过了
  • 因为 l,rl,r 范围很大，所以用map节省空间(类似离散化)

区间合并

CPP
#include<bits/stdc++.h>
using namespace std;
int n,ans,now;
struct node{
	int be,la;
}a[100006];
bool cmp(node x,node y){
	return x.be<y.be;
}
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i].be,&a[i].la);
	}
	sort(a+1,a+n+1,cmp);
	now=a[1].la;
	for(int i=2;i<=n;i++){
		if(now<a[i].be){
			ans++;
			now=a[i].la;
			continue;
		}
		now=max(now,a[i].la);
	}
	printf("%d",ans+1);
	return 0;
}
/*
数组：1e5
*/
  • 先找最靠左的区间(所以按照左边界排序)，取出右边界，继续合并
  • 如果有个右边界合并不了了，那么他就没有存在的必要了，既然这个左边界都比他大，那剩下的肯定都合并不了所以只存一个当前右边界即可

蚂蚁感冒

CPP
#include<bits/stdc++.h>
using namespace std;
int n,ans1,ans2;
signed main(){
	scanf("%d",&n);
	int a;
	scanf("%d",&a);
	if(a<0){
		bool fl=0;
		for(int i=1;i<n;i++){
			int b;
			scanf("%d",&b);
			if(abs(b)<abs(a)&&b>0){
				ans1++;
				fl=1;
			}
			else if(abs(b)>abs(a)&&b<0){
				ans2++;
			}
		}
		if(fl){
			printf("%d",ans1+ans2+1);
		}
		else{
			printf("1");
		}
	}
	else{
			bool fl=0;
			for(int i=1;i<n;i++){
				int b;
				scanf("%d",&b);
				if(abs(b)>abs(a)&&b<0){
					ans1++;
					fl=1;
				}
				else if(abs(b)<abs(a)&&b>0){
					ans2++;
				}
			}
			if(fl){
				printf("%d",ans1+ans2+1);
			}
			else{
				printf("1");
			}
	}
	return 0;
}
  • 这里有个思想，就是碰撞后回头其实是和经过等价
  • 基于这个思想，我们就推断出：
  • 当起始点向右时：左边向右的(必须有右边向左的)和右边向左的碰撞，以此类推

Flavors

CPP
#include<bits/stdc++.h>
using namespace std;
int n,mx,ms,ans;
map <int,pair<int,int> > m;
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		if(y>mx){
			mx=y;
			ms=x;
		}
		if(y>m[x].first){
			m[x].second=m[x].first;
			m[x].first=y;
		}
		else if(y>m[x].second){
			m[x].second=y;
		}
	}
	for(auto i:m){
		//cerr<<i.first<<" "<<i.second.first<<" "<<i.second.second<<"\n";
		if(i.first==ms){
			ans=max(ans,mx+i.second.second/2);
		}
		else{
			ans=max(ans,mx+i.second.first);
		}
	}
	printf("%d",ans);
	return 0;
}
  • 非常简单，没啥好说的

Many Segments 2

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,ans;
int f[200005];
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++){
		f[i]=m;
	}
	bool fl=1;
	for(int i=1;i<=n;i++){
		int l,r;
		scanf("%lld%lld",&l,&r);
		f[l]=min(r-1,f[l]);
		if(l==r&&l==1) fl=0;
	}
	if(fl==0){
		f[1]=0;
	}
	for(int i=m-1;i>=1;i--){
		f[i]=min(f[i],f[i+1]);
	}
	for(int i=1;i<=m;i++){
		ans+=f[i]-i+1;
	}
	printf("%lld",ans);
	return 0;
}
/*
2e5
*/
  • fif_i 的含义就是 ii 点最有端最多到哪
  • 每当有一个线段输入进来，那就会影响左端点及其之前的，但修改会大大增加时间复杂度，所以只修改左端点，最后从右向左取最小值

New Place

CPP
#include<bits/stdc++.h>
using namespace std;
bool check(string a,string b){
	sort(a.begin(),a.end());
	sort(b.begin(),b.end());
	return a==b;
}
int n,ans;
string a,b;
signed main(){
	cin>>n>>a>>b;
	if(!check(a,b)){
		//TODO
		printf("-1");
		return 0;
	}
	int j=n-1;
	for(int i=n-1;i>=0;i--){
		while(j>=0&&a[i]!=b[j]){
			j--;
		}
		if(j<0){
			break;
		}
		ans++;
		j--;
	}
	cout<<n-ans;
	
	return 0;
}
  • 因为它是从头取，所以就是在 AA 中的最长后缀在 BB 中是子序列的长度

Equal Cut

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans=0x7fffffffffffff;
int a[200005];
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		a[i]+=a[i-1];
	}
	int l=1,r=3;
	for(int mid=2;mid<=n-2;mid++){
		while(l+1<mid&&abs(a[mid]-a[l]-a[l])>abs(a[mid]-a[l+1]-a[l+1])){l++;}
		while(r+1<n&&abs(a[n]-a[r]-a[r]+a[mid])>abs(a[n]-a[r+1]-a[r+1]+a[mid])){r++;}
		ans=min(ans,max({a[l],a[mid]-a[l],a[r]-a[mid],a[n]-a[r]})-min({a[l],a[mid]-a[l],a[r]-a[mid],a[n]-a[r]}));
	}
	printf("%lld",ans);
	return 0;
}
/*
2e5
盲猜开龙龙 
*/
  • 就是模拟3个分界点，让没个区间的差最小

[CSP-J 2023] 公路

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,d,ans;
int v[100005],a[100005];
signed main(){
	scanf("%lld%lld",&n,&d);
	for(int i=1;i<n;i++){
		scanf("%lld",&v[i]);
	}
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	int l=1,now=0,x=0;
	for(int i=1;i<n;i++){
		int u=(v[i]-now)/d;
		if((v[i]-now)%d)u++;
		ans+=a[l]*u;
		if(i<n&&a[i+1]<a[l]) l=i+1;
		now+=u*d;
		now-=v[i];
	}
	printf("%lld",ans);
	return 0;
}
/*
十年oi一场空，不开龙龙见祖宗 
*/
  • 首先我们发现在 1 号加油站必须买油，否则根本动不了。接下来我们可以不断开到在当前加油站后比当前加油站油价低的加油站并使油剩得最少

评论

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

正在加载评论...