合肥工業大學 程式設計藝術與方法 小組解題報告

僅供參考~
務必獨立思考~
個人實驗報告https://blog.csdn.net/qq_44977889/article/details/106887871

題目A 機器人足球
足球場地長為 100，寬為 20，對方的球門坐標為(100,10)，你要控制一個機器人踢球，初始位置為(x,y)，機器人可以朝任何方向移動，但不能超出場地邊界，當機器人與球門距離不超過 10 時，可以射門，問機器人從初始位置出發到射門，
最少要移動多少距離？(四舍五入到小數點后 3 位)

解題思路：
這道題解題的關鍵就是要求出機器人球員的初始位置和球門坐標的距離，再對這個距離進行判斷是否需要移動，需要移動時計算出移動的距離，

具體解法：
由于球門的坐標是固定的，則可以畫出球場的坐標系，（x,y）表示的是機器人球員的初始位置，從圖中我們可以清楚的看到圓形區域就是球員的可射門區域，可以很直觀的判斷出進行踢球動作時的范圍，
由于是以點為參考單位，可以先建立一個Point類，在輸入球員的初始坐標后，用來初始化一個Point的物件，接著創建一個球門物件，接下來對該球員的初始位置到對方球門的距離進行計算，判斷他們之間的距離d是否大于10(是否在以點（100,10）為圓心，半徑為10的半圓內)，當d<=10時，則球員直接進行踢球動作，否則先使球員移動到可踢球范圍內，通過對球場模型的數學分析，可以得到球員移動的最短距離即為d-10，因此，球員可以踢球需要移動的最短距離等于(x,y)到(100，10)的距離d-10，
由于題目對輸出結果的精度要求為保留三位小數，所以在輸出結果時要注意格式的控制，

代碼實作：
Point類：
class Point{
public:
Point(double X, double Y) {x = X;y = y;};
~Point() {};
double x;double y;
};
主函式：
#include
#include<math.h>
#include
#include “Point.h”
using namespace std;
double distance(Point p,Point center) {
double d;//機器人球員和球門的距離
d = sqrt(pow((p.x - center.x), 2) + pow((p.y - center.y), 2));
return d;
}
int main() {
double x; double y;//機器人球員的坐標
cout << "請輸入機器人球員的坐標（0<=x<=100,0<=y<=20): ";
cin >> x>> y;
Point p(x, y); Point center(100, 10);
double d = distance(p, center);
if (d <= 10)
cout << “此時機器人球員和球門的距離小于10,可以直接射門！” << endl;
else
cout << “此時機器人球員和球門的距離大于10,仍需移動:” << setprecision(3)<<fixed<<d-10 << endl;
system(“pause”);
return 0;
}

運行結果：

題目B 紙牌識別
Alice 沉迷于機器人研究，他打算做一個機器人來檢查一副撲克是否完整，現在，他想請你幫他寫一個程式，來識別紙牌，每張紙牌都有一個花色（四種花色，分 別用大寫字母P，K，H，T 表示）和一個數字點數（1-13），紙牌可以用ABC 的形式來表示，A 代表花色，BC代表數字，如果數字小于10，會有一位補0，比如花色是P，數字是9 的紙牌會表示成P09，一副完整的紙牌有52張牌，四種不同的花色各有1張數字1-13的牌， 你的程式要讀入一個字串，表示缺少的紙牌有哪些，如果包含相同的紙牌（花色數字都相同）輸出GRESKA，否則輸出每種花色剩余的紙牌數量，

解題思路：
對字串進行遍歷，將花色一樣的紙牌放入一個容器，如果放入的時候容器中已存在，則回傳GRESKA，否則放入，最后可以根據每個容器中的數量計算出每種花色剩余數量，

具體解法：
首先建立四個set容器（set容器可以實作快速查找且沒有重復元素）來分別存放四種花色已出現的數字點數，然后用for回圈對字串遍歷，每次遍歷三個字符，根據第一個字符判斷是哪種花色，再將后面兩個字符轉化成整型變數，判斷是否在該花色容器中存在，存在回傳GRESKA，不存在放入容器，遍歷完成分別輸出剩余數量，

代碼實作：
#include
#include
#include
using namespace std;
int main(){
string str;
cout<<“Input:”;
cin>>str;
set setP;
set setK;
set setH;
set setT;
int countP=0;
int countK=0;
int countH=0;
int countT=0;
for(int i=0;i<str.size();i+=3){
if(str[i]==‘P’){
string s=str.substr(i+1,i+2);
int intStr=stoi(s);
if(setP.count(intStr)0){
setP.insert(intStr);
countP++;
}
else
cout<<“GRESKA”<<endl;
}
if(str[i]‘K’){
string s=str.substr(i+1,i+2);
int intStr=stoi(s);
if(setK.count(intStr)==0){
setK.insert(intStr);
countK++;
}
else
cout<<“GRESKA”<<endl;
}
if(str[i] ==‘H’){
string s=str.substr(i+1,i+2);
int intStr=stoi(s);
if(setH.count(intStr)0){
setH.insert(intStr);
countH++;
}
else
cout<<“GRESKA”<<endl;
}
if(str[i]‘T’){
string s=str.substr(i+1,i+2);
int intStr=stoi(s);
if(setT.count(intStr)==0){
setT.insert(intStr);
countT++;
}
else
cout<<“GRESKA”<<endl;
}
}
cout<<13-countP<<" “<<13-countK<<” “<<13-countH<<” "<<13-countT<<endl;
return 0;
}

