做题记录

123456Mm · 2020-12-20 20:51:19 · 个人记录

中山市选 树

一道树型DP题，类似树型背包的套路

定义 dp_{i,0/1,0/1} 为以 i 为根的子树,按不按，合并完当前子树时候其亮暗情况，注意考虑完整个子树（除了根节点）应该全亮。

首先初始化（没有合并子树的情况）

分类讨论

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+10;
int n,k;
long long m;
long long A[MAXN];
long long P[40];
long long B[MAXN];
long long pre[40];
bool check(long long id){
    for(int i=1;i<=n;i++){
        B[i]=id;
        pre[0]=0;
        for(int j=0;j<=32;j++){
            pre[j+1]=pre[j];
            if((id&P[j])==0)pre[j+1]+=P[j];
        }
        for(int j=32;j>=0;j--){
            if((B[i]&P[j])!=0){
                continue;
            }
            if(B[i]+pre[j]<A[i]){
                B[i]+=P[j];
            }
        }
        B[i]-=A[i];
    }
    sort(B+1,B+n+1);
    long long sum=0;
    for(int i=1;i<=k;i++){
        sum+=B[i];
        if(sum>m)return false;
    }
    return true;
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)cin>>A[i];
    P[0]=1;
    for(int i=1;i<=32;i++)P[i]=P[i-1]*2;
    long long Ans=0;
    for(int i=32;i>=0;i--){
        if(check(Ans+P[i])){
            Ans+=P[i];
        }
    }
    cout<<Ans<<endl; 
}

https://atcoder.jp/contests/dp/tasks/dp_z

Frog3

斜率模板题，但码了半天

出现的bug：忘记将 i 加进单调队列

出队时符号反（应该是不符合要求的出队，如果符合要求了就不出队break)

羊羊列队

一道斜率优化DP题

需要注意的几点

1.dp要赋初值

2.斜率优化之前要注意去重

3.凸包方向不能建反

4.对于每一个j建一个凸包，转移的时候注意j还是j-1

5.注意队头队尾不能写反

6.注意循环顺序（后效性）

#include<bits/stdc++.h>
using namespace std;
const long long INF=1e18;
int n,m;
long long a[10010];
long long b[10010];
long long dp[10010][1010];
deque<long long> dq[1010]; 
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    int cnt=1;
    b[1]=a[1];
    for(int i=2;i<=n;i++){
        if(a[i]!=a[i-1]){
            b[++cnt]=a[i];
        }
    }
    for(int i=0;i<=cnt;i++){
        for(int j=0;j<=m;j++)dp[i][j]=INF;
    }
    dp[0][0]=0;
    dq[0].push_back(0);
    for(int i=1;i<=cnt;i++){
        for(int j=m;j>=1;j--){
            while(dq[j-1].size()>=2){
                int fr=dq[j-1].front();
                dq[j-1].pop_front();
                int fr2=dq[j-1].front();
                //if(j==2)cout<<fr<<" "<<fr2<<endl;
                if(b[i]*(-2*b[fr2+1]+2*b[fr+1])<dp[fr][j-1]+b[fr+1]*b[fr+1]-dp[fr2][j-1]-b[fr2+1]*b[fr2+1]){
                    continue;
                }
                else {
                    dq[j-1].push_front(fr);
                    break;
                }
            }
            if(!dq[j-1].empty()){
                int tp=dq[j-1].front();
                //cout<<i<<" "<<j<<" "<<tp<<endl;
                dp[i][j]=b[i]*(-2*b[tp+1])+b[tp+1]*b[tp+1]+b[i]*b[i]+dp[tp][j-1];
                //y=dp[k][j-1]+b[k+1]^2   k=b[i] x=-2*b[k+1]
            }
            while(dq[j].size()>=2){
                int bk=dq[j].back();
                dq[j].pop_back();
                int bk2=dq[j].back();
                if((dp[i][j]+b[i+1]*b[i+1]-dp[bk][j]-b[bk+1]*b[bk+1])*(-2*b[bk+1]+2*b[bk2+1])>(dp[bk][j]+b[bk+1]*b[bk+1]-dp[bk2][j]-b[bk2+1]*b[bk2+1])*(-2*b[i+1]+2*b[bk+1])){
                    continue;
                }
                else {
                    dq[j].push_back(bk);
                    break; 
                }
            }
            dq[j].push_back(i);
            /*for(int k=i-1;k>=0;k--){
                dp[i][j]=min(dp[i][j],dp[k][j-1]+b[k+1]*b[k+1]-2*b[i]*b[k+1]+b[i]*b[i]);
                //y=dp[k][j-1]+b[k+1]^2   K=b[i] x=-2*b[k+1]
            }*/
        }
    }
    /*for(int i=0;i<=cnt;i++){
        for(int j=0;j<=m;j++){
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }*/
    cout<<dp[cnt][m]<<endl;
}

CF111D Petya 染色

特判 m=1

考虑转化 中间的 m-2 列的颜色数量必然是第一列和第 m列共用的颜色数量

用dp或容斥求出恰好用 i 种颜色涂满 n 个格子的方案数（不需要考虑这 i 种颜色是怎样选取的）

