[ABC176F] Brave CHAIN
先转化一下问题为有\(2\)个数然后每一轮有固定三个数,每一轮在\(5\)个数中删去\(3\)个数
考虑朴素\(dp_{i,j,k}\)表示前\(i\)轮剩余\(j,k\)两个数的最大值,时间复杂度为\(O(10\times n^3)\)
考虑优化,设目前轮的固定的牌是\(A,B,C\),手里还有\(j,k\)
\(Case1:\)
如果\(j,k\)都被删去,则此时转移可以利用\(dp\)的最大值
假设留下\(A,B\),则先考虑\(j=k=C\)的情况要\(+1\),剩下的直接用最大值即可
\(Case2:\)
如果\(j,k\)被删去一个
假设固定\(j\),此时直接暴力\(O(n)\)转移
\(Case3:\)
如果\(j,k\)未被删去
此时\(dp\)的转移只与\(A,B,C\)是否相等有关,相当与直接打增量标记,注意前面的转移要剔除增量的影响
\(Tips:\)分析转移的形式可以优化掉许多无用转移
Show Code
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2005;
int n;
int a[MAXN*3];
int dp[MAXN][MAXN];
int Mp[MAXN];
int fa[MAXN];
int fb[MAXN];
int fc[MAXN];
int main()
{
memset(dp,-0x3f,sizeof(dp));
memset(Mp,-0x3f,sizeof(Mp));
scanf("%d",&n);
for(int i=1;i<=3*n;i++)
{
scanf("%d",&a[i]);
}
dp[a[1]][a[2]]=0;
dp[a[2]][a[1]]=0;
Mp[a[1]]=0;
Mp[a[2]]=0;
int Add=0;
int Maxi=0;
for(int i=3;i<=3*n-2;i+=3)
{
int A=a[i];
int B=a[i+1];
int C=a[i+2];
int Nod=((A==B)&&(B==C));
Add+=Nod;
for(int x=1;x<=n;x++)
{
fa[x]=dp[A][x];
fb[x]=dp[B][x];
fc[x]=dp[C][x];
}
dp[A][B]=max(dp[A][B],(fc[C]+1)-Nod);
dp[A][B]=max(dp[A][B],Maxi-Nod);
dp[B][A]=dp[A][B];
dp[A][C]=max(dp[A][C],(fb[B]+1)-Nod);
dp[A][C]=max(dp[A][C],Maxi-Nod);
dp[C][A]=dp[A][C];
dp[B][C]=max(dp[B][C],(fa[A]+1)-Nod);
dp[B][C]=max(dp[B][C],Maxi-Nod);
dp[C][B]=dp[B][C];
for(int x=1;x<=n;x++)
{
if(B==C)
{
dp[A][x]=max(dp[A][x],fb[x]+1-Nod);
}
dp[A][x]=max(dp[A][x],Mp[x]-Nod);
dp[x][A]=dp[A][x];
}
for(int x=1;x<=n;x++)
{
if(A==C)
{
dp[B][x]=max(dp[B][x],fa[x]+1-Nod);
}
dp[B][x]=max(dp[B][x],Mp[x]-Nod);
dp[x][B]=dp[B][x];
}
for(int x=1;x<=n;x++)
{
if(B==A)
{
dp[C][x]=max(dp[C][x],fb[x]+1-Nod);
}
dp[C][x]=max(dp[C][x],Mp[x]-Nod);
dp[x][C]=dp[C][x];
}
Mp[A]=max(Mp[A],dp[A][B]);
Mp[B]=max(Mp[B],dp[A][B]);
Mp[A]=max(Mp[A],dp[A][C]);
Mp[C]=max(Mp[C],dp[A][C]);
Mp[C]=max(Mp[C],dp[C][B]);
Mp[B]=max(Mp[B],dp[C][B]);
for(int x=1;x<=n;x++)
{
Mp[A]=max(Mp[A],dp[A][x]);
Mp[x]=max(Mp[x],dp[A][x]);
}
for(int x=1;x<=n;x++)
{
Mp[B]=max(Mp[B],dp[B][x]);
Mp[x]=max(Mp[x],dp[B][x]);
}
for(int x=1;x<=n;x++)
{
Mp[C]=max(Mp[C],dp[C][x]);
Mp[x]=max(Mp[x],dp[C][x]);
}
for(int x=1;x<=n;x++)
{
Maxi=max(Maxi,Mp[x]);
}
}
int P=a[3*n];
int Res=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
Res=max(Res,dp[i][j]+Add);
}
}
Res=max(Res,dp[P][P]+Add+1);
printf("%d\n",Res);
}
[ABC213G] Connectivity 2
很明显可以枚举一个\(S\),\(i\in S,k\in S\),然后计算\(S\)的联通子图个数\(\times\)补集随便连的方案
我们就设\(F_S\)为\(S\)的联通子图个数,\(G_S\)为补集随便连的方案
很明显\(G\)就是\(S\)中的边数\(2^{Cnt}\)
最开始我想\(F\)的转移是从\(S\)向外连一条边转移,但\(S\)内部的边不好算方案
这时我们考虑容斥,用总方案\(G_S-\)不合法的方案
考虑不合法的方案是由一个联通的\(sub\)与不联通的\(S \oplus {sub}\)，注意我们要保证\(1\)是联通的
所以\(F_S=\sum\limits_{sub\subseteq S,1\in sub}F_{sub}\times G_{S-sub}\)
Show Code
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
int Pow(int a,int b,int p)
{
int res=1;
int base=a;
while(b)
{
if(b&1)
{
res=((long long)res*base)%p;
}
base=((long long)base*base)%p;
b>>=1;
}
return res;
}
int n,m;
int a[25][25];
int G[(1<<17)+5];
int F[(1<<17)+5];
int Ans[25];
int x,y;
void Print(int S)
{
vector<int>R;
R.clear();
while(S)
{
R.push_back(S&1);
S>>=1;
}
reverse(R.begin(),R.end());
for(int i=0;i<R.size();i++)
{
printf("%d",R[i]);
}
printf("\n");
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);
a[x][y]=1;
}
for(int S=0;S<(1<<n);S++)
{
int Cnt=0;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if((S>>(i-1))&1)
{
if((S>>(j-1))&1)
{
Cnt+=a[i][j];
}
}
}
}
G[S]=Pow(2,Cnt,MOD);
}
F[0]=1;
for(int S=1;S<(1<<n);S++)
{
F[S]=G[S];
for(int sub=(S&(S-1));sub;sub=(S&(sub-1)))
{
if(sub&1)
{
}
else
{
continue;
}
F[S]=((long long)F[S]-((long long)F[sub]*G[S^sub])%MOD+MOD)%MOD;
}
}
int Sp=(1<<n)-1;
for(int S=0;S<(1<<n);S++)
{
if(S&1)
{
for(int i=2;i<=n;i++)
{
if((S>>(i-1))&1)
{
Ans[i]=((long long)Ans[i]+((long long)F[S]*G[Sp^S])%MOD)%MOD;
}
}
}
}
for(int i=2;i<=n;i++)
{
printf("%d\n",Ans[i]);
}
}
[CF1749F]Distance to the Path
原问题的修改肯定不好直接修改,而询问是单点修改肯定是在询问上有不同
我最开始是在询问的点找符合条件的链,貌似可以用树剖维护但会算重
然后换个思路,我们维护\(f_{x,d}\)表示\(x\)点为根,距离刚好为\(d\)的增量
很明显\(x\)的权值为\(\sum\limits_{v是x的祖先}f_{v,dist(v,x)}\)
现在考虑维护\(f\),对于\(x\rightarrow y\),对于其中的\(u\),如果直接给距离\(\le d\)节点\(+k\)
那对于\(fa_u\),给距离\(\le d\)节点\(+k\),对于与\(u\)距离\(<d\)的节点会算重
而\(u\)和\(fa_u\)唯一有用的贡献只有距离刚好为\(d\)的
所以如果我们直接对\(u\in x\rightarrow y\),\(f_{u，d}+=k\)
对于距离\(lca\ge d\)的点应该是不会算重的,但对于\(<d\)的以及\(lca\)外的点是无法加到的
考虑\(lca\)的父亲\(fa\),距离它\(\le d-1\)的点能加上,在\(lca\)子树内距离\(d-2\)
再考虑\(fa\)的父亲\(ffa\)，距离它\(\le d-2\)的点能加上,在\(lca\)子树内距离\(d-4\)
由此启发我们让\(fa\)管理\(d-2\)和\(d-3\),而\(ffa\)管理\(d-4,d-5\)(祖先一次管两层)
可以手玩一下,发现是不会算重的
最后树剖维护一下就好了
Show Code
#include<bits/stdc++.h>
#define ls 2*p
#define rs 2*p+1
using namespace std;
const int MAXN=3e5+5;
int n;
int q,d;
int x,y;
int op,k;
vector<int>g[MAXN];
int dfn[MAXN];
int cnt_dfn;
int Wson[MAXN];
int Siz[MAXN];
int Fa[MAXN];
int dep[MAXN];
int top[MAXN];
void dfs1(int x,int f)
{
Siz[x]=1;
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==f)
{
continue;
}
dep[v]=dep[x]+1;
Fa[v]=x;
dfs1(v,x);
Siz[x]+=Siz[v];
if(Siz[v]>Siz[Wson[x]])
{
Wson[x]=v;
}
}
}
void dfs2(int x,int Top)
{
top[x]=Top;
dfn[x]=++cnt_dfn;
if(Wson[x])
{
dfs2(Wson[x],Top);
}
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==Fa[x])
{
continue;
}
if(v==Wson[x])
{
continue;
}
dfs2(v,v);
}
}
struct Seg_node{
int l,r;
int lazy;
};
struct Seg{
Seg_node Tree[MAXN*4];
void push_down(int p)
{
if(Tree[p].lazy)
{
Tree[ls].lazy+=Tree[p].lazy;
Tree[rs].lazy+=Tree[p].lazy;
Tree[p].lazy=0;
}
}
void Build(int p,int l,int r)
{
Tree[p].l=l;
Tree[p].r=r;
if(l==r)
{
Tree[p].lazy=0;
return;
}
int mid=(l+r)>>1;
Build(ls,l,mid);
Build(rs,mid+1,r);
}
void Update(int p,int l,int r,int k)
{
if(Tree[p].l>=l&&Tree[p].r<=r)
{
Tree[p].lazy+=k;
return;
}
push_down(p);
int mid=(Tree[p].l+Tree[p].r)>>1;
if(l<=mid)
{
Update(ls,l,r,k);
}
if(r>mid)
{
Update(rs,l,r,k);
}
}
int Query(int p,int x)
{
if(Tree[p].l==Tree[p].r)
{
return Tree[p].lazy;
}
push_down(p);
int mid=(Tree[p].l+Tree[p].r)>>1;
if(x<=mid)
{
return Query(ls,x);
}
else
{
return Query(rs,x);
}
}
}tree[21];
int Query_lca(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
{
swap(x,y);
}
x=Fa[top[x]];
}
if(dep[x]<dep[y])
{
swap(x,y);
}
return y;
}
void Update_chain(int x,int y,int k,int d)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
{
swap(x,y);
}
tree[d].Update(1,dfn[top[x]],dfn[x],k);
x=Fa[top[x]];
}
if(dep[x]<dep[y])
{
swap(x,y);
}
tree[d].Update(1,dfn[y],dfn[x],k);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d %d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
int cnt_node=n;
int last=1;
for(int i=0;i<=20;i++)
{
++cnt_node;
g[last].push_back(cnt_node);
g[cnt_node].push_back(last);
last=cnt_node;
}
scanf("%d",&q);
for(int i=0;i<=20;i++)
{
tree[i].Build(1,1,cnt_node);
}
dfs1(cnt_node,0);
dfs2(cnt_node,cnt_node);
while(q--)
{
scanf("%d",&op);
if(op==1)
{
scanf("%d",&x);
int Res=0;
int Now=0;
while(Now<=20)
{
Res+=tree[Now].Query(1,dfn[x]);
// printf("%d %d ?\n",x,tree[Now].Query(1,dfn[x]));
Now++;
x=Fa[x];
}
printf("%d\n",Res);
}
else
{
scanf("%d %d %d %d",&x,&y,&k,&d);
Update_chain(x,y,k,d);
int lca=Query_lca(x,y);
if(d)
{
tree[d-1].Update(1,dfn[lca],dfn[lca],k);
}
lca=Fa[lca];
while(d)
{
// printf("%d?\n",Now);
d--;
tree[d].Update(1,dfn[lca],dfn[lca],k);
if(d)
{
tree[d-1].Update(1,dfn[lca],dfn[lca],k);
}
lca=Fa[lca];
}
}
}
}
CF1770E Koxia and Tree加强版
只说大体思路
肯定是考虑每条边的贡献
首先转换\(k\)个点选\(m\)个点
选定其中一个连通块的中标记点大小\(S\),统计不合法的情况即可计算每条边经过的次数
然后解决每个点子树标记点大小为\(S\)的概率
注意到大小只会有\(1\)的变动,然后\(f_{x,t}\)为\(x\)点在\(t\)时有标记的概率,转移很简单
Show Code
#include<bits/stdc++.h>
using namespace std;
void read(int &x)
{
x=0;
int f=1;
char s=getchar();
while(s<'0'||s>'9')
{
if(s=='-')
{
f*=-1;
}
s=getchar();
}
while(s>='0'&&s<='9')
{
x=(x*10+(s-'0'));
s=getchar();
}
x*=f;
return;
}
const int MAXN=5e5+5;
const int MOD=998244353;
int fac[MAXN];
int inv_fac[MAXN];
int Pow(int a,int b,int p)
{
int res=1;
int base=a;
while(b)
{
if(b&1)
{
res=((long long)res*base)%p;
}
base=((long long)base*base)%p;
b>>=1;
}
return res;
}
int inv(int a,int p)
{
return Pow(a,p-2,p);
}
int C(int n,int m)
{
if(n<m||m<0)
{
return 0;
}
if(n==m||m==0)
{
return 1;
}
return ((((long long)fac[n]*inv_fac[m])%MOD)*inv_fac[n-m])%MOD;
}
int n,k,m;
int x,y;
pair<int,int>edge[MAXN];
int a[MAXN];
int f[MAXN];
int dep[MAXN];
vector<int>g[MAXN];
int Siz[MAXN];
int dp1[MAXN];
int dp2[MAXN];
int dp3[MAXN];
int P;
void dfs(int x,int f)
{
Siz[x]=a[x];
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==f)
{
continue;
}
dep[v]=dep[x]+1;
dfs(v,x);
Siz[x]+=Siz[v];
}
}
int main()
{
fac[0]=1;
for(int i=1;i<=MAXN-5;i++)
{
fac[i]=((long long)fac[i-1]*i)%MOD;
}
inv_fac[MAXN-5]=inv(fac[MAXN-5],MOD);
for(int i=MAXN-5-1;i>=0;i--)
{
inv_fac[i]=((long long)inv_fac[i+1]*(i+1))%MOD;
}
scanf("%d %d",&n,&k);
m=2;
for(int i=1;i<=k;i++)
{
read(x);
f[x]=1;
a[x]=1;
}
for(int i=1;i<n;i++){
read(x);
read(y);
edge[i].first=x;
edge[i].second=y;
g[x].push_back(y);
g[y].push_back(x);
}
int inv2=(MOD-MOD/2);
dfs(1,0);
for(int i=1;i<n;i++)
{
P=i;
int u=edge[P].first;
int v=edge[P].second;
if(dep[u]<dep[v])
{
swap(u,v);
}
int Lu=f[u];
int Lv=f[v];
f[u]=(((long long)Lu+Lv)*inv2)%MOD;
f[v]=(((long long)Lu+Lv)*inv2)%MOD;
dp1[u]=((long long)Lu*((long long)(1-Lv+MOD)%MOD))%MOD;
dp1[u]=((long long)dp1[u]*inv2)%MOD;
dp2[u]=((long long)Lv*((long long)(1-Lu+MOD)%MOD))%MOD;
dp2[u]=((long long)dp2[u]*inv2)%MOD;
dp3[u]=((long long)1-dp1[u]-dp2[u]+MOD)%MOD;
}
int Res=0;
for(int i=1;i<n;i++)
{
int u=edge[i].first;
int v=edge[i].second;
if(dep[u]<dep[v])
{
swap(u,v);
}
if(Siz[u]>=1)
{
int S=Siz[u]-1;
int Np=((long long)C(S,m)+C(k-S,m))%MOD;
Np=((long long)Np*inv(C(k,m),MOD))%MOD;
Np=((long long)1-Np+MOD)%MOD;
Np=((long long)Np*dp1[u])%MOD;
Res=((long long)Res+Np)%MOD;
}
if(1)
{
int S=Siz[u]+1;
int Np=((long long)C(S,m)+C(k-S,m))%MOD;
Np=((long long)Np*inv(C(k,m),MOD))%MOD;
Np=((long long)1-Np+MOD)%MOD;
Np=((long long)Np*dp2[u])%MOD;
Res=((long long)Res+Np)%MOD;
}
if(1)
{
int S=Siz[u];
int Np=((long long)C(S,m)+C(k-S,m))%MOD;
Np=((long long)Np*inv(C(k,m),MOD))%MOD;
Np=((long long)1-Np+MOD)%MOD;
Np=((long long)Np*dp3[u])%MOD;
Res=((long long)Res+Np)%MOD;
}
}
// Res=((long long)Res*2)%MOD;
printf("%d\n",Res);
}
CSAcademy Round #35 Counting Quests
好像第一步转化就不会/kk,原问题等价于设\(S_i\)为覆盖到\(i\)的区间集合,\(S_i\)互不相同
具体证明好像不会/kk,手玩一下挺对的
然后有个性质若\(S_a=S_b,a<b,\)则不会存在选定的区间相交且不包含/包含于\([a,b]\)
证明考虑假设存在选定的区间\(p\)相交且不包含/包含于\([a,b]\),假设\(a\)不被\(p\)覆盖则\(S_a\)不存在\(p\)而\(S_b\)中存在\(p\),所以与\(S_a=S_b\)矛盾
这其实我们可以将最大的\([a,b]\)使得\(S_a=S_b\)划分为\(1\)段具体来说我们可以以\(i=1\)为起点找最后一个\(S_1=S_j\)的位置,将\([1,j]\)划分为一段,并以\(i=j+1\)为新的起点
假设当前的序列划分为若干段,其中一段区间\([a,b]\)满足\(S_a=S_b\),则\([a,b]\)内部连边并不会使得划分的段有变化
考虑\(S_a=S_b\),说明一定存在一个选定区间横跨\([a,b]\),而对于\(i\in(a,b)\),\(S_a \subseteq S_i\),这就保证了按上述方式划分,内部任意连边不会产生影响
这样做有什么意义呢？考虑合法方案其实就是段数为\(n\)的方案,而这样分段好转移
设\(dp_i\)为长度为\(i\)时的合法方案数,考虑用总方案减去不合法的方案
考虑不合法的就是段数小于\(i\)的方案,考虑枚举\(j<i\)
考虑将\(i\)个数划分为\(j\)段(不考虑段与段之间的连边)为\(f_{i,j}\),这个是可以直接求的
在考虑横贯段的连边,为了保持\(j\)个段,也就是说我们可以把每一段看成一个点连边使得\(S\)各不相同,这部分就是\(dp_j\)
Show Code
#include<bits/stdc++.h>
using namespace std;
int MOD;
int n;
int f[305][305];
int dp[305];
int Pow[100005];
int main()
{
scanf("%d %d",&n,&MOD);
Pow[0]=1;
for(int i=1;i<=100000;i++)
{
Pow[i]=((long long)Pow[i-1]*2)%MOD;
}
f[0][0]=1;
for(int i=0;i<=n;i++)
{
for(int j=0;j<=i;j++)
{
if(!f[i][j])
{
continue;
}
for(int k=1;k<=n;k++)
{
if(i+k>n)
{
continue;
}
f[i+k][j+1]=((long long)f[i+k][j+1]+((long long)Pow[(k-1)*(k-2)/2]*f[i][j])%MOD)%MOD;
}
}
}
dp[0]=1;
for(int i=1;i<=n;i++)
{
dp[i]=Pow[(i*(i+1))/2];
//printf("%d %d?\n",i,dp[i]);
for(int j=1;j<i;j++)
{
dp[i]=((long long)dp[i]-((long long)dp[j]*f[i][j])%MOD+MOD)%MOD;
}
}
printf("%d\n",dp[n]);
}
[ARC126E] Infinite Operations
首先我们肯定可以确定的是操作后序列全相同是贡献最大
然后因为和不变所以平均数作为最后的数,然后贡献就是原数减平均数?
这好像没有考虑操作的过程中额外产生的贡献,至少没法构造一种这样的解
然后我们考虑构造一个\(F(x)=\sum\limits_{i<j}|a_i-a_j|\)
我们考虑一次价值为\(x\)的操作对\(F(x)\)的影响,对于操作的\(i,j\)至少会减少\(2x\)
而如果不存在\(a_i<a_k<a_j\),则一定只会减少\(2x\)
而终止条件为\(F(x)=0\),如果我们要价值最大一定是每次都选择上面的\(i,j\)
最大价值为\(\dfrac{F(x)}{2}\),线段树维护一下即可
Show Code
#include<bits/stdc++.h>
#define ls Tree[p].lc
#define rs Tree[p].rc
using namespace std;
const int MAXN=3e6+5;
const int MOD=998244353;
int cnt_node;
struct Seg{
int date;
int lc,rc;
int num;
}Tree[MAXN*4];
int rt;
void Update(int &p,int l,int r,int x,int op)
{
if(!p)
{
p=++cnt_node;
}
Tree[p].date=((long long)Tree[p].date+op*x+MOD)%MOD;
Tree[p].num+=op;
if(l==r)
{
return;
}
int mid=(l+r)>>1;
if(x<=mid)
{
Update(ls,l,mid,x,op);
}
else
{
Update(rs,mid+1,r,x,op);
}
}
int Query(int p,int l,int r,int ql,int qr)
{
if(ql>qr)
{
return 0;
}
if(!p)
{
return 0;
}
if(l>=ql&&r<=qr)
{
return Tree[p].date;
}
int Res=0;
int mid=(l+r)>>1;
if(ql<=mid)
{
Res=((long long)Res+Query(ls,l,mid,ql,qr))%MOD;
}
if(qr>mid)
{
Res=((long long)Res+Query(rs,mid+1,r,ql,qr))%MOD;
}
return Res;
}
int query(int p,int l,int r,int ql,int qr)
{
if(ql>qr)
{
return 0;
}
if(!p)
{
return 0;
}
if(l>=ql&&r<=qr)
{
return Tree[p].num;
}
int Res=0;
int mid=(l+r)>>1;
if(ql<=mid)
{
Res=((long long)Res+query(ls,l,mid,ql,qr))%MOD;
}
if(qr>mid)
{
Res=((long long)Res+query(rs,mid+1,r,ql,qr))%MOD;
}
return Res;
}
int n,q;
int a[MAXN];
int x,y;
int inv2;
int main()
{
inv2=MOD-MOD/2;
scanf("%d %d",&n,&q);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
Update(rt,1,1e9,a[i],1);
}
int F=0;
for(int i=1;i<=n;i++)
{
F=((long long)F+((long long)query(rt,1,1e9,1,a[i]-1)*a[i])%MOD)%MOD;
F=((long long)F-Query(rt,1,1e9,1,a[i]-1)+MOD)%MOD;
F=((long long)F-((long long)query(rt,1,1e9,a[i]+1,1e9)*a[i])%MOD+MOD)%MOD;
F=((long long)F+Query(rt,1,1e9,a[i]+1,1e9))%MOD;
}
F=((long long)F*inv2)%MOD;
while(q--)
{
scanf("%d %d",&x,&y);
F=((long long)F-((long long)query(rt,1,1e9,1,a[x]-1)*a[x])%MOD+MOD)%MOD;
F=((long long)F+Query(rt,1,1e9,1,a[x]-1)+MOD)%MOD;
F=((long long)F+((long long)query(rt,1,1e9,a[x]+1,1e9)*a[x])%MOD)%MOD;
F=((long long)F-Query(rt,1,1e9,a[x]+1,1e9)+MOD)%MOD;
Update(rt,1,1e9,a[x],-1);
a[x]=y;
Update(rt,1,1e9,a[x],1);
F=((long long)F+((long long)query(rt,1,1e9,1,a[x]-1)*a[x])%MOD)%MOD;
F=((long long)F-Query(rt,1,1e9,1,a[x]-1)+MOD)%MOD;
F=((long long)F-((long long)query(rt,1,1e9,a[x]+1,1e9)*a[x])%MOD+MOD)%MOD;
F=((long long)F+Query(rt,1,1e9,a[x]+1,1e9))%MOD;
printf("%d\n",(((long long)F*inv2)%MOD));
}
}
[ARC101F] Robots and Exits
又一次觉得自己是智障
很明显的转化,可以计算每个点左右走最近的出口,设距离为\(L_i,R_i\)
注意如果左或右没有出口直接忽略(可以直接确定是从哪个出口出去的)我就是因为这个被卡了
我最开始想的是给\(L_i\)排序,然后设\(dp_i\)为前\(i\)个数的方案
然后枚举一个\(j,R_j<R_i\)然后我们就假设\((i,j)\)从\(L\)走的,即\(dp_i=dp_j+1\)
不过很明显不对,没有考虑\(L\)的顺序,好像吧
然后换个思路我们考虑答案序列的构造
对于\(L_i\le L_j,R_i\ge R_j\),若\(i\)是从\(R\)走的,那\(j\)一定也是从\(R\)走
因此我们同样可以对\(L_i\)排序,考虑\(i\)如果选择,将会同样选择后面\(<R_i\)的\(j\)
这启示我们可以对第一次的选择\(Dp\)
设\(dp_i\)为前\(i\)个且第一次选择\(i\)的方案,这里要求选的\(i\)是单调递增的,即\(dp_i=\sum dp_j+1,R_j<R_I\)
这个式子和我错误的想法是一样的,大概能过?(/yiw)(反转了,好像举不出反例)
好像可以解释,我最开始想的反例是可能是不对的
Show Code
#include<bits/stdc++.h>
#define ls Tree[p].lc
#define rs Tree[p].rc
#define INF 2e9
using namespace std;
const int MAXN=2e5+5;
const int MOD=1e9+7;
int n,m;
int X[MAXN];
int Y[MAXN];
struct node{
int up,down;
bool operator<(const node x)const{
if(down==x.down)
{
return up>x.up;
}
return down<x.down;
}
}a[MAXN];
int dp[MAXN];
struct Seg{
int date;
int lc,rc;
}Tree[MAXN*20];
int rt;
int cnt_node;
void Update(int &p,int l,int r,int x,int k)
{
if(!p)
{
p=++cnt_node;
}
Tree[p].date=((long long)Tree[p].date+k)%MOD;
if(l==r)
{
return;
}
int mid=(l+r)>>1;
if(x<=mid)
{
Update(ls,l,mid,x,k);
}
else
{
Update(rs,mid+1,r,x,k);
}
}
int Query(int p,int l,int r,int ql,int qr)
{
if(ql>qr)
{
return 0;
}
if(!p)
{
return 0;
}
if(l>=ql&&r<=qr)
{
return Tree[p].date;
}
int Res=0;
int mid=(l+r)>>1;
if(ql<=mid)
{
Res=((long long)Res+Query(ls,l,mid,ql,qr))%MOD;
}
if(qr>mid)
{
Res=((long long)Res+Query(rs,mid+1,r,ql,qr))%MOD;
}
return Res;
}
int main()
{
scanf("%d %d",&n,&m);
printf("%d %d?\n",n,m);
for(int i=1;i<=n;i++)
{
scanf("%d",&X[i]);
}
for(int i=1;i<=m;i++)
{
scanf("%d",&Y[i]);
}
sort(X+1,X+1+n);
sort(Y+1,Y+1+m);
int Cnt=0;
for(int i=1;i<=n;i++)
{
int R=lower_bound(Y+1,Y+1+m,X[i])-Y;
int L=R-1;
if(R==m+1)
{
continue;
}
if(L==0)
{
continue;
}
a[++Cnt].up=Y[R]-X[i];
a[Cnt].down=X[i]-Y[L];
}
sort(a+1,a+1+Cnt);
dp[0]=1;
for(int i=1;i<=Cnt;i++)
{
if(a[i].up==a[i-1].up&&a[i].down==a[i-1].down)
{
continue;
}
// printf("%d?\n",i);
dp[i]=((long long)Query(rt,1,1e9,1,a[i].up-1)+1)%MOD;
Update(rt,1,1e9,a[i].up,dp[i]);
}
int Res=0;
// printf("%d??\n",Cnt);
for(int i=0;i<=Cnt;i++)
{
Res=((long long)Res+dp[i])%MOD;
}
printf("%d\n",Res);
}
[AGC049D] Convex Sequence
首先很明显转化成差分的形式后是下凸函数的形式(然后就不会了/kk)
然后肯定有个底,最下面是平台,我们考虑设平台最左端的点为\(i\)
考虑满足题意最小总和的序列,一定是平台为\(0\),左边依次加\(1\),右边全部为\(0\)
考虑在此基础上经过一些操作使得总和为\(m\)且依旧是个凸函数
回想之前一个很经典的题,构造一个总和为\(m\)的递增序列,具体做法就是用在末尾加\(1\)和整体加\(1\)构造
同样,在这道题中,我们可以设计三个操作
首先可以给序列整体加\(1\)
然后可以给\(i\)左边整体加一个等差数列\((k,k-1,k-2...1)\)
和给右边整体加一个等差数列\((1,2,....k)\)
可以证明这样的操作是可以覆盖所有满足条件的序列且合法的
然后注意到一次操作的贡献是\(n\)或\(\dfrac{k(k+1)}{2}\),说明\(k\)的取值只有\(\sqrt{m}\)个
对于固定的\(i\),做有\(\sqrt m\)个物品的完全背包即可
考虑从\((i-1)\rightarrow i\),不难想到左边的物品多了一个,右边少了一个,做一次完全背包删加物品即可
Show Code
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int MOD=1e9+7;
int n,m;
int dp[MAXN];
int a[MAXN];
int f[MAXN];
int main()
{
scanf("%d %d",&n,&m);
a[0]=0;
for(int i=1;i<=n;i++)
{
a[i]=a[i-1]+i;
if(a[i]>m)
{
a[i]=m+1;
}
}
dp[0]=1;
for(int i=1;i<n;i++)
{
for(int j=a[i];j<=m;j++)
{
dp[j]=((long long)dp[j]+dp[j-a[i]])%MOD;
}
}
for(int i=n;i<=m;i++)
{
dp[i]=((long long)dp[i]+dp[i-n])%MOD;
}
int Res=dp[m];
int Rs=m;
for(int i=2;i<=n;i++)
{
Rs-=(i-1);
if(Rs<0)
{
break;
}
int Del=a[n-i+1];
for(int j=m;j>=Del;j--)
{
dp[j]=((long long)dp[j]-dp[j-Del]+MOD)%MOD;
}
int Add=a[i-1];
for(int j=Add;j<=m;j++)
{
dp[j]=((long long)dp[j]+dp[j-Add])%MOD;
}
Res=((long long)Res+dp[Rs])%MOD;
}
printf("%d\n",Res);
}
