A题

for循环枚举x判断x和n-x是否都为素数,是就输出并且break

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

bool is_prime(int x)
{
	if(x < 2) return 0;
	for(int i = 2;i*i <= x;i++)
	if(x%i == 0) return 0;
	return 1;
}
int main()
{
	int n;
	cin >> n;
	for(int x = 2;x <= n/2;x++)
	if(is_prime(x) && is_prime(n - x))
	{
		cout << n << "=" << x << "+" << n - x;
		break;
	}
	return 0;
}

B题

首先要知道字符串 是一种变量类型，那这题实际就是让我把字符串数组按字典序从小到大排序，因为数据范围很小所以随便用什么排序都不会时间超限

string a[115];
    int t;
    cin >> t;
    for(int k = 1;k <= t;k++)
    {
        int n;
        cin >> n;
        for(int i = 1;i <= n;i++)
        cin >> a[i];
         
        for(int i = 1;i <= n - 1;i++)//用冒泡排序对字符串数组排序
        {
            for(int j = 1;j <= n - i;j++)
            if(a[j] > a[j + 1])
            {
                string x;
                x = a[j];
                a[j] = a[j + 1];
                a[j + 1] = x;
            }
        }
        for(int i = 1;i <= n;i++)
        cout << a[i] << endl;
    }

当然也可以偷懒，直接用C++自带的排序函数sort对字符串数组排序，默认排序规则是按字典序的

int t;
cin>>t;
while(t--)
{
    int n;
    cin>>n;
    string s[100];
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
    }
    sort(s+1,s+n+1);
    for(int i=1;i<=n;i++)
    {
        cout<<s[i]<<endl;
    }
}

C题

字母是成对出现的，字母的第一次出现表示顾客来到了咖啡馆，字母的第二次出现表示该顾客离开了咖啡馆。每一种字母最多出现一对。 先把题目弄清楚

首先思考一下 什么情况下顾客不会得到服务? 显然就是当前位置已经坐满的情况下，所以我们需要实时记录位置是否满了,那怎么去记录呢? 我们可以用一个变量k统计当前有多少人正在享受服务，用一个f数组来标记某个人当前是否得到服务的情况：

1.f[i]=0从未去过，
2.f[i] = -1,去了但去的时候位置满了没有得到服务，
3.f[i]=1得到服务了

代码

#include<bits/stdc++.h>
using namespace std;
int f[27];//f[i]=0从未去过，f[i] = -1,去了但去的时候位置满了没有得到服务，f[i]=1得到服务了 
int main()
{
	int N,k = 0,res = 0;//k是当前有多少人正在享受服务,ans统计有多少人没有得到服务 
	cin >> N;
	string s;
	cin >> s;
	for(int i = 0;i < s.size();i++)
	{
		int d = s[i] - 'A';
		if(!f[d] && k == N){
			f[d] = -1;//位置已满未能得到服务,标记为-1表示这个人未得到服务 
			res++; 
		}
		else if(!f[d] && k < N) //位置未满能得到服务 
		{
			f[d] = 1,k++;
		}
		else if(f[d] == 1)//得到过服务，现在离开了 
		{
			k--; 
		}
	}
	cout << res; 
	return 0;
}

D题

首先理解题意 习大大拿出了2瓶茅台国酒，就一开始有两瓶酒哦,逢店加一倍（酒)(也就是逢店酒瓶数量翻倍)，逢大排档吃醋鱼并喝一瓶（酒）

这题一看，$n,m$小于等于10，很显然就暴力搜索所有的次序了(没学过搜素你就G了)，但是要特别注意细节(数学上0乘以任何数都等于0)，剪枝一下(其实也可以不剪枝的)

void dfs(int a,int b,int res)//当前经过了a个店，b个大排档。res是当前剩下的酒瓶数量 
{
    if(a == n && b == m && res == 0)
    {
        ans++;
        return;
    }
    if(b == m && res != 0) return;//剪枝1 
    if(m - b < res) return;//剪枝2
    if(a == n && res < m - b) return;//剪枝3
     
    if(a < n && res != 0)//店 ,必须判断res不等于0 
    {
        dfs(a + 1,b,res*2);
    }
    if(b < m && res != 0)//大排档
    {
        dfs(a,b + 1,res - 1);
    }
}

E题

*1.第一次传递一定是从F传到5个朋友之一，现在剩下n-1次传递

*2.我们设从5个朋友之一开始传经过i次传到小F手中的方案为G[i]

*3.设从小F开始传递，传经过i次传到小F手中的方案为F[i]

*4.我们答案就是F[n],关键是怎么求得F[n]呢？递推即可 先求G[i]