枚举共用颜色数量 x ，非共用颜色数量 y

共用颜色选择方案数 C(k,x)

对于第一列 方案数为 C(k-x,y)\times dp_{x+y}

对于第 m 列 方案数为 C(k-x-y,y)\times dp_{x+y} (最后一列的 y 种颜色不能和第一列相同)

中间 m-2 列方案数为 x^{(m-2)\times n}

枚举 x,y ,每次用乘法原理累乘即可

P4381岛屿

一道好题。

考虑每个点向外连一条边，一个连通块内必然有且只有一个环，即形成一个基环树森林。

采用拓扑排序把基环树森林缩成若干个环，在拓扑排序的过程中DP记录每个节点为根节点获得的最大价值（dp值）。此过程类似树型DP。不难发现，每个环对答案的贡献是独立的。

分类讨论：

进行常数分离

枚举 r 即可得出 sum_r+val_r ,只要维护r-sz+1 到 r 区间内 val_l-sum_l 最大值即可

使用单调队列可以简单解决问题

最后对于每个联通块相加即可

10.17

ABC223D

一道拓扑排序的魔改题。

很容易想到建图

首先如果原图有环，必然为 -1

跑出来的拓扑序必然是符合题意的，只是我们需要使字典序最小。

我们可以把原先的 queue 换成 priority\ queue ,这样就可以从小到大选择，就可使字典序最小。

10.3学校比赛补题

P1314

一道挺妙的二分

我们通过不知道什么方法可以知道

对于构造，如果序列长度为奇数，则必然有 a_{l_i-1}=a_{r_i+1} ,则最后对于 l_i\leq j \leq r_i , a_j=a_{l_i-1} 或 a_{r_i-1}

如果是偶数，则前半部分等于 a_{l_i-1} ,后半部分等于 a_{r_i-1}

9.3

CF1057C

一道 dp 。

考虑实际上他走的路径构成一个DAG（因为他只能从小的节点往大的节点走，大小关系又是确定的），必然可以 dp

设计状态：令 dp_{i,j} 表示到节点 i 获得值为 j 的最小路程。

考虑从小到大处理，一个较大的节点必然可以从一个较小的异色节点转移，且代价为 |x_i-x_j| ,暴力转移即可，时间复杂度 O(n^2k)

#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
struct Node{
    int id;
    int val;
}A[60];
int n,s,k;
string T;
bool cmp(Node a,Node b){
    return a.val<b.val;
}
int dp[60][2060];
int main(){
    cin>>n>>s>>k;
    for(int i=1;i<=n;i++){
        A[i].id=i;
        cin>>A[i].val;
    }
    cin>>T;
    sort(A+1,A+n+1,cmp);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k+50;j++)dp[i][j]=INF;
    }
    for(int i=1;i<=n;i++){
        int x=A[i].id;
        int v=A[i].val;
        for(int j=0;j<=v;j++)dp[x][j]=abs(x-s);
        for(int j=1;j<i;j++){
            int y=A[j].id;
            if(T[x-1]!=T[y-1]&&v>A[j].val){
                for(int r=v;r<=k+50;r++){
                    dp[x][r]=min(dp[x][r],dp[y][r-v]+abs(y-x));
                }
            }
        }
    }
    int Ans=INF;
    for(int i=1;i<=n;i++){
        for(int j=k;j<=k+50;j++)Ans=min(Ans,dp[i][j]);
    }
    if(Ans==INF)cout<<-1<<endl;
    else cout<<Ans<<endl;
}

9.2

CF486D

考虑没有 d 的限制的情况，我们可以令 dp_i 为这个子树中的最大值，然后用 f_i=\prod\ (f_j+1)，其中 j 为 i 的儿子。

有 d 的限制的情况，对于每个点作为根做 n 次 dp , 注意我们钦定根节点是权值最大的节点（若有多个相同的则应该是编号最大的），这样才能做到不漏

