一）优秀的拆分
一般来说，一个正整数可以拆分成若干个正整数的和。例如，1=1，10=1+2+3+4 等。
对于正整数 n 的一种特定拆分，我们称它为“优秀的”，当且仅当在这种拆分下，n 被分解为了若干个不同的 2 的正整数次幂。注意，一个数 x 能被表示成 2 的正整数次幂，当且仅当 x 能通过正整数个 2 相乘在一起得到。
例如，10=8+2=2^3+2^1是一个优秀的拆分。但是，7=4+2+1=2^2+2^1+2^0 就不是一个优秀的拆分，因为 1 不是 2 的正整数次幂。
现在，给定正整数 n，你需要判断这个数的所有拆分中，是否存在优秀的拆分。若存在，请你给出具体的拆分方案。
输入格式
输入文件名为 power.in。
输入文件只有一行，一个正整数 n，代表需要判断的数。
输出格式
输出文件名为 power.out。
如果这个数的所有拆分中，存在优秀的拆分。那么，你需要从大到小输出这个拆分中的每一个数，相邻两个数之间用一个空格隔开。可以证明，在规定了拆分数字的顺序后，该拆分方案是唯一的。
若不存在优秀的拆分，输出“-1”（不包含双引号）。
样例 1 输入
6
样例 1 输出
4 2
样例 1 解释
6=4+2=2^2+2^1 是一个优秀的拆分。注意，6=2+2+2 不是优秀的拆分，因为拆分成的 3 个数不满足每个数互不相同。
样例 2 输入
7
样例 2 输出
-1
数据范围与提示
对于 20% 的数据，n≤10。
对于另外 20% 的数据，保证 n 为奇数。
对于另外 20% 的数据，保证 n 为 2 的正整数次幂。
对于 80% 的数据，n≤1024。
对于 100% 的数据，1≤n≤10^7。

二进制拆分，多重背包的优化里，当模板用。
using namespace std;
int n,p[30] = {1};
int main()
{
    for(int i = 1;i <= 30;++i) p[i] = p[i - 1] * 2;
    cin >> n;
    if(n&1) cout<<-1;
    else
    {
        for(int i = 30;i >= 1;--i)
            if(n >= p[i])
            {
                cout<<p[i]<<" ";
                n -= p[i];
            }
    }
    return 0;
}

二）直播获奖
NOI2130 即将举行，为了增加观赏性，CCF 决定逐一评出每个选手的成绩，并直播即时的获奖分数线。本次竞赛的获奖率为 w%，即当前排名前 w% 的选手的最低成绩就是即时的分数线。
更具体地，若当前已评出了 p 个选手的成绩，则当前计划获奖人数为 max(1,floor(p×w%))，其中 w 是获奖百分比，floor 表示对 x 向下取整，max(x,y) 表示 x 和 y 中较大的数。如有选手成绩相同，则所有成绩并列的选手都能获奖，因此实际获奖人数可能比计划中多。
作为评测组的技术人员，请你帮 CCF 写一个直播程序。
输入格式
输入文件名为 live.in。
第 1 行两个正整数 n,w。分别代表选手总数与获奖率。
第 2 行有 n 个非负整数，依次代表逐一评出的选手成绩。
输出格式
输出文件名为 live.out。
只有一行，包含 n 个非负整数，依次代表选手成绩逐一评出后，即时的获奖分数线。相邻两个整数间用一个空格分隔。
样例 1 输入
10 60
200 300 400 500 600 600 0 300 200 100
样例 1 输出
200 300 400 400 400 500 400 400 300 300
样例 1 解释
注意，在第 9 名选手的成绩评出以后，计划获奖人数为 5 人，但由于有并列，因此实际会有 6 人获奖。
样例 2 输入
10 30
100 100 600 100 100 100 100 100 100 100
样例 2 输出
100 100 600 600 600 600 100 100 100 100
数据范围与提示
测试点编号    n
1~3           =10
4~6                =500
7~10            =2000
11~17            =10000
18~20            =100000
对于所有测试点，每个选手的成绩均为不超过 600 的非负整数，获奖百分比 w 是一个正整数且 1≤w≤99。
在计算计划获奖人数时，如用浮点类型的变量（如 C/C++ 中的 float、double，Pascal 语言中的 real、double、extended 等）存储获奖比例为 w%，则计算 5×60% 时的结果可能为 3.000001，也可能为 2.999999，向下取整后的结果不确定。因此，建议仅使用整型变量，以计算出准确值。

