[数据结构与算法]国庆第五场

FHIJ

F
题意
每一个合法括号都有一个 复杂度 将他们的复杂度相加即可

复杂度是由 这个括号所包含的最大复杂度决定的 (()) 像这外面的一个括号 它的复杂度为 2 因为他里面包含了一个复杂度为1的 ( ( ( ) ) ) 这个最外面的为3 不一定都是这样形式的 我们要求的就是这个括号里面最长的连续括号

由于 长度为60之内
我们直接暴力枚举每一个左括号 找匹配的右括号 在此过程中 找到其内部最长的括号为多长

提供1组样例
( ( ) ( ( ( ) ) ) ( ) ) 12

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
struct node{
	int x,y;
	int step,now;
};
map<int,map<int,int> >mp,vis,cj;
int flag=0;
map<ll,bool>ed;
double pi=3.1415926535;	int n,m,step,r,maxl=1030939;
int dis[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

int main(){
	string s;
	getline(cin,s);
	int sum=0;
	int len=s.size();
	for(int i=0;i<len;i++){
		int z=0,zz=0,y=0,yy=0;
		int maxl=0;
		stack<char>v;
		if(s[i]=='('){
		v.push('(');
		z=1;
		int d=0;
		int k=0;
			for(int j=i+1;j<len;j++){
				if(!v.size()) break;		
				if(s[j]=='(')
				{
					z++;
					v.push('('); 		
					maxl=max(maxl,y+1); //算上末尾的右括号
					y=0;		
				}else if(s[j]==')'){
					v.pop();
					if(d==1) z++; //这是算上了最左侧的左括号 因为当前这个左括号并不是连续过来的
					maxl=max(maxl,z);
					z=0;
					d=1;
					y++;	
				}	
			}
		//	cout<<y<<endl;
			maxl=max(maxl,y);
			sum+=maxl;
		}
	}
	cout<<sum;
	return 0; 
}

H
题意
有一个地图 N*M的
在这个地图中有S个店
我们要从1，1 走到 n,m
走的时候 我们会累 我们的耐久度是F 当我们连续走F步的时候 就不能继续前进了
但如果我们走到一个店的话 可以休息一下 耐久度清0；
求的是 总步数最小 到达n,m
这里考虑用bfs 四个状态 x,y,step,u; 分别是 横坐标 竖坐标 目前的 总步数 和 耐久度

之前的 string 啊 struct 有可能会t 或者 超内存
这里采用了类似 哈希的 +map记录状态 剪枝 如果出现过这种状态既可以不用继续考虑

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
struct node{
	int x,y;
	int step,now;
};
map<int,map<int,int> >mp,vis,cj;
int flag=0;
map<ll,bool>ed;
double pi=3.1415926535;	int n,m,step,r,maxl=1030939;
int dis[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int bfs(){
	node f={1,1,0,0};
	queue<node>q;
	q.push(f);
	ed[10000000000+100000000]=1;
	while(q.size()){
		node nn=q.front();
		q.pop();
		int x=nn.x;
		int y=nn.y;
		int stp=nn.step;
		int now=nn.now;
		if(x==n&&y==m){
			return stp;
		}
		if(now>=step) continue;
		
		
		for(int i=0;i<4;i++){
			int dx=x+dis[i][0];
			int dy=y+dis[i][1];
			
			if(dx>=1&&dx<=n&&dy>=1&&dy<=m){
				int u=now;
				if(mp[dx][dy]) u=-1;
				node sd={dx,dy,stp+1,u+1};
				ll sum=dx*10000000000+dy*100000000+(stp+1)*100000+u+1;
				if(!ed[sum])
					q.push(sd);
				ed[sum]=1;
			}
		}
	}
}
int main(){
	

	cin>>n>>m>>step>>r;
	for(int i=1;i<=r;i++){
		int x,y;
		cin>>x>>y;
		mp[x][y]=1;
	}

	
	cout<<bfs(); 
	return 0; 
}

I题
是个动态规划
题意
简单来说 n个平台
每个平台都有个横坐标 也都有一个高度 这个高度是 输入顺序
第一个输入的高度为1 第二个则为2
要我们从最低的那个平台 跳到 最高的平台
跳跃有限制 不能跳到比自己高k的平台
跳跃也需有消耗 消耗为 |x2-x1|+(y1?y2)^2
求最小消耗
我们要求跳到最高平台的最低消耗 那么就要求跳到最高平台之前的最低消耗

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=2e5+7;
const ll mod=1e9+7;
ll a[maxn];
map<ll,ll>dp;
int main(){
	map<int,int>mp;
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}	 
	//sort(a+1,a+1+n,cmp);
	dp[a[1]]=0;
	
	for(int i=1;i<=n;i++){
		for(int j=i+1;j-i<=m&&j<=n;j++){
			if(dp[j])
			dp[j]=min(dp[j],dp[i]+abs(a[i]-a[j])+(ll)pow(j-i,2));
			else dp[j]=dp[i]+abs(a[i]-a[j])+(ll)pow(j-i,2);
		}
	}
	cout<<dp[n];
	return 0;
}

J题
题意
给L,R的区间 求L,R内的 既是素数 又是回文的个数
L,R 1e12之内

首先回文的话 可以1e6模拟到1e12 所以 首先考虑回文的话直接跑1e6 就可以跑到1e12
我们可以根据前半部分 构造出后半部分的回文

然后判断是否为素数 这里没有预处理 用的是米勒罗宾素数判定法
这个题的难点应该就在这里 需要先学习

其他的没有什么 在构造回文串的时候避免使用string的函数 substr 还有什么stringstream，
可能会T 直接循环的话 1e12 每个数循环10次 也不是很大

#include<bits/stdc++.h>
#include<iostream>
#include<algorithm> 
using namespace std;
typedef long long LL;
const LL maxn=2e5+7;
//const ll mod=1e9+7;
LL prime[6] = {2, 3, 5, 233, 331};
LL qmul(LL x, LL y, LL mod) { // 乘法防止溢出， 如果p * p不爆LL的话可以直接乘； O(1)乘法或者转化成二进制加法
 
 
    return (x * y - (long long)(x / (long double)mod * y + 1e-3) *mod + mod) % mod;
  /*  
	LL ret = 0;
	while(y) {
		if(y & 1)
			ret = (ret + x) % mod;
		x = x * 2 % mod;
		y >>= 1;
	}
	return ret;
	*/
}
LL qpow(LL a, LL n, LL mod) {
    LL ret = 1;
    while(n) {
        if(n & 1) ret = qmul(ret, a, mod);
        a = qmul(a, a, mod);
        n >>= 1;
    }
    return ret;
}
bool Miller_Rabin(LL p) {
    if(p < 2) return 0;
    if(p != 2 && p % 2 == 0) return 0;
    LL s = p - 1;
    while(! (s & 1)) s >>= 1;
    for(int i = 0; i < 5; ++i) {
        if(p == prime[i]) return 1;
        LL t = s, m = qpow(prime[i], s, p);
        while(t != p - 1 && m != 1 && m != p - 1) {
            m = qmul(m, m, p);
            t <<= 1;
        }
        if(m != p - 1 && !(t & 1)) return 0;
    }
    return 1;
}
map<LL,bool>mp;
int main(){
	LL l,r;
	cin>>l>>r;

	LL cnt=0;
	for(int i=1;i<=1000000;i++){
		
		string sum="";
		LL j=i;
		while(j){
			sum+=char('0'+j%10);
			
			j/=10;
		}
		reverse(sum.begin(),sum.end());
		string s1,s2;
		s1=s2=sum;
		reverse(sum.begin(),sum.end());
		s1+=sum;
		int len=sum.size(); 
		
		for(int k=1;k<len;k++) s2+=sum[k];
		LL ss1=0,ss2=0;
		int q=s1.size(),w=s2.size();
		for(int k=0;k<q;k++) ss1=ss1*10+s1[k]-'0';
		for(int k=0;k<w;k++) ss2=ss2*10+s2[k]-'0';
		
		if(ss1>=l&&ss1<=r&&Miller_Rabin(ss1)){
			cnt++;
		}
		if(ss2>=l&&ss2<=r&&Miller_Rabin(ss2)){
			cnt++;
		}

	}
	cout<<cnt;
	return 0;
}