1. A、B两伙马贼意外地在一片沙漠中发现了一处金矿，双方都想独占金矿，但各自的实力都不足以吞下对方，经过谈判后，双方同意用一个公平的方式来处理这片金矿。处理的规则如下：他们把整个金矿分成n段，由A、B开始轮流从最左端或最右端占据一段，直到分完为止。马贼A想提前知道他们能分到多少金子，因此请你帮忙计算他们最后各自拥有多少金子?（两伙马贼均会采取对己方有利的策略）。
代码如下：
#include<iostream>#include<vector>#include<algorithm>using namespace std;int main(){int T = 0;int temp = 0;cin >> T;while(T){++temp;--T;int n = 0;cin >> n;vector<int>vec(n, 0);for (int i=0; i<n; ++i)cin >> vec[i];vector<int>vecsum(n+1, 0);vecsum[0] = 0;for(int i=0; i<n; ++i)vecsum[i+1] = vec[i] + vecsum[i];// 利用动态辅助数组vector<vector<int>>dp(n, vector<int>(n, 0));// 初始化斜对角线和斜对角线下一个数字for(int i=0; i<n; ++i){dp[i][i] = vec[i];if(i<n-1)dp[i][i+1] = max(vec[i], vec[i+1]);}// 初始化剩余的数字for(int j=2; j<n; ++j){for(int i=0; i+j<n; ++i){int sum1 = vecsum[i+j+1] - vecsum[i+1];int sum2 = vecsum[i+j] - vecsum[i];dp[i][i+j] = max(sum1+vec[i]-dp[i+1][i+j], sum2+vec[i+j]-dp[i][i+j-1]);}}cout << "Case #" << temp << ": " << dp[0][n-1] << " "<< vecsum[n] - dp[0][n-1] << endl;}return 0;}
2.小明买了一些彩色的气球用绳子串在一条线上，想要装饰房间，每个气球都染上了一种颜色，每个气球的形状都是各不相同的。我们用1到9一共9个数字表示不同的颜色，如12345则表示一串5个颜色各不相同的气球串。但小明希望得到不出现重复颜色的气球串，那么现在小明需要将这个气球串剪成多个较短的气球串，小明一共有多少种剪法？如原气球串12345的一种是剪法是剪成12和345两个气球串。注意每种剪法需满足最后的子串中气球颜色各不相同（如果满足该条件，允许不剪，即保留原串）。两种剪法不同当且仅当存在一个位置，在一种剪法里剪开了，而在另一种中没剪开。详见样例分析。
代码如下：
#include <bits/stdc++.h>#define maxn 100009using namespace std;int n;int a[maxn], dp[maxn];int cnt[11];const int MOD = 1e9 + 7;int main(){scanf("%d", &n);for(int i = 1; i <= n; i++){scanf("%d", &a[i]);}dp[0] = 1;for(int i = 1; i <= n; i++){memset(cnt, 0 ,sizeof(cnt));for(int j = 0; j < i; j++){cnt[a[i - j]]++;if(cnt[a[i - j]] > 1)break;dp[i] = (dp[i] + dp[i - j - 1]) % MOD;}}printf("%d\n", dp[n]);return 0;}
3.小明同学喜欢体育锻炼，他常常去操场上跑步。跑道是一个圆形，在本题中，我们认为跑道是一个半径为R的圆形，设圆心的坐标为原点(0,0)。小明跑步的起点坐标为(R,0)，他沿着圆形跑道跑步，而且一直沿着一个方向跑步。回到家后，他查看了自己的计步器，计步器显示他跑步的总路程为L。小明想知道自己结束跑步时的坐标，但是他忘记自己是沿着顺时针方向还是逆时针方向跑的了。他想知道在这两种情况下的答案分别是多少。
代码如下：
#include<iostream>#include<vector>#include<algorithm>#include<math.h>using namespace std;#define PI 3.14159265358979323846int main(){double L,R;cin >> L >> R;double peremeter = 2*R*PI;while(L>peremeter)L -= peremeter;double angle = (L/peremeter)*2*PI;if(0<= angle < 0.5*PI){printf("%.3f %.3f\n", R*cos(angle), -1*R*sin(angle));printf("%.3f %.3f\n", R*cos(angle), R*sin(angle));}else if(0.5*PI<= angle < PI){printf("%.3f %.3f\n", -1*R*cos(angle), -1*R*sin(angle));printf("%.3f %.3f\n", -1*R*cos(angle), R*sin(angle));}else if(PI<= angle < 1.5*PI){printf("%.3f %.3f\n", -1*R*cos(angle), -1*R*sin(angle));printf("%.3f %.3f\n", -1*R*cos(angle), R*sin(angle));}else if(1.5*PI<= angle < 2*PI){printf("%.3f %.3f\n", R*cos(angle), R*sin(angle));printf("%.3f %.3f\n", R*cos(angle), -1*R*sin(angle));}return 0;}
选择语
