CCF PTA 编程培训师资认证第五次(c++)

2301_80662593

444人浏览 · 2025-10-28 00:53:39

2301_80662593 · 2025-10-28 00:53:39 发布

第一题

题目大意：

现在第一天发射一颗卫星，第二天，第三天发射两颗卫星，…，依次类推，求解前k天一共发射了多少卫星

思路：

模拟

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
//#define x first
//#define y second
//const int mod=1e9+7;
//const int N=2e5+10;
//int fac[N],invfac[N];  
//int qmi(int a,int b,int p){int res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;}
//int inv(int x){return qmi(x,p-2);}
//int C(int n,int m){if(n<0||m<0||n<m)return 0;return fac[n]*invfac[n-m]%p*invfac[m]%p;}
//void init(){fac[0]=1;for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%p;invfac[N-1]=inv(fac[N-1]);for(int i=N-2;i>=0;i--)invfac[i]=invfac[i+1]*(i+1)%p;}
//struct node{int v,w;bool operator < (const node &x)const{return w==x.w ? v>x.v : w>x.w;}};
//void dijkstra(const vector<vector<node>>&g,vector<int>&dist,vector<bool>&vis,int x){fill(dist.begin(),dist.end(),LLONG_MAX);fill(vis.begin(),vis.end(),false);
//dist[x]=0;priority_queue<node>q;q.push({x,0});while(q.size()){auto u=q.top().v;q.pop();if(vis[u])continue;vis[u]=true;for(auto [v,w]:g[u]){if(dist[v]>dist[u]+w){
//dist[v]=dist[u]+w;q.push({v,dist[v]});}}}}
//struct BIT{int n;vector<int>t;BIT(int _n=0){init(_n);}void init(int _n){n=_n;t.assign(n+2,0);}
//void add(int x,int v){for(;x<=n;x+=(x & -x))t[x]+=v;}int query(int x){int res=0;for(;x;x-=(x & -x))res+=t[x];return res;}};
//int calc_add(const vector<vector<int>>&s,int x1,int y1,int x2,int y2){return s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];}
//void calc_diff(vector<vector<int>>&d,int x1,int y1,int x2,int y2,int c){d[x1][y1]+=c;d[x2+1][y1]-=c;d[x1][y2+1]-=c;d[x2+1][y2+1]+=c;}
//int primes[N],cnt=0;bool st[N];
//void init1(){for(int i=2;i<N;i++){if(!st[i])primes[++cnt]=i;for(int j=1;primes[j]*i<N;j++){st[primes[j]*i]=true;if(i%primes[j]==0)break;}}}
//vector<int>factor[N];void init2(){for(int i=1;i<N;i++){for(int j=i;j<N;j+=i){factor[j].push_back(i);}}}
//int find(vector<int>&pre,int x){return pre[x]=(pre[x]==x ? x : find(pre,pre[x]));}
//void merge(vector<int>&pre,int x,int y){int fx=find(pre,x),fy=find(pre,y);if(fx==fy)return;pre[fx]=fy;}
//bool check(vector<int>&pre,int x,int y){return find(pre,x)==find(pre,y);}
//string add(string x,string y){if((int)x.size()<(int)y.size())swap(x,y);int n=x.size();int m=y.size();reverse(x.begin(),x.end());reverse(y.begin(),y.end());
//int d=0;string ans;for(int i=0;i<n;i++){int x1=(x[i]-'0');int y1=(i<m ? y[i]-'0' : 0);int sum=x1+y1+d;ans.push_back((sum%10)+'0');d=sum/10;}
//if(d>0)ans.push_back(d+'0');reverse(ans.begin(),ans.end());return ans;}
//string mul(string x,string y){if(x=="0"||y=="0")return "0";reverse(x.begin(),x.end());reverse(y.begin(),y.end());int x1=x.size();int y1=y.size();string ans;
//for(int i=0;i<x1;i++){int d=0;int val1=(x[i]-'0');for(int j=0;j<y1;j++){int val2=(y[j]-'0');int len=ans.size();int val=val1*val2+d;
//if(len<=i+j)ans.push_back((val%10)+'0');else val+=(ans[i+j]-'0'),ans[i+j]=((val%10)+'0');d=val/10;}int len=ans.size();int cur_pos=i+y1;
//while(d){if(cur_pos>=len)ans.push_back((d%10)+'0');else d+=ans[cur_pos]-'0',ans[cur_pos]=((d%10)+'0');d/=10;cur_pos++;}}reverse(ans.begin(),ans.end());return ans;}
//struct Seg_Tree{int n;vector<int>t,lz;Seg_Tree(int _n=0){init(_n);}void init(int _n){n=_n;t.assign((n<<2)+2,0);lz.assign((n<<2)+2,0);}
//void pushup(int o){t[o]=t[o<<1]+t[o<<1|1];}void update(int s,int e,int o,int x){t[o]+=x*(e-s+1);lz[o]+=x;}
//void pushdown(int s,int e,int o){if(!lz[o])return ;int mid=(s+e)>>1;update(s,mid,o<<1,lz[o]);update(mid+1,e,o<<1|1,lz[o]);lz[o]=0;}
//void add(int l,int r,int x,int s=1,int e=0,int o=1){if(e==0)e=this->n;if(l>e||r<s)return ;if(l<=s&&e<=r){update(s,e,o,x);return ;}pushdown(s,e,o);int mid=(s+e)>>1;
//add(l,r,x,s,mid,o<<1);add(l,r,x,mid+1,e,o<<1|1);pushup(o);}
//int query(int l,int r,int s=1,int e=0,int o=1){if(e==0)e=this->n;if(l>e||r<s)return 0;if(l<=s&&r>=e)return t[o];pushdown(s,e,o);int mid=(s+e)>>1;
//int x=query(l,r,s,mid,o<<1);int y=query(l,r,mid+1,e,o<<1|1);return x+y;}};
void solve(){
    int k;
    cin>>k;
    int val=1;
    int ans=0;
    while(k){
        if(k>=val)ans+=val*val;
        else ans+=val*k;
        //cout<<ans<<'\n';
        if(k>=val)k-=val;
        else k=0;
        val++;
    }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    //init();   
    //init1();
    //init2();
    int _=1;
    //cin>>_;
    while(_--)solve();
    return 0;
}

