AtCoder Educational DP Contest 总结
前言
感觉都初一升初二了，再做这个题是不是有点太菜了啊……
里面大概都是些 DP 板子题（确信，题目质量还挺高的，不过不涉及太难的优化（实际上只有最后一题是斜率优化）。
不管了，还是写个 blog 来总结一下吧~
T Permutation
题目大意：给你一个长度为 \(n-1\) 的只有 < 或者 > 两种字符的字符串 \(s\)，分别代表 \(p_i<p_{i+1}\) 或 \(p_i>p_{i+1}\)，求有多少个 \(1\) 到 \(n\) 的排列 \(p\) 满足这个要求。
数据范围：\(n\leq 3000\)
这个数据范围就明摆着的 \(O(n^2)\) DP？
一开始容易想到一个错误的状态 \(f(i,j)\) 表示第 \(i\) 个数为 \(j\) 的情况数。
这个状态错误的原因就是我们不应该关心 \(p_i\) 的值，而是应该关心 \(p_i\) 在前 \(i\) 个数中的排名。（高妙啊！）
这样就不难设计出 DP 状态 \(f(i,j)\) 表示第 \(i\) 个数在 \(1\) 到 \(i\) 中排名为 \(j\) 的情况。
转移:
- 若 \(s_{i-1}\) 为
<，则 \(f(i,j)\leftarrow \sum_{k=1}^{j-1}f(i-1,k)\)。 - 否则 \(f(i,j)\leftarrow \sum_{k=j}^nf(i-1,k)\)
这个东西大力不行，用前缀和优化一下即可。
时间复杂度 \(O(N^2)\)。
代码：
#include<bits/stdc++.h>
#define rep(i,n) for(int i=1;i<=n;i++)
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,x,y) for(int i=x;i<=y;i++)
#define sz(x) (int)(x.size())
#define LL long long
#define pii pair<int, int>
#define pLL pair<LL, LL>
using namespace std;
template<typename T>inline void chmax(T &a,T b){a = max(a, b);}
template<typename T>inline void chmin(T &a,T b){a = min(a, b);}
const int maxn=3005,mod=1e9+7;
int n,dp[maxn][maxn],presum[maxn][maxn];
string s;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>s;s=' '+s;
dp[1][1]=1;
for(int i=1;i<=n;i++)presum[1][i]=1;
for(int i=2;i<=n;i++){
if(s[i-1]=='<'){
for(int j=1;j<=i;j++)dp[i][j]=presum[i-1][j-1];
}
else{
for(int j=1;j<=i;j++)dp[i][j]=(presum[i-1][n]-presum[i-1][j-1]+mod)%mod;
}
for(int j=1;j<=n;j++)presum[i][j]=(presum[i][j-1]+dp[i][j])%mod;
}
cout<<presum[n][n]<<endl;
return 0;
}
U Grouping
题意：给你 \(n\) 个物品需要分组，你可以将它们分成一些组合，每组内部每一对 \((i,j)\) 都会产生一个贡献 \(a_{i,j}\)（可能为负数），问你最大可能产生的总贡献。
数据范围：\(n\leq 16\)
裸状压 DP，没啥技术含量，差评。
一看这个数据范围就知道肯定是状压 DP。
然后你知道这个以后就容易设计出 DP 状态：设 \(f(i)\) 表示选择状态为 \(i\) 时的最大总贡献。
考虑转移，转移就是你一个 \(i\) 有两种选择：
不划分（直接成为一个集合，即 \(i\) 内部两两直接产生贡献）
划分成多个集合（划分后每个集合分别计算）
但你考虑这个情况并不需要真的划分成多个集合，只要划分成 2 个然后这 2 个在递归继续划分。
划分成 2 个的过程可以通过用二进制枚举子集来实现。
总时间复杂度 \(O(2^N)\)。
代码：
#include <bits/stdc++.h>
#define sz(x) (int)(x.size())
using namespace std;
const int mod=1e9+7,Base=233,INF=0x3f3f3f3f;
template<typename T>inline void chmax(T &a, T b){a=max(a,b);}
template<typename T>inline void chmin(T &a, T b){a=min(a,b);}
inline void trans(int &a,int b){a+=b;if(a>mod)a-=mod;}
int n;
long long a[20][20],dp[1<<16];
long long dfs(int mask)
{
if(dp[mask]!=-1)
return dp[mask];
long long &ret=dp[mask];
ret=0;
for(int i=0;i<n;i++)
if((mask>>i)&1)
for(int j=i+1;j<n;j++)
if((mask>>j)&1)
ret+=a[i][j];
for(int i=mask&(mask-1);i>0;i=(i-1)&mask)
chmax(ret,dfs(i)+dfs(mask^i));
return ret;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>a[i][j];
memset(dp,-1,sizeof(dp));
cout<<dfs((1<<n)-1)<<"\n";
return 0;
}
V Subtree
题目大意：有一棵 \(n\) 个节点的数，你要给它黑白染色，但是限定染黑的节点必须连在一起（即形成一个连通块），对于每一个 \(i=1...n\)，问如果强制将 \(i\) 节点染黑的染色方案数。（注意：模数不保证为质数）
数据范围：\(n\leq 10^5\)
感觉 \(O(N)\) 的 DP 且要对于每个 \(i\) 都求的要么就是一次全算出来，要么是换根 DP。
这题一开始想的是拓扑排序的一个做法，但是不太会。后来看了 ft 巨佬题解才贺出来（划掉）。
不过这道题不用换根 DP 也能解释？（不懂
你需要分两类，即 \(u\) 子树里（不含 \(u\)）和除了 \(u\) 的子树（含 \(u\)）。
对这两类分别使用 \(f(u),g(u)\) 来表示强制 \(u\) 染色的代价。
首先考虑 \(f(u)\) 的转移，这是简单的：
\]
这个式子就表示每个子树都可以染或不染，染就 \(f(v)\) 种，不染就一车空白 1 种。
但是 \(g(u)\) 的转移就需要从 \(f(u)\) 进行倒推了（貌似和某模拟赛我想的思路一样）：
\]
这个转移分成 2 类：
父亲及祖先（\(g(p)\)）
兄弟的子树（\(\prod_{v\in son(p)}(f(v)+1)\)）
剩下的 \(1\) 就是啥都不染的代价。
这样就可以得到一个 \(O(N^2)\) 的做法了。
Some Optimization:
考虑到 \(O(N^2)\) 并不能通过此题（至少我不能，所以需要优化转移。
考虑到复杂度瓶颈为枚举兄弟节点，容易想到一个优化就是 \(\prod_{v\in son(p)}(f(v)+1)=\frac{f(p)}{f(u)+1}\)，但是不能直接用乘法逆元搞。
仔细想想维护前缀和后缀积就行，这样时间复杂度 \(O(N)\)。
代码：
#include <bits/stdc++.h>
#define sz(x) (int)(x.size())
using namespace std;
const int Base=233,INF=0x3f3f3f3f;
template<typename T>inline void chmax(T &a, T b){a=max(a,b);}
template<typename T>inline void chmin(T &a, T b){a=min(a,b);}
const int maxn=1e5+5;
int n,mod,F[maxn],G[maxn];
vector<int> g[maxn],pre[maxn],suf[maxn];
inline void trans(int &a,int b){a+=b;if(a>mod)a-=mod;}
void dfs1(int x,int p)
{
pre[x].resize(sz(g[x]),1);
suf[x].resize(sz(g[x]),1);
F[x]=1;
if(sz(g[x])==1&&g[x][0]==p)
return;
for(int i=0;i<sz(g[x]);i++)
{
int to=g[x][i];
if(to==p)
continue;
dfs1(to,x);
F[x]=1LL*F[x]*(F[to]+1)%mod;
}
for(int i=1;i<sz(g[x]);i++)
{
pre[x][i]=pre[x][i-1];
if(g[x][i-1]==p)
continue;
pre[x][i]=1LL*pre[x][i]*(F[g[x][i-1]]+1)%mod;
}
for(int i=sz(g[x])-2;i>=0;i--)
{
suf[x][i]=suf[x][i+1];
if(g[x][i+1]==p)
continue;
suf[x][i]=1LL*suf[x][i]*(F[g[x][i+1]]+1)%mod;
}
}
void dfs2(int x,int p,int id)
{
G[x]=1;
if(p)
{
int tr=G[p];
tr=1LL*tr*pre[p][id]%mod;
tr=1LL*tr*suf[p][id]%mod;
trans(G[x],tr);
}
for(int i=0;i<sz(g[x]);i++)
{
int to=g[x][i];
if(to==p)
continue;
dfs2(to,x,i);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>mod;
int u,v;
for(int i=1;i<n;i++)
{
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(1,0);
dfs2(1,0,0);
for(int i=1;i<=n;i++)
cout<<1LL*F[i]*G[i]%mod<<"\n";
return 0;
}
W Intervals
题目大意：你要构造一个长度为 \(n\) 的 01 串，它的价值由 \(m\) 条规则组成，每条规则如下：
- 若在区间 \([l_i,r_i]\) 中有
1，则会获得 \(a_i\) 的价值（注意：\(a_i\) 可能为负数）。
求可能的最大价值。
数据范围：\(n\leq 10^5\)
我的评价是：高妙啊！tql！
容易想到的是按 \(r_i\) 排序，对于每个 \(r_i\) 分别计算到 \(l_i\) 的贡献。
我当时的做法是设 \(f(i)\) 表示到第 \(i\) 个字符并且必须选 \(i\) 的最大价值。然后大概推了推式子就弃掉了……
实际上这道题的思路是先设计出 \(O(N^2)\) 的状态再优化，优化就比较套路了。
具体来说，可以设 \(f(i,j)\) 表示到第 \(i\) 个字符并且上一个选的字符是 \(j\)（\(j=i\) 表示选了第 \(i\) 个字符）的最大价值。
转移比较容易：
f(i,i)=\min_{j<i}f(i-1,j)\\
f(i,j)=f(i-1,j)+\sum_{r_k=i,l_k\leq j}a_k
\end{cases}
\]
这个东西用线段树搞一下时间空间直接 ok 了。
#include <bits/stdc++.h>
#define sz(x) (int)(x.size())
using namespace std;
const int mod=1e9+7,Base=233,inf=0x3f3f3f3f;
const long long INF=0x3f3f3f3f3f3f3f3f;
template<typename T>inline void chmax(T &a, T b){a=max(a,b);}
template<typename T>inline void chmin(T &a, T b){a=min(a,b);}
inline void trans(int &a,int b){a+=b;if(a>mod)a-=mod;}
const int maxn=2e5+5;
int n,m;
struct node
{
int l,r;
long long val,tag;
};
struct segmentree
{
node tree[maxn<<2];
void pushup(int x)
{
tree[x].val=max(tree[x<<1].val,tree[x<<1|1].val);
}
void pushdown(int x)
{
if(!tree[x].tag)
return;
tree[x<<1].tag+=tree[x].tag;
tree[x<<1|1].tag+=tree[x].tag;
tree[x<<1].val+=tree[x].tag;
tree[x<<1|1].val+=tree[x].tag;
tree[x].tag=0;
}
void build(int x,int l,int r)
{
tree[x].l=l;
tree[x].r=r;
tree[x].val=-INF;
tree[x].tag=0;
if(l==r)
return;
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
}
void update1(int x,int p,long long v)
{
if(tree[x].l==tree[x].r)
{
tree[x].val=v;
return;
}
int mid=(tree[x].l+tree[x].r)>>1;
if(p<=mid)
update1(x<<1,p,v);
else
update1(x<<1|1,p,v);
pushup(x);
}
void update2(int x,int l,int r,long long v)
{
if(tree[x].l>=l&&tree[x].r<=r)
{
tree[x].val+=v;
tree[x].tag+=v;
return;
}
pushdown(x);
int mid=(tree[x].l+tree[x].r)>>1;
if(l<=mid)
update2(x<<1,l,r,v);
if(r>mid)
update2(x<<1|1,l,r,v);
pushup(x);
}
}tr;
struct rule
{
int l,r;
long long val;
bool operator < (const rule &x) const
{
return r<x.r;
}
}a[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>a[i].l>>a[i].r>>a[i].val;
sort(a+1,a+m+1);
tr.build(1,1,n);
int p=1;
for(int i=1;i<=n;i++)
{
tr.update1(1,i,max(0LL,tr.tree[1].val));
while(a[p].r==i)
{
tr.update2(1,a[p].l,i,a[p].val);
p++;
}
}
cout<<max(0LL,tr.tree[1].val)<<"\n";
return 0;
}
最新文章
- c#设计模式-观察者模式
- css圆角边框
- fir.im Weekly - 工欲善其事，必先利其器
- HTML5之本地文件系统API - File System API
- VS2010调试多进程--医疗His调试中使用
- WM_CLOSE、WM_DESTROY、WM_QUIT的区别（询问，销毁窗口，退出进程，都不是一回事）
- 2015.9.11模拟赛 codevs 4159【hzwer的迷の数列】
- ural1471 Distance in the Tree
- 提升R代码运算效率的11个实用方法——并行、效率
- nginx 详解反向代理负载均衡
- PDF怎样添加注释，PDF文件添加注释的方法
- [问题解决]eclipse.ini 文件配置jdk版本
- java线程中的notifyAll唤醒操作
- 关于canvas补充说明
- 如何获取java运行时动态生成的class文件？
- JavaScricp（总回顾）
- Intel P4 CPU
- python字典的排序，按key排序和按value排序---sorted()
- 拍照一分钟，修图两小时，PS大神是这样修片的！
- Informatica增量抽取时间的设置