2023牛客寒假算法基础集训营4-无HIK_2023牛客寒假算法训练营4

A：清楚姐姐学信息论

结论是越靠近e进制效率越高（第一次知道）

当时现场推的，证明如下

即证x^y>y^x

两边同时取对数，移位得

lnx /x>lny /y

即证lnx/x的单调性

求导即可发现是在e处

对整数讨论23附近发现是3,1不参与讨论，3以后是递减。故取3

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
 
const int N=1e5+10;
 
signed main(){
    cin.tie(0),cout.tie(0);
    int x,y;
    cin>>x>>y;
    if(x>2&&y>2) cout<<min(x,y);
    else if(x==2&&y==3) cout<<3;
    else if(x==3&&y==2) cout<<3;
    else cout<<2;
    
    return 0;
}

B：清楚姐姐学构造

观察其性质，联想奇函数和偶函数（这谁想得到啊只能看以往做题经验）

任何一个函数都可以表示成一个奇函数和一个偶函数的和

不妨假设f(x)=h(x)+g(x),其中h(x)偶函数，g(x)奇函数

f(-x)=h(x)-g(x)

得

h(x)=[f(x)+f(-x)]/2

g(x)=[f(x)－f(-x)]/2

故可以表示

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define fir for(int i=1;i<=n;i++)
using namespace std;
 
const int N=1e5+10;
typedef pair<int,int>PII;
 
int a[N],b[N],c[N];
int n,m,inv2;
 
int pow2(int a,int b){
    int res=1;
    a=(a%m+m)%m;
    while(b){
        if(b&1) res=res*a%m;
        a=a*a%m;
        b>>=1;
    }
    return res;
}
 
int inv(int x){
    return pow2(x,m-2);
}
 
void solve(){
    inv2=inv(2);
    for(int i=1;i<=n;i++){
        a[i]=(c[i]+c[n-i+1])*inv2%m;
        b[i]=(c[i]+m-c[n-i+1])*inv2%m;
    }
    puts("Yes");
    for(int i=1;i<=n;i++) cout<<a[i]<<' ';
    cout<<endl;
    for(int i=1;i<=n;i++) cout<<b[i]<<' ';
    cout<<endl;
}
 
bool check(){
    for(int i=1;i<=n;i++)
        if(c[i]!=c[n-i+1]) return false;
    return true;
}
 
void solve_2(){
    if(check()){
        puts("Yes");
        for(int i=1;i<=n;i++){
            cout<<c[i]<<' ';
        }
        cout<<endl;
        for(int i=1;i<=n;i++) cout<<0<<' ';
        cout<<endl;
    }else puts("No");
}
 
signed main(){
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>c[i];
    if(m==2) solve_2();
    else solve();
    return 0;
}

其中inv(2)的作用是求2的逆元,因为两边虽然都要同除2，但是是模系，所以需要除2的逆元

那一堆操作就是2的逆元的求解。（具体操作的以后再说，先把整体掌握，同余整个知识点以后整理。）

C:清楚姐姐学01背包（简单版）

01背包过程中有状态转移，满足f[j-w[i]]+v[i]>f[j]时进行转移

那么就可以根据这个转移方程，进行转移。

先做一次01背包，然后不带第i个物品做一次01背包，根据其与原答案的差即可找到答案。

代码:第一个是错误答案，问为什么不对？

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define fir for(int i=0;i<n;i++)
using namespace std;
 
const int N=2e5+10;
typedef pair<int,int>PII;
 
int w[N],idx,v[N],f[N];
 
signed main(){
    cin.tie(0),cout.tie(0);
    
    int n,m;
    cin>>n>>m;
    fir{
        cin>>w[i]>>v[i];
        for(int j=m;j>=0;j--)
            if(j-v[i]>=0) f[j]=max(f[j],f[j-w[i]]+v[i]);
    }
    //第一趟，找到最开始的背包。
    int res=f[m];
    for(int k=0;k<n;k++){
        memset(f,0,sizeof f);
        fir{
            if(i==k) continue;
            for(int j=m;j>=0;j--)
                if(j-w[i]>=0) f[j]=max(f[j],f[j-w[i]]+v[i]);
        }
        int ans=1ll<<60;
        for(int j=m-w[k];j>=0;j--){
            ans=min(ans,max(res-(f[j]+v[k])+1,0ll));
        }
        cout<<ans<<endl;
    }
    return 0;
}