第二题：

题目大意：

给定一个数字n，每次可以将添加一个正整数，添加的正整数的值需要比当前的值一半要小，可以得到一个合法的序列，现在可以求解这个序列有多少方案数

思路一：

递归：

这个题的暴力方法是递归，可以一直往当前值的一半进行递归

代码一：

#include<bits/stdc++.h>
#define int long long
using namespace std;
//#define x first
//#define y second
//const int mod=1e9+7;
//const int N=10000;
//int fac[N],invfac[N];  
//int qmi(int a,int b,int p){int res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;}
//int inv(int x){return qmi(x,p-2);}
//int C(int n,int m){if(n<0||m<0||n<m)return 0;return fac[n]*invfac[n-m]%p*invfac[m]%p;}
//void init(){fac[0]=1;for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%p;invfac[N-1]=inv(fac[N-1]);for(int i=N-2;i>=0;i--)invfac[i]=invfac[i+1]*(i+1)%p;}
//struct node{int v,w;bool operator < (const node &x)const{return w==x.w ? v>x.v : w>x.w;}};
//void dijkstra(const vector<vector<node>>&g,vector<int>&dist,vector<bool>&vis,int x){fill(dist.begin(),dist.end(),LLONG_MAX);fill(vis.begin(),vis.end(),false);
//dist[x]=0;priority_queue<node>q;q.push({x,0});while(q.size()){auto u=q.top().v;q.pop();if(vis[u])continue;vis[u]=true;for(auto [v,w]:g[u]){if(dist[v]>dist[u]+w){
//dist[v]=dist[u]+w;q.push({v,dist[v]});}}}}
//struct BIT{int n;vector<int>t;BIT(int _n=0){init(_n);}void init(int _n){n=_n;t.assign(n+2,0);}
//void add(int x,int v){for(;x<=n;x+=(x & -x))t[x]+=v;}int query(int x){int res=0;for(;x;x-=(x & -x))res+=t[x];return res;}};
//int calc_add(const vector<vector<int>>&s,int x1,int y1,int x2,int y2){return s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];}
//void calc_diff(vector<vector<int>>&d,int x1,int y1,int x2,int y2,int c){d[x1][y1]+=c;d[x2+1][y1]-=c;d[x1][y2+1]-=c;d[x2+1][y2+1]+=c;}
//int primes[N],cnt=0;bool st[N];
//void init1(){for(int i=2;i<N;i++){if(!st[i])primes[++cnt]=i;for(int j=1;primes[j]*i<N;j++){st[primes[j]*i]=true;if(i%primes[j]==0)break;}}}
//vector<int>factor[N];void init2(){for(int i=1;i<N;i++){for(int j=i;j<N;j+=i){factor[j].push_back(i);}}}
//int find(vector<int>&pre,int x){return pre[x]=(pre[x]==x ? x : find(pre,pre[x]));}
//void merge(vector<int>&pre,int x,int y){int fx=find(pre,x),fy=find(pre,y);if(fx==fy)return;pre[fx]=fy;}
//bool check(vector<int>&pre,int x,int y){return find(pre,x)==find(pre,y);}
//string add(string x,string y){if((int)x.size()<(int)y.size())swap(x,y);int n=x.size();int m=y.size();reverse(x.begin(),x.end());reverse(y.begin(),y.end());
//int d=0;string ans;for(int i=0;i<n;i++){int x1=(x[i]-'0');int y1=(i<m ? y[i]-'0' : 0);int sum=x1+y1+d;ans.push_back((sum%10)+'0');d=sum/10;}
//if(d>0)ans.push_back(d+'0');reverse(ans.begin(),ans.end());return ans;}
//string mul(string x,string y){if(x=="0"||y=="0")return "0";reverse(x.begin(),x.end());reverse(y.begin(),y.end());int x1=x.size();int y1=y.size();string ans;
//for(int i=0;i<x1;i++){int d=0;int val1=(x[i]-'0');for(int j=0;j<y1;j++){int val2=(y[j]-'0');int len=ans.size();int val=val1*val2+d;
//if(len<=i+j)ans.push_back((val%10)+'0');else val+=(ans[i+j]-'0'),ans[i+j]=((val%10)+'0');d=val/10;}int len=ans.size();int cur_pos=i+y1;
//while(d){if(cur_pos>=len)ans.push_back((d%10)+'0');else d+=ans[cur_pos]-'0',ans[cur_pos]=((d%10)+'0');d/=10;cur_pos++;}}reverse(ans.begin(),ans.end());return ans;}
//struct Seg_Tree{int n;vector<int>t,lz;Seg_Tree(int _n=0){init(_n);}void init(int _n){n=_n;t.assign((n<<2)+2,0);lz.assign((n<<2)+2,0);}
//void pushup(int o){t[o]=t[o<<1]+t[o<<1|1];}void update(int s,int e,int o,int x){t[o]+=x*(e-s+1);lz[o]+=x;}
//void pushdown(int s,int e,int o){if(!lz[o])return ;int mid=(s+e)>>1;update(s,mid,o<<1,lz[o]);update(mid+1,e,o<<1|1,lz[o]);lz[o]=0;}
//void add(int l,int r,int x,int s=1,int e=0,int o=1){if(e==0)e=this->n;if(l>e||r<s)return ;if(l<=s&&e<=r){update(s,e,o,x);return ;}pushdown(s,e,o);int mid=(s+e)>>1;
//add(l,r,x,s,mid,o<<1);add(l,r,x,mid+1,e,o<<1|1);pushup(o);}
//int query(int l,int r,int s=1,int e=0,int o=1){if(e==0)e=this->n;if(l>e||r<s)return 0;if(l<=s&&r>=e)return t[o];pushdown(s,e,o);int mid=(s+e)>>1;
//int x=query(l,r,s,mid,o<<1);int y=query(l,r,mid+1,e,o<<1|1);return x+y;}};
void solve(){
    int n;
    cin>>n;
    vector<int>dp(n+1,-1);
    dp[1]=1;
    function<int(int)> dfs=[&](int x)->int{
        int ans=1;
        if(dp[x]!=-1)return dp[x];
        for(int i=1;i<=x/2;i++){
            ans=ans+dfs(i);
        }
        return dp[x]=ans;
    };
    dfs(n);
    cout<<dp[n]<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    //init();   
    //init1();
    //init2();
    int _=1;
    //cin>>_;
    while(_--)solve();
    return 0;
}

