注：以下题目与代码来源于各种渠道

第0章 C++常用函数与头文件

1. 算法 #include <algorithm>

如果使用了 using namespace std; 下面的std都可以不用写。

函数	作用	示例
std::max(a, b)	返回最大值	int max = std::max(a,b)
std::min(a, b)	返回最小值	int min = std::min(a,b)
std::abs(a)	返回绝对值	int b = std::abs(a)
std::swap(a, b)	交换a与b的值	std::swap(a,b)
std::reverse(begin, end)	逆转begin到end的元素	int a[4]={1,2,3,4}; std::reverse(a,a+4); std::string str = "abc"; reverse(str.begin(),str.end());
std::fill(begin, end, x)	将begin到end中的元素都填充为x	int a[4]; std::fill(a, a+4, 1);
std::sort(begin, end, cmp)	排序，cmp为比较函数名，可省，默认为升序，也可以使用less和greater替代，less表示升序，greater表示降序	bool cmp(int x,int y){ return x<y; } int a[4]={3,1,2,4}; std::sort(a,a+4,cmp); int a[4]={3,1,2,4}; std::sort(a,a+4,std::less<int>()); std::sort(a,a+4,std::greater<int>());

2. 栈 #include <stack>

如果使用了 using namespace std; 下面的std都可以不用写。

函数	作用
std::stack<int> S	定义一个类型为 int 的栈
S.push(x)	将x压入栈S中
S.top()	返回栈顶的元素，不会删除栈顶元素
S.pop()	弹出栈顶的元素，会删除栈顶元素
S.size()	返回栈中元素的个数
S.empty()	检查栈是否为空，若为空返回true，否则返回false

3. 队列 #include <queue>

如果使用了 using namespace std; 下面的std都可以不用写。

函数	作用
std::queue<int> Q	定义一个类型为 int 的队列
Q.front()	返回队列中的第一个元素
Q.back()	返回队列中最后一个元素
Q.push(x)	在队尾插入一个元素 x
Q.pop()	在队头删除一个元素
Q.size()	返回队列中元素个数
Q.empty()	检查队列是否为空，若为空返回true，否则返回false

4. 优先队列 #include <queue>

如果使用了 using namespace std; 下面的std都可以不用写。

class cmp {
public:
	bool operator() (int x, int y){
		return x < y;
	}
};

函数	作用
std::priority_queue< int, std::vector, std::less > Q	定义一个int类型，使用vector容器的大顶堆，优先级大的位于队首；小顶堆使用greater；也可以自定义比较类cmp
Q.top()	返回优先队列的顶部元素，即优先级最大的元素
Q.push(x)	在队尾插入一个元素 x
Q.pop()	在队头删除一个元素
Q.size()	返回队列中元素个数
Q.empty()	检查队列是否为空，若为空返回true，否则返回false

5. map #include <map>

如果使用了 using namespace std; 下面的std都可以不用写。

（1）定义一个键为string类型，值为int类型的map

std::map<std::string, int> M;

（2）插入，两种方式，一种数组，一种使用insert()函数

	M["a"]=1;
	M["b"]=2;
	M["c"]=3;
	M.insert(std::pair<std::string, int>("d", 4));

（3）按键查找

std::cout<<M["d"]<<std::endl;

（4）按键删除，删除成功返回1，失败返回0

int n=M.erase("d");

（5）顺序遍历，it->first是键，it->second是值

	for(std::map<std::string, int>::iterator it=M.begin(); it!=M.end(); it++) {
		std::cout<<it->first<<" "<<it->second<<std::endl;
	}

（6）map的大小

int len=maps.size();

（7）判断map是否为空

M.empty();

（8）清空map

M.clear();

第一章 概论

1. 杰哥与数字

题目

参考代码

#include <iostream>
int test[10];
int main()
{
    long x, n;
    int num = 0;
    std::cin >> x;

    for (int i = 0; i < 10; i++) {
        test[i] = 0;
    }

    n = x;
    while (n > 0) {
        test[n % 10] = 1;
        n /= 10;
    }

    for (int i = 1; i * i <= x; i++) {
        if (x % i == 0) {
            int j = x / i;

            n = j;
            while (n > 0) {
                if (test[n % 10] == 1) {
                    num++;
                    break;
                }
                n /= 10;
            }
            
			if(i==j) continue;
            n = i;
            while (n > 0) {
                if (test[n % 10] == 1) {
                    num++;
                    break;
                }
                n /= 10;
            }
        }
    }

    std::cout << num;

}