答：因为最开始的背包是所有东西都在的背包

换言之，你无法确定你当前选中的不要的物品，是否在这个背包中。

就会造成，如果单一，那么这个东西在背包中，为必选物品了，但你+1了，于是WA

如果不单一，那么这个物品可以有多种选择，代码跑一下可能结果输出是0，但是都一样的话必须+1才能选。于是WA。

反正总有一款WA适合你

当时甚至忘了模拟状态转移的时候要把m-w[k]以下的全部转移一遍，还是被打的WAWA大哭了。哎。

所以，为了避免上述过多情况的讨论，我们采用了先不要第i个物品，再在最后进行一次模拟状态转移，以求出值。

正解代码：

这里把无穷大赋值为0x3f3f3f3f还不行，后面的样例过不了，必须更大

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define fir for(int i=1;i<=n;i++)
using namespace std;
 
const int N=2e5+10;
typedef pair<int,int>PII;
 
int w[N],idx,v[N],f[N];
 
int n,m;
 
int cal(int k){
    memset(f,0,sizeof f);
    fir{
        if(i==k) continue;
        for(int j=m;j>=w[i];j--)
            f[j]=max(f[j],f[j-w[i]]+v[i]);
    }
    //此时是从剩下的物品中挑选的东西
    //而状态转移方程为如果f[j-w[i]+v[i]]更大，即价值需要转移
    //此时手动模拟
    int res=f[m];
    int ans=1ll<<60;
    for(int j=m-w[k];j>=0;j--){
        ans=min(ans,max(res-(f[j]+v[k])+1,0ll));
    }
 
    return ans;
}
 
signed main(){
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    fir cin>>w[i]>>v[i];
    for(int k=1;k<=n;k++) cout<<cal(k)<<endl;
    return 0;
}

即不需要找原本的第一趟的背包，因为没必要，以此法不是不能解，而是麻烦。

只要我们让最后的时候能够状态转移并求其中的答案，那么就是好答案

这样才是必选物品，而不是本身就有可能在其中的物品。

卡死在这个点上了。。。需要注意。

D：困难版

图论中的有向无环图的最短路模型，与动态规划有一定程度上的联系。

（

太妙了！！！茅塞顿开，拨云见日！

智商被按在地上碾压的快感，万物之间被证明联系性的快感。

就像细胞学说打破了动物学和植物学之间的壁垒一样，01背包的二维模式与图中最短路径类问题之间的联系打破了各个题之间独立的思路。

哇，太强了！！

）

（知道解法后的胡言乱语，请无视···）

我们思考一下easy版本的情况

我们发现我们必须要不带第i个物品求一次背包，强制性的求。

那么我们有没有什么办法一次性求得这个背包呢？不用来回多次求？

我们思考一下01背包问题，把他原本的样子展现出来

首先，接触01背包的时候我们大多数人都会接触到数字三角形模型。即从顶到底一个数字三角形求其权值最大，抽象一下，这也是一种“最短路”模型，换句话说应该叫最优路模型。

而动态规划实际上就是在找这一最优路。

考虑图论当中的最短路模型，假设我们有从s-t的最短路，那么必然存在s-u,u-v,v-t的最短路。

那么已知s-u,v-t的最短路，我们枚举所有的u-v的路径长度，必然能找到最短路。

因为我们必定经过某一条u-v的边。

而01背包的物品是没有顺序的，先放谁无所谓，那么我们既可以从1-n放，也可以从n-1放

假设dp1[i,j]表示前i个物品中容量为j的情况下能放的最大值

dp2[i,j]表示后i个物品中容量为j的情况下能放的最大值

那么dp1[i-1,j]+dp2[i+1,j]就是去掉第i个物品的dp数组（从第i+1个物品到最后一个物品）

那么这就抽象成了一个最短路模型，或者说一道数字金字塔

只要是这种强制选的dp方程，都可以尝试抽象成一个图，可以站在图论模型的角度上去解决问题

