关于flag，都立下了

T1

考试的时候就觉得是贪心，但是不会反悔emm……

于是正解就是一个堆优化可反悔的贪心=。=

每次找前面最小的，于是是小根堆。

我们在交易的时候发现后面的一个可以更优。

于是可以发现$x_i-x_j+x_j-x_k=x_i-x_k$

这样就可以反悔，如果发现$k$可以更优，就把$j$退回去，

所以每次决策完，直接压堆或是更新，并把两个数一起放进去。

一个用来退货，另一个用来再买。

#include <iostream>

#include <cstring>

#include <cstdio>

#include <queue>

#define N 111111

#define LL long long

using namespace std;

priority_queue<int,vector<int>,greater<int> >q;

LL pn,arr[N],ans=0;

int main(){

	scanf("%lld",&pn);

	for(int i=1;i<=pn;i++)

		scanf("%lld",arr+i);

	for(int i=1;i<=pn;i++){

		if(q.empty())q.push(arr[i]);

		else if(q.top()<arr[i]){

			ans+=arr[i]-q.top();

			q.pop();

			for(int j=0;j<2;j++)

				q.push(arr[i]);

		}

		else q.push(arr[i]);

	}

	printf("%lld\n",ans);

}

T2

一个数学题，但是转换成莫队了。

打个样辉三角就可以知道这两个柿子。

$$\begin{align}
S_{n,m}=S_{n,m-1}+C_n^m \tag 1\\
S_{n,m}=S_{n-1,m} \times 2 - C_{n-1}^m \tag 2
\end{align}$$

我没写错吧

于是化为序列询问。

从$[m,n]$向$[m+1,n],[m-1,n],[m,n+1],[m,n-1]$移动。

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#define N 111111

#define LL long long

using namespace std;

const int Mod=1e9+7;

struct Query{

	int n,m;

	int id;

}qs[N];

int qn;

LL ans[N],fac[N],inv[N];

int inp[N],pl;

inline int get_part(int id){

	return (id-1)/pl+1;

}

LL ppow(LL a,LL b){

	LL res(1);

	while(b){

		if(b&1)res=res*a%Mod;

		a=a*a%Mod;

		b>>=1;

	}

	return res;

}

void prerun(){

	pl=sqrt(100000)+1;

	for(int i=0;i<=100000;i++)

		inp[i]=get_part(i);

	fac[0]=inv[0]=1;

	for(int i=1;i<=100000;i++){

		fac[i]=fac[i-1]*i%Mod;

		inv[i]=ppow(fac[i],Mod-2);

	}

}

LL C(int n,int m){

	return fac[n]*inv[m]%Mod*inv[n-m]%Mod;

}

int main(){

//	freopen("1.in","r",stdin);

//	freopen("wa.out","w",stdout);

	prerun();

	scanf("%*d%d",&qn);

	for(int i=1;i<=qn;i++){

		scanf("%d%d",&qs[i].n,&qs[i].m);

		qs[i].id=i;

	}

	sort(qs+1,qs+qn+1,[](const Query &x,const Query &y){return inp[x.n]<inp[y.n]||(inp[x.n]==inp[y.n]&&(inp[x.n]&1?x.m<y.m:x.m>y.m));});

	int nn=1,nm=1;//S(0,0)

	LL nans=2;

	for(int i=1;i<=qn;i++){

		while(nn<qs[i].n){

			nans=(nans*2%Mod-C(nn,nm)+Mod)%Mod;

			nn++;

		}

		while(nn>qs[i].n){

			nans=(nans+C(nn-1,nm))%Mod*inv[2]%Mod;

			nn--;

		}

		while(nm<qs[i].m){

			nans+=C(nn,nm+1);

			nans%=Mod;

			nm++;

		}

		while(nm>qs[i].m){

			nans-=C(nn,nm);

			nans=(nans+Mod)%Mod;

			nm--;

		}

		ans[qs[i].id]=nans%Mod;

	}

	for(int i=1;i<=qn;i++)

		printf("%lld\n",ans[i]);

}

T3

考试的时候一直没看见边长至少有一个是$1$……

于是按$x,y$分别排序并建边，具体实现……没打完。

我想的是用两个$set$维护。

有人要部分代码么……啥都没有

/*CECECECECECECECE*/

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <set>

#define N 111111

using namespace std;

struct XBLOCK{

	int lx,ly,rx,ry;

	int id;

	XBLOCK(int a,int b,int c,int d,int e):lx(a),ly(b),rx(c),ry(d),id(e){}

	friend operator < (const XBLOCK &a,const XBLOCK &b){

		if(a.lx==b.lx)

			return a.ly<b.ly;

		return a.lx<b.lx;

	}

};

struct YBLOCK{

	int lx,ly,rx,ry;

	int id;

	YBLOCK(int a,int b,int c,int d,int e):lx(a),ly(b),rx(c),ry(d),id(e){}

	friend operator < (const YBLOCK &a,const YBLOCK &b){

		if(a.ly==b.ly)

			return a.lx<b.lx;

		return a.ly<b.ly;

	}

};

set<XBLOCK>xb;

set<YBLOCK>yb;

int lines,cols,bn,qn;

int ans[N];

int pre[N];

int fa[N];

void prerun(){

	for(int i=1;i<=bn;i++)

		fa[i]=i;

}

int faind(int x){

	if(x!=fa[x])fa[x]=faind(fa[x]);

	return fa[x];

}

void unite(int a,int b){

	a=faind(a);

	b=faind(b);

	fa[a]=b;

}

int main(){

	int lx,ly,rx,ry,opt,qd;

	scanf("%*d%d%d%d%d",&lines,&cols,&bn,&qn);

	prerun();

	for(int i=1;i<=bn;i++){

		scanf("%d%d%d%d",&lx,&ly,&rx,&ry);

		pre[lx-1]-=ry-ly+1;

		pre[ly]+=ry-ly+1;

		xb.insert(XBLOCK(lx,ly,rx,ry,i));

		yb.insert(YBLOCK(lx,ly,rx,ry,i));

	}

	for(int i=1;i<=lines;i++)

		pre[i]+=pre[i-1];

	for(int i=1;i<=lines;i++)

		pre[i]+=pre[i-1];

	for(auto i:xb){

		if(i.lx==1){

			auto f=yb.lower_bound(i.lx,i.ly-1,-1,-1),

				 t=yb.lower_bound(i.rx+1,i.ly-1,-1,-1);

			for(auto i=f;i!=t;i++){

				i->id

			}

			continue;

		}

		auto xf=xb.lower_bound(XBLOCK(i.lx-1,i.ly,-1,-1)),

			 xt=xb.lower_bound(XBLOCK(i.lx-1,i.ry+1,-1,-1));

		for(auto i=f;i!=t;i++){

		}

		auto yf=yb.lower_bound(YBLOCK()),

			 yt=yb.lower_bound(YBLOCK());

		for(auto i=f;i!=t;i++){

		}

	}

	for(int i=1;i<=qn;i++){

		scanf("%d%d",&opt,&qd);

		if(opt)

			printf("%d\n",ans[qd]);

		else

			printf("%d\n",pre[qd]);

	}

	return 0;

}

巴特西

1008-Redo

T1

T2

T3

最新文章

热门文章