2.区间

题目

参考代码

#include <iostream>
// 找到左边最小和右边最大，记录下他们的下标；
// 匹配下标，有一样则输出下标，否则-1； 
// o(n)?

/*
数组L和数组R； 
每次输入li，判断是否为最小值，是则在L数组中记录编号i；
每次输入ri，判断是否为最大值，是则在R数组中记录编号i；

同时遍历L和R;
如果L[j]<R[k],则j++;
如果L[j]>R[k],则k++;
相等，则输出L[j]；

如果都没有则输出-1；

o(n) 

*/
int main()
{
    int N;
    
    std::cin>>N;
    long L[N],R[N];
    long min=1000000000,max=0,li,ri;
    int lenL=0,lenR=0;
    
    for(int i=1;i<=N;i++){
    	std::cin>>li>>ri;
    	
    	if(li<min){
    		min=li;
    		lenL=0;
    		L[lenL++]=i;
		}
		else if(li==min){
			L[lenL++]=i;
		}
		
		if(ri>max){
			max=ri;
			lenR=0;
			R[lenR++]=i;
		}
		else if(ri==max){
			R[lenR++]=i;
		}
	}
	
	int j=0,k=0;
	while(j<lenL&&k<lenR){
		if(L[j]==R[k]){
			std::cout<<L[j];
			return 0;
		}
		else if(L[j]<R[k]){
			j++;
		}
		else{
			k++;
		}
	}
	
	std::cout<<-1;
}

3. 人数过半

题目

参考代码

#include <iostream>
/*
count=1； 
记录第一个数num，后面每输入一个数x，判断num==x？，是则count++；否则count--
如果count==0；则num=x；count=1； 

输出num； 
*/
int main()
{
    int N,count=1;
    long x,num;
    
    std::cin>>N;
	std::cin>>num;
    for(int i=1;i<N;i++){
    	std::cin>>x;
    	if(x==num){
    		count++;
		}
		else{
			count--;
			if(count==0){
				num=x;
				count=1;
			}
		}
	}
	std::cout<<num;
}

4. 我想静静

题目

参考代码

#include <iostream>

int main()
{
    int n,ans;
    
    std::cin>>n;
    int id[n];
    
    for(int i=0;i<n;i++){
    	scanf("%d", &id[i]);
	}
	
	if(n==1){
		ans=id[0];
	}
	else{
		ans=id[0]^id[1];
		for(int i=2;i<n;i++){
			ans^=id[i];
		}
	}
	std::cout<<ans;
}

5. Joyvan的矩阵

题目

参考代码

#include <iostream>
#define swap(a,b) { int t=a;a=b;b=t;}
/*
存储矩阵A；
申请行数组R和列数组C，初始赋值为1，2，3，---，n(m)

交换行x和行y —— R[x-1]=y;R[y-1]=x;
交换列x和列y —— C[x-1]=y;C[y-1]=x;
输出第x行第y列的元素 ——输出A[R[x-1]-1][C[y-1]-1];


*/
int main() {
	int n,m,q,op,x,y;

	scanf("%d %d %d", &n, &m, &q);

	int A[n+1][m+1],R[n+1],C[m+1];

	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			scanf("%d", &A[i][j]);
			C[j]=j;
		}
		R[i]=i;
	}

	for(int i=0; i<q; i++) {
		scanf("%d %d %d", &op, &x, &y);
		switch(op) {
			case 0:
				swap(R[x],R[y]);
				break;
			case 1:
				swap(C[x],C[y]);
				break;
			case 2:
				printf("%d\n", A[R[x]][C[y]]);
				break;
		}
	}
}

第二章 递归与分治

1. 01序列

题目

参考代码

