[LibreOJ 2538][PKUWC2018]Slay the Spire
给定一个\(2n\)张卡的卡组，其中有\(n\)张强化卡（其权值为一大于\(1\)的整数），\(n\)张攻击卡（其权值为一正整数）。在一次游戏中，你需要有序的打出一些卡牌，如果说你打了一张权值为\(x\)的攻击卡，那么对对方造成\(x\)点伤害；如果说你打出了一张权值为\(x\)的强化卡，那么之后所有伤害乘上\(x\)。
现在，你需要随机从卡组中抽出\(m\)张牌，然后选出其中的\(k\)张照一定顺序打出，要求使得产生的伤害最大化。求伤害的期望，答案乘\(\binom{2n}{m}\)再膜\(998244353\)输出。
\(1\leq k\leq m\leq 2n\leq 3000, 1\leq x\leq 10^8\)（其中\(x\)为牌的权值）。
多组数据，满足\(\sum 2n\leq 30000\)。
[LibreOJ 2316][NOIP2017]逛公园
给你一张\(n\)个点\(m\)条边的有向图，设从\(1\)到\(n\)的最短路为\(d\)，那么请问有多少\(1\)到\(n\)的路径（可以是非简单路径）满足其长度在\([d, d + K]\)中，如果答案为无限大的话输出\(-1\)。
\(1\leq n\leq 10^5, 1\leq m\leq 2\times 10^5, 0\leq K\leq 50\)。
[UOJ 110][APIO2015]Bali Sculptures
第一次做subtask题= =其实这题也没啥难度吧
其实就是两个subtask……
对于第一个subtask，就是满足\(1\leq n\leq 100\)且\(1\leq a\leq b\leq n\)。我们应该优先满足高位为\(0\)，于是乎可以贪心，从高位枚举到低位，看是否能在满足之前几位的限制条件的同时满足这一位答案为\(0\)。这个判定过程的话，可以设计状态\(d[i][k]\)表示前\(i\)位割成\(k\)段是否满足约束条件，枚举断点\(O(n)\)转移。
第二个subtask，虽然有\(n\leq 2000\)但是满足\(a = 1\)。这意味着分段数想怎么小就怎么小，所以我们可以直接去求这个序列要满足限制条件的话最少可以割成几段，这样的话第二维就可以省掉了。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
typedef long long ll;
const int maxn = 2005;
ll Y[maxn], S[maxn];
int n, a, b;
const int maxb = 41;
ll st = 0;
namespace Task1 {
bool d[105][105];
bool dp(int bi) {
memset(d, 0, sizeof(d));
d[0][0] = true;
for(int i = 1; i <= n; i ++) {
for(int k = 1; k <= b; k ++) {
for(int j = 0; j < i; j ++) {
ll sum = S[i] - S[j];
if((sum & (st | (1LL << bi))) == 0LL) {
d[i][k] = (d[i][k] || d[j][k - 1]);
}
}
}
}
for(int k = a; k <= b; k ++) {
if(d[n][k]) return true;
}
return false;
}
};
namespace Task2 {
int d[maxn];
bool dp(int bi) {
d[0] = 0;
for(int i = 1; i <= n; i ++) {
d[i] = 0x3f3f3f3f;
for(int j = 0; j < i; j ++) {
ll sum = S[i] - S[j];
if(!(sum & (st | (1LL << bi)))) {
d[i] = std::min(d[i], d[j] + 1);
}
}
}
return (d[n] <= b);
}
};
ll solve() {
ll ans = 0;
for(int i = maxb; i >= 0; i --) {
bool flag = n <= 100 ? Task1::dp(i) : Task2::dp(i);
if(flag) {
st |= (1LL << i);
} else {
ans |= (1LL << i);
}
}
return ans;
}
int main() {
scanf("%d%d%d", &n, &a, &b);
for(int i = 1; i <= n; i ++) {
scanf("%lld", &Y[i]);
S[i] = S[i - 1] + Y[i];
}
printf("%lld\n", solve());
return 0;
}
[BZOJ 1009][HNOI2008]GT考试
好劲啊这题……
首先先想DP的做法，我们用[tex]p[i][j][/tex]表示若字符串已匹配前缀[tex][1,i][/tex]，有多少种方案使得追加上一个数后匹配[tex][1,j][/tex]，这个用KMP可以很方便的求出（事实上暴力也可以）。
然后再来看DP的做法，转移方程大致是这样的：
[tex]d[i][j]=\Sigma_{k=0}^{m-1}(d[i-1][k]\times p[k][j])[/tex]
但是n非常大，这么做注定要TLE。
不过看这个转移方程，是不是和矩阵乘法的定义很像？是的。
我们可以用一个[tex]1\times m[/tex]的矩阵[tex]D[/tex]来表示某一个阶段的DP值，我们可以把[tex]p[/tex]组织成一个[tex]m\times m[/tex]矩阵[tex]P[/tex]。然后我们可以发现：
[tex]D_i\times P=D_{i+1}[/tex]
由于矩阵乘法满足结合律，所以：
[tex]D_n=D_0\times P^n[/tex]
很明显可以快速幂搞出来。
代码：
/**************************************************************
Problem: 1009
User: danihao123
Language: C++
Result: Accepted
Time:80 ms
Memory:820 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef ull Matrix[22][22];
ull MOD;
#define REP(i,n) for(i=0;i<(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
#define CP_ARR(from,to) memcpy(to,from,sizeof(from))
inline void MatrixMul(Matrix A,Matrix B,int m,int n,int p,Matrix& res){
register int i,j,k;
Matrix C;
CL_ARR(C,0);
REP(i,m){
REP(j,p){
REP(k,n){
C[i][j]=(C[i][j]+(A[i][k]*B[k][j])%MOD)%MOD;
}
}
}
CP_ARR(C,res);
}
void MatrixPow(Matrix A,int m,ull p,Matrix& res){
Matrix a,temp;
register int i;
CL_ARR(a,0);
memcpy(a,A,sizeof(a));
CL_ARR(temp,0);
REP(i,m){
temp[i][i]=1;
}
while(p){
if(1&p){
MatrixMul(temp,a,m,m,m,temp);
}
p>>=1;
MatrixMul(a,a,m,m,m,a);
}
CP_ARR(temp,res);
}
char buf[25];
int f[25];
int main(){
register int i,u,j;
register ull ret=0;
ull n;
int m;
Matrix ans,P;
scanf("%llu%d%llu",&n,&m,&MOD);
scanf("%s",buf+1);
CL_ARR(ans,0);
ans[0][0]=1;
CL_ARR(P,0);
P[0][0]=9;P[0][1]=1;
// f[0]=f[1]=0;
for(i=1;i<m;i++){
u=f[i];
while(u && buf[u+1]!=buf[i+1]){
u=f[u];
}
if(buf[u+1]==buf[i+1]){
f[i+1]=u+1;
}else{
f[i+1]=0;
}
for(j=0;j<10;j++){
u=i;
while(u && buf[u+1]!=j+'0'){
u=f[u];
}
if(buf[u+1]==j+'0'){
P[i][u+1]=(P[i][u+1]+1)%MOD;
}else{
P[i][0]=(P[i][0]+1)%MOD;
}
}
}
MatrixPow(P,m,n,P);
MatrixMul(ans,P,1,m,m,ans);
for(i=0;i<m;i++){
ret=(ret+ans[0][i])%MOD;
}
printf("%llu\n",ret);
return 0;
}
[CodeVS 3729]飞扬的小鸟
论如何把一个完全背包出的高大上……
这个题啊……细节特别多……
首先，不建议开滚动数组，细节处理就会疯。
然后呢……真的不太好说了……还是看代码吧（尽管代码还是有明显的滚动数组痕迹）。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10005,maxm=1005;
const int INF=0x7f7f7f7f;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
int GZ[maxn][2];
bool haveGZ[maxn];
int A[maxn][2];
int d[maxn][maxm];
int main(){
int n,m,k,temp;
register int i,j,v,now,pre,ans=INF,cnt;
scanf("%d%d%d",&n,&m,&k);
cnt=k;
REP(i,n){
scanf("%d%d",&A[i][0],&A[i][1]);
}
for(i=0;i<=n;i++){
GZ[i][0]=0;
GZ[i][1]=m+1;
}
REP_B(i,k){
scanf("%d",&temp);
haveGZ[temp]=true;
scanf("%d%d",&GZ[temp][0],&GZ[temp][1]);
}
memset(d,0x7f,sizeof(d));
memset(d[0],0,sizeof(d[0]));
d[0][0]=INF;
REP_B(i,n){
now=i;
pre=i-1;
d[now][0]=INF;
int& X=A[i-1][0];
int& Y=A[i-1][1];
REP_B(j,m){
if(j-X>0 && d[pre][j-X]<INF)
d[now][j]=min(d[now][j],d[pre][j-X]+1);
if(j-X>0 && d[now][j-X]<INF)
d[now][j]=min(d[now][j],d[now][j-X]+1);
if(j==m)
for(v=j-X;v<=m;v++){
if(d[pre][v]<INF)
d[now][j]=min(d[now][j],d[pre][v]+1);
if(d[now][v]<INF)
d[now][j]=min(d[now][j],d[now][v]+1);
}
}
for(j=GZ[i][0]+1;j<GZ[i][1];j++){
if(j+Y<=m && d[pre][j+Y]<INF)
d[now][j]=min(d[now][j],d[pre][j+Y]);
}
if(haveGZ[i]){
REP_B(j,GZ[i][0])
if(d[now][j]<INF){
d[now][j]=INF;
}
for(j=GZ[i][1];j<=m;j++)
if(d[now][j]<INF){
d[now][j]=INF;
}
}
}
for(i=n;i>=1;i--){
for(j=m;j>=1;j--){
ans=min(ans,d[i][j]);
}
if(ans<INF)
break;
if(haveGZ[i])
cnt--;
}
if(cnt==k){
printf("1\n%d\n",ans);
}else{
printf("0\n%d\n",cnt);
}
return 0;
}
[UVa 10635]Prince and Princess
这个名字真有童话风味哎……
直接LCS肯定会TLE。注意每个序列都是不重复序列，所以可以将A映射到[tex][1,p+1][/tex]，然后再把B映射一下（有的可能A里面没有？反正既然A里没有就和LCS没关系了），就相当于求B的LIS。LIS可以在[tex]O(nlogn)[/tex]时间内完成。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=62510;
#define CL_ARR(x,v) memset(x,v,sizeof(x))
int B[maxn];
int Hash[maxn];
int d[maxn],g[maxn];
int main(){
int T,n,p,q,x;
register int i,ans,k,Case=0;
scanf("%d",&T);
while(T--){
Case++;
scanf("%d%d%d",&n,&p,&q);
CL_ARR(Hash,0);
for(i=1;i<=(p+1);i++){
scanf("%d",&x);
Hash[x]=i;
}
for(i=1;i<=(q+1);i++){
scanf("%d",&x);
B[i]=Hash[x];
}
CL_ARR(g,0x7f);
ans=0;
for(i=1;i<=(q+1);i++){
k=lower_bound(g+1,g+2+q,B[i])-g;
d[i]=k;
g[k]=B[i];
ans=max(ans,d[i]);
}
printf("Case %d: %d\n",Case,ans);
}
return 0;
}
[LA 3942]Remember the Word
Trie第一题……
首先，容我吐槽一下UVa这个OJ，速度特别感人（同学们可以实践一下）。
这个题最容易想到的是[tex]O(n^2)[/tex]的DP——对于[tex]S[i\ldots n][/tex]，枚举其前缀查是否为单词，然后转移。但是啊……对于[tex]n\le 300000[/tex]这种方法肯定会T飞。
然后我们可以考虑使用Trie优化DP。对于每个[tex]S[i\ldots n][/tex]，在前缀树中查找之，就能找到所有可以作为其前缀的单词。由于每个单词最大长度也只是100，所以查找会很快辣~
代码：
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=300005;
const int maxW=4005,maxL=105;
const int MOD=20071027;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define DREP(i,n) for(i=(n)-1;i>=0;i--)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
int n;
vector<int> AnsList;
namespace Trie{
const int maxnode=400005;
const int sigma_siz=26;
int Tree[maxnode][sigma_siz];
int val[maxnode];
int siz;
inline int idx(char c){
return c-'a';
}
inline void InitTrie(){
siz=0;
val[0]=0;
CL_ARR(Tree[0],0);
}
void Insert(char *s,int v){
register int u=0,n=strlen(s);
register int i,c;
REP(i,n){
c=idx(s[i]);
if(!Tree[u][c]){
siz++;
Tree[u][c]=siz;
val[siz]=0;
CL_ARR(Tree[siz],0);
}
u=Tree[u][c];
}
val[u]=v;
}
void Query(char *s,int len){
register int i,c,u=0;
AnsList.clear();
REP(i,len){
if(!s[i])
break;
c=idx(s[i]);
if(!Tree[u][c])
break;
u=Tree[u][c];
if(val[u])
AnsList.push_back(val[u]);
}
}
};
char Text[maxn];
int len[maxW];
char buf[maxL];
int d[maxn];
int main(){
register int i,j,Case=0;
int m;
while(scanf("%s%d",Text,&m)==2){
Case++;
n=strlen(Text);
Trie::InitTrie();
REP_B(i,m){
scanf("%s",buf);
len[i]=strlen(buf);
Trie::Insert(buf,i);
}
d[n]=1;
DREP(i,n){
d[i]=0;
Trie::Query(Text+i,n-i);
REP(j,AnsList.size()){
d[i]=(d[i]+d[i+len[AnsList[j]]])%MOD;
}
}
printf("Case %d: %d\n",Case,d[0]);
}
return 0;
}
[CF 710E]Generate a String
很不错的题。
很容易想到大爆搜：每搜索一个点，预处理只插入的深度，然后限制之。之后再加一些其他的剪枝。不过估计会炸。
然后有同学就想：那个删除操作真特么棘手啊……因为这个就用不了DP了……哎
不过，删除的目的是什么？下一步干啥？再插入？那就有病了。肯定是要复制。所以说我们可以想出如下状态转移方程（i11r的TeX插件好像不能排版多行公式，所以分两部分写吧）：
[tex]i[/tex]为偶数时[tex]f[i]=min(f[i-1]+x,f[i/2]+y)[/tex]
[tex]i[/tex]为奇数时[tex]f[i]=min(f[i-1]+x,f[(i+1)/2]+x+y)[/tex]
然后问题就迎刃而解了。
代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e7+2;
typedef long long ll;
#define REP(i,n) for(i=1;i<=(n);i++)
ll d[maxn];
int main(){
ll n,x,y;
cin>>n>>x>>y;
register ll i;
d[0]=0;
REP(i,n+1)
d[i]=x*i;
REP(i,n){
if(1&i){
d[i]=min(d[i-1]+x,d[(i+1)/2]+x+y);
}else{
d[i]=min(d[i-1]+x,d[i>>1]+y);
}
}
cout<<d[n]<<endl;
return 0;
}
[VIJOS P1037]搭建双塔
很不错的题啊……
很容易想到构造三维的状态，但无论时间还是空间都不好。我们可以构造[tex]f[i][delta][/tex]这种状态，表示用前[tex]i[/tex]块水晶，搭建出的双塔高度差为[tex]delta[/tex]时较大塔的高度。显然答案为[tex]f[n][0][/tex]。
转移的时候，要考虑放到高塔上还是低塔上，以及是否会导致高低塔地位对调。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=101,maxV=2001;
int d[2][maxV];
int V[maxn];
int main(){
int n,maxj=0;
register int i,j,now,pre;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&V[i]);
maxj+=V[i];
}
memset(d,-1,sizeof(d));
d[0][0]=0;
for(i=1;i<=n;i++){
now=i%2;
pre=1-now;
for(j=0;j<=maxj;j++){
if(d[pre][j]>=0)
d[now][j]=d[pre][j];
if(V[i]<=j){
if(d[pre][j-V[i]]>=0){
d[now][j]=max(d[now][j],d[pre][j-V[i]]+V[i]);
}
}
if(V[i]>j && d[pre][V[i]-j]>=0){
d[now][j]=max(d[now][j],d[pre][V[i]-j]+j);
}
if(j+V[i]<=maxj && d[pre][j+V[i]]>=0)
d[now][j]=max(d[now][j],d[pre][j+V[i]]);
}
}
if(d[1&n][0]<=0)
puts("Impossible");
else
printf("%d\n",d[1&n][0]);
return 0;
}
[CodeVS 3269]混合背包
哎……现在才敢说真正会背包DP……
这个题可以分成三类问题分别处理，然后用一个一维数组一起递推。
0-1背包和完全背包都很简单。多重背包直接递推的话复杂度很高，可以考虑单调队列优化……然而窝太弱……不过还是用了
代码：
#include <cstdio>
#include <algorithm>
#include <queue>
#include <deque>
using namespace std;
const int maxn=201,maxv=200001;
struct DQueue{
deque<int> D;
queue<int> Q;
void push(int x){
Q.push(x);
while(!D.empty() && x>D.back())
D.pop_back();
D.push_back(x);
}
int top(){
return D.front();
}
void pop(){
if(D.front()==Q.front())
D.pop_front();
Q.pop();
}
int size(){
return Q.size();
}
void clear(){
while(!Q.empty())
Q.pop();
D.clear();
}
};
int d[maxv];
int v;
void pack(int V,int W,int c){
register int i,j,m;
if(c==1){
for(i=v;i>=V;i--)
d[i]=max(d[i],d[i-V]+W);
}else{
if(c==-1){
for(i=V;i<=v;i++)
d[i]=max(d[i],d[i-V]+W);
}else{
c=min(c,v/V);
for(i=0;i<V;i++){
m=(v-i)/V;
DQueue Q;
for(j=0;j<=m;j++){
if(Q.size()==c+1)
Q.pop();
Q.push(d[j*V+i]-j*W);
d[j*V+i]=Q.top()+j*W;
}
}
}
}
}
int main(){
register int i;
int n,x,y,z;
scanf("%d%d",&n,&v);
for(i=1;i<=n;i++){
scanf("%d%d%d",&x,&y,&z);
pack(x,y,z);
}
printf("%d\n",d[v]);
return 0;
}
