北京第四天

北京第四天

上午T1，我把

 

1. #include<iostream>
2. using namespace std;
3. for(int i strlen())
4. return 0;

写到for里了，zzzzz.然后T掉了40分，这可是noip的D1T1啊。

---

第2题想错了，我按左端点拍的序，实际上要按右端点，还是基础不行，当时就没彻底弄懂，后来就忘了，实际是线段树。

---

T3我打的暴力啦，40分。想到正解，或者说是优化了，但是写不出来啦。

---

中午怕麻烦没回去，也就没睡觉，真不行，下午困毁了。一开始怎么都听不进去，最后才缓过来，晚上让老师又讲了一遍，这回理解得差不多了。单调队列优化dp主要适用于转移时，要从一段区间里求最大值，比如：

 

1. dp[i]=max{dp[j]},i*q<j<i*p

主要是一个插入和删除操作

 

1. void Insert(int x)
2. {
3. while (l<=r && s[r]<=x) r--;
4. s[++r]=x; t[r]=++cnt;
5. }
6. int Query()
7. {
8. return s[l];
9. }
10. void Delete()
11. {
12. CNT++;
13. if (t[l]==CNT) l++;
14. }
16. cin>>Q;
17. l=1; r=0; //单调队列中没有元素
18. while (Q--)
19. {
20. cin>>A;
21. if (A==1) //Insert
22. {
23. cin>>x;
24. Insert(x);
25. }
26. if (A==2)
27. {
28. cout<<Query()<<endl;
29. }
30. if (A==3)
31. {
32. Delete();
33. }
34. }

比赛的时候我忘了重载运算符怎么写，QAQ。 
浪费了近20分钟，我怎么不先写一个

 

1. bool cmp()

明天的题貌似是noip day2的难度，继续努力。