#include <iostream>
#include <cmath>
/*
递归
中序遍历三叉树
定位L的位置——每进入一个子树，判断L是在左子树，中子树还是右子树；
从L开始中序遍历，同时记录1个个数
不遍历L的左边序列，也不遍历R的右边序列

序列个数 —— pow(2,int((log(N)/log(2)))+1)-1

T:O(R-L)
S:O(log N)?

*/
long L,R;

long long int midOrder(long n, long long int len, long long int mid) {
	if(mid+len/2<L||mid-len/2>R) return 0;
	if(len==1) return n%2;

	if(L<=mid&&mid<=R)
		return midOrder(n/2,len/2,mid-(len+1)/4)+n%2+midOrder(n/2,len/2,mid+(len+1)/4);
	else if(R<mid)
		return midOrder(n/2,len/2,mid-(len+1)/4);
	else
		return midOrder(n/2,len/2,mid+(len+1)/4);
}

int main(void) {
	long N;

	std::cin>>N>>L>>R;

	long long int len=pow(2,int((log(N)/log(2)))+1);

//	std::cout<<int((log(N)/log(2)))+1<<std::endl;
//	std::cout<<len<<std::endl;

	std::cout<<midOrder(N,len,len/2);
}

2. 白给题

题目

参考代码

#include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m;
int num[200001];

bool testnum(int x,int tes[])       //判断当前间隔是否合理 
{
	int flag=0;
	int sum=1;
	for(int i=1;i<n;i++)
	{
		if(tes[i]>=x+tes[flag])
		{
			flag=i;          //若当前位置符合间隔，则计数加1 
			sum++;
		}
		if(sum>=m) return true;
	}
	return false;
}

int dic(int l,int r,int tes[])          //二分法寻找最大间隔 
{
	if(l>r) return 0;
	int mid=(l+r)/2;
	if(testnum(mid,num))         //若此间隔合理，往较大方向二分 
	{
		return max(dic(mid+1,r,tes),mid);
	}
	else     //若此间隔不合理，往较小的方向二分 
	{
		return dic(l,mid-1,tes);
	}
}

int main()
{
	scanf("%d %d",&n,&m);    //输入n，m
	for(int i=0;i<n;i++)
	{
		scanf("%d",&num[i]);       //输入数据 
	}
	sort(num,num+n);      //升序排序数据，便于寻找
	int res=dic(0,(num[n-1]-num[0])/(m-1),num);        //存储结果
	printf("%d\n",res);
	return 0; 
}

3. 画三角形

题目

参考代码

#include<iostream>
#include<string>
using namespace std;
void from_bottom(int n, string tp[])
{
	int step = (1<<n-1);
	for(int i=2*step-1;i>=step;i--)
	{
		tp[i] = tp[i-step];
		string middleBlank(2*step-1-i,' ');	
		tp[i] += middleBlank;
		tp[i] += tp[i-step];
	}
	for(int i=step-1; i>=0; i--){
		string frontBlank(step,' ');
		tp[i] = frontBlank + tp[i];
	}
}
int main()
{
	ios::sync_with_stdio(false);
	string triangle[1024]={" /\\","/__\\"};
	int N;
	cin >> N;
	for(int i=2;i<=N;i++)
		from_bottom(i, triangle);
	for(int i=0; i<=(1<<N)-1; i++){
		if(i!=((1<<N)-1))
			cout << triangle[i] << endl;
		else cout << triangle[i];
	}
	return 0;
}

4. 杰哥和序列

题目

参考代码

#include <iostream>
/*
求逆序对个数

归并排序中后面节点往前移动的距离总数就是逆序对的个数
 
*/

int a[100001],b[100001];
long long int count=0;

void merge(int start,int mid,int end){
	int i=start,j=mid+1,k=start;
	while(i<=mid&&j<=end)
		if(a[i]<=a[j])
			b[k++]=a[i++];
		else{
            count+=j-k;
			b[k++]=a[j++];
			
		}
			
	while(i<=mid)
		b[k++]=a[i++];
		
	while(j<=end)
		b[k++]=a[j++];
	
	for(int i=start;i<=end;i++){
		a[i]=b[i];
	}
}

void mergeSort(int start,int end){		// end：最后一个元素的下标 
	if(start>=end) return;
	
	mergeSort(start,(start+end)/2);
	mergeSort((start+end)/2+1,end);
	merge(start,(start+end)/2,end);
}