不局限于此处的01背包问题，这种思路和套路需要掌握。

//背包型dp可以抽象成一个图上的最优路问题 
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define fir for(int i=1;i<=n;i++)
using namespace std;
 
const int N=5e3+10;
typedef pair<int,int>PII;
 
int w[N],v[N],f1[N][N],f2[N][N];
 
int n,m;
 
int cal(int k){
    int limit=0;
    for(int i=0;i<=m;i++) limit=max(limit,f1[k-1][i]+f2[k][i]);
    //从容量为0开始向右方向转移状态，求前k-1个物品和后k个物品的f值
    int ans=1ll<<60;
    for(int i=0;i<=m-w[k];i++){
        int pick=f1[k-1][i]+f2[k][i+w[k]]+v[k];
        //直接加的原因是第k个物品不选，相当于状态直接转移了 
        //然后加上的目的是为了后面作差
        //我大雾了，之前一直想不明白 
        ans=min(ans,max(limit-pick+1,0ll));
    }
    return ans;
}
 
signed main(){
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    fir cin>>w[i]>>v[i];
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            //按照图论思想，此处状态可以直接向下转移，也可以转移到加上这个物品之后的下一个地方 
            f1[i+1][j]=max(f1[i+1][j],f1[i][j]);
            if(j+w[i+1]<=m) f1[i+1][j+w[i+1]]=max(f1[i+1][j+w[i+1]],f1[i][j]+v[i+1]);
        }
    }
    for(int i=n;i;--i){
        for(int j=0;j<=m;j++){
            f2[i-1][j]=max(f2[i-1][j],f2[i][j]);
            if(j-w[i]>=0) f2[i-1][j-w[i]]=max(f2[i-1][j-w[i]],f2[i][j]+v[i]);
        }
    }
    for(int id=1;id<=n;id++) cout<<cal(id)<<endl;
    return 0;
}

乱用define害死人，虽然确实能提速，但是······

找bug真的痛苦呜呜呜，找了快一个多小时的bug

E：清楚姐姐打怪升级

一道纯模拟题，题目读题的时候有坑。一是怪物每秒回血，这是每个时刻初的意思，二是注意先打一刀然后才进入判定，会好判断不少，三是攻击时刻从1开始。

不好判断的话，自己试着对一个怪进行攻击，然后脑内模拟什么时候会死，推导一下需要攻击的方程式即可

“如果打一只怪物和N只怪物是没有区别或者关系的，那么就不要先考虑N只怪，先考虑如何打一个怪，重复N次即可”

把问题细分就行了

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define x first
#define y second
using namespace std;
 
const int N=1e5+10;
typedef pair<int,int>PII;
 
PII h[N];
 
signed main(){
    cin.tie(0),cout.tie(0);
    int n,t,a;
    cin>>n>>t>>a;
    for(int i=0;i<n;i++) cin>>h[i].x>>h[i].y;
    sort(h,h+n);
    int cnt=0;
    bool success=true;
    for(int i=0;i<n;i++){
        if(h[i].x<=a) cnt++;
        else{
            if(a<=t*h[i].y){
                success=false;
                break;
            }else{
                cnt+=(h[i].x-a)/(a-t*h[i].y);
                if((h[i].x-a)%(a-t*h[i].y)) cnt++;
                cnt++;
            }
        }
    }
    if(!success) puts("-1");
    else cout<<(cnt-1)*t+1;
    return 0;
}

他们说可以二分，但我感觉这纯模拟题不需要二分吧，有公式直接O（1）解决了攻击次数。

然后新学到的东西：a/b向上取整

等于(a+b-1)/b,因为一旦a/b有余数，就能和b-1结合。如果没有余数，自动向下取整不影响答案

F:清楚姐姐学树状数组

区区树状数组（鼻青脸肿.jpg）

官方题解写的非常详细了，详细到我都不觉得需要额外补充一些什么了

无论是推导左右子树还是别的什么的，都很详细了

当时完全只靠印象，知道+lowbit找父节点。。。看来还是得好好复习一下树状数组。

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define fir for(int i=1;i<=n;i++)
using namespace std;
 
 
const int N=2e3+10;
typedef pair<int,int>PII;
 