这题有坑。看上去很简单；
由于每一轮都要马上出分数线，如果采用sort的话，就要反复地sort，那么时间复杂度就变成O(n*n*logn)，严重超时了。
需要有一个“一边输入，一边可以统计，不需要反复排序”的算法。
桶排序和堆排序，都满足条件。
或者采用单调队列，也可以解决问题。
总之，不能采用sort，这就是坑。

#include "bits/stdc++.h"
using namespace std;
int a[1005];
int main()
{
    int n,w;cin>>n>>w;
    for(int i=1;i<=n;i++)
    {
        int t;cin>>t;
        int p=max(1,(int)floor(1.0*i*w/100));
        a[t]++;
        int s;s=0;
        for(int j=1000;j>=0;j--)
        {
            s+=a[j];
            if(s>=p)
            {
                printf("%d ",j);
                break;
            }
        }
        if(s < p) printf("0 ");
    }
    return 0;
}

三）表达式
小 C 热衷于学习数理逻辑。有一天，他发现了一种特别的逻辑表达式。在这种逻辑表达式中，所有操作数都是变量，且它们的取值只能为 0 或 1，运算从左往右进行。如果表达式中有括号，则先计算括号内的子表达式的值。特别的，这种表达式有且仅有以下几种运算：
    与运算：a & b。当且仅当 a 和 b 的值都为 1 时，该表达式的值为 1。其余情况该表达式的值为 0。
    或运算：ab。当且仅当 a 和 b 的值都为 0 时，该表达式的值为 0。其余情况该表达式的值为 1。
    取反运算：!a。当且仅当 a 的值为 0 时，该表达式的值为 1。其余情况该表达式的值为 0。
小 C 想知道，给定一个逻辑表达式和其中每一个操作数的初始取值后，再取反某一个操作数的值时，原表达式的值为多少。
为了化简对表达式的处理，我们有如下约定：
表达式将采用后缀表达式的方式输入。后缀表达式的定义如下：
    如果 E 是一个操作数，则 E 的后缀表达式是它本身。
    如果 E 是 E1 op E2形式的表达式，其中op是任何二元操作符，且优先级不高于 E1、E2 中括号外的操作符，则 E 的后缀式为 E1′ E2′ op，其中 E1′、E2′分别为 E1、E2的后缀式。
    如果 E 是 (E1) 形式的表达式，则 E1后缀式就是 E 的后缀式。

同时为了方便，输入中：
a）与运算符（&）、或运算符（|）、取反运算符（!）的左右均有一个空格，但表达式末尾没有空格。
b）操作数由小写字母 x 与一个正整数拼接而成，正整数表示这个变量的下标。例如：x10，表示下标为 10 的变量 x10。数据保证每个变量在表达式中恰好出现一次。

输入格式
输入文件名为 expr.in。
第一行包含一个字符串 s，表示上文描述的表达式。
第二行包含一个正整数 n，表示表达式中变量的数量。表达式中变量的下标为 1,2,…,n。
第三行包含 n 个整数，第 i 个整数表示变量 xi 的初值。
第四行包含一个正整数 q，表示询问的个数。
接下来 q 行，每行一个正整数，表示需要取反的变量的下标。注意，每一个询问的修改都是临时的，即之前询问中的修改不会对后续的询问造成影响。
数据保证输入的表达是合法。变量的初值为 0 或 1。
输出格式
输出文件名为 expr.out。
输出一共有 q 行，每行一个 0 或 1，表示该询问下表达式的值。
样例 1 输入
x1 x2 & x3 |
3
1 0 1
3
1
2
3

样例 1 输出
1
1
0

样例 1 解释
该后缀表达式的中缀表达式形式为 (x1 & x2) | x3。
对于第一次询问，将 x1 的值取反。此时，三个操作数对应的赋值依次为 0，0，1。原表达式的值为 (0 & 0) | 1 = 1。
对于第二次询问，将 x2 的值取反。此时，三个操作数对应的赋值依次为 1，1，1。原表达式的值为 (1 & 1) | 1 = 1。
对于第三次询问，将 x3 的值取反。此时，三个操作数对应的赋值依次为 1，0，0。原表达式的值为 (1 & 0) | 0 = 0。

样例 2 输入
x1 ! x2 x4 | x3 x5 ! & & ! &
5
0 1 0 1 1
3
1
3
5

