Ediv2 58
- 随手AK.jpg
D
裸的虚树，在这里就不写了
E
傻逼贪心？这个题过的比$B$都多.jpg
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <iostream>
#include <bitset>
using namespace std;
#define N 500005
#define ll long long
int n,now_mx,maxx;char s[10];
int main()
{scanf("%d",&n);while(n--){int x,y;scanf("%s%d%d",s+1,&x,&y);if(x<y)swap(x,y);if(s[1]=='+')now_mx=max(x,now_mx),maxx=max(y,maxx);else puts(x>=now_mx&&y>=maxx?"YES":"NO");}
}F
似乎正解的那个单调队列做法没啥意思啊...
直接暴力二分+剪枝就好了...
然后其实能卡掉，但是懒得去卡了.jpg
然后卡一卡常数就好了.jpg
随便剪一剪枝前测就能过.jpg
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <iostream>
#include <bitset>
using namespace std;
#define N 405
#define ll long long
int a[N],n,m,s,t,f,c,l,r;ll ans;
inline bool check(int x)
{register int i,tc=c;register int now=x;for(i=s;i<t;i++){if(a[i+1]-a[i]>x)return 0;if(a[i+1]-a[i]>now){if(!tc)return 0;tc--;now=x;}now-=a[i+1]-a[i];}return 1;
}
int main()
{scanf("%d%d",&n,&m);l=0,r=1<<30;for(int i=1;i<=n;i++)scanf("%d",&a[i]);while(m--){scanf("%d%d%d%d",&s,&t,&f,&c);if(s>t)swap(s,t);if(check(ans/f))continue;l=(ans/f)+1;r=a[t]-a[s];while(l<r){int mid=(l+r)>>1;if(check(mid))r=mid;else l=mid+1;}ans=max((ll)l*f,ans);}printf("%lld\n",ans);
}G
一个结论，能划分出的段数是线性基里的基的个数
证明嘛：
对于任意一个已经存在的基，都可以被一些数表达出来
然后就可以发现，不可能存在一个划分的段数比线性基里的基数更多（根据线性基的定义
然后就完了.jpg
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <iostream>
#include <bitset>
using namespace std;
#define N 200005
#define ll long long
int a[32],now;
void insert(int x)
{for(int i=30;~i;i--)if((x>>i)&1)if(a[i])x^=a[i];else {a[i]=x;return ;}
}
int main()
{int n,x;scanf("%d",&n);while(n--)scanf("%d",&x),insert(x),now^=x;if(!now)return puts("-1"),0;x=0;for(int i=30;~i;i--)if(a[i])x++;printf("%d\n",x);
}
