T1：优秀的拆分（power）
题目描述
一般来说，一个正整数可以拆分成若干个正整数的和。例如， 1 = 1， 10 = 1 + 2 + 3 + 4 等。
对于正整数 n 的一种特定拆分，我们称它为“优秀的”，当且仅当在这种拆分下， n 被分解为了若干个不同的 2 的正整数次幂。注意， 一个数 x 能被表示成示成 2 的正整数次幂，当且仅当 x 能通过正整数个 2 相乘在一起得到。
例如， 10 = 8 + 2 = 23 + 21 是一个优秀的拆分。但是， 7 = 4 + 2 + 1 = 22 + 21 + 20 就不是一个优秀的拆分，因为 1 不是 2 的正整数次幂。
现在，给定正整数 n，你需要判断这个数的所有拆分中，是否存在优秀的拆分。 若存在， 请你给出具体的拆分方案。
输入
输入文件只有一行，一个正整数 n，代表需要判断的数。
输出
如果这个数的所有拆分中，存在优秀的拆分。那么， 你需要从大到小输出这个拆分中的每一个数， 相邻两个数之间用一个空格隔开。 可以证明， 在规定了拆分数字的顺序后， 该拆分方案是唯一的。
若不存在优秀的拆分，输出“-1”（不包含双引号）。
参考解法
#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）
题目描述
NOI2130 即将举行。为了增加观赏性， CCF 决定逐一评出每个选手的成绩，并直播即时的获奖分数线。 本次竞赛的获奖率为 w%， 即当前排名前 w%的选手的最低成绩就是即时的分数线。
更具体地， 若当前已评出了 p 个选手的成绩， 则当前计划获奖人数为max(1, ⌊p × w%⌋)， 其中 w 是获奖百分比， ⌊x⌋ 表示对 x 向下取整，
max(x, y) 表示 x 和 y 中较大的数。如有选手成绩相同，则所有成绩并列的选手都能获奖，因此实际获奖人数可能比计划中多。
作为评测组的技术人员，请你帮 CCF 写一个直播程序。
输入
第 1 行两个正整数 n, w。 分别代表选手总数与获奖率。
第 2 行有 n 个非负整数，依次代表逐一评出的选手成绩。
输出
只有一行，包含 n 个非负整数，依次代表选手成绩逐一评出后，即时的获奖分数线。 相邻两个整数间用一个空格分隔。
参考解法
#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）
题目描述
小 C 热衷于学习数理逻辑。有一天，他发现了一种特别的逻辑表达式。在这种逻辑表达式中， 所有操作数都是变量，且它们的取值只能为 0 或 1， 运算从左往右进行。如果表达式中有括号，则先计算括号内的子表达式的值。特别的，这种表达式有且仅有以下几种运算：
1. 与运算： a & b。当且仅当 a 和 b 的值都为 1 时，该表达式的值为1。其余情况该表达式的值为 0。
2. 或运算： a | b。当且仅当 a 和 b 的值都为 0 时，该表达式的值为0。其余情况该表达式的值为 1。
3. 取反运算： !a。当且仅当 a 的值为 0 时，该表达式的值为 1。其余情况该表达式的值为 0。
小 C 想知道，给定一个逻辑表达式和其中每一个操作数的初始取值后， 再取反某一个操作数的值时，原表达式的值为多少。
为了化简对表达式的处理，我们有如下约定：
表达式将采用后缀表达式的方式输入。后缀表达式的定义如下：
1. 如果 E 是一个操作数，则 E 的后缀表达式是它本身。
2. 如果 E 是 E1 op E2 形式的表达式， 其中 op 是任何二元操作符， 且优先级不高于 E1、 E2 中括号外的操作符， 则 E 的后缀式为 E1' E2' op，其中 E1'、E2' 分别为 E1、 E2 的后缀式。
3. 如果 E 是 (E1) 形式的表达式，则 E1 的后缀式就是 E 的后缀式。
同时为了方便， 输入中：
a) 与运算符（&）、或运算符（|）、取反运算符（！）的左右均有一个空格，但表达式末尾没有空格。
b) 操作数由小写字母 x 与一个正整数拼接而成，正整数表示这个变量的下标。例如： x10， 表示下标为 10 的变量 x10。数据保证每个变量在表达式中出现恰好一次。
输入
第一行包含一个字符串 s，表示上文描述的表达式。
第二行包含一个正整数 n，表示表达式中变量的数量。表达式中变量的下标为 1,2, … , n。
第三行包含 n 个整数， 第 i 个整数表示变量 xi 的初值。
第四行包含一个正整数 q，表示询问的个数。
接下来 q 行，每行一个正整数，表示需要取反的变量的下标。注意，每一个询问的修改都是临时的，即之前询问中的修改不会对后续的询问造成影响。
数据保证输入的表达式合法。 变量的初值为 0 或 1。
输出
输出一共有 q 行，每行一个 0 或 1，表示该询问下表达式的值。
#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）
题目描述
设有 n × m 的方格图，每个方格中都有一个整数。现有一只小熊， 想从图的左上角走到右下角，每一步只能向上、向下或向右走一格， 并且不能重复经过已经走过的方格，也不能走出边界。小熊会取走所有经过的方格中的整数，求它能取到的整数之和的最大值。
输入
第 1 行两个正整数 n, m。
接下来 n 行每行 m 个整数， 依次代表每个方格中的整数。
输出
一个整数，表示小熊能取到的整数之和的最大值 。
参考程序
#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;
}