運行結果：

題目C 卡牌對決
有2N張牌，它們的點數分別為1到2N，Alice拿了其中的N張，Bob拿了剩下的N 張，Alice和Bob會進行N 輪游戲，在每輪游戲中，Alice和Bob各出一張牌，出了的牌不能識訓，在前N/2輪中，每輪誰的牌點數大誰就贏；在后N/2輪中，每輪誰的牌點數小誰就贏，已知Bob每一輪會出什么牌，試求Alice最多能贏多少輪，

解題思路：
這道題類似排列組合問題，Bob的出牌順序是已知的，按照卡牌規則，在前N/2 輪中，每輪誰的牌點數大誰就贏；在后N/2 輪中，每輪誰的牌點數小誰就贏,對Alice的牌按照升序進行排序，然后進行比對，

具體解法：
Alice出的牌用vector1存盤，Bob出的牌按照升序在vector2中存盤，用一個unordered_map存盤卡牌的每一次對決，key為Alice的牌，value為Bob的牌，
對Alice的前N/2的牌進行降序排列，用Alice的前N/2和Bob的后N/2張牌進行pk,通過雙重for回圈進行比較，用Alice的后N/2和Bob的前N/2張牌進行對比，

代碼實作：
#include
#include
#include
#include <unordered_map>
using std::cin;
using std::clog;
using std::cout;
using std::endl;
using std::unordered_map;
using std::vector;
class Solution{
public:
int paxWinNumber(vector vec, int n);
};
int Solution::paxWinNumber(vector vec, int n){
int win_nup = 0;
vector bob{};
unordered_map<int, int> result{};
for (int i = 1; i < 2 * n + 1; i++){
if (std::find(vec.begin(), vec.end(), i) == vec.end()){
bob.push_back(i);
}
}
std::sort(vec.begin(), vec.begin() + n / 2);
for (int j = 0; j < n / 2; j++){
for (int k = j + n / 2; k < n; k++){
if (vec[j] < bob[k]){
result[j] = k;
break;
}
}
}
std::sort(vec.begin() + n / 2, vec.end());
for (int p = 0; p < n / 2; p++){
for (int q = p + n / 2; q < n; q++){
if (vec[q] > bob[p])
{
result[q] = p;
break;
}
}
}
return result.size();
}
int main()
{
int n = __cplusplus;
clog << "please input a even, n: " << endl;
if (!(cin >> n) || n % 2 != 0)
exit(EXIT_SUCCESS);
vector alice{};
int cart_number = 0;
clog << "please input Alice cart " << endl;
for (int i = 0; i < n; i++)
{
if (!(cin >> cart_number) || cart_number > 2 * n)
exit(EXIT_SUCCESS);

    alice.push_back(cart_number);
}

Solution solu;
cout << "most numbers to win is " << solu.paxWinNumber(alice, n) << endl;
return 0;

}

運行結果：

題目D自駕游
P 省有N 個城市，編號分別為1…N，煩煩家住1 號城市，N 號城市是省會，P省的交通非常發達，有M 條有向的高速公路連接這N 個城市，第i 條高速公路(1<=i<=M)從城市ui 連向城市vi，
這天，煩煩想自己開車從家前往省會城市游玩，煩煩是個做事很細致的人，為了有備無患，她決定同時開著heroMap 和amap 這兩個不同的導航軟體來幫助自己完成這次旅程，這兩個導航軟體內部采用了不同的演算法，對于第i 條高速公路（1<=i<=M），heromap 認為通過時間為Pi 分鐘，amap 則認為通過時間為Qi 分鐘，這兩個導航軟體會根據自己的資料來計算從當前位置到目標位置所需的最短時間是多少，對于第i 個城市(1<=i<=N)，記heromap 認為從i 到N
的最短時間為hero(i)，記amap 認為i 到N 的最短時間為a(i)，煩煩開車途徑某條高速公路(1<=i<=M)時，如果heromap 認為從ui 到N 不應該走這條路，即hero(vi)+Pi>hero(ui)，則發出一次警告，同樣的，如果amap 認為從ui 到N 不應該走這條路，即a(vi)+Qi>a(ui)，也會發出一次警告，現在煩煩希望自己選擇一條路徑，使得受到的警告總數最少，請你編程解決這一問題，

解題思路
此題可理解為帶權值有向圖；耗時最短即為到達目的地的最短路徑,通過Dijkstra演算法確定不同軟體的最短路徑,然后求出兩條不同的最短路徑發出警報次數，最后選取發出警報次數少的路徑，通過題目條件hero(vi)+Pi>hero(ui) 和 a(vi)+Qi>a(ui)再次運用Dijkstra演算法求出兩條不同的最短路徑發出警報次數

