T1：优秀的拆分（power）

参考解法

#include <bits/stdc++.h>
using namespace std;

/*
定义：分解为了若干个不同的 2 的正整数次幂
性质：是偶数，奇数不存在优秀的拆分

思路：
如果n是偶数，将n进行进制转换
10 -> 1010
*/
int a[110],n,k = 0;//k表示a数组的下标

int main(){
    cin>>n;
    //特判奇数的情况
    if(n % 2 != 0){
        cout<<-1;
        return 0;
    }

    //进制转换
    int t = 1;//表示2的次方
    while(n != 0){
        if(n % 2 != 0){
            k++;
            a[k] = t;
        }
        t = t * 2;
        n = n / 2;
    }

    //逆序输出结果
    for(int i = k;i >= 1;i--){
        cout<<a[i]<<" ";
    }
    return 0;
}

T2：直播获奖（ live）

参考解法

#include <bits/stdc++.h>
using namespace std;

/*
1.获奖人数为k = max(1, int(p × w%))
2.选手的成绩均为不超过 600 的非负整数
思路：使用数组统计每个分值得分的人数
从大到小统计出k个人，最后一次循环对应的分值就是要求的获奖分数
*/
int a[610];
int n,w,x;

int main(){
    scanf("%d%d",&n,&w);
    int k;//获奖人数
    int ans;//统计人数
    //读入n个人的分数，读一个算一个
    for(int i = 1;i <= n;i++){
        scanf("%d",&x);
        a[x]++;//统计每个分值对应的人数
        //计算获奖人数
        k = max(1,int(i * w / 100.0));
        ans = 0;
        //从最高分的人数向下统计出>=k个人
        for(int j = 600;j >= 0;j--){
            if(ans + a[j] < k) ans += a[j];//+=
            else{
                printf("%d ",j);
                break;
            }
        }
    }
	return 0;
}

T3：表达式（expr）

#include <bits/stdc++.h>
using namespace std;

/*
取反某一个操作数的值时，原表达式的值为多少
思路：
1.读入表达式，将表达式建成二叉树
2.计算出表达式的值
3.深搜，求出哪些结点的值修改后对结果有影响
*/
const int N = 1e6 + 10;
struct node{
    int to,next;
}a[N];//邻接表
int pre[N],k;//存储以每个点为起点的最后一条边的编号
int num[N];//存储二叉树每个结点的值
char c[N];//存储操作符
int m;//表示c数组的下标
bool f[N];//标记哪些点的值修改后对结果有影响
int n;
string s,w;//w用来存储每个操作数的下标
stack<int> st;//用于计算后缀表达式

//建边
void add(int u,int v){
    k++;
    a[k].to = v;
    a[k].next = pre[u];
    pre[u] = k;
}

//深搜求哪些结点的值修改后对结果有影响
void dfs(int x){
    f[x] = true;
    if(x <= n) return;//如果是叶子结点
    if(c[x] == '!') dfs(a[pre[x]].to);
    else{
        int n1 = a[pre[x]].to,n2 = a[a[pre[x]].next].to;
        if(c[x] == '&'){
            if(num[n1] == 1) dfs(n2);
            if(num[n2] == 1) dfs(n1);
        }else if(c[x] == '|'){
            if(num[n1] == 0) dfs(n2);
            if(num[n2] == 0) dfs(n1);
        }
    }
}

int main()
{
    getline(cin,s);
    cin>>n;
    for(int i = 1;i <= n;i++){
        scanf("%d",&num[i]);
    }

    //分析表达式，建树
    int x,y;
    m = n;
    for(int i = 0;i < s.size();i++){
        if(isdigit(s[i])){
            w = w + s[i];
            //如果连续数字结束
            if(i==s.size()-1||!isdigit(s[i+1])){
                st.push(atoi(w.c_str()));//将操作数的下标入栈
                w = "";
            }
        }else if(s[i] == '!'){
            //如果是取反操作符
            m++;
            c[m] = s[i];//操作符的编号是m
            x = st.top();//取栈顶元素来运算
            st.pop(); //出栈
            //建边
            add(m,x);
            num[m] = !num[x];
            st.push(m);
        }else if(s[i] == '&' || s[i] == '|'){
            //如果是& |操作符
            m++;
            c[m] = s[i];
            //取2个操作数
            x = st.top();
            st.pop();
            y = st.top();
            st.pop();
            //建边
            add(m,x);
            add(m,y);
            //计算结点的值
            if(s[i] == '&') num[m] = num[x] & num[y];
            else if(s[i] == '|') num[m] = num[x] | num[y];

            st.push(m);
        }
    }

    int ans = num[st.top()];
    //cout<<ans;
    //深搜求哪些结点的值修改后对结果有影响
    dfs(st.top());//从根开始深搜

    //q次询问
    int q;
    cin>>q;
    while(q--){
        scanf("%d",&x);
        if(f[x]==true) printf("%d\n",!ans);
        else printf("%d\n",ans);
    }

    return 0;
}

T4：方格取数（number）

参考程序

#include <bits/stdc++.h>
using namespace std;
/*
左上角走到右下角
每一步只能向上、向下或向右走一格
不能重复经过已经走过的方格

计算的结果，要用long long
*/
const int N = 1010;
int a[N][N];//读入的每个点的值
typedef long long LL;
LL f[N][N];
int n,m;

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            scanf("%d",&a[i][j]);
        }
    }

    /*
    DP求出走到每个点经过的数字和的最大值
    一列一列求，对于每一列而言，要求从上向下走到每个点经过的数字和的最大值
    也要求从下向上走到每个点经过的数字和的最大值
    */
    memset(f,-0x7f,sizeof(f));

    LL ma;//走到每个格子经过的数字和最大
    f[1][0] = 0;
    for(int j = 1;j <= m;j++){
        //从上向下求
        ma = -1e18;
        for(int i = 1;i <= n;i++){
            ma = max(ma,f[i][j-1]) + a[i][j];
            f[i][j] = max(f[i][j],ma);
        }

        //从下向上求
        ma = -1e18;
        for(int i = n;i >= 1;i--){
            ma = max(ma,f[i][j-1]) + a[i][j];
            f[i][j] = max(f[i][j],ma);
        }
    }

cout<<f[n][m];
return 0;
}

---

添加 家长论坛微信