T1 雷老师的正偏态分布
简要题意： 给出一个数组 \(a\) 要找一段 平均数 \(<\) 中位数的子集的方案 其中子集大小是奇数
其中 \(a_i\leq V\)
范围: \(n\leq 100\space V\leq 800\)
这里有两个思路
- 1 枚举平均数 锁定中位数 比较难找 可以抛弃
- 2 枚举中位数 锁定平均数
我们发现第二种很好做
只需要把数组排序 然后 \(O(n)\) 枚举一个中位数
然后再 \(O(n)\) 枚举以这个数为中心左右找几个数 他们的和小于这个中位数的某个倍数
然后这个东西前后做一次背包和前缀和就行了
时间复杂度 \(O(n^3V)\) 空间复杂度 \(O(n^3V)\)
时间(理论)是过得去的 实际真的能过去 但是空间炸了
于是要优化空间
正着做的背包顺序做很简单
倒着做的背包考虑一下倒背包很快解决
后面就是一些卡常问题
AC code
#include<bits/stdc++.h>
#pragma GCC optimize (1)
#pragma GCC optimize (2)
#pragma GCC optimize (3,"Ofast","inline")
#define ll long long
#define N 105
#define M N*800
using namespace std;
const int mod = 998244353;
int n,m,sum;
int ans;
int a[N],b[N];
int f[N][M],f1[N][M],g[N][M];
void add(int &a,int b)
{
a=a+b>mod?a+b-mod:a+b;
}
void solve(int l,int r)
{
int mid=(a[l]+a[r])/2;
for(int i=1;i<=min(l,n-r+1);i++)
for(int j=0;j<i*mid*2;j++)
add(ans,1ll*f1[i][j]*g[i][i*mid*2-j-1]%mod);
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),sum+=a[i];
sort(a+1,a+1+n);
f[0][0]=g[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=n;j>=1;j--)
{
for(int k=sum;k>=a[i];k--)
add(g[j][k],g[j-1][k-a[i]]);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=sum;k>=a[i];k--)
add(g[j][k],mod-g[j-1][k-a[i]]);
}
solve(i,i);
for(int j=n;j>=1;j--)
{
for(int k=sum;k>=a[i];k--)
add(f[j][k],f[j-1][k-a[i]]);
}
f1[0][0]=f[0][0];
for(int j=1;j<=n;j++)
for(int k=1;k<=sum;k++)
f1[j][k]=(f[j][k]+f1[j][k-1])-(f[j][k]+f1[j][k-1]>mod?mod:0);
}
printf("%d",ans);
return 0;
}
T2 假期计划Ⅱ
原题: 传送门
纯纯毒瘤题目
题意：给出一个稠密图 \(n\) 个点 \(n^2\) 条边 每次删掉一条边 求 \(1\to n\) 走 \(k\) 条边的最短路
\(n\leq 300\space k\leq 8\)
只能说很毒
首先这种删边肯定很不好做 考虑时间倒流加边
正解是折半 大分类
维护 :
\(f_{i,j}\) 表示从 \(1\) 走 \(j\) 条边到 \(i\) 的最短路 其中 \(j\leq 4\)
\(g_{i,j}\) 表示从 \(i\) 走 \(j\) 条边到 \(n\) 的最短路 其中 \(j\leq 4\)
\(dp_{i,j,k}\) 表示从 \(i\) 走 \(k\) 条边到 \(j\) 的最短路 其中 \(k\leq 2\)
\(f,g,dp\) 的更新是 \(O(n)\) 的
总时间复杂度 \(O(n^3)\) 可以通过
但是不想写大分类怎么办(((
直接考虑分层图 spfa !
总共有 \(nk\) 个点 \(n^2k\) 条边
总时间复杂度应该是 \(O(n^4k)\) 直接升天
但是它就是卡过去了
假代码就不放了 (((
T3 惊蛰
写的最痛心的一题
传送门
这题一眼 dp 思考出最简单的 dp 不难
考虑 \(f_{i,j}\) 表示第 \(i\) 个时刻花 \(j\) 精力去做
滚一个后缀最小值就可以优化成 \(O(n^2)\) 的了
最重要的是考虑到这道题的单调性
如果当前分界点是 \(pos\) 那么这个位置前后一定是成单调上升的
原因就在于加上的数是单调上升的
这样经过多重优化可以简化代码
这里放出优化到最简洁的 \(O(n^2)\) 代码
#include<bits/stdc++.h>
#define ll long long
#define N 10005
using namespace std;
int n,m,a[N],b[N];
ll f[N];
int main()
{
// freopen("c.in","r",stdin);
// freopen("c.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),b[i]=a[i];
sort(b+1,b+1+n);
int len=unique(b+1,b+1+n)-b-1;
f[len+1]=1e17;
for(int i=1;i<=n;i++)
{
int pos=lower_bound(b+1,b+1+len,a[i])-b;
for(int j=1;j<pos;j++)
f[j]=f[j]+m;
for(int j=pos;j<=n;j++)
f[j]=f[j]+b[j]-a[i];
int first=lower_bound(f,f+1+pos-1,f[pos])-f;
for(int j=first;j<pos;j++)
f[j]=f[pos];
}
cout<<f[1];
return 0;
}
到这一步 也就是最难的一步 要把 dp 数组拍到线段树上面
第一个 for 区间加 很好解决
第二个要加上一个数组 不是很好搞 这个后面说
第三个是推平 容易写
难点就在于 在 \(1\to pos\) 中找第一个比 \(f[pos]\) 大的数
这里考虑记下当前线段树最左边的端点 然后二分即可
因此 增加一个数组 记录一下系数和映射的数即可
调吐了
我写的估计比较丑和冗杂
AC code
#include<bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
int n,m;
ll a[N],b[N];
struct tree{
ll add,cov,tag,first,v;
// 增加 覆盖 增加系数 最右边的值
}tr[N*4];
void Pushup(int x)
{
tr[x].first=tr[x*2].first;
}
void Pushdown(int x)
{
if(tr[x].cov)
{
tr[x*2].cov=tr[x*2+1].cov=tr[x].cov;
tr[x*2].add=tr[x*2+1].add=tr[x*2].tag=tr[x*2+1].tag=0;
tr[x*2].first=tr[x*2+1].first=tr[x].cov;
tr[x].cov=0;
}
if(tr[x].add)
{
tr[x*2].add+=tr[x].add,
tr[x*2+1].add+=tr[x].add;
tr[x*2].first+=tr[x].add;
tr[x*2+1].first+=tr[x].add;
tr[x].add=0;
}
if(tr[x].tag)
{
tr[x*2].tag+=tr[x].tag,
tr[x*2+1].tag+=tr[x].tag;
tr[x*2].first+=tr[x].tag*b[tr[x*2].v];
tr[x*2+1].first+=tr[x].tag*b[tr[x*2+1].v];
tr[x].tag=0;
}
}
void updata(int l,int r,int L,int R,int x,ll v)
{
if(l>R||r<L) return;
if(l>=L&&r<=R)
{
tr[x].add+=v;
tr[x].first+=v;
return;
}
int mid=(l+r)/2;
Pushdown(x);
updata(l,mid,L,R,x*2,v);
updata(mid+1,r,L,R,x*2+1,v);
Pushup(x);
}
void modify(int l,int r,int L,int R,int x)
{
if(l>R||r<L) return;
if(l>=L&&r<=R)
{
tr[x].tag++;
tr[x].first+=b[tr[x].v];
return;
}
int mid=(l+r)/2;
Pushdown(x);
modify(l,mid,L,R,x*2);
modify(mid+1,r,L,R,x*2+1);
Pushup(x);
}
ll query(int l,int r,int L,int x)
{
if(l==r) return tr[x].first;
Pushdown(x);
int mid=(l+r)/2;
if(L<=mid) return query(l,mid,L,x*2);
else return query(mid+1,r,L,x*2+1);
}
void cover(int l,int r,int L,int R,int x,ll v)
{
if(l>R||r<L) return;
if(l>=L&&r<=R)
{
tr[x].add=tr[x].tag=0;
tr[x].cov=tr[x].first=v;
return;
}
Pushdown(x);
int mid=(l+r)/2;
cover(l,mid,L,R,x*2,v);
cover(mid+1,r,L,R,x*2+1,v);
Pushup(x);
}
void access(int l,int r,int L,int R,int x,ll v)
{
if(l>R||r<L) return;
if(l==r)
{
tr[x].first=min(tr[x].first,v);
return ;
}
int mid=(l+r)/2;
Pushdown(x);
if(mid+1>=R)
access(l,mid,L,R,x*2,v);
else
{
if(tr[x*2+1].first>=v)
{
cover(mid+1,r,mid+1,R,x*2+1,v);
access(l,mid,L,R,x*2,v);
}
else
access(mid+1,r,L,R,x*2+1,v);
}
Pushup(x);
}
void build(int l,int r,int x)
{
if(l==r)
{
tr[x].first=0;
tr[x].v=l;
return;
}
int mid=(l+r)/2;
build(l,mid,x*2);
build(mid+1,r,x*2+1);
tr[x].v=tr[x*2].v;
}
int main()
{
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]),b[i]=a[i];
sort(b+1,b+1+n);
int len=unique(b+1,b+1+n)-b-1;
build(1,len,1);
for(int i=1;i<=n;i++)
{
int pos=lower_bound(b+1,b+1+len,a[i])-b;
updata(1,len,1,pos-1,1,m);
updata(1,len,pos+1,len,1,-a[i]);
modify(1,len,pos+1,len,1);
ll val=query(1,len,pos,1);
access(1,len,1,pos,1,val);
}
printf("%lld",query(1,len,1,1));
return 0;
}
这个题评蓝 可以说是蓝题巅峰了