D3早上
2024-10-07 15:58:57
发布于:浙江
// {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;
}
全部评论 12
1周前 来自 浙江
01周前 来自 浙江
01周前 来自 浙江
01周前 来自 浙江
01周前 来自 浙江
01周前 来自 浙江
01周前 来自 浙江
0老师你给我的样例是小写它当然不输出
1周前 来自 浙江
0老师你给我的样例是小写它当然不输出
1周前 来自 浙江
0?
1周前 来自 浙江
0二首屏
1周前 来自 北京
0题解
1周前 来自 北京
0
有帮助,赞一个