D3晚上
2024-10-07 20:16:44
发布于:浙江
// [L(1,N-1),R(3,N-2)]
// 序列:
// 是指一串数字(234,141,12,123,13,13,4,5),对于每一个序列中的每个数字,称为元素
// 子序列:
// 从序列当中抽取部分的元素,或者抽取全部的元素,取出构成一个新的序列,也有先后循序(141,123,5)✅ (141,5,4)❌
// 保证一个相对位置不发生改变
// 子串:
// 从序列中去抽取任意个连续的字符组成的子序列我们称之为子串
// 符合题目的子串:
// 1.包含一个H,至少包含两个G
// 2.包含一个G,至少包含两个H
// 1-3数据:
// 暴力的方式枚举当前的左端点和右端点,统计出[l,r]范围内G和H出现的次数,时间复杂度为O(N*N*N)
// 枚举当前的左端点
// 枚举当前的右端点
// 统计当前的范围内,H和G的数量
//=============代码
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// freopen("lonely.in","r",stdin);
// freopen("lonely.out","w",stdout);
// long long n;
// string s;
// cin>>n>>s;
// long long sum=0;//求最终答案,也就是孤独的子串的数量
// //枚举起点和终点,并且统计一下当前区间H,G的数目
// for(int l=0;l<n;l++){
// for(int r=l+2;r<n;r++){//长度至少为3
// int g=0,h=0;//分别统计当前区间的G和H的数量
// for(int i=l;i<=r;i++){
// if(s[i]=='G')g++;
// else h++;
// }
// if(g==1||h==1){//首先保证个数一定是大于等于3
// sum++;
// }
// }
// }
// cout<<sum<<endl;
// fclose(stdin);
// fclose(stdout);
// return 0;
// }
// 50%:搜索+剪枝,当枚举到[l,r]内G和H的个数都是大于2,100%是没有可能,直接提前中断当前的for,不需要继续再枚举
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// freopen("lonely.in","r",stdin);
// freopen("lonely.out","w",stdout);
// long long n;
// string s;
// cin>>n>>s;
// long long sum=0;//求最终答案,也就是孤独的子串的数量
// //枚举起点和终点,并且统计一下当前区间H,G的数目
// for(int l=0;l<n;l++){
// for(int r=l+2;r<n;r++){//长度至少为3. 枚举右端点
// int g=0,h=0;//分别统计当前区间的G和H的数量
// for(int i=l;i<=r;i++){
// if(s[i]=='G')g++;
// else h++;
// }
// if(g==1||h==1){//首先保证个数一定是大于等于3
// sum++;
// }
// // [1,5]. [1,6] [1,7] [1,8]
// if(g>=2&&h>=2){
// break;
// }
// }
// }
// cout<<sum<<endl;
// fclose(stdin);
// fclose(stdout);
// return 0;
// }
// 90%:搜索继续优化,拿到90%分数,当前的状态是[l,r],下一个位置[l,r+1],[l,r+1]比[l,r]多了一个+1,可以直接通过[l,r]求出[l,r+1]
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// freopen("lonely.in","r",stdin);
// freopen("lonely.out","w",stdout);
// long long n;
// string s;
// cin>>n>>s;
// long long sum=0;//求最终答案,也就是孤独的子串的数量
// //枚举起点和终点,并且统计一下当前区间H,G的数目
// for(int l=0;l<n;l++){
// int g=0,h=0;
// //先处理[l,l+1]这段区间的G和H的数目
// for(int i=l;i<=l+1&&i<n;i++){
// if(s[i]=='G')g++;
// else h++;
// }
// //每一个区间的的计算方式都在前一一个区间的计数上,只需要判断s[r]
// for(int r= l+2;r<n;r++){
// if(s[r]=='G')g++;
// else if(s[r]=='H')h++;
// if(g==1||h==1){//首先保证个数一定是大于等于3
// sum++;
// }
// // [1,5]. [1,6] [1,7] [1,8]
// if(g>=2&&h>=2){
// break;
// }
// }
// }
// cout<<sum<<endl;
// fclose(stdin);
// fclose(stdout);
// return 0;
// }
//所有符合条件的子串有一个字母只出现一次
//我们可以设计出合理的算法:枚举满足要求的子串中的字符 (即只出现一次的那个字符的位置)。 左拓展至l,(s[l-1]=si)
//右拓展到r,这样端点在 [l,r] 之间且经过 i 的子串(长度 len≥3)均满足要求!
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// freopen("lonely.in","r",stdin);
// freopen("lonely.out","w",stdout);
// fclose(stdin);
// fclose(stdout);
// return 0;
// }
// 每个位置的字符作为子串中非第一次出现的字符,只会被左边的第一个不同字符计算时访问一次,只和右边的第一个不同字符计算时访问一次,
// 当作为只出现一次的那个字符会访问一次,所以 N 个字符最多访问 3*N 次 , 所以时间复杂度
// si
// 1.si在子串的左侧或者右侧,经过si的子串只能为si作为终点或者起点。 HGGGG
// 起点:r-l+1r-l+1 以s点作为起点,答案也是一样
// 2、si在子串中间,分类讨论:
// ○ si作为子串终点方案数:i-l-1
// ○ si作为子串起点方案数:r-i-1
// ○ si不做起点和终点:那么起点选择的区间为 [l , i-1] ,终点选择的区间为 [i+1 , r] , 使用乘法原理,方案数为 (i-l)*(r-i)
#include <bits/stdc++.h>
using namespace std;
int main(){
freopen("lonely.in","r",stdin);
freopen("lonely.out","w",stdout);
int n;
string s;
cin>>n>>s;
long long sum = 0; //记录个数满足区间的
for(int i=0;i<n;i++){
int l = i-1 , r = i+1;
//向左寻找第一个等于s[i]的位置
while(l>=0 && s[l]!=s[i]){
l--;
}
l++; //[l,i-1] 满足不等于 s[i]
//向右寻找第一个等于s[i]的位置
while(r<n && s[r]!=s[i]){
r++;
}
r--; //[i+1,r] 满足不等于 s[i]
//s[i]在子串最左边或最右边
if(l==i || r==i){
//防止l,r,i在同一位置,子串长度为 1
if(l!=i || r!=i){
sum += r-l-1;
}
}
else{
sum += i-l-1; //s[i]作为终点
sum += r-i-1; //s[i]作为起点
sum += 1LL*(i-l)*(r-i); //s[i]不作起点终点,1LL是long long类型的 1
}
}
cout<<sum;
fclose(stdin);
fclose(stdout);
return 0;
}
// 如果一个关键格(x,y)能够到达关键格(xi,yi)和(xj,yj)
// 那么(xj,yj)也能通过(x,y)和(xi,yi)
// 那这道题其实就是寻找一个包含所有重要结点的连通块,使得这个连通块中的相邻两数差值的最大值最小,
// 在包含所有重要结点的连通块的集合中最小,那我们可以从一个重要结点开始从小到大枚举差值,判断在这个差值限制下,
// 从该重要起点开始扩展出的连通块能否包括所有重要结点,如果能包含所有重要结点,因为我们是从小到大枚举的差值,所以这个差值就是答案。
// 那么连通块扩展的过程我们可以使用BFS完成,其实就是从一个重要结点出发的染色问题。
// 分析题面:
// ● 有矩阵
// ● 有规则(上下左右)
// ● 还有能走不能走
// ● 没有明确的起点、终点
// BFS 实现,需要参数 dif ,代表两点之间海拔差的最大值限制。
// bfs(dif):
// while(没走完):
// x->下一个点,y->下一个点;
// if(越界或走过) continue;
// if(海拔差>=dif) continue;
// if(是关键点) 记录;
// 标记走过;
// 进队;
// 定义一个结构体:
// struct point{
// int x,y;//横纵坐标
// };
// 规则:
// int dir_x[] = {1 , 0 , -1 , 0};
// int dir_y[] = {0 , 1 , 0 , -1};
// 判重数组:
// bool vis[510][510]; //标记
// 初始化
// memset(vis,0,sizeof(vis)); //标记数组清空
// queue<point> q;
// q.push({sx,sy}); //起点入队
// vis[sx][sy] = 1; //起点标记
// num--; //未被扩展的重要结点数减一
// 搜索部分
// while(!q.empty()){
// int x = q.front().x;//取队头
// int y = q.front().y;
// q.pop();
// for(int i=0; i<4; i++){
// int x1 = x+dir_x[i],y1 = y+dir_y[i];//根据规则找能走的点
// if(x1<1||x1>n||y1<1||y1>m||vis[x1][y1]) continue;//越界或者走过了
// if(abs(h[x1][y1]-h[x][y])>dif) continue;//海拔差(“难度值”)太大,不走
// if(imp[x1][y1]) num--;//未被扩展的重要结点数减一
// vis[x1][y1]=1;//记录已经走过了
// q.push({x1,y1});
// }
// }
// 30:
// #include <bits/stdc++.h>
// using namespace std;
// using ll = long long;
// int n,m;
// int dir_x[] = {1 , 0 , -1 , 0};
// int dir_y[] = {0 , 1 , 0 , -1};
// int h[510][510]; //存储高度
// int imp[510][510]; //存储是否为关键点
// bool vis[510][510]; //标记
// struct point{
// int x,y;//横纵坐标
// };
// int sx , sy;
// bool bfs(int num, int dif){
// memset(vis,0,sizeof(vis)); //标记数组清空
// queue<point> q;
// q.push({sx,sy}); //起点入队
// vis[sx][sy] = 1; //起点标记
// num--; //未被扩展的重要结点数减一
// while(!q.empty()){
// int x = q.front().x;//取队头
// int y = q.front().y;
// q.pop();
// for(int i=0; i<4; i++){
// int x1 = x+dir_x[i],y1 = y+dir_y[i];//根据规则找能走的点
// if(x1<1||x1>n||y1<1||y1>m||vis[x1][y1]) continue;//越界或者走过了
// if(abs(h[x1][y1]-h[x][y])>dif) continue;//海拔差(“难度值”)太大,不走
// if(imp[x1][y1]) num--;//未被扩展的重要结点数减一
// vis[x1][y1]=1;//记录已经走过了
// q.push({x1,y1});
// }
// }
// return num==0;
// }
// int main(){
// freopen("skiing.in","r",stdin);
// freopen("skiing.out","w",stdout);
// //输入
// cin>>n>>m;
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// cin>>h[i][j];
// }
// }
// int num=0; //关键点个数
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// cin>>imp[i][j];
// if(imp[i][j]==1) {
// sx = i , sy = j; //记录一个关键点位置
// num++;
// }
// }
// }
// //从小到大枚举差值
// for(int i=0;i<=1000000000;i++){
// if(bfs(num , i)){
// cout<<i;
// return 0;
// }
// }
// fclose(stdin);
// fclose(stdout);
// return 0;
// }
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n,m;
int dir_x[] = {1 , 0 , -1 , 0};
int dir_y[] = {0 , 1 , 0 , -1};
int h[510][510]; //存储高度
int imp[510][510]; //存储是否为关键点
bool vis[510][510]; //标记
struct point{
int x,y;//横纵坐标
};
int sx , sy;
bool bfs(int num, int dif){
memset(vis,0,sizeof(vis)); //标记数组清空
queue<point> q;
q.push({sx,sy}); //起点入队
vis[sx][sy] = 1; //起点标记
num--; //未被扩展的重要结点数减一
while(!q.empty()){
int x = q.front().x;//取队头
int y = q.front().y;
q.pop();
for(int i=0; i<4; i++){
int x1 = x+dir_x[i],y1 = y+dir_y[i];//根据规则找能走的点
if(x1<1||x1>n||y1<1||y1>m||vis[x1][y1]) continue;//越界或者走过了
if(abs(h[x1][y1]-h[x][y])>dif) continue;//海拔差(“难度值”)太大,不走
if(imp[x1][y1]) num--;//未被扩展的重要结点数减一
vis[x1][y1]=1;//记录已经走过了
q.push({x1,y1});
}
}
return num==0;
}
int main(){
freopen("skiing.in","r",stdin);
freopen("skiing.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>h[i][j];
}
}
int num=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>imp[i][j];
if(imp[i][j]==1) {
sx = i , sy = j;
num++;
}
}
}
int l=0, r=1000000000;//二分效率很高,不妨把l和r都设为极值
int ans=0;
while(l<=r)
{
int mid=(l+r)/2;
if(bfs(num,mid))
{
r=mid-1;
ans=mid;
}
else l=mid+1;
}
cout<<ans;
fclose(stdin);
fclose(stdout);
return 0;
}
// n==7
// [1,2][2,3][3,4][4,5][5,6][6,7]
// 通过两层for循环的方式控制左端点和右端点,然后判断当前的取值范围内是否是可行的
// #include<bits/stdc++.h>
// using namespace std;
// int arr[100023];
// int main(){
// freopen("deliver.in","r",stdin);
// freopen("deliver.out","w",stdout);
// int n;
// cin>>n;
// for(int i=1;i<=n;i++){
// cin>>arr[i];
// }
// long long sum=0;
// for(int i=1;i<n;i++){
// for(int j=i+1;j<=n;j++){
// int mi=min(arr[i],arr[j]);
// int ans=0;//假装当前是可行的
// for(int k=i+1;k<j;k++){
// if(arr[k]>mi){
// ans=1;break;
// }
// }
// if(ans==0)sum+=(j-i+1);
// }
// }
// cout<<sum<<endl;
// fclose(stdin);
// fclose(stdout);
// return 0;
// }
#include <bits/stdc++.h>
using namespace std;
long long n,ans=0;
long long a[300005];
stack<long long>s;
int main() {
freopen("deliver.in","r",stdin);
freopen("deliver.out","w",stdout);
cin>>n;
for (int i=1;i<=n;i++)cin>>a[i];
for (int i=1;i<=n;i++){
while (!s.empty()&&a[s.top()]<a[i]){
ans+=i-s.top()+1;
s.pop();
}
if (!s.empty())ans+=i-s.top()+1;
s.push(i);
}
cout<<ans<<endl;
fclose(stdin);
fclose(stdout);
return 0;
}
//考虑对于每一条路径记录cnt[x][y],表示从x到y最短路径的条数
//如果a[x][k]+a[k][y]< a[x][y] -> cnt[x][y]=1; 将原先的清空
//如果a[x][k]+a[k][y]==a[x][y] -> cnt[x][y]++;
//当前维护出的最短路并不好似最正确的,但是我们可以保证直接相邻的数量是正确的,非直接相连的只需要记录一条
// 统计答案,对于边[x,y],如果cnt[x][y]>1,对应边删除,ans++;
// floyd实现
#include<bits/stdc++.h>
using namespace std;
int d[505][505];
int g[505][505];
int cnt[505][505];
int main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
memset(d,0x7f,sizeof d);
memset(g,0x7f,sizeof g);
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
d[x][y]=d[y][x]=g[x][y]=g[y][x]=z;
}
for(int k=1;k<=n;k++){//中转点
for(int i=1;i<=n;i++){//左
if(i==k)continue;
for(int j=1;j<=n;j++){//右
if(k==j||i==j)continue;
int res=d[i][k]+d[k][j];//从i点出发,从中转点K转移,到达j的路径长度
if(d[i][j]>res){//
cnt[i][j]=0;
d[i][j]=res;
}
else if(d[i][j]==res){
cnt[i][j]++;
}
}
}
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1+i;j<=n;j++){
if(g[i][j]==0x7f7f7f7f)continue;
if(g[i][j]>d[i][j]){
ans++;
}
else if(g[i][j]==d[i][j]&&cnt[i][j]>0){
ans++;
}
}
}
cout<<ans<<endl;
fclose(stdin);
fclose(stdout);
return 0;
}
这里空空如也
有帮助,赞一个