具體解法：
宣告一個結構體node用于表示城市ui高速公路所連接的下一城市vi以及之間的距離，分別用Dijkstra演算法求出使用兩個不同導航軟體時的最短路徑并將距離分別存入兩個不同陣列，比較兩個路徑的距離，選取最短的一個，再用Dijkstra演算法判斷該路線中每個節點用另一個導航軟體到終點的最短路徑中的下一節點是否相同，若不相同則警報次數加一，

代碼實作：
#include ;
#include ;
#include ;
using namespace std;
const int maxn = 100;
const int maxm = 100;
const int inf = 999999;
int N, M;//點 邊

struct edge {
int amap;
int hero;
int next;
int to;
};

struct new_edge {
int to;
int dis;
};

edge e[maxm];

vector<new_edge> v[maxn];

int cnt, head[maxn], dist_1[maxn], dist_2[maxn], dist_3[maxn];
bool mark[maxn]; //標記點

inline void add_edge(int ui, int vi, int Pi, int Qi) { //行內函式
cnt++;
e[cnt].to = ui;
e[cnt].hero = Pi;
e[cnt].amap = Qi;
e[cnt].next = head[vi];
head[vi] = cnt;
}

struct node {
int dis;
int pos;
bool operator <(const node& x)const { //運算子多載函式
return x.dis < dis;
}
};
priority_queueq; //優先佇列，在佇列基礎上添加了一個內部排序

void dij1(int s) {
fill(dist_1, dist_1 + maxn, inf);//容器填充：將inf從d1開始填充至d1+maxn；距離初始化為inf
dist_1[s] = 0;//本身距離為0
q.push(node{ 0, s }); //將最短距離和點存入佇列
while (!q.empty()) {
node tmp = q.top();
q.pop();
int x = tmp.pos;//點
mark[x] = true; //標記
for (int i = head[x]; i; i = e[i].next) {
int y = e[i].to;
if (dist_1[y] > dist_1[x] + e[i].hero) {
dist_1[y] = dist_1[x] + e[i].hero;
if (!mark[y]) {
q.push(node{ dist_1[y], y });
}
}
}
}
}

void dij2(int s) {
fill(mark, mark + maxn, false);
fill(dist_2, dist_2 + maxn, inf);
dist_2[s] = 0;
q.push(node{ 0, s });
while (!q.empty()) {
node tmp = q.top();
q.pop();
int x = tmp.pos;
mark[x] = true;
for (int i = head[x]; i; i = e[i].next) {
int y = e[i].to;
if (dist_2[y] > dist_2[x] + e[i].amap) {
dist_2[y] = dist_2[x] + e[i].amap;
if (!mark[y]) {
q.push(node{ dist_2[y], y });
}
}
}
}
}

void dij3(int s) {
fill(mark, mark + maxn, false);
fill(dist_3, dist_3 + maxn, inf);
dist_3[s] = 0;
q.push(node{ 0, s });
while (!q.empty()) {
node tmp = q.top();
q.pop();
int x = tmp.pos;
mark[x] = true;
for (int i = 0; i < v[x].size(); i++) {
new_edge tmp2 = v[x][i];
int y = tmp2.to;
if (dist_3[y] > dist_3[x] + tmp2.dis) {
dist_3[y] = dist_3[x] + tmp2.dis;
if (!mark[y]) {
q.push(node{ dist_3[y], y });
}
}
}
}
}

int main() {
cin >> N >> M;//點 邊
for (int i = 1; i <= M; i++) {
int ui, vi, Pi, Qi;
cin >> ui >> vi >> Pi >> Qi;
add_edge(ui, vi, Pi, Qi);
}
dij1(N);//找到最短路徑，將節點存入佇列
dij2(N);
for (int i = 1; i <= N; i++) {
for (int j = head[i]; j; j = e[j].next) {
new_edge tmp;
tmp.dis = 0;
if (dist_1[i] + e[j].hero > dist_1[e[j].to])tmp.dis++;
if (dist_2[i] + e[j].amap > dist_2[e[j].to])tmp.dis++;
tmp.to = i;
v[e[j].to].push_back(tmp);
}
}
dij3(1);
cout << dist_3[N];
return 0;
}
運行結果：

題目E現代藝術
給出平面上N個點的坐標點集，求這N個點有多少條整體對稱軸，整體對稱軸是指一條直線，對于每個點，都能找到點集中的一個點 與他關于這條直線對稱，求對稱軸數量

解題思路
利用找凸包的方法，找到點集的凸包，獲得點集的中心點，橫坐標為所有點的橫坐標之和的平均數，縱坐標為所有點縱坐標之和的平均數，以點集的中心點和凸包中每相鄰兩點的中點連成的直線作為對稱軸，判斷該對稱軸和這相鄰兩點的連線是否垂直，垂直則說明該對稱軸就是點集的整體對稱軸，否則不是點集的整體對稱軸，

