[CF952X]April Fools Contest 2018

又是一年愚人节时,今年CF照例举办了愚人节比赛。

不过今年出题的人倒是说了:This year I tried to make the problems less puzzling and more versatile.

也就是说,题目的费解程度会下降,但会更有意思。

还有一点:今年的比赛用不到OEIS了,再也不用研究数列找规律了。

接下来进入正题。

继续阅读[CF952X]April Fools Contest 2018

[CF934X]Codeforces Round #462 (Div.2)

这次比赛真的在一个很好的时候举办了,这次比赛前,老师要求我们全部到班比赛,否则就怀疑我们去旁边电影院了(你懂的):)

比赛充分展现了各位出题dalao的大智慧,成功坑倒一片人(当然包括我),难度嘛,绝对达到了极高水平(比如Div.2的D题),题目中还有无数陷阱,比赛结束后,哀叹声不断。

好了,话不多说,进入正题(我读完题后才知道自己过的都是假春节)

继续阅读[CF934X]Codeforces Round #462 (Div.2)

[洛谷 2367]语文成绩

题目链接

https://www.luogu.org/problemnew/show/P2367

题解

区间修改?乍一看似乎要用线段树才能解决。不过读完题目,就会发现只需要在最后求出最小值,并不需要线段树这样的在线算法。

于是自然而然想到差分了,这样只需要\(O(n)\)的时间复杂度就可以解决这道题了。

#include <cstdio>
#include <algorithm>
using namespace std;
int a[5000005],diff[5000005],n,p,mina;
int main()
{
 scanf("%d%d",&n,&p);
 for(int i=1;i<=n;i++)
 {
  scanf("%d",&a[i]);
  diff[i]=a[i]-a[i-1];
 }
 for(int i=1;i<=p;i++)
 {
  int x,y,z;
  scanf("%d%d%d",&x,&y,&z);
  diff[x]+=z;
  diff[y+1]-=z;
 }
 mina=diff[1];
 for(int i=1;i<=n;i++)
 {
  a[i]=a[i-1]+diff[i];
  mina=min(a[i],mina);
 }
 printf("%d",mina);
 return 0;
}