//由于数据范围过大，不可能真的建立一棵树，故手动推导，用数学说话
int k,q,n,x;
 
int lowbit(int x){
    return x&(-x);
}
 
int size(int x){
    return (lowbit(x)<<1)-1;
}
 
bool is_left_child(int x){
    return !(x&(lowbit(x)<<1));
}
 
int fa(int x){
    return is_left_child(x)?x+lowbit(x):x-lowbit(x);
}
 
int lch(int x){
    return x^lowbit(x)^(lowbit(x)>>1);
}
 
int rch(int x){
    return x^(lowbit(x)>>1); 
}
 
int VLR(int x){
    int root=n;
    int ret=1;
    while(root!=x){
        ++ret;
        if(x<root) root=lch(root);
        else ret+=size(lch(root)),root=rch(root);
    }
    return ret;
}
 
int LRD(int x){
    if(x==n) return n;
    int root=x;
    int ret=size(root);
    while(root!=n){
        if(root==rch(fa(root))) ret+=size(lch(fa(root)));
        root=fa(root);
    }
    return ret;
}
 
signed main(){
    cin.tie(0),cout.tie(0);
    cin>>k>>q;
    n=1ll<<k;
    while(q--){
        cin>>x;
        cout<<VLR(x)<<' '<<x<<' '<<LRD(x)<<endl;
    }
    //中序遍历，输入即输出序列 
    
    return 0;
    
}

基本就是照搬人家的代码了，因为人家写的很好了

放个链接方便过去找

https://ac.nowcoder.com/discuss/1114959?type=101&order=0&pos=3&page=0&channel=-1&source_id=1

一切不清楚为啥的，这个题多看几遍题解手动推一推应该就能理解了

写的很太详细了，尤其是左右孩子的反推那一块，秀到我头皮发麻

G：清楚姐姐逛街

直接bfs，毕竟最早碰到

#include<bits/stdc++.h>
#define endl '\n'
//#define int long long
#define fir for(int i=1;i<=n;i++)
using namespace std;
 
const int N=1e3+10;
typedef pair<int,int>PII;
string g[N];
int vis[N][N];
int n,m,x,y,question;
 
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};
 
void bfs(){
    queue<PII>q;
    q.push({x,y});
    memset(vis,-1,sizeof vis);
    vis[x][y]=0;
    while(q.size()){
        PII t=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int u=t.first+dx[i],v=t.second+dy[i];
            if(u<0||u>=n||v<0||v>=m) continue;
            if(vis[u][v]!=-1||(u==x&&v==y)) continue; 
            if(g[u][v]!='#') vis[u][v]=vis[t.first][t.second]+1,q.push({u,v});
        }
    }
    return ;
}
 
//终点会按照固定方式移动的迷宫搜索问题 
signed main(){
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>x>>y>>question;
    for(int i=0;i<n;i++) cin>>g[i];
    bfs();
    map<char,int>mp;
    mp['U']=0,mp['R']=1,mp['D']=2,mp['L']=3,mp['#']=-1;
    for(int i=0;i<question;i++){
        int tx,ty;
        cin>>tx>>ty;
        //看来是判断写错了 
        int f1=0,res=1;
        while(1){
            int u=tx,v=ty;
            if(g[tx][ty]=='U'&&g[tx-1][ty]!='#') tx--;
            else if (g[tx][ty]=='D' && g[tx+1][ty]!='#') tx++;
            else if (g[tx][ty]=='R' && g[tx][ty+1]!='#') ty++;
            else if (g[tx][ty]=='L' && g[tx][ty-1]!='#') ty--;
            
            if(tx==u&&ty==v){
                if(vis[tx][ty]==-1||vis[tx][ty]==0){
                f1=-1;
                break;
                }
            }
            if(vis[tx][ty]<=res){
                f1=max(res,vis[tx][ty]);
                break;
            }
            res++;
        }
        cout<<f1<<endl;
    }
        
    return 0;
}

终点不断变化的迷宫问题，只需要bfs一遍，然后判断即可

这里之前出了一个小插曲