具體解法：
創建一個Point型別的陣列p[]，用來存盤點集，并在輸入點集資料的時候計算得到中心點center的坐標,為了方便凸包的尋找，將點集中的資料進行排序，這里用到的排序演算法中的比較函式，是自定義的turn函式（根據叉積來進行排序），將以上操作完成之后就可以進行凸包的尋找，
在尋找凸包時，先建立一個Point型別的陣列temp[]，用來儲存凸包中的點，利用掃描法，根據角度判斷是否入堆疊，進而得到凸包，經過上面操作后，temp[]陣列中的點全部是凸包中的點，將凸包中的點兩兩組合，以每兩點的中點與中心點center之間的連線為軸，如果該軸為這兩點連線的中垂線，則說明該軸為點集的整體對稱軸，反之則不是，由于點的組合可能會重復,如(p1,p2)與（p2,p1），導致求出的對稱軸可能會重復，這時候利用set容器的元素不可重復性，將對稱軸的斜率存入set容器中，得到的set容器的size就是整體對稱軸的條數，

代碼實作：
Point類：
class Point{
public:
Point() {};
Point(int X, int Y) { x = X; y = Y; }
~Point() {};
int x;int y;
};
主函式：
#include
#include
#include
#include"Point.h"
#define MAX 1000
#define maxK double(1e8)//表示斜率不存在時的情況
Point p[MAX];
Point temp[MAX];
using namespace std;
set k;
/求兩個點之間的距離/
double getDistance(Point a, Point b) {
return sqrt(pow((a.x - b.x), 2) + pow((a.y - b.y), 2));
}
/求兩個向量的叉積，如果為正則為逆時針方向，如果為負則為順時針方向，在這里a為兩個向量的公共點/
double getCross(Point a, Point b, Point c) {
int x1 = b.x - a.x;
int y1 = b.y - a.y;
int x2 = c.x - a.x;
int y2 = c.y - a.y;
return x1y2- y1x2;
}
/求兩個點連成直線的斜率，需要分三種情況討論/
double getK(Point a, Point b) {
if (a.y == b.y)//平行于x軸，斜率為0
return 0;
else if (a.x == b.x)//垂直于x軸，斜率不存在
return maxK;//這里用一個很大的值表示斜率不存在的情況
else
return (b.y - a.y) / (b.x - a.x);
}
/在對點集排序時將會用到的一個函式，根據叉積來判斷排序的方式/
bool test(Point a, Point b) {
bool result= getCross(p[0], a, b);
if (result == 0)
return getDistance(a, p[0]) < getDistance(b, p[0]);
else
return getCross(p[0], a, b) > 0;
}
/將點按照縱坐標由低到高排序，當縱坐標相同時比較橫坐標，根據test進行排序/
void turn(int N) {
for (int i = 1; i < N; i++) {
if ((p[i].y < p[0].y))
swap(p[i], p[0]);
else if (p[i].y == p[0].y && p[i].x < p[0].x)
swap(p[i], p[0]);
}
sort(p + 1, p + N, test);
}
int main() {
int N;
cin >> N;
/求凸包時用到的中心點，中心點的位置用所有點的位置的平均值表示/
Point center;
center.x = 0; center.y = 0;
for (int i = 0; i < N; i++) {
cin >> p[i].x >> p[i].y;
center.x = (center.x + p[i].x);
center.y = (center.y + p[i].y);
}
center.x=center.x/N;center.y=center.y/N;//中心點的坐標
turn(N);//根據位置資訊對點集進行排序
/將符合條件的點放入堆疊中,定義一個陣列用來存盤凸包中的元素，num是堆疊頂元素的序號/
temp[0] = p[0]; temp[1] = p[1];
int num = 1;
for (int i = 2; i < N; i++) {
while (getCross(temp[num - 1], temp[num], p[i]) <= 0 && num >=1)//角拐向左側，該點就不符合條件
num–;//彈堆疊
num++;//壓堆疊
temp[num] = p[i];
}
//經過以上操作以后temp陣列中的點全部是凸包中的點
for (int i = 0; i <= num; i++) {
for (int j = i + 1; j <= num; j++) {
Point point;//用來存盤凸包中兩個元素的中點
point.x = (temp[i].x + temp[j].x) / 2;
point.y = (temp[i].y + temp[j].y) / 2;
/此時由數學知識可得，經過中心點的凸包上的中垂線即為整體對稱軸/
if ( (temp[i].x - temp[j].x)* (point.x - center.x) + (temp[i].y - temp[j].y) (point.y - center.y) ==0){
if (point.x == center.x && point.y == center.y)
k.insert(getK(temp[i], temp[j]));
else {
k.insert(getK(point, center));
}
}
}
}
if (k.size() == 1)
cout << k.size() + 1 << endl;
else
cout << k.size() << endl;
system(“pause”);
return 0;
}