样例 2 输出
0
1
1

样例 2 解释
该表达式的中缀表达式形式为 (!x1 )&(!((x2 |x4)&(x3 &(!x5))))。
数据范围与提示
对于 20% 的数据，表达式中有且仅有与运算（&）或者或运算（|）。
对于另外 30% 的数据，s≤1000，q≤1000，n≤1000。
对于另外 20% 的数据，变量的初值全为 0 或全为 1。
对于 100% 的数据，1≤s≤1×10^6，1≤q≤1×10^5，2≤n≤1×10^5。
其中，s表示字符串 s 的长度。

这题需要先建成后缀表达式的树，获得初始化的值；
然后根据修改的值，再逆着树求解。

using namespace std;
vector < int > bcb;
char cs[1000005];
int n,q,qs[100005]= {0};
bool ns[100005]= {0};
bool di(){
    vector < bool > nsi;
    int wi=0;
    while(wi < bcb.size()) {
        int a=bcb[wi++];
        if(a==-1) {
            bool z=nsi.back();
            nsi.pop_back();
            nsi.push_back(!z);
        } else if(a==-2) {
            bool z1=nsi.back();
            nsi.pop_back();
            bool z2=nsi.back();
            nsi.pop_back();
            nsi.push_back(z1&z2);
        } else if(a==-3) {
            bool z1=nsi.back();
            nsi.pop_back();
            bool z2=nsi.back();
            nsi.pop_back();
            nsi.push_back(z1|z2);
        } else {
            nsi.push_back(ns[a]);
        }
    }
    return nsi.back();
}
int main(){
    while(1) {
        char pp[10]= {0};
        scanf("%s",pp);
        if(pp[0]=='x') {
            int ans=0;
            for(int i=1; i < strlen(pp); i++) {
                ans*=10;
                ans+=pp[i]-'0';
            }
            bcb.push_back(ans);
        } else if(pp[0]=='!')bcb.push_back(-1);
        else if(pp[0]=='&')bcb.push_back(-2);
        else if(pp[0]=='|')bcb.push_back(-3);
        else {
            int ans=0;
            for(int i=0; i < strlen(pp); i++)
                ans*=10,ans+=pp[i]-'0';
            n=ans;
            break;
        }
    }
    for(int i=1; i<=n; i++)scanf("%d",&ns[i]);
    cin>>q;
    for(int i=0; i < q; i++) {
        int ads=0;
        scanf("%d",&ads);
        ns[ads]=!ns[ads];
        printf("%d\n",di());
        ns[ads]=!ns[ads];
    }
    return 0;
}

另一位朋友的代码，干净利落：
#define N 100010
using namespace std;

int n,q,tot=100000;
int top,st[N];
int fa[N<<1],son[N<<1][2];
int ans[N<<1];
bool Ans,x[N<<1],id[N<<1],rev[N<<1],opt[N<<1];//1 &,0 |

int init(int u)
{
    if(u<=n)
    {
        x[u]^=rev[u];
        return x[u];
    }
    if(opt[u]) x[u]=init(son[u][0])&init(son[u][1]);
    else x[u]=init(son[u][0])|init(son[u][1]);
    x[u]^=rev[u];
    return x[u];
}

bool dfs(int u,bool v,bool val)
{
    bool tmp;
    if(opt[u]) tmp=x[son[u][v^1]]&val;
    else tmp=x[son[u][v^1]]|val;
    tmp^=rev[u];
    if(u==tot) return tmp;
    if(tmp==x[u]) return Ans;
    if(ans[u]!=-1) return ans[u];
    return (ans[u]=dfs(fa[u],id[u],tmp));
}

int main()
{
    memset(ans,-1,sizeof(ans));
    char ch=getchar();
    while(ch!='\r'&&ch!='\n')
    {
        if(ch=='x')
        {
            int x=0;
            ch=getchar();
            while(ch>='0'&&ch<='9')
            {
                x=(x<<1)+(x<<3)+(ch^'0');
                ch=getchar();
            }
            st[++top]=x;
            continue;
        }
        if(ch=='!') rev[st[top]]^=1;
        if(ch=='&'||ch=='|')
        {
            tot++;
            opt[tot]=(ch=='&');
            fa[st[top]]=tot,id[st[top]]=0,son[tot][0]=st[top],top--;
            fa[st[top]]=tot,id[st[top]]=1,son[tot][1]=st[top],top--;
            st[++top]=tot;
        }
        ch=getchar();
    }
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int tmp;
        scanf("%d",&tmp);
        x[i]=tmp;
    }
    Ans=init(tot);
    scanf("%d",&q);
    while(q--)
    {
        int a;
        scanf("%d",&a);
        printf("%d\n",dfs(fa[a],id[a],x[a]^1));
    }
    return 0;
}