思路二：

动态规划：

可以发现一个规律就是当前的值就是当前的数除以2，直到一为止，所以可以定义一个数组就是dp[i]：表示到当前i为止的方案数为dp[i]，所以需要维护一个前缀和数组来维护sum[i]：到i为止，前i/2的和，状态转移方程为dp[i]=sum[i]+1;

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
//#define x first
//#define y second
//const int mod=1e9+7;
//const int N=10000;
//int fac[N],invfac[N];  
//int qmi(int a,int b,int p){int res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;}
//int inv(int x){return qmi(x,p-2);}
//int C(int n,int m){if(n<0||m<0||n<m)return 0;return fac[n]*invfac[n-m]%p*invfac[m]%p;}
//void init(){fac[0]=1;for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%p;invfac[N-1]=inv(fac[N-1]);for(int i=N-2;i>=0;i--)invfac[i]=invfac[i+1]*(i+1)%p;}
//struct node{int v,w;bool operator < (const node &x)const{return w==x.w ? v>x.v : w>x.w;}};
//void dijkstra(const vector<vector<node>>&g,vector<int>&dist,vector<bool>&vis,int x){fill(dist.begin(),dist.end(),LLONG_MAX);fill(vis.begin(),vis.end(),false);
//dist[x]=0;priority_queue<node>q;q.push({x,0});while(q.size()){auto u=q.top().v;q.pop();if(vis[u])continue;vis[u]=true;for(auto [v,w]:g[u]){if(dist[v]>dist[u]+w){
//dist[v]=dist[u]+w;q.push({v,dist[v]});}}}}
//struct BIT{int n;vector<int>t;BIT(int _n=0){init(_n);}void init(int _n){n=_n;t.assign(n+2,0);}
//void add(int x,int v){for(;x<=n;x+=(x & -x))t[x]+=v;}int query(int x){int res=0;for(;x;x-=(x & -x))res+=t[x];return res;}};
//int calc_add(const vector<vector<int>>&s,int x1,int y1,int x2,int y2){return s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];}
//void calc_diff(vector<vector<int>>&d,int x1,int y1,int x2,int y2,int c){d[x1][y1]+=c;d[x2+1][y1]-=c;d[x1][y2+1]-=c;d[x2+1][y2+1]+=c;}
//int primes[N],cnt=0;bool st[N];
//void init1(){for(int i=2;i<N;i++){if(!st[i])primes[++cnt]=i;for(int j=1;primes[j]*i<N;j++){st[primes[j]*i]=true;if(i%primes[j]==0)break;}}}
//vector<int>factor[N];void init2(){for(int i=1;i<N;i++){for(int j=i;j<N;j+=i){factor[j].push_back(i);}}}
//int find(vector<int>&pre,int x){return pre[x]=(pre[x]==x ? x : find(pre,pre[x]));}
//void merge(vector<int>&pre,int x,int y){int fx=find(pre,x),fy=find(pre,y);if(fx==fy)return;pre[fx]=fy;}
//bool check(vector<int>&pre,int x,int y){return find(pre,x)==find(pre,y);}
//string add(string x,string y){if((int)x.size()<(int)y.size())swap(x,y);int n=x.size();int m=y.size();reverse(x.begin(),x.end());reverse(y.begin(),y.end());
//int d=0;string ans;for(int i=0;i<n;i++){int x1=(x[i]-'0');int y1=(i<m ? y[i]-'0' : 0);int sum=x1+y1+d;ans.push_back((sum%10)+'0');d=sum/10;}
//if(d>0)ans.push_back(d+'0');reverse(ans.begin(),ans.end());return ans;}
//string mul(string x,string y){if(x=="0"||y=="0")return "0";reverse(x.begin(),x.end());reverse(y.begin(),y.end());int x1=x.size();int y1=y.size();string ans;
//for(int i=0;i<x1;i++){int d=0;int val1=(x[i]-'0');for(int j=0;j<y1;j++){int val2=(y[j]-'0');int len=ans.size();int val=val1*val2+d;
//if(len<=i+j)ans.push_back((val%10)+'0');else val+=(ans[i+j]-'0'),ans[i+j]=((val%10)+'0');d=val/10;}int len=ans.size();int cur_pos=i+y1;
//while(d){if(cur_pos>=len)ans.push_back((d%10)+'0');else d+=ans[cur_pos]-'0',ans[cur_pos]=((d%10)+'0');d/=10;cur_pos++;}}reverse(ans.begin(),ans.end());return ans;}
//struct Seg_Tree{int n;vector<int>t,lz;Seg_Tree(int _n=0){init(_n);}void init(int _n){n=_n;t.assign((n<<2)+2,0);lz.assign((n<<2)+2,0);}
//void pushup(int o){t[o]=t[o<<1]+t[o<<1|1];}void update(int s,int e,int o,int x){t[o]+=x*(e-s+1);lz[o]+=x;}
//void pushdown(int s,int e,int o){if(!lz[o])return ;int mid=(s+e)>>1;update(s,mid,o<<1,lz[o]);update(mid+1,e,o<<1|1,lz[o]);lz[o]=0;}
//void add(int l,int r,int x,int s=1,int e=0,int o=1){if(e==0)e=this->n;if(l>e||r<s)return ;if(l<=s&&e<=r){update(s,e,o,x);return ;}pushdown(s,e,o);int mid=(s+e)>>1;
//add(l,r,x,s,mid,o<<1);add(l,r,x,mid+1,e,o<<1|1);pushup(o);}
//int query(int l,int r,int s=1,int e=0,int o=1){if(e==0)e=this->n;if(l>e||r<s)return 0;if(l<=s&&r>=e)return t[o];pushdown(s,e,o);int mid=(s+e)>>1;
//int x=query(l,r,s,mid,o<<1);int y=query(l,r,mid+1,e,o<<1|1);return x+y;}};
void solve(){
    int n;
    cin>>n;
    vector<int>sum(n+1),dp(n+1);
    dp[1]=1;
    sum[1]=1;
    for(int i=2;i<=n;i++){
        dp[i]=sum[i/2]+1;
        sum[i]=sum[i-1]+dp[i];
    }
    for(int i=1;i<=n;i++)cout<<sum[i]<<' ';
    cout<<'\n';
    cout<<dp[n]<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    //init();   
    //init1();
    //init2();
    int _=1;
    //cin>>_;
    while(_--)solve();
    return 0;
}

