四个半小时做下来感觉超级爽！！！最后一题暴力 \(85\)，开个 \(O_2\) 就过了
实际得分：\(100+100+85\)
考完才知道这叫 \(min-max\) 对抗搜索……不是一个暴搜就解决的东西吗
暴力有 \(80\)，出题人还是很良心的
我来讲一下我的做法吧
我们记录一个数组 \(f[i]\) 表示第 \(i\) 行用了 \(f[i]\) 个棋子最大/最小相差得分。显然 \(f_i\geq f_{i+1}\)
所以发现情况不多，可以证明有 \(C(2*n-1,n)\) 种。对于每种情况枚举每一行的情况，如果 \(f_{i-1}>f_i\) 就将 \(f_i+1\)。我们直接暴力状压，不用哈希，多一个 \(map\)，时间复杂度 \(O(nC(2\times n-1,n)\log C(2\times n-1,n))\)
\(Code\ Below:\)
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
using namespace std;
const ll inf=0x3f3f3f3f;
ll n,m,a[20][20],b[20][20],H[20];
map<ll,ll> mp;
struct node{
ll s[20],sta,f;
};
inline ll read(){
register ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return (f==1)?x:-x;
}
ll dfs(node u){
if(mp.count(u.sta)) return mp[u.sta];
node v;v=u;v.f=-v.f;
ll ans=u.f==1?-inf:inf;
for(ll i=0;i<n;i++){
if(u.s[i]<m&&(i==0||u.s[i-1]>u.s[i])){
v.s[i]++;v.sta+=H[i];
if(u.f==1){
ans=max(ans,dfs(v)+a[i][u.s[i]]);
}
else {
ans=min(ans,dfs(v)-b[i][u.s[i]]);
}
v.s[i]--;v.sta-=H[i];
}
}
return mp[u.sta]=ans;
}
int main()
{
n=read(),m=read();
for(ll i=0;i<n;i++)
for(ll j=0;j<m;j++) a[i][j]=read();
for(ll i=0;i<n;i++)
for(ll j=0;j<m;j++) b[i][j]=read();
H[0]=1;
for(ll i=1;i<n;i++) H[i]=H[i-1]*(m+1);
node u;
for(ll i=0;i<n;i++) u.s[i]=0;
u.sta=0;u.f=1;
ll ans=0;
for(ll i=0;i<n;i++) ans+=H[i]*m;
mp[ans]=0;
printf("%lld\n",dfs(u));
return 0;
}构造题出成线段树也是神仙啊。
这个预留位置还是在考场上现场 \(yy\) 的，自己造数据一直跟暴力拍不上。。。
将问题转化为线段树的区间加区间最小值，在线段树上二分。
\(Code\ Below:\)
#include <bits/stdc++.h>
#define lson (rt<<1)
#define rson (rt<<1|1)
using namespace std;
const int maxn=500000+10;
const int inf=0x3f3f3f3f;
int n,a[maxn],cnt[maxn],siz[maxn],fa[maxn],vis[maxn],ans[maxn],sum[maxn<<2],add[maxn<<2];double k;
inline int read(){
register int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return (f==1)?x:-x;
}
inline void pushup(int rt){
sum[rt]=min(sum[lson],sum[rson]);
}
inline void pushdown(int rt){
if(add[rt]){
sum[lson]+=add[rt];sum[rson]+=add[rt];
add[lson]+=add[rt];add[rson]+=add[rt];
add[rt]=0;
}
}
void build(int l,int r,int rt){
if(l == r){
sum[rt]=l;
return ;
}
int mid=(l+r)>>1;
build(l,mid,lson);
build(mid+1,r,rson);
pushup(rt);
}
void update(int L,int R,int C,int l,int r,int rt){
if(L <= l && r <= R){
sum[rt]+=C;add[rt]+=C;
return ;
}
pushdown(rt);
int mid=(l+r)>>1;
if(L <= mid) update(L,R,C,l,mid,lson);
if(R > mid) update(L,R,C,mid+1,r,rson);
pushup(rt);
}
int query(int x,int l,int r,int rt){
if(l == r){
return sum[rt]>=x?l:l+1;
}
pushdown(rt);
int mid=(l+r)>>1;
if(sum[rson]<x) return query(x,mid+1,r,rson);
return query(x,l,mid,lson);
}
bool cmp(int a,int b){
return a>b;
}
int main()
{
n=read();
scanf("%lf",&k);
for(int i=1;i<=n;i++) a[i]=read();
sort(a+1,a+n+1,cmp);
build(1,n,1);
for(int i=n;i>=1;i--){
cnt[i]=(a[i]==a[i+1])?cnt[i+1]+1:0;
fa[i]=(int)floor(1.0*i/k);siz[i]++;
siz[fa[i]]+=siz[i];
}
int now;
for(int i=1;i<=n;i++){
if(fa[i]&&!vis[fa[i]]){
update(ans[fa[i]],n,siz[fa[i]]-1,1,n,1);
vis[fa[i]]=1;
}
now=query(siz[i],1,n,1);
now+=cnt[now];cnt[now]++;
ans[i]=now;
update(ans[i],n,-siz[i],1,n,1);
}
for(int i=1;i<=n;i++) printf("%d ",a[ans[i]]);
printf("\n");
return 0;
}神仙的整体 \(DP\) + 拉格朗日插值没看懂。。。发一个暴力 + \(O_2\) 卡过去的代码
设 \(f[i][j][k]\) 为 以 \(i\) 为根的联通块中权值 \(\geq j\) 有 \(k\) 个的方案数
\[f[i][j][k]=\prod_{u\in son_i}f[u][j][k']\ (d_i<k,\sum k'=k)\]
\[f[i][j][k]=\prod_{u\in son_i}f[u][j][k']\ (d_i\geq k,\sum k'=k-1)\]
然后我们每次枚举 \(j\)，省掉一维，时间复杂度 \(O(n^2W)\)
小优化：
1、不用 \(memset\)
2、在 \(sum>=k\) 时再 \(dp\)
3、能不取模就不取模
4、开个 \(O_2\)，最大一个点 \(3s\) 左右
\(Code\ Below:\)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2000+10;
const int p=64123;
int n,k,W,a[maxn],siz[maxn],b[maxn],f[maxn][maxn],ans;
int head[maxn],to[maxn<<1],nxt[maxn<<1],tot;
inline int read(){
register int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return (f==1)?x:-x;
}
inline void addedge(int x,int y){
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void dfs(int x,int fa){
f[x][siz[x]]=1;
register int i,j,t,y;
for(i=head[x];i;i=nxt[i]){
y=to[i];
if(y==fa) continue;
dfs(y,x);
for(j=siz[x];j>=0;j--)
if(f[x][j])
for(t=siz[y];t>=0;t--)
if(f[y][t]){
f[x][j+t]+=(ll)f[x][j]*f[y][t]%p;
if(f[x][j+t]>=p) f[x][j+t]-=p;
}
siz[x]+=siz[y];
}
for(i=k;i<=siz[x];i++){
ans+=f[x][i];
if(ans>=p) ans-=p;
}
}
int main()
{
n=read(),k=read(),W=read();
register int x,y,i,j,t;
for(i=1;i<=n;i++) a[i]=read(),b[a[i]]++;
for(i=1;i<n;i++){
x=read(),y=read();
addedge(x,y);addedge(y,x);
}
for(i=W;i>=1;i--) b[i]+=b[i+1];
for(i=1;i<=W;i++){
if(b[i]>=k){
for(j=1;j<=n;j++)
for(t=0;t<=2*siz[j]&&t<=2000;t++) f[j][t]=0;
for(j=1;j<=n;j++) siz[j]=(a[j]>=i)?1:0;
dfs(1,0);
}
}
printf("%d\n",ans);
return 0;
}原文：https://www.cnblogs.com/owencodeisking/p/10225866.html