Living-Dream 系列笔记 第25期

Problem

T1

/*
思路：
对于操作1，直接+=拼接即可；
对于操作2，直接令s=s.substr(a,b)即可；
对于操作3，直接令s=s.insert(a,t)即可；
对于操作4，直接s.find(str)即可，注意特判-1。
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;

int q;
string s; 

signed main(){
	ios::sync_with_stdio(0);
	cin>>q>>s;
	while(q--){
		int op,a,b; string t;
		cin>>op;
		if(op==1){
			cin>>t;
			s+=t;
			cout<<s<<'\n';
		}
		else if(op==2){
			cin>>a>>b;
			s=s.substr(a,b);
			cout<<s<<'\n';
		}
		else if(op==3){
			cin>>a>>t;
			s.insert(a,t);
			cout<<s<<'\n';
		}
		else{
			cin>>t;
			if(s.find(t)!=string::npos) cout<<s.find(t)<<'\n';
			else cout<<"-1\n";
		}
	}
	return 0;
}

T2

/*
思路：
考虑贪心，
因为越晚结束的比赛应该越早打完，
这样留出来的时间就越多，
所以需要对比赛按结束时间从小到大排序。
然后依次遍历每个比赛，能打则打，最后输出能打的比赛数即可。
这便是著名的线段覆盖问题。
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,last=-1,ans;
struct node{
	int l,r;
}a[1000031];
bool cmp(node x,node y){
	return x.r<y.r;
}

signed main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].l>>a[i].r;
	a[0].l=a[0].r=0;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
		if(a[i].l>=last) 
			ans++,last=a[i].r;
	cout<<ans;
	return 0;
}

T3

/*
思路：按照题意模拟排序过程即可。
坑点：
1.题面加粗的排序规则不是按Ei排序，而是按每个人的权值排序。
2.注意序号与编号的差别。
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,k;
int e[31];
struct node{
	int val,id,d;
}p[20031];

bool cmp(node x,node y){ 
    if(x.val==y.val) return x.id<y.id;
	return x.val>y.val; 
}

signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>k;
	for(int i=1;i<=10;i++) cin>>e[i];
	for(int i=1;i<=n;i++) 
		cin>>p[i].val,p[i].id=i;
	sort(p+1,p+n+1,cmp);
	for(int i=1;i<=n;i++) 
	    p[i].d=i,p[i].val+=e[(p[i].d-1)%10+1];
	sort(p+1,p+n+1,cmp);
	for(int i=1;i<=k;i++) cout<<p[i].id<<' ';
	return 0;
}

T4

/*
思路：
考虑dfs求连通块，
首先连通块的最大大小很好求，
求周长其实就是对于每个连通块中的点，
扫描一遍它四个方向的所有点，
因为每个点只有它四周有不为'#'的点时才会贡献周长，
所以统计它四个方向上不为'#'的点的个数即可。
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;

int n;
int are,cir,Are=-1e9,Cir=1e9,tmp;
bool vis[1031][1031];
bool vis2[1031][1031];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1}; 
char mp[1031][1031];

void dfs(int x,int y){
	if(vis[x][y]) return;
	vis[x][y]=1,are++;
	for(int i=0;i<4;i++){
		int xx=x+dx[i],yy=y+dy[i];
		if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&mp[xx][yy]=='#'&&!vis[xx][yy]) dfs(xx,yy);
	} 
	for(int i=0;i<4;i++){
		int xx=x+dx[i],yy=y+dy[i];
		if((mp[xx][yy]!='#'||xx<1&&xx>n&&yy<1&&yy>n)) 
			cir++,vis2[xx][yy]=tmp;
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>mp[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			if(!vis[i][j]&&mp[i][j]=='#'){
				are=cir=0,tmp++;
				dfs(i,j);
				if(Are<are) Are=are,Cir=cir;
				if(Are==are&&cir<Cir) Are=are,Cir=cir;
				//cout<<cir<<'\n';
				//memset(vis2,0,sizeof(vis2));
			}
		}
	cout<<Are<<' '<<Cir;
	return 0;
}