题目地址：https://oj.splayx.com/vjudge/contest/view.action?cid=4#problem/A
A：水题，一个快速幂搞定。

//tvoj 1116

#include <bits/stdc++.h>
using namespace std;
const int mod = 7;
int powmod(int a, int b){
    int res = 1;
    while(b){
        if(b&1) res = res*a%mod;
        a = a*a%mod;
        b>>=1;
    }
    return res;
}
int main()
{
    int n;
    while(scanf("%d", &n) != EOF)
    {
        int ans = 0;
        for(int i = 1; i <= n; i++){
            int x = powmod(2, i);
            int y = ((i%7)*(i%7))%7;
            if((x-y+7)%7==0) ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

B：显然应该是一个DP。状态表示为 dp[i][0]表示第i天，我们能换得最多的马克，dp[i][1]表示第i天，我们能换得最多的美元。然后转移就非常简单了。

        dp[i][0] = max(dp[i-1][0], dp[i-1][1]*(double)a[i]/100.0);
        dp[i][1] = max(dp[i-1][1], dp[i-1][0]/(double)(a[i])*100.0);

就是美元和马克的相互变换，计算对应的答案。

//tyvj 1095

#include <bits/stdc++.h>
using namespace std;
int n, a[105];
double dp[105][2]; //dp[i][0]表示第i天，我们能换得最多的马克，dp[i][1]表示第i天，我们能换得最多的美元

int main()
{
 scanf("%d", &n);
 for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
 dp[1][0] = a[1];
 dp[1][1] = 100;
 for(int i = 2; i <= n; i++){
 dp[i][0] = max(dp[i-1][0], dp[i-1][1]*(double)a[i]/100.0);
 dp[i][1] = max(dp[i-1][1], dp[i-1][0]/(double)(a[i])*100.0);
 }
 printf("%.2f\n", dp[n][1]);
}

C:行列的交换可以用指示行列的指针来间接交换，或者由于数据水直接暴力也可过。

//tyvj 2012

#include <bits/stdc++.h>
using namespace std;
int a[710][710], row[710], col[710];
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            scanf("%d", &a[i][j]);
        }
    }
    for(int i = 1; i <= n; i++) row[i] = i, col[i] = i;
    while(k--){
        char op[10];
        int x, y;
        scanf("%s%d%d", op, &x, &y);
        if(op[0] == 'R'){
            swap(row[x], row[y]);
        }
        else if(op[0] == 'C'){
            swap(col[x], col[y]);
        }
        else{
            printf("%d\n", a[row[x]][col[y]]);
        }
    }
}

D,相当于树上的分组背包问题。只不过这里没有组里只能取一个的限制，而是可以取多个。我们考虑dp[i][j]表示第i门课程，包括其自身在内选j门子课程的最大收益。那么对于节点i转移比较简单应该是dp[i][j]=max(dp[i][j], dp[i][j-k]+dp[(i的子结点v)][k] k∈[0,j) (不能取k=j，因为至少有一门是先修课v） j倒序循环（分组背包思想）

//tyvj 1051

#include <bits/stdc++.h>
using namespace std;
const int maxn = 410*410;
int n, m, edgecnt, head[410];
int dp[410][410], score[410];
struct edge{
    int v, nxt;
    edge(){}
    edge(int v, int nxt):v(v), nxt(nxt){}
}E[maxn];
void init(){
    edgecnt = 0; memset(head, -1, sizeof(head));
}
void addedge(int u, int v){
    E[edgecnt].v = u, E[edgecnt].nxt = head[v], head[v] = edgecnt++;
}
void dfs(int x){
    dp[x][1] = score[x];
    for(int i = 2; i <= m; i++) dp[x][i] = 0;
    for(int i = head[x]; ~i; i = E[i].nxt){
        int v = E[i].v;
        dfs(v);
        for(int j = m; j; j--){
            for(int k = 0; k < j; k++){
                dp[x][j] = max(dp[x][j], dp[x][j-k]+dp[v][k]);
            }
        }
    }
}
int main(){
    init();
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        int u;
        scanf("%d%d", &u, &score[i]);
        addedge(i, u);
    }
    m++;
    dfs(0);
    printf("%d\n", dp[0][m]);
    return 0;
}

E，线段树区间开根，考虑一个1e12的数，不超过10次可以开到1，所以我们打个lazy标记就可以很快把一个线段缩成一个点，线段树经典套路了。注意l有可能小于r。

//tyvj 1941
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
#define lson l,m,o*2
#define rson m+1,r,o*2+1
namespace segementtree{
    int c[maxn*4];
    long long sum[maxn*4];
    void pushup(int o){
        sum[o] = sum[o*2]+sum[o*2+1];
        c[o] = c[o*2] || c[o*2+1] ? 1 : 0;
    }
    void build(int l, int r, int o)
    {
        if(l == r){
            scanf("%lld", &sum[o]);
            c[o] = sum[o]>1?1:0;
            return;
        }
        int m = (l+r)/2;
        build(lson);
        build(rson);
        pushup(o);
    }
    void update(int L, int R, int l, int r, int o){
        if(!c[o]) return;
        if(l == r){
            sum[o] = sqrt(sum[o]);
            if(sum[o]<=1) c[o]=0;
            return;
        }
        int m=(l+r)/2;
        if(L<=m&&c[o*2]) update(L, R, lson);
        if(m<R&&c[o*2+1]) update(L, R, rson);
        pushup(o);
    }
    long long query(int L,int R, int l, int r, int o){
        if(L<=l&&r<=R) return sum[o];
        int m=(l+r)/2;
        if(R<=m) return query(L, R, lson);
        else if(L>m) return query(L,R, rson);
        else{
            return query(L,m,lson)+query(m+1,R,rson);
        }
    }
}
using namespace segementtree;
int main()
{
    int n, m;
    scanf("%d", &n);
    build(1, n, 1);
    scanf("%d", &m);
    for(int i = 1; i <= m; i++){
        int cmd, l, r;
        scanf("%d%d%d", &cmd, &l, &r);
        if(l>r) swap(l, r);
        if(cmd == 1) printf("%lld\n", query(l, r, 1, n, 1));
        else update(l, r, 1, n, 1);
    }
    return 0;
}