记笔记记笔记 学习大佬代码
思路(结合代码举例来看)
假设数组 1 2 3 2 4 5
因为只有一个for循环 先找到第一个非降序字串 1 2 3 然后len是3
这个1 2 3 所包含所有nice(也就是非降序的字串,也包括它自身也是字串)还有1+……+len-1 (这里也就是1+2=3)包括1 2和2 3和1 2 3
然后len=1回到原样 下一个 2 4 5 同样的道理
一开始ans=n的原因是 这个数组里的每一个单独的数都看做nice字串
code:
#include<bits/stdc++.h>
#include<stack>
typedef long long ll;
using namespace std;
const double pi=acos(-1.0);
const double eps = 1e-8;
typedef pair<int, int> PII;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+6;
const ll mod = 1000000007;
//string a[maxn];
#define mst(x, a) memset( x,a,sizeof(x) )
#define rep(i, a, b) for(int i=(a);i<=(b);++i)
#define dep(i, a, b) for(int i=(a);i>=(b);--i)
ll read() {
ll x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
void out(ll x) {
int stackk[40];
if (x < 0) {
putchar('-');
x = -x;
}
if (!x) {
putchar('0');
return;
}
int top = 0;
while (x) stackk[++top] = x % 10, x /= 10;
while (top) putchar(stackk[top--] + '0');
}
ll i,j,n;
ll a[maxn];
ll ans,len=1;
int main()
{
n=read();
for(int i=0;i<n;i++)
a[i]=read();
ans=n;//单独的也算非降序
for(i=0;i<n-1;i++){
if(a[i+1]>=a[i])
len++;
else{
if(len>=2){
for(j=1;j<=len-1;j++)
ans+=j;
}
len=1;
}
}
if(len>=2){
for(j=1;j<=len-1;j++)
ans+=j;
}
out(ans);
return 0;
}