第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛 C题-上进的凡凡

记笔记记笔记 学习大佬代码

第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛 C题-上进的凡凡
思路(结合代码举例来看)
假设数组 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;
 } 
上一篇:第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛 黑洞密码


下一篇:第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛-热身赛