int main(void){
	int N,A,B;
	
	std::cin>>N>>A>>B;
	
	for(int i=0;i<N;i++){
		std::cin>>a[i];
	}
	
	mergeSort(0,N-1);
	
	std::cout<<count*((A>B)?B:A);
} 

5. Joyvan的难题

题目

参考代码

#include <iostream>
using namespace std;

long Square(long x){
	return x*x;
} 
long minNum = 0x7ffffff;
int main()
{
    int n;
    scanf("%d", &n);
    long temp = 0;
    long sum[n+10];
    int a;
    for(int i = 0; i < n; i++){
        scanf("%d", &a);
        temp += a;
        sum[i] = temp;
    }
    
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            if(Square(j-i) > minNum){
                break;
            }
            minNum = min(minNum, Square(j-i) + Square(sum[j] - sum[i]));
        }
    }
    cout << minNum << endl;
    return 0;
}

第3章 动态规划

1. 眯眯眼天使

题目

参考代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int max(int a, int b) {
    return a > b ? a : b;
}
const int N = 200, M = 3000;
int dp[M+1], v[N * M+1], w[N * M+1];
int main()
{
    int n, m, k = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int vv, ww, s;
        cin >> vv >> ww >> s;
        for (int i = 1; i <= s; i *= 2)  
            v[k] = vv * i, w[k++] = ww * i, s -= i;
        if (s > 0)
            v[k] = vv * s, w[k++] = ww * s;
    }
    for (int i = 0; i <k; i++)        
        for (int j = m; j >= v[i]; j--)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    cout << dp[m] << endl;
    return 0;
}

2. 小火龙

题目

参考代码

#include<stdio.h>
#include<algorithm>
#include<string.h>
#define NPM 100305
#define M 100005
#define N 305
using namespace std;

int n,m,v_sum=0,dp[NPM],result[M]= {0};

struct arr0 {
	int c,v,t,type;
} arr[NPM];

bool cmp(const arr0& a, const arr0& b) {
	if(a.t < b.t) {
		return true;
	} else if(a.t > b.t) {
		return false;
	} else if(a.t == b.t) {
		if(a.type < b.type) {
			return true;
		} else {
			return false;
		}
	}
}

int main() {
	scanf("%d%d",&n,&m);
	for(int i=0; i<n; i++) {
		scanf("%d%d%d",&arr[i].c,&arr[i].v,&arr[i].t);
		arr[i].type=0;
		v_sum += arr[i].v;
	}

	for(int i=n; i<n+m; i++) {
		scanf("%d%d",&arr[i].t,&arr[i].c);
		arr[i].v=i-n; // 用于存储输入时的顺序（当作询问时不作为价值）
		arr[i].type=1;
	}

	memset(dp,0x3f,sizeof(dp));
	dp[0] = 0;

	sort(arr,arr+n+m,cmp); // 根据日期和类型进行排序
	for(int i=0; i<n+m; i++) {
		if(arr[i].type == 0) {
			for(int j=v_sum; j>=arr[i].v; j--) {
				dp[j] = min(dp[j], dp[j-arr[i].v]+arr[i].c);
			}
			for(int j=arr[i].v; j>=0; j--) {
				dp[j] = min(dp[j], dp[j+1]);
			}
		} else {
			result[arr[i].v] = upper_bound(dp, dp+v_sum, arr[i].c)-dp-1;
		}

		int t=0;
		for(int k=0; k<min(v_sum*7,N*N); k++) {
			t = k;
		}
	}

	for(int i=0; i<m; i++) {
		printf("%d\n",result[i]);
	}

	return 0;
}

3. 小鲨鱼

题目

参考代码

#include<bits/stdc++.h>
using namespace std;

int main(){
    int N,M;
    cin >> N >> M;
    int dp[3001] = {0};

    while(N--){
        int c, v, k;
        scanf("%d%d%d", &c, &v, &k);
        for(int i = 1; i <= k; i <<= 1){
            for(int j = M; j >= i * c; j--){
                dp[j] = max(dp[j], dp[j - i*c] + i*v);
            }
            k -= i;
        }
        if(k != 0){
            for(int j = M; j >= k * c; j--){
                dp[j] = max(dp[j], dp[j - k*c] + k*v);
            }
        }
    }
    cout << dp[M] << endl;
}