題目F 領家割草
鄰居Alice家有一塊大草坪，每隔一段時間他都要用割草機修剪草坪；可以把草坪看成是一個NM的矩陣，割草時需要N 臺割草機水平方向穿過草地，M臺割草機垂直方向穿過草地，草地并不是完全平整的，有高有低；如圖所示，高的地方用深色表示，矮的地方用淺色表示，割草機作業時需要消耗燃油，在走過不同高度的草地時，會消耗A元燃油燃油費；(比如從低的地方走到高的地方，從高的地方走到低的地方，在相同高度的地塊上運行割草機的燃油消耗可以忽略），Alice 為了節省燃油費，準備改造一些地形；可以給一些地塊加土來升高地形，或者把高的地方鏟平來降低地形高度，對一個地塊進行改造要花費B 元，你能幫鄰居Alice設計一個方案，讓他花費最小嗎？

解題思路：
可以通過最大流最小割演算法，但我是通過回圈對每一塊地的費用進行比較，選擇一個花費最少的策略，然后再次回圈，直到沒有土地改變狀態為止，

具體解法：
用一個vector<vector> grass_map存盤原始地圖，然后對每一塊土地進行遍歷，比較土地的兩種策略所需的費用，那一個費用少就使用那一種策略，把所有的土地遍歷完成之后，再次遍歷，直到沒有土地更改為止，這樣就防止了區域最優而不一定全域最優的缺陷，

代碼實作：
#include
#include
using std::cin;
using std::cout;
using std::endl;
using std::vector;

int n = __cplusplus;
int m = __cplusplus;
int a = 0;
int b = 0;
bool is_end = false;

class Solution
{
public:
vector<vector> MinMap(vector<vector> grass);
int OnePointPrice(vector<vector> &grass, int row = 0, int column = 0, bool change = false);
int MinPrice(vector<vector> &end_grass, vector<vector> &grass);
};

vector<vector> Solution::MinMap(vector<vector> grass)
{

is_end = true;

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < m; j++)
    {
        if (OnePointPrice(grass, i, j, false) > OnePointPrice(grass, i, j, true))
        {
            is_end = false;
            if (grass[i][j] == '#')
                grass[i][j] = '.';
            else
            {
                grass[i][j] = '#';
            }
        }
    }
}
return grass;

}

int Solution::OnePointPrice(vector<vector> &grass, int row, int column, bool change)
{
int price = 0;
if (!change)
{
if (row > 0)
{
if (grass[row][column] != grass[row - 1][column])
price = price + a;
}
if (row < n - 1)
{
if (grass[row][column] != grass[row + 1][column])
price = price + a;
}
if (column > 0)
{
if (grass[row][column] != grass[row][column - 1])
price = price + a;
}
if (column < m - 1)
{
if (grass[row][column] != grass[row][column + 1])
price = price + a;
}
}
else
{
price += b;

    if (row > 0)
    {
        if (grass[row][column] == grass[row - 1][column])
            price = price + a;
    }
    if (row < n - 1)
    {
        if (grass[row][column] == grass[row + 1][column])
            price = price + a;
    }
    if (column > 0)
    {
        if (grass[row][column] == grass[row][column - 1])
            price = price + a;
    }
    if (column < m - 1)
    {
        if (grass[row][column] == grass[row][column + 1])
            price = price + a;
    }
}

return price;

}

int Solution::MinPrice(vector<vector> &end_grass, vector<vector> &begin_grass)
{
int min_price = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (end_grass[i][j] != begin_grass[i][j])
{
min_price += b;
}
if (i > 0)
{
if (end_grass[i][j] != end_grass[i - 1][j])
min_price += a;
}
if (j > 0)
{
if (end_grass[i][j] != end_grass[i][j - 1])
min_price += a;
}
}
}

return min_price;

}
int main()
{
if (!(cin >> n >> m >> a >> b))
{
std::clog << “input isn’t suitable” << endl;
exit(EXIT_SUCCESS);
}
vector<vector> grass_map(n);
for (int i = 0; i < grass_map.size(); i++)
grass_map[i].resize(m);

char c = ' ';
for (int i = 0; i < n; i++)
{
    for (int j = 0; j < m; j++)
    {
        cin >> c;
        grass_map[i][j] = c;
    }
}
Solution solu;
auto result = grass_map;
while (!is_end)
{
    result = solu.MinMap(result);
}
cout << endl
     << solu.MinPrice(result, grass_map) << endl;
return 0;

}

運行結果：