第三题

题目大意：

求解当前树的最大深度

思路：

递归即可

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
//#define x first
//#define y second
//const int mod=1e9+7;
//const int N=10000;
//int fac[N],invfac[N];  
//int qmi(int a,int b,int p){int res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;}
//int inv(int x){return qmi(x,p-2);}
//int C(int n,int m){if(n<0||m<0||n<m)return 0;return fac[n]*invfac[n-m]%p*invfac[m]%p;}
//void init(){fac[0]=1;for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%p;invfac[N-1]=inv(fac[N-1]);for(int i=N-2;i>=0;i--)invfac[i]=invfac[i+1]*(i+1)%p;}
//struct node{int v,w;bool operator < (const node &x)const{return w==x.w ? v>x.v : w>x.w;}};
//void dijkstra(const vector<vector<node>>&g,vector<int>&dist,vector<bool>&vis,int x){fill(dist.begin(),dist.end(),LLONG_MAX);fill(vis.begin(),vis.end(),false);
//dist[x]=0;priority_queue<node>q;q.push({x,0});while(q.size()){auto u=q.top().v;q.pop();if(vis[u])continue;vis[u]=true;for(auto [v,w]:g[u]){if(dist[v]>dist[u]+w){
//dist[v]=dist[u]+w;q.push({v,dist[v]});}}}}
//struct BIT{int n;vector<int>t;BIT(int _n=0){init(_n);}void init(int _n){n=_n;t.assign(n+2,0);}
//void add(int x,int v){for(;x<=n;x+=(x & -x))t[x]+=v;}int query(int x){int res=0;for(;x;x-=(x & -x))res+=t[x];return res;}};
//int calc_add(const vector<vector<int>>&s,int x1,int y1,int x2,int y2){return s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];}
//void calc_diff(vector<vector<int>>&d,int x1,int y1,int x2,int y2,int c){d[x1][y1]+=c;d[x2+1][y1]-=c;d[x1][y2+1]-=c;d[x2+1][y2+1]+=c;}
//int primes[N],cnt=0;bool st[N];
//void init1(){for(int i=2;i<N;i++){if(!st[i])primes[++cnt]=i;for(int j=1;primes[j]*i<N;j++){st[primes[j]*i]=true;if(i%primes[j]==0)break;}}}
//vector<int>factor[N];void init2(){for(int i=1;i<N;i++){for(int j=i;j<N;j+=i){factor[j].push_back(i);}}}
//int find(vector<int>&pre,int x){return pre[x]=(pre[x]==x ? x : find(pre,pre[x]));}
//void merge(vector<int>&pre,int x,int y){int fx=find(pre,x),fy=find(pre,y);if(fx==fy)return;pre[fx]=fy;}
//bool check(vector<int>&pre,int x,int y){return find(pre,x)==find(pre,y);}
//string add(string x,string y){if((int)x.size()<(int)y.size())swap(x,y);int n=x.size();int m=y.size();reverse(x.begin(),x.end());reverse(y.begin(),y.end());
//int d=0;string ans;for(int i=0;i<n;i++){int x1=(x[i]-'0');int y1=(i<m ? y[i]-'0' : 0);int sum=x1+y1+d;ans.push_back((sum%10)+'0');d=sum/10;}
//if(d>0)ans.push_back(d+'0');reverse(ans.begin(),ans.end());return ans;}
//string mul(string x,string y){if(x=="0"||y=="0")return "0";reverse(x.begin(),x.end());reverse(y.begin(),y.end());int x1=x.size();int y1=y.size();string ans;
//for(int i=0;i<x1;i++){int d=0;int val1=(x[i]-'0');for(int j=0;j<y1;j++){int val2=(y[j]-'0');int len=ans.size();int val=val1*val2+d;
//if(len<=i+j)ans.push_back((val%10)+'0');else val+=(ans[i+j]-'0'),ans[i+j]=((val%10)+'0');d=val/10;}int len=ans.size();int cur_pos=i+y1;
//while(d){if(cur_pos>=len)ans.push_back((d%10)+'0');else d+=ans[cur_pos]-'0',ans[cur_pos]=((d%10)+'0');d/=10;cur_pos++;}}reverse(ans.begin(),ans.end());return ans;}
//struct Seg_Tree{int n;vector<int>t,lz;Seg_Tree(int _n=0){init(_n);}void init(int _n){n=_n;t.assign((n<<2)+2,0);lz.assign((n<<2)+2,0);}
//void pushup(int o){t[o]=t[o<<1]+t[o<<1|1];}void update(int s,int e,int o,int x){t[o]+=x*(e-s+1);lz[o]+=x;}
//void pushdown(int s,int e,int o){if(!lz[o])return ;int mid=(s+e)>>1;update(s,mid,o<<1,lz[o]);update(mid+1,e,o<<1|1,lz[o]);lz[o]=0;}
//void add(int l,int r,int x,int s=1,int e=0,int o=1){if(e==0)e=this->n;if(l>e||r<s)return ;if(l<=s&&e<=r){update(s,e,o,x);return ;}pushdown(s,e,o);int mid=(s+e)>>1;
//add(l,r,x,s,mid,o<<1);add(l,r,x,mid+1,e,o<<1|1);pushup(o);}
//int query(int l,int r,int s=1,int e=0,int o=1){if(e==0)e=this->n;if(l>e||r<s)return 0;if(l<=s&&r>=e)return t[o];pushdown(s,e,o);int mid=(s+e)>>1;
//int x=query(l,r,s,mid,o<<1);int y=query(l,r,mid+1,e,o<<1|1);return x+y;}};
void solve(){
    int n;
    cin>>n;
    vector<int>G[n+1];
    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        G[i].push_back(l);
        G[i].push_back(r);
    }
    vector<int>dep(n+1);
    dep[1]=1;
    function<void(int,int)> dfs=[&](int x,int fa)->void{
        dep[x]=dep[fa]+1;
        for(auto y:G[x]){
            if(y==fa)return ;
            dfs(y,x);
        }
    };
    dfs(1,0);
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,dep[i]);
    }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    //init();   
    //init1();
    //init2();
    int _=1;
    //cin>>_;
    while(_--)solve();
    return 0;
}

