D3早上
2024-10-07 15:58:57
发布于：浙江
104阅读
0回复
0点赞
// {1,7,12,12,8,1,2,4,9,11,12} 序列
// 子序列：取出其中部分元素[1~10,L~10]，{7,8,9,11}
// 字串：连续的字符组成的子序列，称之子串
// 取出一段的范围[L,R];枚举左端点L和右端点R，统计范围内G和H出现的次数。O(n^3)
// #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 l=0;l<n;l++){
// for(int r=l+2;r<n;r++){//长度至少为3
// //1. G H
// //2. GH HG
// 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){
// sum++;
// }
// }
// }
// cout<<sum<<endl;
// fclose(stdin);
// fclose(stdout);
// return 0;
// }
// //加上一个剪枝，统计过程中G和H的数量大于2的时候，当前不需要再枚举以L作为起点的区间
// #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 l=0;l<n;l++){
// for(int r=l+2;r<n;r++){//长度至少为3
// //1. G H
// //2. GH HG
// 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){
// sum++;
// }
// if(g>=2&&h>=2){
// break;
// }
// }
// }
// cout<<sum<<endl;
// fclose(stdin);
// fclose(stdout);
// return 0;
// }
//[l,r]->[l,r+1] 在[l,r]基础上统计r+1
// {1,7,12,12,8,1,2,4,9,11,12} 序列
// 子序列：取出其中部分元素[1~10,L~10]，{7,8,9,11}
// 字串：连续的字符组成的子序列，称之子串
// 取出一段的范围[L,R];枚举左端点L和右端点R，统计范围内G和H出现的次数。O(n^3)
// #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 l=0;l<n;l++){
// for(int r=l+2;r<n;r++){//长度至少为3
// //1. G H
// //2. GH HG
// 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){
// sum++;
// }
// }
// }
// cout<<sum<<endl;
// fclose(stdin);
// fclose(stdout);
// return 0;
// }
//加上一个剪枝，统计过程中G和H的数量大于2的时候，当前不需要再枚举以L作为起点的区间
// #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 l=0;l<n;l++){
// int g=0,h=0;
// //先处理[l,l+1]这段区间的内容
// 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 h++;
// if(g==1||h==1){
// sum++;
// }
// if(g>=2&&h>=2){
// break;
// }
// }
// }
// cout<<sum<<endl;
// fclose(stdin);
// fclose(stdout);
// return 0;
// }
#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{
// gggg h gggg
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)
// (xi,yi)也可以到达(x,y)和(xj,yj)，反之亦然。
// 搜索 中找到一个连通块，使得连通块内相邻两数差值的最大值，在包含所有重要结点的连通块的集合中最小，
// 那我们可以从一个重要结点开始从小到大枚举差值，判断在这个差值限制下，从该重要起点开始扩展出的连通块能否包括所有重要结点，
// 如果能包含所有重要结点，因为我们是从小到大枚举的差值，所以这个差值就是答案。
// 那么连通块扩展的过程我们可以使用BFS完成，其实就是从一个重要结点出发的染色问题。
// 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});
// }
// }
// #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;
// }
// 显然在我们从小到大对差值最大值的枚举中，当有一个差值满足以bfs()函数时，比其大的差值也必然都可以满足bfs()函数，那这个答案就具有单调性，
#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;
}
// #include<bits/stdc++.h>
// using namespace std;
// int arr[300022];
// int f[300022];
// 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];
// }
// int 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;
// }
// 1. 初始化：创建一个空栈和一个变量 ans 用于累加结果。
// 2. 遍历数组：从左到右遍历输入的身高数组。
// 3. 维护单调栈：
// ○ 当栈不为空且当前元素大于栈顶元素时，进行以下操作：
// ■ 计算当前位置与栈顶位置的间隔，并加到 ans 中。
// ■ 弹出栈顶元素。
// ■ 重复这个过程，直到栈为空或栈顶元素大于等于当前元素。
// ○ 如果栈不为空，还需要加上当前位置与新栈顶的间隔。
// ○ 将当前元素的索引压入栈中。
// 4. 结果输出：遍历结束后，ans 中存储的就是所有满足条件的间隔之和。
#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;
}
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 6;
const int INF = 1e9;
int n, m;
int dist[MAXN][MAXN];
tor<pair<int, int>> edges[MAXN];
bool used[MAXN * MAXN];
void floyd_warshall() {
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
bool check() {
int temp[MAXN][MAXN];
memcpy(temp, dist, sizeof(dist));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (i != j) temp[i][j] = INF;
for (int i = 0; i < n; i++)
for (auto &e : edges[i])
if (!used[e.second])
temp[i][e.first] = temp[e.first][i] = dist[i][e.first];
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
temp[i][j] = min(temp[i][j], temp[i][k] + temp[k][j]);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (temp[i][j] != dist[i][j])
return false;
return true;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
dist[i][j] = (i == j) ? 0 : INF;
for (int i = 0; i < m; i++) {
int x, y, w;
cin >> x >> y >> w;
x--; y--;
edges[x].push_back({y, i});
edges[y].push_back({x, i});
dist[x][y] = dist[y][x] = w;
}
floyd_warshall();
int result = 0;
for (int i = 0; i < m; i++) {
used[i] = true;
if (check()) result++;
else used[i] = false;
}
cout << result << endl;
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=i+1;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;
}
有帮助，赞一个