題目 G 括號序列
括號序列是指由‘(’和‘)’組成的序列，假如一個括號序列中，包含相同數量的左括 號和右括號，并且對于每一個右括號，在他的左側都有左括號和他匹配，則這個 括號序列就是一個合法括號序列，比如(())()就是一個合法括號序列，但 (())(()不是合法括號序列， 給出兩個長度相同的合法括號序列A 和B，那么A < B當且僅當：A 和B至少有一位不相同，在A 和B從左往右數第一個不相同的位置i，A[i]=(，B[i]=) 比如A = (())()，B = ()()()，則A < B，因為從左邊數第一個不相同的 是第二個字符，A[2] = (,B[2] = )，對于長度 N，由于定義了小于關系， 則可以通過這個關系推出所有長度為 N 的合法括號序列的大小關系，對于長度 為6的合法括號序列，從小到大排列順序如下： 1.((())) 2.(()()) 3.(())() 4.()(()) 5.()()() 給出N和M，求長度為N的合法括號序列中，第M 小的合法括號序列是？

解題思路
第一步是根據合法序列的定義將所有的合法序列找出來放入容器中，然后將容器中的元素冒泡排序，直到找到第M小的元素，

具體解法：
首先創建一個string型別的vector容器，來存放所有合法序列，然后寫一個fun函式將‘（’和‘）’全排列，并將其中合法序列push到vector中，最后寫一個compare函式對vector中元素排序找到第M小的元素，

代碼實作：
#include
#include
#include
using namespace std;
void fun(int tag,string result,int count1,int count2,int N,vector &all)
{//該函式用來找到所有的合法序列，并放到vector中
int nexttag=tag+1;
for(int i=1;i<=2;i++){
if(i1)//1表示當前result[tag]是（
{
if(count1N/2)
continue;
else{
string s=result;
s.push_back(’(’);
int count_1=count1+1;
if(nexttagN)
all.push_back(s);
else
fun(nexttag,s,count_1,count2,N,all);//遞回呼叫
}
}
if(i2)//1表示當前result[tag]是）{
if(count1<=count2)
continue;
else {
string s=result;
s.push_back(’)’);
int count_2=count2+1;
if(nexttag==N)
all.push_back(s);
else
fun(nexttag,s,count1,count_2,N,all);
}
}
}
}
void compare(vector all,int M){
//該函式用來找到第M小的序列
//可以直接用AscaII順序
for(int i=0;i<M;i++){
int min=all.size()-1;
for(int j=all.size()-2;j>=i;j–){
if(all[min]<all[j]){
string temp=all[j];
all[j]=all[min];
all[min]=temp;
}
}
}
cout<<all[M-1]<<endl;
}
int main(){
vector all;//用來存放合法序列
int N,M;
cin>>N>>M;
string result;//一種可能序列
result.reserve(N);
result.push_back(’(’);
int count1=1;//計數（已用的個數
int count2=0;//計數）已用的個數
fun(1,result,count1,count2,N,all);
compare(all,M);
return 0;
}

運行結果：

題目 H 不要回文
給出一個字串S，你需要盡可能少的修改S 中的字符，使得S 不包含長度大于等于2 的回文子串，

解題思路
通過第i和i+1以及第i和i+2是否相等判斷是否存在回文；存在則修改并計數

具體解法：
將字串轉化成整形并存盤于陣列中，首先通過temp[i] == temp[i + 2]判斷相鄰三個字符是否存在回文，若存在則通過temp[i] == temp[i - 1]判斷修改第一個還是修改最后一個字符；通過temp[i] == temp[i + 1]判斷兩兩相鄰是否存在回文，若存在則修改第一個，遍歷陣列，
代碼實作：
#include
using namespace std;
int temp[30], num = 0;//計數

int t = 26;//修改字符
string s;
int main() {
cin >> s;
int len = s.length();
//字串轉化成整形并存盤于陣列中
for (int i = 0; i < len; i++) {
temp[i + 1] = s[i] - ‘a’ + 1;
}
for (int i = 1; i <= len; i++) {
//判斷相鄰三個字符是否存在回文
if (temp[i] == temp[i + 2]) {
//判斷修改第一個還是最后一個
if (temp[i] == temp[i - 1]) {
temp[i] = t++;
num++;
}
else
temp[i + 2] = t++, num++;
}
}
//判斷兩兩相鄰是否存在回文
for (int i = 1; i <= len; i++) {
if (temp[i] == temp[i + 1]) {
temp[i + 1] = t++;
num++;
}
}
cout << num;
return 0;
}
運行結果：

題目I 你的名字
Alice想要計算他那N只貓的名字的價值.每只貓的名字由不超過1000個大小寫字母構成，沒有一個名字是空字體串，Alice 有一張“價值字串表”，上面有M個代表價值的字串.每個字串由不超過30個大小寫字母構成，同樣不存在空字串，一個貓的名字蘊含多少個價值字串，這個名字就有多少價值，所謂“蘊含”，是指某個能量字串的所有字符都在名字串中按順序出現（不一定一個緊接著一個），所有的大寫字母和小寫字母都是等價的，比如，在貝茜的名字“Bessie”里，蘊含 有“Be”“si”“EE”以及“Es”等等字串，但不蘊含“Ls”或“eB”，請幫Alice 計算他的貓的名字的價值，

解題思路：
由于在比較時不考慮大小寫的區別，則將貓的名字和價值字串先轉化為小寫再進行比較，比較時采用傳統的方法，將價值字串和每只貓的名字進行匹配，匹配成功就做一個標記，

具體解法：
先創建catName、valueString來存盤貓的名字和價值字串，輸入的第一行是兩個整數 N（N 行，每行一個字串表示貓的名字）、M （M 行，每行一個價值字串 ），然后輸入貓的名字（每個名字全部轉化為小寫之后再存入容器catName內），輸入價值字串（每個價值字串轉化為小寫之后再存入容器valueString內），
要判斷是否蘊含價值字串，就要從每個價值字串的第一個字符開始，從前往后單個字母的比對，每找到一個，count++，再繼續判斷下一個字符，這個字串判斷完畢后，最后判斷count的值和該價值字串的長度是否相等，相等則蘊含該價值字串，不相等則不蘊含，如此即可計算出貓的名字的價值，

代碼實作：
#include
#include
#include
#include
using namespace std;
vectorcatName;//貓的名字
vectorvalueString;//價值表
vector::iterator it;
vector::iterator iter;
int main() {
int N;//這N行,每行一個字串用來表示貓的名字
int M;//這M行,每行一個價值字串
cin >> N >> M;
int *value= new int[N];//用來存盤每只貓名字中價值字串的個數
/輸入貓的名字/
for (int i = 0; i < N; i++) {
string name;
cin >> name;
/由于在比較價值字串時，不區分大小寫，因此將貓的名字全部轉化為大小或者小寫，方便進行比較，此處轉化為小寫/
transform(name.begin(), name.end(), name.begin(), ::tolower);//這里用到了STL中的一個模板函式
value[i] = 0;
catName.push_back(name);
}
/輸入價值字串/
for (int i = 0; i < M; i++) {
string value;
cin >> value;
transform(value.begin(), value.end(), value.begin(), ::tolower);
valueString.push_back(value);
}
/接下來進行字串的匹配/
int num = 0;//用于方便記錄貓的價值陣列的下標
for (it = catName.begin(); it != catName.end(); it++) {
for (iter = valueString.begin(); iter != valueString.end(); iter++) {
/要判斷是否蘊含價值字串，就要從價值字串的第一個字符開始，從前往后單個字母的比對，每找到一個，
count++,最后判斷count的值和該價值字串的長度是否相等，相等則蘊含該價值字串，不相等則不蘊含/
int count=0;
for (int i = 0; i < (*iter).length();i++ ) {
for (int j = 0; j < (*it).length(); j++) {
if ((*it).substr(j, 1) == (*iter).substr(i, 1)) {//這個字符匹配成功
count++;
if (count == (*iter).length())
value[num]++;
i++;//下一個字符
}
}
}
}
num++;
}
/輸出每只貓名字蘊含多少個價值字串/
for (int i = 0; i < N; i++)
cout << value[i] << endl;
system(“pause”);
return 0;
}

運行結果：

題目J 密信
Alice 想給Bob發短信，短信的內容可以看成是一個只有小寫字母的字串p； 為了加密短信，Alice需要只有小寫字母長度為n的字串h，并且p是h的子 串；Alice 想知道，這樣的字串有多少種，給出n和M還有字串p，假設一共有K種不同的h，輸出K mod M，

解題思路：
第一步將26個字母以給定的n位全排列，找到所有n位字符的字串，第二步，對這些字串進行判斷，如果字串中包含字串ab則計數，最后可以得到所有h的個數，

具體解法：
首先用while回圈分別測驗每組，count表示h的個數，adress函式是n位字符的所有可能的字串，具體就是遍歷26個字母，來表示第tag位可能的字符，然后遞回呼叫來依次確定后面位的字符，從而找到所有可能的字串，isSub函式是判斷該種字串是否包含子串p，包含回傳true且count++；

代碼實作：
#include
#include
using namespace std;
bool isSub(string s1,string s2){
string::size_type idx;
idx=s1.find(s2);
if(idxstring::npos)
return false;
else
return true;
}
void adress(string s,string result,long &count,int n,int tag){
if(tagn){
if(isSub(result,s))
count++;
}
else{
for(char i=‘a’;i<=‘z’;i++){
string r=result;
r.push_back(i);
adress(s,r,count,n,tag+1);
}
}
}
int main(){
int T;
cin>>T;
while (T–){
int n;
int M;
cin>>n>>M;
string s;
cin>>s;
string result;
long count=0;
adress(s,result,count,n,0);
cout<<count%100<<endl;
}
return 0;
}

運行結果：

題目K 福報
員工績效評估對于任何公司都是很重要的，在績效考核中，員工會就最近完成的作業撰寫作業反饋，反饋會被遞給他們的上級，然后上級根據收到的反饋來決定績效，
Alice負責一家知名公司工程部門的績效考核系統，該部門遵循樹形結構，每位員工都有一個直接上級，最上級是部門總監，讓上級評估其直接下屬的表現并不是很有效，經過深入研究，Alice想出了一個新的績效考核系統，主要思路是在現有的公司結構中補充每個員工的技術等級，
新的績效評估流程如下，員工要準備他們的作業反饋，然后向所有比他技術等級高的上級（直接上級和間接上級）遞交作業反饋；上級需要花時間審核所有遞交給他的作業反饋，Alice對這個新系統感到非常滿意，但她不確定這在實踐中是否可行，她想知道每個員工審核下屬作業反饋所需的時間，你能幫她嗎？

解題思路：
創建一個員工樹，每個員工結點包含當自身結點的編號，上級結點的編號，技術等級，審核他的作業需要的時間，和他的孩子結點，然后 BFS每個員工 （注意等級高的員工(A) 也可能是等級低的員工(B)的子節點，在BFS程序中，在算A審核所需時間的時候，不可以加上B審核所需的時間）

具體解法：
創建一個員工樹，每個員工結點包含當自身結點的編號，上級結點的編號，技術等級，審核他的作業需要的時間，和他的孩子結點，然后 BFS每個員工（注意等級高的員工(A) 也可能是等級低的員工(B)的子節點，在BFS程序中，在算A審核所需時間的時候，不可以加上B審核所需的時間），比較偶然的是，員工號從0開始遞增，和vector儲存方式相同，可以安裝順序去初始化結點，這個員工數不是絕對的樹，父節點里只儲存孩子結點，沒有儲存孫子結點，

代碼實作：
#include
#include
#include
using std::queue;
using std::vector;
using std::cout;
using std::cin;
using std::endl;

int e = 0; // staffs number

struct Node
{
int mi = 0; // 上級節點編號
int ri = 0; // 等級
int ti = 0; // 審核該結點所需的時間
int itself = 0; // 自身節點的編號
vector child {}; // 孩子節點集合
Node(int m, int r, int t, int i) : mi(m), ri?, ti(t), itself(i){ };
};

class Solution
{
public:
Node Initialize(vector<vector > vec, int num);
int BFS(vector &node_staffs, int n);
};

// 初始化編號為 it_num的節點

Node Solution::Initialize(vector<vector > vec, int it_num)
{
Node node(vec[it_num-1][0], vec[it_num-1][1], vec[it_num-1][2], it_num);
for(int i = 0; i < e; i++)
{
if(vec[i][0] == it_num)
{
node.child.push_back(Node(it_num, vec[i][1], vec[i][2], i+1));
}
}
return node;
}

int Solution::BFS(vector &node_staffs, int n)
{
queue que{};
int time = 0;
que.push(node_staffs[n-1]);
int grade = node_staffs[n-1].ri;
while (!que.empty())
{
Node temp = que.front();
que.pop();
if(temp.ri < grade)
time += temp.ti;
auto childs = temp.child;

    for(int i = 0; i < childs.size(); i++)
    {    
        que.push(node_staffs[childs[i].itself - 1]);
    }
 
}   
return time;

}
int main()
{

int information = 0;
if(!(cin >> e))
{
    std::clog << "input is not suitable " << endl;
    exit(EXIT_SUCCESS);
}

vector<vector<int> > staffs(e);
for(int i = 0; i < e; i++)
{
    staffs[i].resize(3);
}
for(int i = 0; i < e; i++)
{
    for(int j = 0; j < 3; j++)
    {
        cin >> information;
        staffs[i][j] = information;
    }
}

vector<Node> node_staffs {};
Solution solu;

// initialize node
for(int i = 1; i <= e; i++)
{
    auto m = solu.Initialize(staffs, i);
    node_staffs.push_back(m);
}

// BFS node
for(int i = 1; i <= e; i++)
{
    cout << solu.BFS(node_staffs, i) << endl;
}
return 0;

}
運行結果：

題目L 曲奇工廠
曲奇工廠是一個經典好玩的益智游戲，游戲中你的目標是生產至少C 塊曲奇；
游戲的規則十分簡單；游戲開始時你有0 塊曲奇，每分鐘可以手作業出S 塊曲奇，你也可以從N 個工廠中選擇一些買下來；工廠依次編號為1-N，買下第i 個
工廠需要花費Ai 個曲奇餅，但是工廠會為你帶來更多收益，買下第i 個工廠后，
每分鐘曲奇產出會增加Bi 塊，對于每個工廠，你只能買一次；你只能在整數分鐘時購買工廠，并且可以一次買
多個工廠，請問達成目標所用最短時間是多少？
解題思路
貪心策略，運用深搜演算法遍歷所有情況取最優，
具體解法：
運用DFS遍歷所有結果，每遍歷完成一次，用calc函式計算所需的時間，并且更新所需的最少時間，
代碼實作：
#include
#include
using namespace std;
const int N = 10;
int n, c, s, cnt;
int f[N];
struct {
int x, y;
} a[N], b[N], d[N];
int ans;

int calc(int n) {
int sum = 0, v = s, ans = 0;
for (int i = 1; i <= n; i++) {
if (sum < d[i].x) {
int t = (d[i].x - sum + v - 1) / v;
sum += t * v;
ans += t;
}
sum -= d[i].x;
v += d[i].y;
}
if (sum < c) ans += (c - sum + v - 1) / v;
return ans;
}

void dfs(int now) {
if (now > n) {
for (int i = 1; i <= cnt; i++) f[i] = i;
do {
for (int i = 1; i <= cnt; i++) d[i] = b[f[i]];
ans = min(ans, calc(cnt));
} while (next_permutation(f + 1, f + 1 + cnt));
}
else {
dfs(now + 1);
b[++cnt] = a[now];
dfs(now + 1);
–cnt;
}
}
int main() {
scanf_s("%d%d%d", &n, &c, &s);
for (int i = 1; i <= n; i++)
scanf_s("%d%d", &a[i].x, &a[i].y);
ans = (c + s - 1) / s;
dfs(1);
printf("%d\n", ans);
}
運行結果：