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);

}