首页 > 其他分享 >luogu P4786 [BalkanOI2018]Election

luogu P4786 [BalkanOI2018]Election

时间:2022-11-13 17:56:28浏览次数:83  
标签:子段 P4786 luogu 删掉 BalkanOI2018 long 区间 using define

题面传送门

离谱题,结论出奇的简单。

首先我们考虑\(O(nq)\)怎么做。

显然所有C都要放在最终序列中,然后问题就变成往里面填T

我们考虑第一个T填在能填的最开始的位置上,因为如果这个T往后移动,那么其实只会更劣。因此一个基础的想法就是能填就填。

我们发现这个形式和最大子段和满足的性质是一样的,即一个最大子段和是满足这个性质的。

而对应的,一个区间的最大子段和去掉以后,前区间的后缀和后区间的前缀都是非正的。

而考虑现在将这两个区间删掉若干个T使得这两个区间的总和恰好为\(0\),容易发现这是必要的,为了最优,我们应该使左区间删掉右边的,右区间删掉左边的。这样左区间的前缀和右区间的后缀本身就是非负的,而左区间的后缀和右区间的前缀也被删成了非负的。

所以答案就是最大子段和减去区间和,用线段树维护,时间复杂度\(O(n+q\log n)\)。

code:

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n))
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned ll;
using namespace std;const int N=600+5,M=2e7,K=(1<<10)+5,mod=1e9+7,Mod=mod-1;ll INF=1e18+7;const db eps=1e-5;mt19937 rnd(time(0));
int n,m,k,x,y,Q[N],P[N];ll f[N][N],g[N],Ans;
int main(){
	freopen("1.in","r",stdin);
	int i,j,h;scanf("%d%d",&n,&k);m=2*n;for(i=1;i<=k;i++) scanf("%d%d",&x,&y),P[x]=y,P[y]=x,Q[x]=Q[y]=1;
	for(i=1;i<=m;i++) Q[i]=Q[i-1]+(!Q[i]);for(g[0]=1,i=2;i<=m;i+=2) g[i]=g[i-2]*(i-1)%mod;
	for(i=m;i;i--){
		for(j=i;j<=m;j++) {
			int Fl=0;if((Q[j]-Q[i-1])&1) continue;for(h=i;h<=j;h++) if(Q[h]==Q[h-1]&&(P[h]<i||P[h]>j)) {Fl=1;break;}if(Fl) continue;
			f[i][j]=g[Q[j]-Q[i-1]];for(h=i+1;h<=j;h++) f[i][j]=(f[i][j]+(mod-g[Q[h-1]-Q[i-1]])*f[h][j])%mod;Ans+=f[i][j]*g[m-2*k-(Q[j]-Q[i-1])]%mod;
		}
	}printf("%lld\n",Ans%mod);
}

标签:子段,P4786,luogu,删掉,BalkanOI2018,long,区间,using,define
From: https://www.cnblogs.com/275307894a/p/16886427.html

相关文章

  • LuoguP1586 题解
    也可以在LuoguP1586(tencentcs.com)获得更好的阅读体验。Luogu_P1586题解一道比较简单的题目,看到求种类数,考虑DP。设\(f_{i,j}\)表示第\(i\)个数划分为\(j\)......
  • Luogu P5816[CQOI2010]内部白点题解
    LinkLuoguP5816Description一个平面直角坐标系内有\(n\)个黑点,其余点为白点,将会进行若干次变换,每次变换会把上下左右方向都有黑点的白点变成黑点,直到找不到符合要求......
  • 【题解】Luogu P8743 【[蓝桥杯 2021 省 A] 异或数列】
    最近刚好在刷博弈论,看到这道题没有题解,所以刚好来水一发题目链接[蓝桥杯2021省A]异或数列题目描述Alice和Bob正在玩一个异或数列的游戏。初始时,Alice和Bob......
  • luogu 5022
    任意选定一个城市作为起点,然后从起点开始,每次可以选择一条与当前城市相连的道路,走向一个没有去过的城市,或者沿着第一次访问该城市时经过的道路后退到上一个城市。当回到......
  • Luogu5518
    太闲了,推柿子!\(type=1\)\[\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\frac{\operatorname{lcm}\{i,j\}}{\gcd\{i,k\}}\\=\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\frac{......
  • luogu 3155
     m 个节点的无根树,选一个根,将一些节点染成黑色或白色。你的着色方案应保证根节点到各叶子节点的简单路径上都包含一个有色节点,哪怕是叶子本身。对于每个叶子节点 u,定......
  • Luogu P5435 基于值域预处理的快速 GCD
    最近做这道题的时候被卡常了,然后突然想起来曾经偶然在陈指导的博客看到过这个\(O(1)\)做\(\gcd\)的方法其实理解了之后还是比较简单的,以下设数的值域为\(S\)首先我们定义......
  • Luogu4315 月下“毛景树” - 树链剖分 -
    题目链接:https://www.luogu.com.cn/problem/P4315题意:一棵有边权的树,维护树上的链加、链覆盖、修改边权、链上max题解:好难写...首先把边权转化为儿子的点权然后树链剖......
  • 【luogu P1600】天天爱跑步(线段树合并)(LCA)
    天天爱跑步题目链接:luoguP1600题目大意有一棵树,给你若干条路径,对于每个点,有一个数x,求出有多少条路径的第x个点是当前点。思路考虑把路径拆成两个部分,向上和向下。......
  • 【XSY2444】【BZOJ4042】【CERC2014】【luogu4757】Parades(树形dp+状压dp)
    题面Description从前有个A国,它有\(n\)个城市和\(n-1\)条道路。每条路连接两个城市。城市之间两两可达。每个城市与不超过10条道路相连。现在给出\(m\)条路径,要求从这些......