4. bracket-sequence

题目

参考代码

#include<iostream>
#include<cstring>
using namespace std;

#define ll long long

const int N = 5010, MOD = 998244353;

ll f[2][N];

int n;
int suf_left[N], suf_right[N];
bool first = true;
char s[N], t[N], s1[N], s2[N];

ll solve(){
    
    f[0][0] = 1;
    for(int i = 1; i <= n; i++){

        int idx = i & 1;  // i%2

        if(s[i] == '('){
            f[idx][0] = 0;
            for(int j = 1; j <= n; j++){
                f[idx][j] = f[1 - idx][j - 1];
            }
        }
        else {
            f[idx][0] = f[1 - idx][1];
            for(int j = 1; j <= i; j++){
                if(s[i] == ')')
                    f[idx][j] = f[1 - idx][j + 1];
                
                else
                    f[idx][j] = (f[1 - idx][j - 1] + f[1 - idx][j + 1]) % MOD;
            }
        }

    }
    return f[n&1][0];

}


void dfs(int pos, int cnt, int k, int left, int right){

    if(cnt < 0 || !first || left + suf_left[pos] > n / 2 || right + suf_right[pos] > n / 2) return ;
    
    if(pos == n + 1){
        if(cnt == 0){
            if(first){
                first = false;
                if(k)
                    copy(s + 1, s + 1 + n, s1);
                else
                    copy(s + 1, s + 1 + n, s2);
            }
            return ;
        }
        return ;
    }

    if(s[pos] == '(') dfs(pos + 1, cnt + 1, k, left + 1, right);
    else if(s[pos] == ')') dfs(pos + 1, cnt - 1, k, left, right + 1);
    else{
        if(k){
            s[pos] = '(';
            dfs(pos + 1, cnt + 1, k, left + 1, right);
            s[pos] = ')';
            dfs(pos + 1, cnt - 1, k, left, right + 1);
        }
        else{
            s[pos] = ')';
            dfs(pos + 1, cnt - 1, k, left, right + 1);
            s[pos] = '(';
            dfs(pos + 1, cnt + 1, k, left + 1, right);
        }
        s[pos] = '*';
    }

}

int main()
{
    scanf("%s", s + 1);

    n = strlen(s + 1);

    for(int i = n; i >= 1; i--){
        suf_left[i] = suf_left[i + 1] + (s[i] == '(');
        suf_right[i] = suf_right[i + 1] + (s[i] == ')');
    }

    ll res = solve();

    cout << res << '\n';
    if(res){
        dfs(1, 0, 1, 0, 0);
        first = true;
        dfs(1, 0, 0, 0, 0);
        printf("%s\n%s\n", s1, s2);

    }

    return 0;
}

5. stack

题目

参考代码

#include <iostream>
using namespace std;

const long long mod = 998244353;
long long status[2002][2002];

int main() {
    int n, t, p, d;
    cin >> n >> t >> p >> d;

    int np = p;

    // 计算栈扩容的门槛
    int threshold = 2 * t - p;
    if (threshold < 0)
        threshold = 0;

    status[0][0] = 1;

    for (int i = 1; i <= 2 * n; i++) {
        if (i > threshold)
            np = p + d;
        status[i][0] = status[i - 1][1];
        for (int j = 1; j <= np; j++)
            status[i][j] = (status[i - 1][j - 1] + status[i - 1][j + 1]) % mod;
    }

    cout << status[2 * n][0];

    return 0;
}

第4章 贪心算法

1. 传送门

题目

参考代码