第四题

题目大意：

给定一个字符串，可以将当前字符串删除k位求解最小的数字

思路：

维护一个单调栈即可

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
//#define x first
//#define y second
//const int mod=1e9+7;
//const int N=10000;
//int fac[N],invfac[N];  
//int qmi(int a,int b,int p){int res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;}
//int inv(int x){return qmi(x,p-2);}
//int C(int n,int m){if(n<0||m<0||n<m)return 0;return fac[n]*invfac[n-m]%p*invfac[m]%p;}
//void init(){fac[0]=1;for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%p;invfac[N-1]=inv(fac[N-1]);for(int i=N-2;i>=0;i--)invfac[i]=invfac[i+1]*(i+1)%p;}
//struct node{int v,w;bool operator < (const node &x)const{return w==x.w ? v>x.v : w>x.w;}};
//void dijkstra(const vector<vector<node>>&g,vector<int>&dist,vector<bool>&vis,int x){fill(dist.begin(),dist.end(),LLONG_MAX);fill(vis.begin(),vis.end(),false);
//dist[x]=0;priority_queue<node>q;q.push({x,0});while(q.size()){auto u=q.top().v;q.pop();if(vis[u])continue;vis[u]=true;for(auto [v,w]:g[u]){if(dist[v]>dist[u]+w){
//dist[v]=dist[u]+w;q.push({v,dist[v]});}}}}
//struct BIT{int n;vector<int>t;BIT(int _n=0){init(_n);}void init(int _n){n=_n;t.assign(n+2,0);}
//void add(int x,int v){for(;x<=n;x+=(x & -x))t[x]+=v;}int query(int x){int res=0;for(;x;x-=(x & -x))res+=t[x];return res;}};
//int calc_add(const vector<vector<int>>&s,int x1,int y1,int x2,int y2){return s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];}
//void calc_diff(vector<vector<int>>&d,int x1,int y1,int x2,int y2,int c){d[x1][y1]+=c;d[x2+1][y1]-=c;d[x1][y2+1]-=c;d[x2+1][y2+1]+=c;}
//int primes[N],cnt=0;bool st[N];
//void init1(){for(int i=2;i<N;i++){if(!st[i])primes[++cnt]=i;for(int j=1;primes[j]*i<N;j++){st[primes[j]*i]=true;if(i%primes[j]==0)break;}}}
//vector<int>factor[N];void init2(){for(int i=1;i<N;i++){for(int j=i;j<N;j+=i){factor[j].push_back(i);}}}
//int find(vector<int>&pre,int x){return pre[x]=(pre[x]==x ? x : find(pre,pre[x]));}
//void merge(vector<int>&pre,int x,int y){int fx=find(pre,x),fy=find(pre,y);if(fx==fy)return;pre[fx]=fy;}
//bool check(vector<int>&pre,int x,int y){return find(pre,x)==find(pre,y);}
//string add(string x,string y){if((int)x.size()<(int)y.size())swap(x,y);int n=x.size();int m=y.size();reverse(x.begin(),x.end());reverse(y.begin(),y.end());
//int d=0;string ans;for(int i=0;i<n;i++){int x1=(x[i]-'0');int y1=(i<m ? y[i]-'0' : 0);int sum=x1+y1+d;ans.push_back((sum%10)+'0');d=sum/10;}
//if(d>0)ans.push_back(d+'0');reverse(ans.begin(),ans.end());return ans;}
//string mul(string x,string y){if(x=="0"||y=="0")return "0";reverse(x.begin(),x.end());reverse(y.begin(),y.end());int x1=x.size();int y1=y.size();string ans;
//for(int i=0;i<x1;i++){int d=0;int val1=(x[i]-'0');for(int j=0;j<y1;j++){int val2=(y[j]-'0');int len=ans.size();int val=val1*val2+d;
//if(len<=i+j)ans.push_back((val%10)+'0');else val+=(ans[i+j]-'0'),ans[i+j]=((val%10)+'0');d=val/10;}int len=ans.size();int cur_pos=i+y1;
//while(d){if(cur_pos>=len)ans.push_back((d%10)+'0');else d+=ans[cur_pos]-'0',ans[cur_pos]=((d%10)+'0');d/=10;cur_pos++;}}reverse(ans.begin(),ans.end());return ans;}
//struct Seg_Tree{int n;vector<int>t,lz;Seg_Tree(int _n=0){init(_n);}void init(int _n){n=_n;t.assign((n<<2)+2,0);lz.assign((n<<2)+2,0);}
//void pushup(int o){t[o]=t[o<<1]+t[o<<1|1];}void update(int s,int e,int o,int x){t[o]+=x*(e-s+1);lz[o]+=x;}
//void pushdown(int s,int e,int o){if(!lz[o])return ;int mid=(s+e)>>1;update(s,mid,o<<1,lz[o]);update(mid+1,e,o<<1|1,lz[o]);lz[o]=0;}
//void add(int l,int r,int x,int s=1,int e=0,int o=1){if(e==0)e=this->n;if(l>e||r<s)return ;if(l<=s&&e<=r){update(s,e,o,x);return ;}pushdown(s,e,o);int mid=(s+e)>>1;
//add(l,r,x,s,mid,o<<1);add(l,r,x,mid+1,e,o<<1|1);pushup(o);}
//int query(int l,int r,int s=1,int e=0,int o=1){if(e==0)e=this->n;if(l>e||r<s)return 0;if(l<=s&&r>=e)return t[o];pushdown(s,e,o);int mid=(s+e)>>1;
//int x=query(l,r,s,mid,o<<1);int y=query(l,r,mid+1,e,o<<1|1);return x+y;}};
void solve(){
    string s;
    int k;
    cin>>s>>k;
    int n=s.size();
    vector<int>stk;
    for(int i=0;i<n;i++){
        while(stk.size()&&k&&s[stk.back()]>s[i])stk.pop_back(),k--;
        stk.push_back(i);
    }
    if(k){
        while(k&&stk.size())stk.pop_back(),k--;
    }
    int m=stk.size();
    string t;
    for(int i=0;i<m;i++)t+=s[stk[i]];
    int st=0;
    while(st<(int)t.size()&&t[st]=='0')st++;
    if(st==(int)t.size()){
        cout<<0<<'\n';
    }
    else{
        cout<<t.substr(st)<<'\n';
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    //init();   
    //init1();
    //init2();
    int _=1;
    //cin>>_;
    while(_--)solve();
    return 0;
}

第五题

题目大意：

在一个矩阵中取数，取数规则如下：
1、每次取数须从每行各取走一个元素，共n个
2、每次取走的元素各个元素只能是该元素所在的行的首部和尾部
3、每次取数都有一个得分值，为每行取数的得分之和
每行取数的得分=被取走元素2i，i表示编号
4、经过m次取出的得分数之和
求解最后将所有元素都取出之后最大的得分

思路：

可以发现这个题是 $2^i$ ，最大值是 $1000*1000*2^{80}$ 很明显这个题会爆long long，所以需要使用高精度，或者使用int128也可以，但是需要注意最后输出并不能使用int128，现在看这道题进行思考，每次都只能取行首或者行尾，可能第一直觉是贪心，但是这个题不能使用贪心，因为局部最优并不能体现出整体最优，所以可以考虑区间DP，对每一行进行区间DP，时间复杂度是 $O (n * m * m)$

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
//#define x first
//#define y second
//const int mod=1e9+7;
//const int N=10000;
//int fac[N],invfac[N];  
//int qmi(int a,int b,int p){int res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;}
//int inv(int x){return qmi(x,p-2);}
//int C(int n,int m){if(n<0||m<0||n<m)return 0;return fac[n]*invfac[n-m]%p*invfac[m]%p;}
//void init(){fac[0]=1;for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%p;invfac[N-1]=inv(fac[N-1]);for(int i=N-2;i>=0;i--)invfac[i]=invfac[i+1]*(i+1)%p;}
//struct node{int v,w;bool operator < (const node &x)const{return w==x.w ? v>x.v : w>x.w;}};
//void dijkstra(const vector<vector<node>>&g,vector<int>&dist,vector<bool>&vis,int x){fill(dist.begin(),dist.end(),LLONG_MAX);fill(vis.begin(),vis.end(),false);
//dist[x]=0;priority_queue<node>q;q.push({x,0});while(q.size()){auto u=q.top().v;q.pop();if(vis[u])continue;vis[u]=true;for(auto [v,w]:g[u]){if(dist[v]>dist[u]+w){
//dist[v]=dist[u]+w;q.push({v,dist[v]});}}}}
//struct BIT{int n;vector<int>t;BIT(int _n=0){init(_n);}void init(int _n){n=_n;t.assign(n+2,0);}
//void add(int x,int v){for(;x<=n;x+=(x & -x))t[x]+=v;}int query(int x){int res=0;for(;x;x-=(x & -x))res+=t[x];return res;}};
//int calc_add(const vector<vector<int>>&s,int x1,int y1,int x2,int y2){return s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];}
//void calc_diff(vector<vector<int>>&d,int x1,int y1,int x2,int y2,int c){d[x1][y1]+=c;d[x2+1][y1]-=c;d[x1][y2+1]-=c;d[x2+1][y2+1]+=c;}
//int primes[N],cnt=0;bool st[N];
//void init1(){for(int i=2;i<N;i++){if(!st[i])primes[++cnt]=i;for(int j=1;primes[j]*i<N;j++){st[primes[j]*i]=true;if(i%primes[j]==0)break;}}}
//vector<int>factor[N];void init2(){for(int i=1;i<N;i++){for(int j=i;j<N;j+=i){factor[j].push_back(i);}}}
//int find(vector<int>&pre,int x){return pre[x]=(pre[x]==x ? x : find(pre,pre[x]));}
//void merge(vector<int>&pre,int x,int y){int fx=find(pre,x),fy=find(pre,y);if(fx==fy)return;pre[fx]=fy;}
//bool check(vector<int>&pre,int x,int y){return find(pre,x)==find(pre,y);}
//string add(string x,string y){if((int)x.size()<(int)y.size())swap(x,y);int n=x.size();int m=y.size();reverse(x.begin(),x.end());reverse(y.begin(),y.end());
//int d=0;string ans;for(int i=0;i<n;i++){int x1=(x[i]-'0');int y1=(i<m ? y[i]-'0' : 0);int sum=x1+y1+d;ans.push_back((sum%10)+'0');d=sum/10;}
//if(d>0)ans.push_back(d+'0');reverse(ans.begin(),ans.end());return ans;}
//string mul(string x,string y){if(x=="0"||y=="0")return "0";reverse(x.begin(),x.end());reverse(y.begin(),y.end());int x1=x.size();int y1=y.size();string ans;
//for(int i=0;i<x1;i++){int d=0;int val1=(x[i]-'0');for(int j=0;j<y1;j++){int val2=(y[j]-'0');int len=ans.size();int val=val1*val2+d;
//if(len<=i+j)ans.push_back((val%10)+'0');else val+=(ans[i+j]-'0'),ans[i+j]=((val%10)+'0');d=val/10;}int len=ans.size();int cur_pos=i+y1;
//while(d){if(cur_pos>=len)ans.push_back((d%10)+'0');else d+=ans[cur_pos]-'0',ans[cur_pos]=((d%10)+'0');d/=10;cur_pos++;}}reverse(ans.begin(),ans.end());return ans;}
//struct Seg_Tree{int n;vector<int>t,lz;Seg_Tree(int _n=0){init(_n);}void init(int _n){n=_n;t.assign((n<<2)+2,0);lz.assign((n<<2)+2,0);}
//void pushup(int o){t[o]=t[o<<1]+t[o<<1|1];}void update(int s,int e,int o,int x){t[o]+=x*(e-s+1);lz[o]+=x;}
//void pushdown(int s,int e,int o){if(!lz[o])return ;int mid=(s+e)>>1;update(s,mid,o<<1,lz[o]);update(mid+1,e,o<<1|1,lz[o]);lz[o]=0;}
//void add(int l,int r,int x,int s=1,int e=0,int o=1){if(e==0)e=this->n;if(l>e||r<s)return ;if(l<=s&&e<=r){update(s,e,o,x);return ;}pushdown(s,e,o);int mid=(s+e)>>1;
//add(l,r,x,s,mid,o<<1);add(l,r,x,mid+1,e,o<<1|1);pushup(o);}
//int query(int l,int r,int s=1,int e=0,int o=1){if(e==0)e=this->n;if(l>e||r<s)return 0;if(l<=s&&r>=e)return t[o];pushdown(s,e,o);int mid=(s+e)>>1;
//int x=query(l,r,s,mid,o<<1);int y=query(l,r,mid+1,e,o<<1|1);return x+y;}};
void solve(){
    int n,m;
    cin>>n>>m;
    vector G(n+1,vector<int>(m+1));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>G[i][j];
        }
    }
    __int128 ans=0;
    auto calc=[&](int x)->__int128{
        vector dp(85,vector<__int128>(85));
        for(int len=0;len<=m;len++){
            for(int i=1;i+len<=m;i++){
                dp[i][i+len]=max(2*(dp[i][i+len-1]+G[x][i+len]),2*(dp[i+1][i+len]+G[x][i]));
            }
        }
        return dp[1][m];
    };
    for(int i=1;i<=n;i++)ans+=calc(i);
    vector<int>vec;
    while(ans){
        vec.push_back(ans%10);
        ans/=10;
    }
    reverse(vec.begin(),vec.end());
    for(auto x:vec)cout<<x;
    cout<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    //init();   
    //init1();
    //init2();
    int _=1;
    //cin>>_;
    while(_--)solve();
    return 0;
}

魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

小参数・大码力・易部署 | Qwen3.6-27B上线魔乐社区，基于昇腾的部署教程来了

继一周前模型开源发布后，千问再度开源Qwen3.6-27B —— 一个拥有270亿参数的稠密多模态模型，也是社区呼声最高的模型规格。Qwen3.6-27B 依然支持多模态思考与非思考模式，在智能体编程方面达到了旗舰级表现，全面超越前代开源旗舰 Qwen3.5-397B-A17B（总参数397B / 激活参数17B的MoE模型）。作为稠密架构，它无需MoE路由即可部署，是开发者在实用、可广泛部署规模