第十二届蓝桥杯省赛第一场C++A/B/C组真题

题解：模拟+字符串处理

#include

using namespace std;
typedef long long LL;
typedef pairPII;
const int N=2e5+10;
const int mod=1000000009;
LL n;
int main(){
    cin>>n;
    n/=1000;
    int s=n%60;
    n/=60;
    int m=n%60;
    n/=60;
    int h=n%24;
    printf("%02d:%02d:%02d",h,m,s);
    return 0;
}

题解一：每个砝码有三种选择（不选、放左边、放右边）

#include

using namespace std;
typedef long long LL;
typedef pairPII;
const int N=1e5+10;
const int mod=1000000009;
int n;
bool c1[N]={0},c2[N]={0};
int w[110];
int main(){
    cin>>n;
    for(int i=0;i>w[i];
    for(int  i=0;i 
题解二：dp,背包问题
 
#include

using namespace std;
typedef long long LL;
typedef pairPII;
const int N=1e5+10;
const int mod=1000000009;
int n;
int w[110];
bool f[110][N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>w[i];
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=100000;j++){
            if(w[i]+j<=100000){
                f[i][w[i]+j]=f[i-1][j]||f[i-1][w[i]+j]||f[i][w[i]+j];
            }//放左边
            f[i][abs(j-w[i])]=f[i][abs(j-w[i])]||f[i-1][j]||f[i-1][abs(j-w[i])];
            //放右边
            f[i][j]=f[i][j]||f[i-1][j];
            //两边都不放
        }
    }
    int ans=0;
    for(int i=1;i<=100000;i++){
        if(f[n][i]) ans++;
    }
    cout< 
题目：3422. 左孩子右兄弟 

 
 
 题解：树型dp。最大的深度maxd一定是由子节点的数量ct_son+子节点中最大的深度d_son组成（实际上就是求子节点中儿子数量的最大值）。
 
#include

using namespace std;
typedef long long LL;
typedef pairPII;
const int N=1e5+10;
const int mod=1000000009;
int n;
vector g[N];
int dp[N];
void dfs(int u){
    dp[u]=g[u].size();
    int sum=0;
    for(int i=0;i>n;
    int x;
    for(int i=2;i<=n;i++){
        scanf("%d",&x);
        g[x].push_back(i);
    }
    dfs(1);
    cout<