#include <iostream>
/*
* 判断当前i+a[i]是否可以到达n-1的位置，可以则结束；
* 否则寻找i+1到i+a[i]范围内的最大值(j+a[j])；
* 然后i跳到j
* 重复
* 时间O(n)
*/
int main()
{
	//FILE* s;
	//freopen_s(&s,"5.txt", "r", stdin);
	int n, count = 0;

	scanf("%d", &n);
	int* a = new int[10001];

	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}

	int i = 0, len = a[0], max;
	while (i<n-1) {
		max = 0;
		len = i + a[i];
		if (len >= n - 1) {
			count++;
			break;
		}
		for (int j = i + 1; j <= len; j++) {
			if (j + a[j] > max) {
				max = j + a[j];
				i = j;
			}
		}
		count++;
	}

	printf("%d", count);
}

2. 洪尼玛与巧克力工厂

题目

参考代码

#include <stdio.h>
#define min(a,b) a<b?a:b

long long chocolate(int n, int s) {
    int cost_min = 1000000000;
    long long ans = 0;
    int c, a;
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &c, &a);
        cost_min = min(cost_min + s, c); //cost_min + s 表示前一天一个巧克力的最小花费再存储一天的总费用
        ans += cost_min * a;  //贪心选择最小花费
    }
    return ans;
}

int main() {
    int n, s;
    scanf("%d%d", &n, &s);
    printf("%lld", chocolate(n, s));
    return 0;
}

3. 洪尼玛与神秘信封

题目

参考代码

#include<bits/stdc++.h>
using namespace std;

char S[100001];
int a[100001]={0};
int b[100001]={0};
int n;
long long cost=0;
int num = 0;
priority_queue <int,vector<int>,greater<int> > q;  

long long money(){
	for(int i=0;i<n;i++){
		if(S[i] == 'o'){
			num = num + 1;
		}else{
			num = num - 1;
		}
		
		if(S[i] == '*'){
			q.push(a[i] - b[i]);
		}
		if(num < 0 ){
			if(q.empty()) return -1;
			cost += q.top();
			q.pop();
			num +=2;
		}
	}
	if(num != 0) return -1;
	return cost;
}
int main(){
	scanf("%s",S);
	n = (int)strlen(S);
	
	for(int i=0;i<n;i++){
		if(S[i]=='*'){
			scanf("%d%d",&a[i],&b[i]);
			cost += b[i];
		}
	}
	printf("%d\n",money());
	return 0;
}

4. 洪尼玛与网络攻防战

题目

参考代码

#include<algorithm>
using namespace std;

int Index[100005], C[100005], T[100005];
long long weight=0, sum=0; 
int n;

bool compare(const int a, const int b){     // 根据Ci/Ti从大到小排序
	return C[a]*T[b] > C[b]*T[a];
}

int main(){
	scanf("%d",&n);
	for(int i=0; i<n; ++i){
		scanf("%d %d", &C[i], &T[i]);
		Index[i] = i;
		weight = weight + C[i];   // 将权重初始化为所有Ci之和
	}
	
	sort(Index, Index+n, compare);  // 按照函数进行排序，排在前面的黑客，优先攻防
	
	for(int i=0; i<n; ++i){
		weight = weight - C[Index[i]];    // 权重更新
		sum = sum + weight*T[Index[i]]*2;
	}
	printf("%lld\n",sum);
	return 0;
}

5. 山峰

题目

参考代码

#include <stdio.h>

int main() {
    int n, height[1001], length = 1;
    int previous = 0;  // 记录先前的趋势是上升还是下降
    int current;  // 记录当前的趋势是上升还是下降
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &height[i]);
    }
    if (n == 1)
        printf("1");
    else {
        for (int i = 2; i <= n; ++i) {
            if (height[i] == height[i - 1])
                continue;
            current = height[i] > height[i - 1] ? 1 : -1;  // 上升：1，下降：-1
            length += (current != previous); // 若当前趋势与先前趋势不同，符合山峰序列，长度增加
            previous = current;
        }
        printf("%d", length);
    }

    return 0;
}

第5章 回溯法

1. 合并果子

题目

参考代码

#include <iostream>
#include <algorithm>
using namespace std;
int n, sum;
int temp;
int apple[13];
int yh[13][13];