再求F[i]

代码

void init()
{
	F[1] = 0;//1次肯定回不到小F手上 
	G[1] = 1;//1次从好友手上直接传到小F手上，所以有一种可能 
	for(int i = 2;i <= 20;i++)
	{
		F[i] = 5*G[i - 1];
		G[i] = 4*G[i - 1] + F[i - 1];
	}
}//别忘了，数据范围很大要用long long

F题

题目可以简化为 在一个数轴上有n条线段，现要选取其中k条线段使得这k条线段两两没有重合部分，问最大的k为多少。

最左边的线段放什么最好？

显然放右端点最靠左的线段最好，从左向右放，右端点越小妨碍越少

其他线段放置按右端点排序，贪心放置线段，即能放就放 用结构体存线段

struct line{
	int begin,end;
};

line a[N];
bool cmp(line x,line y)//按右端点小到大排序
{
	return x.end < y.end;
}
//主要代码
sort(a,a + n,cmp);
int k = 1,last_end = a[0].end;//排序后的第一条线一定要的，last_end记录选择的上一条线的右端点 
for(int i = 1;i < n;i++)
if(a[i].begin >= last_end) //要把=算进去 
{
	k++;
	last_end = a[i].end; 
}

G题

这题就是**BFS广度优先搜索**变形，看你是否真的理解广度优先搜素了。现在地图的墙可以通过需要额外的1个单位时间，有怪物打败怪兽需要4单位时间。 关于BFS,广度优先搜索,会优先考虑每种状态的和初始状态(起点)的距离,形象点说,与初始状态越接近的情况就会越先考虑。再具体一点:每个时刻(阶段)要做的事情就是从上个时刻(阶段)每个状态扩展出新的状态。 我们BFS入门的时候，从当前状态到相邻状态都只需要1个单位时间，所以放进队列里队列靠前的点，一定是离 初始状态(起点)最近的，现在这题到达相邻的位置不一定是1个单位时间了有可能是1,2,4 放进队列里队列靠前的点，不一定是离 初始状态(起点)最近的，那怎么才能保证放进队列里队列靠前的点，一定是离 初始状态(起点)最近的点呢？用优先队列存放每个状态

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
bool vis[N][N];
struct p{
	int x,y,t;
	friend int operator<(p a,p b)//定义优先队列排序规则
    {
        return a.t>b.t;
    }
};
int sx,sy,ex,ey,n,m,ans;
int dx[] = {-1,1,0,0},dy[] = {0,0,-1,1};
string s[N];
void bfs()
{
	ans = -1;
	memset(vis,0,sizeof vis);
	priority_queue<p> q;
	vis[sx][sy] = 1;
	q.push({sx,sy,0});
	while(q.size())
	{
		p cur = q.top(); q.pop();
		int cx = cur.x,cy = cur.y,ct = cur.t;
		if(cx == ex && cy == ey)
		{
			ans = ct;
			break;
		}
		for(int i = 0;i < 4;i++)
		{
			int nx = cx + dx[i],ny = cy + dy[i];
			if(nx < 0 || ny < 0 || nx >= n || ny >= m || vis[nx][ny] || s[nx][ny] == 'K')
			continue;
			if(s[nx][ny] == '#')
			{
				vis[nx][ny] = 1;
				q.push({nx,ny,ct + 2});
			}
			else if(s[nx][ny] == 'A')
			{
				vis[nx][ny] = 1;
				q.push({nx,ny,ct + 4});
			}
			else {
				vis[nx][ny] = 1;
				q.push({nx,ny,ct + 1});
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	while(cin >> n >> m)
	{
		if(!n && !m) break;
		for(int i = 0;i < n;i++)
		cin >> s[i];
		for(int i = 0;i < n;i++)
		for(int j = 0;j < m;j++)
		if(s[i][j] == 'S'){
			sx = i,sy = j;
		}
		else if(s[i][j] == 'T')
		{
			ex = i,ey = j;
		}
		bfs();
		cout << ans << endl;
	}
	return 0;
}

当然这题其实是单源最短路，也可以用Dijkstra算法

H

这题显然贪心策略是：种一棵树尽可能在多个区间，这样最后就可以少种树了

我们对所以区间按右端点从小到大排序，每个区间选择种树尽可能靠区间右端种树，这样就可以让后面的区间共用这个些树

#include<bits/stdc++.h>
using namespace std;
const int N = 3e4 + 10;
bool f[N];
struct node{
	int b,e,t;
};
node a[N];
bool cmp(node x,node y)
{
	return x.e < y.e;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n,h;
	cin >> n >> h;
	for(int i = 0;i < h;i++)
	cin >> a[i].b >> a[i].e >> a[i].t;
	
	sort(a,a+h,cmp);
	int res = 0;
	for(int i = 0;i < h;i++)
	{
		if(i == 0)
		{
			for(int j = a[i].e - a[i].t + 1;j <= a[i].e;j++)//第一个区间靠右种树 
			f[j] = 1,res++;
		}
		else{
			for(int j = a[i].b;j <= a[i].e;j++)//前面区间种的树可能会在当前区间 
			if(f[j] && a[i].t) a[i].t--;
			
			int k = a[i].e;//靠右种树,从后面往前种树 
			while(a[i].t)
			{
				if(!f[k])
				{
					f[k] = 1;
					res++;
					a[i].t--;
				}
				k--;
			}
		}
	}
	cout << res;
	return 0;
}

I题

这题如果圆形的半径大于w/2，就能喷水覆盖一个小矩形草坪 图中绿色的矩形，那么你想象一下就知道这个问题可以转化为：

假设该圆形的是 x,r。那a[i] = x -sqrt(r*r - (w/2)*(w/2)); b[i] = x + sqrt(r*r - (w/2)*(w/2));

那现在怎么贪心，才能使所选的区间数最小

1.将所有区间按照左端点从小到大进行排序

2.从前往后枚举每个区间，在所有能覆盖start的区间中，选择右端点的最大区间，然后将start更新成右端点的最大值

#include<bits/stdc++.h>
using namespace std;
const int N = 15e3 + 10;
struct line{
	double b,e;
};
line a[N];

bool cmp(line x,line y)
{
	return x.b < y.b;
}

int main()
{
	int T;
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> T;
	while(T--)
	{
		int n,k = 0;
		cin >> n;
		double x,r,l,w;
		cin >> l >> w;
		for(int i = 0;i < n;i++)
		{
			cin >> x >> r;
			if(r > w/2)
			{
				double d = sqrt(r*r - (w/2)*(w/2));
				a[k].b = x - d,a[k].e = x + d;//计算该圆形覆盖的矩形区间的左右端点 
				k++;
			}
		}
		sort(a,a+k,cmp);
		double start = 0;
		bool ok = 1;
		int res = 0,now = 0;
//		cout << "GG" << endl;
		while(start < l)
		{
			int rd = -1,mr = 0;
			while(now < k && a[now].b <= start)
			{
				if(a[now].e > mr)
				{
					mr = a[now].e;
					rd = now;
				}
				now++;
			}
			if(rd >= 0 && a[rd].b <= start)
			{
				res++; start = a[rd].e;
			}
			else{
				ok = 0;
				break;
			}
		}
		if(!ok) cout << -1 << endl;
		else cout << res << endl;
	}
	return 0;
}

J题

贪心 + 优先队列(优先队列是个好东西，要是你不会你会吃大亏的)

我们肯定是那个作业紧急那个优先嘛，所以按期限从小到大排序。因为作业可以提前做，我们当前这一天选做的作业不一定是最佳选择 如果按期限从小到大做有可能后面分数很高的作业没时间做了，我们可以将后面分数高的作业提前做，提前做应该牺牲前面的已做了的某个作业，到底牺牲谁呢？贪心：显然是前面做过的作业中分数最小被牺牲，我们用优先队列存储所有已做过的作业。确保堆顶是分数最小的作业(这里涉及结构体里运算符重载，运算符重载会跟优先队列里想要的相反!!!) 我提交的时候错了两次。。。死因：运算符重载

关键代码

struct homework{
	int dd,score;
	bool operator < (const homework &x)const{
		return score > x.score;
	}
};
homework a[N];
bool f[N];
bool cmp(homework x,homework y)
{
	if(x.dd == y.dd) return x.score > y.score;
	return x.dd < y.dd;
}
/////////////////////////////////////////////////
sort(a,a + n,cmp);
priority_queue<homework> q;
int res = 0;
int mn = 1;//到那一天了 
for(int i = 0;i < n;i++)
{
	if((mn <= a[i].dd && !f[mn]))
	//没超过期限且第mn天没被用来做其他作业，直接做当前作业 
	{
		f[mn] = 1;
		mn++;
		res += a[i].score;
		q.push(a[i]);
	}
	else if(q.size() && q.top().score < a[i].score && q.top().dd <= a[i].dd)
	{
		//如果队列里前面做过的作业中分数最小就会被被牺牲，因为当前作业分数比它高 
		homework t = q.top(); q.pop();
		q.push(a[i]);
		res += (a[i].score - t.score);
	}
}
cout << res;