7-1 子集和问题
#include<iostream>
using namespace std;int n;
int c;
int final=0; //当前元素加到最后一个元素 的总和
int sum=0; //已选元素之和
int a[10000]; //原数组
bool b[10000]; //判断元素选不选bool Backtrack(int t){
if(sum==c) return true; //已找到
if(t>n) return false; //未找到final-=a[t]; //先减去该元素if(sum+a[t]<=c){ //如果 已选元素之和 加上 该元素 小于等于c，则b[t]=true; //选上该元素sum+=a[t]; //已选元素之和 加上 该元素if(Backtrack(t+1)) return true; //下一个元素Backtrack成功 返回truesum-=a[t]; //否则 减回去
}if(sum+final>=c){ //如果 已选元素之和 加上 当前元素加到最后一个元素的总和 大于等于c， 则b[t]=false; //不选当前元素if(Backtrack(t+1)) return true; //下一个元素Backtrack成功 返回true
}final+=a[t]; //加回去
return false; //未找到
}int main(){
cin>>n>>c;
for(int i=0;i<n;i++){cin>>a[i];final+=a[i];
}
if(!Backtrack(0))cout<<"No Solution!"<<endl;
else{for(int i=0;i<n;i++){if(b[i]) cout<<a[i]<<" "; //如果该元素为ture，则输出}
}
return 0;
}
7-2 h0325. ID Codes
#include <iostream>
#include <algorithm>
#include <string>
std::string find_successor(std::string code) {// 从右往左找到第一个非增序的字符int i = code.size() - 2;while (i >= 0 && code[i] >= code[i + 1]) {i--;}// 如果没有非增序的字符，说明已经是最大识别码if (i == -1) {return "No Successor";}// 从右往左找到第一个比code[i]大的字符int j = code.size() - 1;while (code[j] <= code[i]) {j--;}// 交换这两个字符std::swap(code[i], code[j]);// 将i之后的字符逆序排列std::reverse(code.begin() + i + 1, code.end());return code;
}
int main() {std::string code;while (std::cin >> code) {if (code == "#") {break;}std::cout << find_successor(code) << std::endl;}return 0;
}
7-3 h0069. 假币问题
#include <iostream>
#include <cstring>using namespace std;char Left[3][7]; // 天平左边硬币
char Right[3][7]; // 天平右边硬币
char result[3][2]; // 结果bool IsFake(char c, bool light);int main() {int t;cin >> t;while (t--) {for (int i = 0; i < 3; ++i) cin >> Left[i] >> Right[i] >> result[i];for (char c = 'A'; c <= 'L'; ++c) { // 枚举假的硬币，从A-Lif (IsFake(c, false)) {cout << c << " is the counterfeit coin and it is light." << endl;break;} else if (IsFake(c, true)) {cout << c << " is the counterfeit coin and it is heavy." << endl;break;}}}return 0;
}bool IsFake(char c, bool light) {for (int i = 0; i < 3; ++i) {char *pLeft, *pRight; // 指向天平两边的字符串if (light) {pLeft = Left[i];pRight = Right[i];} else { // 如果假设假币是重的，则把称量结果左右对换pLeft = Right[i];pRight = Left[i];}switch (result[i][0]) { // 天平右边的情况case 'u': // 假币为轻的情况下，天平右边翘起来if (strchr(pRight, c) != NULL)return false;break;case 'e':if (strchr(pLeft, c) != NULL || strchr(pRight, c) != NULL)return false;break;case 'd':if (strchr(pLeft, c) != NULL)return false;break;}}return true;
}
7-4 h0108. 三字棋
#include <iostream>
#include <vector>
#include <string>using namespace std;bool isWinning(const vector<string>& board, char player) {bool win;// 检查行for (int i = 0; i < 3; ++i) {win = true;for (int j = 0; j < 3; ++j) {if (board[i][j] != player) {win = false;break;}}if (win) return true;}// 检查列for (int j = 0; j < 3; ++j) {win = true;for (int i = 0; i < 3; ++i) {if (board[i][j] != player) {win = false;break;}}if (win) return true;}// 检查对角线win = true;for (int i = 0; i < 3; ++i) {if (board[i][i] != player) {win = false;break;}}if (win) return true;win = true;for (int i = 0; i < 3; ++i) {if (board[i][2 - i] != player) {win = false;break;}}return win;
}bool isValid(const vector<string>& board) {int countX = 0, countO = 0;for (const string& row : board) {for (char c : row) {if (c == 'X') countX++;if (c == 'O') countO++;}}if (!(countX == countO || countX == countO + 1)) return false; // X总是先手，数量差校验bool xWins = isWinning(board, 'X');bool oWins = isWinning(board, 'O');if (xWins && oWins) return false; // 不可能同时有两个胜者if (xWins && countX != countO + 1) return false; // X赢了应该比O多一步if (oWins && countX != countO) return false; // O赢了X和O应该数量相等return true;
}int main() {int N;cin >> N;vector<string> board(3);string line;getline(cin, line); // 读取N后面的换行符for (int i = 0; i < N; i++) {if (i > 0) getline(cin, line); // 读取每个case之间的空行for (int j = 0; j < 3; j++) {getline(cin, board[j]);}cout << (isValid(board) ? "yes" : "no") << endl;}return 0;
}
7-5 h0224.Strategic game
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=5000;
vector<int>v[maxn];
int n;
int in[maxn];
int vis[maxn];
int dp[maxn][2];
void dfs(int x)
{dp[x][1]=1;dp[x][0]=0;vis[x]=1;for(int i=0;i<v[x].size();i++){if(vis[v[x][i]])continue;int to=v[x][i];dfs(to);dp[x][1]+=min(dp[to][0],dp[to][1]);dp[x][0]+=dp[to][1];}
}
int main()
{while(~scanf("%d",&n)){memset(vis,0,sizeof(vis));memset(in,0,sizeof(in));memset(dp,0,sizeof(dp));for(int i=0;i<=n;i++)v[i].clear();int f,sum,child;for(int i=0;i<n;i++){scanf("%d:(%d)",&f,&sum);while(sum--){scanf("%d",&child);v[f].push_back(child);in[child]++;} }for(int i=0;i<n;i++){if(in[i]==0){dfs(i);printf("%d\n",min(dp[i][1],dp[i][0]));break;}}}
}
7-6 h0330. 大理石在哪里?
//大理石在哪
#include <cstdio>
#include <algorithm>
using namespace std;const int maxn = 10000;int main()
{
int num, ques, x, a[maxn], kase = 0;
while(scanf("%d%d", &num, &ques) == 2 && num){printf("CASE# %d:\n", ++kase);for(int i = 0; i < num; i++)scanf("%d", &a[i]);sort(a, a+num); //排序while(ques --){scanf("%d", &x);int p = lower_bound(a, a+num, x) - a; //在已排序数组a中找xif(a[p] == x)printf("%d found at %d\n", x, p+1);elseprintf("%d not found\n", x);}
}
return 0;
}
7-7 h0172. 方格取数
#include <iostream>
using namespace std;const int N = 15;
int w[N][N], f[2 * N + 1][N][N];int main() {int n;cin >> n;while (1) {int x, y, v;cin >> x >> y >> v;if (x == 0 && y == 0 && v == 0) break;w[x][y] = v;}for (int k = 2; k <= n * 2; k++) for (int i1 = 1; i1 <= n; i1++) for (int i2 = 1; i2 <= n; i2++) {int j1 = k - i1, j2 = k - i2;if (1 <= j1 && j1 <= n && 1 <= j2 && j2 <= n) {// 如果走到了同一位置，只能加一次，否则加两次int t = i1 == i2 ? w[i1][j1] : w[i1][j1] + w[i2][j2];int &v = f[k][i1][i2];v = max(v, f[k - 1][i1 - 1][i2 - 1] + t);v = max(v, f[k - 1][i1][i2 - 1] + t);v = max(v, f[k - 1][i1 - 1][i2] + t);v = max(v, f[k - 1][i1][i2] + t);}}cout << f[n * 2][n][n] << endl;return 0;
}
7-8 h0038. 扫雷游戏
#include<stdio.h>
#include<string.h>
#include<math.h>
int main()
{
int k,i,j,s,p,q,t=0;
char a[11][11],b[11][11];
scanf("%d",&k);
for(i=0;i<k;i++)
{scanf("%s",a[i]);//地雷
}
for(i=0;i<k;i++)
{scanf("%s",b[i]);//踩
}
for(i=0;i<k;i++)
{for(j=0;j<k;j++){if(a[i][j]=='*' && b[i][j]=='x'){t=1;//踩雷了 break;}}
}
for(i=0;i<k;i++)
{for(j=0;j<k;j++){if(b[i][j]=='x') {if(a[i][j]=='*' && t==1)//雷 {printf("*");}else{s=0;p=i==0?0:i-1; for(;p<=i+1 && p<k;p++){q=j==0?0:j-1;for(;q<=j+1 && q<k;q++){if(a[p][q]=='*')//数雷的个数 {s++;}}}printf("%d",s);}}else if(a[i][j]=='*' && t==1){printf("*");//雷 }else{printf(".");}}printf("\n");
}
return 0;
}