int main()
{
    cin >> n >> sum;
    if (n == 1)
    {
        cout << "1" << endl;
    }
    if (n == 2)
    {
        cout << "1 2" << endl;
    }
    int *apple = new int[n];
    int **yh = new int *[n];
    // 构造杨辉三角
    yh[0] = new int[1];
    yh[0][0] = 1;
    yh[1] = new int[2];
    yh[1][0] = 1;
    yh[1][1] = 1;
    for (int i = 2; i < n; i++)
    {
        yh[i] = new int[i + 1];
        yh[i][0] = 1;
        for (int j = 1; j < i; j++)
        {
            yh[i][j] = yh[i - 1][j - 1] + yh[i - 1][j];
        }
        yh[i][i] = 1;
    }

    // 计算系数
    bool flag = false;
    for (int i = 0; i < n; i++)
        apple[i] = i + 1;
    do
    {
        temp = 0;
        for (int i = 0; i < n; i++)
        {
            temp = temp + apple[i] * yh[n - 1][i];
        }
        if(temp == sum)
        {
            flag = true;
            break;
        }
    } while (next_permutation(apple, apple + n));
    if (flag)
    {
        for (int i = 0; i < (n - 1); i++)
            cout << apple[i] << " ";
        cout << apple[n - 1] << endl;
    }
    else
    {
        cout << "GG" << endl;
    }
    return 0;
}

2. 洪尼玛的围栏

题目

参考代码

#include <iostream>
#include <algorithm>
#define MAX 10
/*
* n个数如果可以组成等边三角形，则边长为：n个数总和/3
* 从大到小排序，
* 遍历，如果该元素可以放进第一边，则放入，不可以则放入下一条边；
* 如果三条边都放不下，则一定无法组成等边三角形
* 如果所有元素都放入，则组成等边三角形。
*/
bool cmp(int a, int b) {
    return a > b;
}

bool canBuild(int a[], int n, int avg) {
    int tri[3] = { 0 };

    std::sort(a, a + n, cmp);
    for (int j = 0; j < n; j++) {
        if (tri[0] + a[j] <= avg) {
            tri[0] += a[j];
        }
        else if (tri[1] + a[j] <= avg) {
            tri[1] += a[j];
        }
        else if (tri[2] + a[j] <= avg) {
            tri[2] += a[j];
        }
        else {
            return false;
        }
    }

    return true;
}

int main()
{
    int T, n, a[MAX];
    float sum, avg;

    std::cin >> T;

    for (int i = 0; i < T; i++) {
        std::cin >> n;
        sum = 0;
        for (int j = 0; j < n; j++) {
            std::cin >> a[j];
            sum += a[j];
        }
        avg = sum / 3;
        //std::cout << sum<<" " << avg << " " << (int)avg << std::endl;
        if (avg != (int)avg) {
            std::cout << "No" << std::endl;
        }
        else {
            if (canBuild(a, n, (int)avg)) {
                std::cout << "Yes" << std::endl;
            }
            else {
                std::cout << "No" << std::endl;
            }
        }
    }
}

3. 二十四点

题目

参考代码

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

const int TARGET = 24;
const double EPSILON = 1e-7;
const int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;

bool solve(vector<double>& list);

bool doJudge(vector<int>& nums) {
    vector<double> list;
    for (int num : nums) {
        list.push_back((double)num);
    }
    return solve(list);
}

bool solve(vector<double>& list) {
    if (list.size() == 0) {
        return false;
    }
    if (list.size() == 1) {
        return abs(list[0] - TARGET) < EPSILON;
    }
    int size = list.size();
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            if (i != j) {
                vector<double> list2;
                for (int k = 0; k < size; k++) {
                    if (k != i && k != j) {
                        list2.push_back(list[k]);
                    }
                }
                for (int k = 0; k < 4; k++) {
                    if (k < 2 && i > j) {
                        continue;
                    }
                    switch (k) {
                    case ADD:
                        list2.push_back(list[i] + list[j]);
                        break;
                    case MULTIPLY:
                        list2.push_back(list[i] * list[j]);
                        break;
                    case SUBTRACT:
                        list2.push_back(list[i] - list[j]);
                        break;
                    case DIVIDE:
                        if (abs(list[j]) < EPSILON) {
                            continue;
                        }
                        else {
                            list2.push_back(list[i] / list[j]);
                        }
                        break;
                    default:
                        break;
                    }
                    if (solve(list2)) {
                        return true;
                    }
                    list2.pop_back();
                }
            }
        }
    }
    return false;
}

