#include
using namespace std;
long long n;
long long ans;
long long a[1000005];
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
for(int i=1;i)
{
int x=a[i],y=a[i+1];
if(x>y)
{
ans=(long long)ans+(x-y)*(n-x+1);
}
else
{
ans=ans+(long long)(y-x)*x;
}
}
ans+=(long long)a[n]*(n-a[n]+1);
cout<<ans;
return 0;
}
2 快来 pick sxk：(时间限制：2s 空间限制：512MB)
2.1 题目描述:
千古神犇邵徐坤 ，他现在利用自己猴子的属相变成了 n个会打篮球的分身，
每个会打篮球的分身都 有一个鸡儿你真美值，这些分身是乱序的。
你需要将其按鸡儿你真美值从小到大排序，每次你可以将一个分身揪到任意一个位置（某两个分身中 间），
代价是你要掉该分身的鸡儿你真美值的毛。 为了不变成sxk这样的聪明"绝顶"的大猴子，
你要以尽量少的代价完成这个任务，你需要回答每一次sxk分身后你会掉的最少毛数。
2.2 输入格式:
从文件pick.in 中读入数据。
数据的第1 行包含一个非负整数 t 表示 sxk分身的次数。对于 的数据满足对于每一组数据
第 1 行包含一个非负整数 n表示sxk分身的个数
第2 行包含 n个数，ai表示第 i个分身的鸡儿你真美值
2.3 输出格式:
输出到文件pick.out 中。
对于每一个询问输出一个整数，表示你最少会掉的毛数;
2.4 样例输入:
2
5
9 5 7 2 8
5
7 6 5 4 3
2.5 样例输出:
11
18
2.6 数据约定:
对于 30%的数据满足:∑ n<=1000;
对于另外30% 的数据满足:ai>=ai+1;
对于 100%的数据满足:∑ n<=20000,ai<=10^7;
这题其实有60分是良心送分，对于前30%的数据，我们可以转换一下题意，
得到题目就是让我们删去一些数，得到一个权值最大的单调递增的序列；
然后我们不难发现如果答案要最优，那么一个数最多只会被移一次；
所以我们就可以用dp来做，定义一个f数组表示以 i 结尾的上升序列的最大权值；
对于另外的30%的数据可以特判过掉；
最后的数据，我们考虑优化之前的dp，那么，我们可以用·线段树来维护f 数组；
每做一次f 就把他加入树上维护，这道题目就变成了单点修改，区间查询的dp题了
代码如下：
#include
using namespace std;
int n,t;
struct tree{
int l,r;
long long dat;
}e[4000000];
map<int,int>q;
long long a[1000000];
long long b[1000000];
long long ans;
long long sum;
long long c[1000000];
int cnt;
int Read()
{
char w=getchar();
int ch=0;
while(w<‘0‘||w>‘9‘){
w=getchar();
}
while(w>=‘0‘&&w<=‘9‘){
ch=ch*10+w-‘0‘;
w=getchar();
}
return ch;
}
void build(int q,int l,int r)
{
e[q].l=l;
e[q].r=r;
e[q].dat=0;
if(l==r)
return;
int mid=(l+r)>>1;
build(q*2,l,mid);
build(q*2+1,mid+1,r);
}
void add(int q,int l,long long val)
{
if(e[q].l==e[q].r&&e[q].r==l)
{
e[q].dat=max(e[q].dat,val);
return;
}
int mid=(e[q].l+e[q].r)>>1;
if(mid>=l) add(q*2,l,val);
if(mid2+1,l,val);
e[q].dat=max(e[q*2].dat,e[q*2+1].dat);
}
long long ask(int q,int l,int r)
{
long long num=0;
if(e[q].l>=l&&e[q].r<=r)
return e[q].dat;
int mid=(e[q].l+e[q].r)>>1;
if(mid>=l) num=max(num,ask(q*2,l,r));
if(mid2+1,l,r));
return num;
}
int main()
{
t=Read();
while(t--){
n=Read();
ans=0; sum=0;
for(int i=1;i<=n;i++)
{
a[i]=Read();
b[i]=a[i];
sum+=a[i];
}
build(1,1,n);
sort(b+1,b+1+n);
for(int i=1;i<=n;i++)
{
if(i==1||b[i]!=b[i-1])
q[b[i]]=++cnt;
else
q[b[i]]=cnt;
}
for(int i=1;i<=n;i++)
c[i]=q[a[i]];
for(int i=1;i<=n;i++)
{
long long f=ask(1,1,c[i])+a[i];
add(1,c[i],f); ans=max(f,ans);
}
for(int i=1;i<=n;i++)
q[a[i]]=0;
cnt=0;
cout<endl;
}
return 0;
}
3 一道另类的前缀和：（时间限制：3s 空间限制：64MB）
已知常数 n， k，p 和函数
3.2 输入格式 :
从文件 prefix .in中读入数据。
数据的第 1行包含三个非负整数 n， k，p意义如题目描述。
输出到文件prefix.out 中。输出一行一个正整数， 可能为分数，所以输出 
对 p 取模的结果。
即 输出
3.4 样例输入 :
5 2 998244353
3.5 样例输出 :
465847367
这题我在考试的时候没写出来，后来隔壁大佬教了我我也不会；
于是，这题我没写出来，如果有会写的大佬，希望能讲一下做法；
谢谢！
如果大家觉得我写的还可以的话，点个赞吧~~~
京公网安备 11010802041100号