我用map<char,int>mp开一个0-3的四个方向，然后对应dx[4],dy[4]数组

每次用mp[g[tx][ty]]取得当前值，就可以直接对应dx[i],dy[i]的i了

但是这样不行，会WA

想一想这是为什么？

···

···

···

答案其实很简单，因为当g[x][y]是'#’时，map并没有相关的东西

而你又强制要求有一个，那么便会自动开辟一个mp['#']=0

那么自然而然就错了

这个bug让我de了大半天，最后突然想起来map的注意事项

以及，有一个小问题是我初始值memset为-1的时候，会有1个样例无法通过，但是我没找到bug在哪里，所以就放在那儿了。这个代码是对的，另一个就不放了，不清楚问题出在哪里了，但思路是一样的。

J:清楚姐姐学排序

从快排中得到启示（实际也不需要）

只要我们能确定他前后的个数，那么就能确定这个数字的位置

换言之，假设他有a个前面的数，b个后面的数，满足a+b==n-1即可

就像快排找位置一样。

所以暴力搜即可

#include<bits/stdc++.h>
#define endl '\n'
//#define int long long
#define fir for(int i=1;i<=n;i++)
using namespace std;
 
const int N=1e3+10;
typedef pair<int,int>PII;
int n,m,ans[N]; 
vector<int> L[N],G[N];
bool vis[N];
 
void dfs(int x,vector<int> G[],int &cnt, bool flag=true){
    if(vis[x]) return;
    if(flag){
        cnt++;
        vis[x]=true;
    }
    for(auto i:G[x]) dfs(i,G,cnt);
}
 
int calc_kth(int x){
    memset(vis,0,sizeof vis);
    int cntl=0,cntg=0;
    dfs(x,L,cntl,false);
    dfs(x,G,cntg,false);
    return cntl+cntg+1==n?cntl+1:0;
}
 
signed main(){
    cin.tie(0),cout.tie(0);
    //从快排当中得到启示，如果能确定b个在前a个在后，那么a+b=n-1时
    //即已经和所有元素得到比较，那么他的位置就能确定。
    //很妙
    //暴力搜即可
    
    //涉及到01矩阵的或操作都可以用bitset优化
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        L[i].clear();
        G[i].clear();
        memset(ans,-1,sizeof ans);
    }
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        L[v].push_back(u);
    }
    for(int i=1;i<=n;i++) ans[calc_kth(i)]=i;
    
    for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
    cout<<endl;
    return 0;
}

有点思路但没想到暴力搜，还没想到dfs能写的这么简单，我以为要写一科很大的树然后各种遍历来着。

L：清楚姐姐的三角形I

简单到不能再简单的签到题，只需要注意三者和必为偶数就能过

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
 
const int N=1e5+10;
 
signed main(){
    cin.tie(0),cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        int va,vb,vc;
        cin>>va>>vb>>vc;
        int all=va+vb+vc>>1,sum=va+vb+vc;
        if(sum&1) puts("No");
        else if(all<2*va&&all<2*vb&&all<2*vc){
            puts("Yes");
            cout<<all-va<<' '<<all-vb<<' '<<all-vc<<endl;
        }else puts("No");
    }
    
    return 0;
}

M：清楚姐姐的三角形II

诈骗题！！！！

快气死了当时，国家反诈骗中心app你怎么不警告我啊

样例给了斐波那契数列，那很自然的想，诶那不就斐波那契完美符合么

但是忘了数据范围限制，1e5后斐波那契数已经超了范围了

我还专门开了long long······

我是小丑哈哈哈哈

那最后只需要凑112一类的无限循环即可。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
 
const int N=1e5+10;
 
signed main(){
    cin.tie(0),cout.tie(0);
    int f1=1,f2=1,f3=2,temp=0;
    int n;
    cin>>n;
    if(n==1) cout<<f1;
    else if(n==2) cout<<f1<<' '<<f2;
    else{
        for(int i=0;i<n;i++){
            cout<<f1<<' ';
            temp=f1,f1=f2,f2=f3,f3=temp;
        }
    }
    
    return 0;
}

HIK：等我cf上上分再看！毕竟现在还没那个实力，基础先稳定再说。