int main() {
    vector<int> nums(4);
    for (int n = 0; n < 4; n++) {
        cin >> nums[n];
    }
    bool result = doJudge(nums);
    cout << boolalpha << result << endl;
    return 0;
}

4. 分小球

题目

参考代码

#include<stdio.h>
#include<algorithm>

using namespace std;
int n, m, j;
int allocation(int need[], int balls[], int end, int j);

int main() {
    //n为need，m为balls的个数
    scanf("%d%d", &n, &m);
    int balls[1000] = {0};
    int need[m];
    //为balls赋值
    for (int i = 0; i < n; i++) {
        scanf("%d", &j);
        balls[j - 1]++;
    }
    //为need数组赋值
    for (int i = 0; i < m; i++) {
        scanf("%d", &j);
        need[i] = j;
    }
    j = 0;
    //把数字凑在一起
    for (int i = 0; i < 1000; i++) {
        if (balls[i] != 0) {
            balls[j++] = balls[i];
        }
    }
    //对需求进行排序
    sort(need, need + m);
    //m为balls的数量，j为小球种类的个数
    if (allocation(need, balls, m - 1, j)) {
        printf("true");
    } else {
        printf("false");
    }
    return 0;
}


int allocation(int need[], int balls[], int end, int j) {
    if (end == -1) {
        return 1;
    }
    //将某类小球分类给需求
    for (int i = 0; i < j; i++) {
        //如果该类小球个数不足以满足需求，进入下一类小球。
        if (balls[i] < need[end]) {
            continue;
        }
        //该类小球个数足以满足需求，将需求个数
        if (balls[i] >= need[end]) {
            balls[i] = balls[i] - need[end];
            if (allocation(need, balls, end - 1, j)) {
                return 1;
            }
            //如果小球分配需求不合理，则退回分配其他类小球
            balls[i] = balls[i] + need[end];
        }
    }
    return 0;
}

5. 真-白给题

题目

参考代码

#include <iostream>
#include <stack>
#define N 21
/*
* 独立集问题
* 回溯法
* 剑走偏锋，反正n才20，可以算出答案存到数组。
* 1
* 1 2
* 1 2 3
* 1 2 3 4
* 1 4 3 2 5
* 1 4 3 2 5 6
* 1 2 3 4 7 6 5
* 1 2 3 4 7 6 5 8
* 1 2 3 4 7 6 5 8 9
* 1 2 3 4 7 6 5 8 9 10
* 1 2 3 4 7 10 9 8 5 6 11
* 1 2 3 4 7 6 5 12 11 8 9 10
* 1 2 3 4 7 6 5 12 11 8 9 10 13
* 1 2 3 4 7 6 13 10 9 8 11 12 5 14
* 1 2 3 4 7 6 5 12 11 8 15 14 9 10 13
* 1 2 3 4 7 6 5 12 11 8 9 10 13 16 15 14
* 1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 11
* 1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 11 18
* 1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 11 18 19
* 1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 19 18 11 20
*/
bool a[N][N];
bool b[N];
int stack[N];
int n;
bool flag = false;

bool isPrime(int num) {
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}

void setAB() {
    for (int i = 1; i < N; i++) {
        for (int j = i; j < N; j++) {
            a[i][j] = a[j][i] = isPrime(i + j);
        }
        b[i] = true;
    }
}

void find(int i) {
    for (int j = 1; j <= n; j++) {
        if (a[stack[i - 1]][j] && b[j]) {
            stack[i] = j;
            b[j] = false;
            if (i == n) {
                flag = true;
                return;
            }
            find(i + 1);
            if (flag) {
                return;
            }
            else {      // 回退
                b[j] = true;
            }
        }
    }
}


int main()
{
    std::cin >> n;
    if (n <= 1) {
        std::cout << (n==1)?1:-1;

        return 0;
    }

    setAB();
    stack[1] = 1;
    b[1] = false;
    find(2);

    if (flag) {
        for (int i = 1; i <= n; i++) {
            std::cout << stack[i] << ' ';
        }
    }
    else {
        std::cout << -1;
    }
}