暑假集训笔记
刷题刷的好累啊...不想刷题了...然后就来写题解了...
昨天晚上打了场div2..2000来名，加了155分....现在rating1281...我是菜鸡..暑假之前就打到了1200分以上了，结果暑假一掉再掉，直接掉到1100了...然后我就一直压力很大.......
昨天在机房打的..感觉很好，以后就在机房打吧....
其实昨天晚上能出D的，我的思路很对...但是当时没想太明白，还有20分钟的时候就去玩游戏了..
今天早上10分钟该出来了.....
我真的是吐了！！！没办法啊...人总要有遗憾的....
感觉还是比赛过程中感觉D出的太少了，就有点不想做了...
其实吧，赛后我感觉自己的实力已经完全能够出D题了....
不然感觉这场能加200多分...直接到1300+
Problem - C - Codeforces
昨天比赛的C题，刚开始的时候没啥思路....
看了样例想了一会，发现最后几个反转是最优的..
但到底反转几个呢..，看了几个样例发现反转log2（n）+1好像是最优的...
但是样例没过，卡在20了...这就尴尬了..
然后我就想着能不能枚举..
发现确实可以，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
比较可惜的一道题吧..感觉赛时能出的...
但是我区间合并的时候有点想错了..
我们对区间左端点从小到大排序，右端点从大到小排序，
对于正在处理的区间的左端点必须小于等于正在合并的区间的b的最大值，然后才能合并！！
这点确实比赛时候没有想清楚，今天早上想明白了.但感觉还剩20分钟应该能出来
然后就是二分了
我们可以发现一个规律：我们遍历已经合并的区间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的时候感觉自己思路没啥问题...
我们通过样例发现长度为n的排列最小次数为n/2，
如果n为偶数的话，依次交换