#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
const int MAXN=2010;
int n,d;
long long a[MAXN];
vector<int> Adj[MAXN];
long long Ans=0;
long long dp[MAXN];
bool vis[MAXN];
int st;
void dfs(int u){
    //cout<<u<<endl;
    for(int i=0;i<Adj[u].size();i++){
        int x=Adj[u][i];
        //cout<<"YEAH"<<endl;
        if(vis[x])continue;
        //cout<<"YEAH"<<endl;
        if(a[x]>a[st])continue;
        //cout<<x<<" "<<st<<endl;
        //cout<<a[x]<<" "<<a[st]<<endl;
        //cout<<"YEAH"<<endl;
        if(a[x]==a[st]&&x>st)continue;
        //cout<<"YEAH"<<endl;
        if(a[st]-a[x]>d)continue;
        vis[x]=true;
        dfs(x);
        dp[u]*=(dp[x]+1);
        dp[u]%=mod;
        vis[x]=false;
    }
}
int main(){
    cin>>d>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int u,v;
    for(int i=1;i<n;i++){
        cin>>u>>v;
        Adj[u].push_back(v);
        Adj[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        for(int j=1;j<=n;j++)dp[j]=1;
        vis[i]=true;
        st=i;
        dfs(i);
        //cout<<dp[st]<<endl;
        //cout<<endl;
        Ans+=dp[st];
        Ans%=mod;
    }
    cout<<Ans<<endl;
}

8.30

难度适中的一道题

算法一

8.13

网络流，最小割变形 题目

拆点的trick

把一个点拆成入点和出点，分别记为 i 号点和 i+n 号 点

连边时连(i->n+i,1),(n+i->i,0),(u+n->v,INF),(v+n->u,INF),(v->u+n,0),(u->v+n,0)

直接跑最小割（最大流）板子即可

注意起点会变成s+n

8.9

CF603A 考虑一个trick,即LIS 可设计出状态，f_{i,0} 表示该位不反转，前面也无反转的最长长度，f_{i,1} 表示该位不反转，但前面有反转的的最长长度，f_{i,2}表示该位反转的情况。分类讨论s_i 和 s_{i-1} 是否相同转移即可。注意边界。 可知dp之难点者，在于状态之设计也。代码非常简洁美观，如下

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100010;
int n;
string s;
long long dp[MAXN][4];
long long ans=1; 
int main(){
    cin>>n;
    cin>>s;
    dp[0][0]=dp[0][1]=dp[0][2]=1;
    for(int i=1;i<n;i++){
        if(s[i]==s[i-1]){
            dp[i][0]=dp[i-1][0];
            dp[i][1]=max(dp[i-1][1],dp[i-1][2]+1);
            dp[i][2]=max(dp[i-1][0]+1,dp[i-1][2]);
        }
        else {
            dp[i][0]=dp[i-1][0]+1;
            dp[i][1]=max(dp[i-1][1]+1,dp[i-1][2]);
            dp[i][2]=max(dp[i-1][0],dp[i-1][2]+1);
        }
        ans=max(max(max(dp[i][0],dp[i][1]),dp[i][2]),ans);
    }
    cout<<ans<<endl;
} 

8.6

CF621C

基础的概率期望题，但我还是看了一眼题解，挂了两发

坑点： 1 拿钱的时候是两个人一起获得，而非单方面获得

2.注意实数运算（样例水）

ABC212 D

赛场上clf神仙用线段树写出来了，\% \% \% ,而我写自闭了

这里是正解

参考了官方解法

我们先定义数组a,其中当opt_i=2时 a_i=x_i ,否则a_i=0

考虑前缀和的思想，定义s_i=\sum a_i,每次各数即为

显然s_k 为定值，因而我们只要在每次opt_i=1操作时找到最小的(x_i-s_i),考虑使用priority queue 进行维护，注意开long long

代码

#include<bits/stdc++.h>
using namespace std;
priority_queue<long long> q;
int n;
long long sum=0;
int main(){
    cin>>n;
    int opt;
    long long x;
    for(int i=1;i<=n;i++){
        cin>>opt;
        if(opt==1){
            cin>>x;
            q.push(sum-x);
        }
        if(opt==2){
            cin>>x;
            sum+=x;
        }
        if(opt==3){
            long long tp=q.top();
            q.pop();
            long long temp=sum-tp;
            cout<<temp<<endl;
        }
    }
}

7.31

差分约束，注意边的方向，还有没有确定源点时的处理

7.30

欧拉定理:对于任意a\perp n ,a^{\varphi(n)}\equiv 1(mod\ n)

扩展欧拉定理：当 b\geq \varphi(n)时 ,a^b \equiv a^{b\%\varphi(n)+\varphi(n)}(mod\ n)

需要注意的是，当 b\leq \varphi(n)时原式不一定成立

7.7

P6218

问题很多

1 1<<n 会爆 long \ long

2

dp[i][0][0]=1;
//dp[i][1][1]=1;
//dp[i][1][i]=1;
//dp[i][0][i-1]=1;

dp 转移的时候注意重复转移和后效性

3 细节问题

for(int k=0;k+num<=cnt/2;k++){//是cnt而不是i 
    ans+=dp[i][0][k];//dp[i][0][k]而不是dp[i][0][k+num] 
}

7.5

P2602 数字计数

ans+=num*Power[i-1];//注意不是ans+=num 

7.3

P3379 LCA板子

1.递推（DP）时注意后效性

2.特判结点0

5.29

P5231

第一道紫题

AC自动机板子，注意在 find 函数中打标记，用-1不用0

3.6

P2979 看了题解

注意：完全背包（顺序）+分类讨论+贪心

2.28

P1725 自己做出

线段树优化DP O(nlogn)

单调队列优化DP O(n)?

12.26

CF7B 自己做出

P3865参考了书

P6278模拟赛补题

算法：树状数组（类似桶） 差分

CF27C

算法：前缀后缀最大值

注意：转移

P4873 补题

线段树优化dp

P3112 补题

状压dp

注意：不要使用某些贪心，虽然好写，但会丢分

P4302

区间dp

P3205

同上

注意转移方程设计

12.25

CF3B debug时参考了题解

注意：1.边界（防止越界） 2.特判

12.20

P4170 自己做出

CF2B 思路看了题解 注意：1.边界

2.矩阵中有0时要特判