刷題刷的好累啊...不想刷題了...然后就來寫題解了...

昨天晚上打了場div2..2000來名，加了155分....現(xiàn)在rating1281...我是菜雞..暑假之前就打到了1200分以上了，結(jié)果暑假一掉再掉，直接掉到1100了...然后我就一直壓力很大.......

昨天在機(jī)房打的..感覺很好，以后就在機(jī)房打吧....

其實(shí)昨天晚上能出D的，我的思路很對(duì)...但是當(dāng)時(shí)沒想太明白，還有20分鐘的時(shí)候就去玩游戲了..

今天早上10分鐘該出來了.....

我真的是吐了！！！沒辦法啊...人總要有遺憾的....

感覺還是比賽過程中感覺D出的太少了，就有點(diǎn)不想做了...

其實(shí)吧，賽后我感覺自己的實(shí)力已經(jīng)完全能夠出D題了....

不然感覺這場能加200多分...直接到1300+

Problem - C - Codeforces

昨天比賽的C題，剛開始的時(shí)候沒啥思路....

看了樣例想了一會(huì)，發(fā)現(xiàn)最后幾個(gè)反轉(zhuǎn)是最優(yōu)的..

但到底反轉(zhuǎn)幾個(gè)呢..，看了幾個(gè)樣例發(fā)現(xiàn)反轉(zhuǎn)log2（n）+1好像是最優(yōu)的...

但是樣例沒過，卡在20了...這就尷尬了..

然后我就想著能不能枚舉..

發(fā)現(xiàn)確實(shí)可以，n的范圍為250，完全可以枚舉！！！

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#include<stack>
#include<deque>
#include<vector>
#include<map>
#include<set>
#include <utility>
#include <list>
using namespace std;
typedef  long  long ll ;
typedef  unsigned long  long ull ;
#define pii pair<int,int>
const int inf = 0x3f3f3f3f;//106110956
inline int read(){int 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<<1) + (x<<3) + (ch^48);ch = getchar();}return x * f;
}
void print(__int128 num) {if(num) {print(num/10);putchar(num%10+'0');}
}
int t;
int main(){scanf("%d",&t);while(t--){ll ans=0;ll n;scanf("%lld",&n);		for(int k=n;k>=1;k--){ll sum=0;ll maxn=0;ll j=n-k+1;for(ll i=n;i>=n-k+1;i--){maxn=max(maxn,i*j);sum=sum+i*j;j++;}for(ll i=1;i<=n-k;i++){	sum=sum+i*i;}ans=max(ans,sum-maxn);}printf("%lld\n",ans);}return 0;
}

Problem - D - Codeforces

比較可惜的一道題吧..感覺賽時(shí)能出的...

但是我區(qū)間合并的時(shí)候有點(diǎn)想錯(cuò)了..

我們對(duì)區(qū)間左端點(diǎn)從小到大排序，右端點(diǎn)從大到小排序，

對(duì)于正在處理的區(qū)間的左端點(diǎn)必須小于等于正在合并的區(qū)間的b的最大值，然后才能合并！！

這點(diǎn)確實(shí)比賽時(shí)候沒有想清楚，今天早上想明白了.但感覺還剩20分鐘應(yīng)該能出來

然后就是二分了

我們可以發(fā)現(xiàn)一個(gè)規(guī)律：我們遍歷已經(jīng)合并的區(qū)間b的最大值一定是遞增的！！

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#include<stack>
#include<deque>
#include<vector>
#include<map>
#include<set>
#include <utility>
#include <list>
using namespace std;
typedef  long  long ll ;
typedef  unsigned long  long ull ;
#define pii pair<int,int>
const int inf = 0x3f3f3f3f;//106110956
inline int read(){int 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<<1) + (x<<3) + (ch^48);ch = getchar();}return x * f;
}
void print(__int128 num) {if(num) {print(num/10);putchar(num%10+'0');}
}struct Node{ll l,r,a,b;
}s[200005];struct Node1{ll left,right,a,b;
}d[200005];bool cmp(Node s1,Node s2){if(s1.l!=s2.l)return s1.l<s2.l;return s1.r>s2.r;
}int t;int main(){scanf("%d",&t);while(t--){	int n;scanf("%d",&n);	for(int i=1;i<=n;i++){scanf("%lld%lld%lld%lld",&s[i].l,&s[i].r,&s[i].a,&s[i].b);}sort(s+1,s+1+n,cmp);int q;scanf("%d",&q);int cnt=1;d[1].left=s[1].l;d[1].right=s[1].r;d[1].a=s[1].a;d[1].b=s[1].b;for(int i=2;i<=n;i++){if(s[i].l<=d[cnt].b){d[cnt].right=max(d[cnt].right,s[i].r);d[cnt].a=min(d[cnt].a,s[i].a);d[cnt].b=max(d[cnt].b,s[i].b);}else{cnt++;d[cnt].left=s[i].l;d[cnt].right=s[i].r;d[cnt].a=s[i].a;d[cnt].b=s[i].b;}}while(q--){ll x;scanf("%lld",&x);int x1=1;int x2=cnt;ll ans=x;while(x1<=x2){int mid=(x1+x2)/2;if(d[mid].left<=x&&x<=d[mid].right){ans=max(ans,d[mid].b);x1=mid+1;continue;}if(x>d[mid].right)x1=1+mid;else x2=mid-1;}			printf("%lld ",ans);}printf("\n");}return 0;
}

Problem - C - Codeforces

一道雙指針的題目..vp的時(shí)候感覺自己思路沒啥問題...

我們通過樣例發(fā)現(xiàn)長度為n的排列最小次數(shù)為n/2，

如果n為偶數(shù)的話，依次交換