四）方格取数
设有 n×m 的方格图，每个方格中都有一个整数。现有一只小熊，想从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。小熊会取走所有经过的方格中的整数，求它能取到的整数之和的最大值。
输入格式
输入文件名为 number.in。
第 1 行两个正整数 n,m。
接下来 n 行每行 m 个整数，依次代表每个方格中的整数。
输出格式
输入文件名为 number.out。
一个整数，表示小熊能取到的整数之和的最大值。
样例 1 输入
3 4
1 -1 3 2
2 -1 4 -1
-2 2 -3 -1

样例 1 输出
9
样例 1 解释
按上述走法，取到的数之和为 1+2+(-1)+4+3+2+(-1)+(-1)=9，可以证明为最大值。
注意，上述走法是错误的，因为第 2 行第 2 列的方格走过了两次，而根据题意，不能重复经过已经走过的方格。
另外，上述走法也是错误的，因为没有走到右下角的终点。
样例 2 输入
2 5
-1 -1 -3 -2 -7
-2 -1 -4 -1 -2

样例 2 输出
-10

样例 2 解释
按上述走法，取到的数之和为 (-1)+(-1)+(-3)+(-2)+(-1)+(-2)=-10，可以证明为最大值。因此，请注意，取到的数之和的最大值也可能是负数。
数据范围与提示
对于 20% 的数据，n,m≤5。
对于 40% 的数据，n,m≤50。
对于 70% 的数据，n,m≤300。
对于 100% 的数据，1≤n,m≤1000。
方格中整数的绝对值不超过 10^4。

这题数据比较大。
深搜如果简单地仿效《细胞》和CSP在线测试的数星座的话，只能拿到20-30分；
宽搜撑死拿到50分；
记忆化测试需要很仔细的优化，大约可以拿到80-100分。
类似采花生、数搭的方式，作特殊处理的动规，是正解。
using namespace std;
const int maxn = 1050;
const long long inf = 1e18;
int n,m,a[maxn][maxn];
long long f[maxn][maxn];
int main(){
    cin>>n >>m;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            cin>>a[i][j];
    for(int i = 1; i <= n; i ++) f[1][i] = f[1][i - 1] + a[i][1];
    for(int i = 2; i <= m; i ++){
        int s = 0;
        long long mx = -inf;
        for(int j = 1; j <= n; j ++){
            mx = max(mx,f[i - 1][j] - s);
            s += a[j][i];
            f[i][j] = mx + s;
        }
        s = 0,mx = -inf;
        for(int j = n; j >= 1; j --){
            mx = max(mx,f[i - 1][j] - s);
            s += a[j][i];
            f[i][j] = max(f[i][j],mx + s);
        }
    }
    printf("%lld\n",f[m][n]);
    return 0;
}

深搜也是可能的，但是一定要采用记忆化。
#include "bits/stdc++.h"
#define MIN -0x7ffffff
using namespace std;
const int dx[] = {0,1,-1};
const int dy[] = {1,0,0};
int n,m;
int mp[1001][1001];
long long ans[3][1001][1001];
bool visit[1001][1001];
long long dfs(int x,int y,int t)
{

    if(ans[t][x][y] != MIN)return ans[t][x][y];
    if(x == n && y == m)return mp[x][y];
    visit[x][y] = true;
    long long answer = MIN;
    for(int i = 0; i < 3; i++)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(xx < 1 || xx > n ||yy < 1 ||yy > m || visit[xx][yy])
        {
            continue;
        }
        answer = max(answer,dfs(xx,yy,i) + mp[x][y]);
    }
    visit[x][y] = false;
    ans[t][x][y] = answer;
    return ans[t][x][y];
}

int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> mp[i][j],ans[0][i][j] = MIN,ans[1][i][j] = MIN,ans[2][i][j] = MIN;
    cout << max(dfs(1,1,0),max(dfs(1,1,1),dfs(1,1,2)));
    return 0;
}