A-标记

统计各个标记的出现次数，再用while循环输出即可，注意要把小写字母统一为大写。

#include<bits/stdc++.h>

using namespace std;

int main()

{

string s;

cin>>s;

int len=s.size();

int num1=0,num2=0,num3=0,num4=0;

for(int i=0; i<len; i++)

{

char c=s[i];

if(c=='G'||c=='g')

num1++;

else if(c=='P'||c=='p')

num2++;

else if(c=='L'||c=='l')

num3++;

else if(c=='T'||c=='t')

num4++;

}

while(num1||num2||num3||num4)

{

if(num1>0)

{

printf("G");

num1--;

}

if(num2>0)

{

printf("P");

num2--;

}

if(num3>0)

{

printf("L");

num3--;

}

if(num4>0)

{

printf("T");

num4--;

}

}

return 0;

}

B-阅读统计

模拟题，易错点如下：

1. 计算借书总时间时计算出错，可以将时间转化为一个int类型的整数来进行减法运算。
2. 如果当天借书次数=0，那么最后计算平均阅读时间时可能发生除以 0 的情况，需要特判。
3. 需要能够自动识别并排除无效的记录，也就是说一本书被借走后需要标记，书被还回的时候查看这本书有没有被标记，再统计借书次数。
4. 有多组数据，每组数据之间需要清空数组和各种变量。

#include <bits/stdc++.h>

using namespace std;
 

const int maxn=60;

int book[maxn]; //记录书借出的时间，-1表示没被借
 

int gettime(string s) //将时间转化为用数字来表示

{

int h = (s[0] - '0') * 10 + s[1] - '0';

int m = (s[3] - '0') * 10 + s[4] - '0';

int time = h * 60 + m;

return time;

}

int main()

{

int n;

cin >> n;

for(int i = 0; i < n; i++)

{

for(int j = 0; j < maxn; j++) book[j] = -1; //标记所有书没被借

int cnt = 0, sum = 0; //cnt-借书次数，sum-总阅读时间

while(1)

{

int id;

char ch;

string s;

cin >> id >> ch >> s;

if(id == 0) //一天结束

{

int ans; //平均阅读时间

if(cnt) ans = sum / cnt;

else ans = 0;

cout << cnt << " " << ans << endl;

break; //跳出循环，开始下一天

}

if(ch == 'S') book[id] = gettime(s); //记录借出的时间

else if(ch == 'E' && book[id] != -1)

// book[id] != -1表示这本书已经被借出

{

cnt++; //在这里记录借书次数，就自然的忽略了无效的借书记录

sum += gettime(s) - book[id];

book[id] = -1; //还了书后，标记这本书没被借出

}

}

}

return 0;

}

C-小镇规划

解法一：bfs或dfs  O(n^2)

此题数据范围较小，可以直接搜索解决。以每个点为起点开始搜索，可以得到其他所有点到它的距离，最后求和，再在所有点中找到和最小的即可。

鉴于此题数据较小，存图用邻接矩阵邻接表都可以。

#include <bits/stdc++.h>

using namespace std;

bool g[105][105]; //邻接矩阵

bool v[105];

int n,num[105],ans=0x7f7f7f7f;

struct node

{

int u,step;

};

int bfs(int x) //bfs找点x为医院设置点时的总距离

{

memset(v,0,sizeof(v));

queue<node> q;

v[x]=1;

q.push((node){x,0});

int sum=0;

while(!q.empty())

{

node now=q.front();

q.pop();

for(int i=1; i<=n; i++)

if(g[now.u][i]&&!v[i])

{

node nex = {i, now.step+1};

sum+=num[i]*nex.step;

v[i]=1;

q.push(nex);

}

}

return sum;

}

int main()

{

scanf("%d",&n);

for(int i=1; i<=n; i++)

{

int a,l,r;

scanf("%d%d%d",&a,&l,&r);

num[i]=a;

if(l) g[i][l]=g[l][i]=1;

if(r) g[i][r]=g[r][i]=1;

}

for(int i=1; i<=n; i++) ans=min(ans,bfs(i));

printf("%d",ans);

return 0;

}

解法二：树的重心  O(n)

解法三：Floyd算法   O(n^3)

鉴于是提高组算法，这里不再展开，有兴趣可以来问老师或自己尝试写。

D-足球赛

思路：折半搜索

如果n≤20，那么显然暴搜即可，但在n≤40的情况下，O(2^n)的时间复杂度是不可接受的，需要想办法优化搜索。

考虑到n≤20时O(2^n)的时间复杂度可以接受，所以可以先搜索前一半，然后搜索后一半。每搜到一种方案，就将该种方案的总预算放入一个数组中。这样，两次搜索就得到了两个数组。

将其中一个数组排序，枚举第二个数组中的元素。对于每个元素，在第一个数组中使用二分查找找到与它的和<=m的值的个数，用ans累加这个个数，即可得到最终的答案。

时间复杂度大约为：O(nlogn2^(n/2))

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

int n;
ll m, ans, a[47];
vector <ll> k[2];
//k[0]中存储搜索前一半能够搜到的所有预算
//k[1]中存储搜索后一半能够搜到的所有预算

void dfs(int x, ll sum, int num)
//num==0表示是第一次搜索（前一半），==1是第二次搜索（后一半）
{
// 剪枝，总预算不超过m
if (sum > m) return;
// 如果 num==0，那么搜到一半就要停止；否则，搜到n再停止
int maxr = n;
if (num == 0) maxr /= 2;
if (x > maxr)
{
k[num].push_back(sum);//累计答案
return;
}
// 选x和不选x 两种情况
dfs(x+1, sum+a[x], num);
dfs(x+1, sum, num);
}

int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
dfs(1, 0, 0);
dfs(n/2+1, 0, 1);

sort(k[0].begin(), k[0].end()); //对第一个数组中的内容排序，方便二分查找
int len = k[1].size();
for(int i = 0; i < len; i++)
{
int l = 0, r = k[0].size() - 1, tmp = -1;
// 找到最大的ans使得 k[0][ans] + k[1][i] <= m
while(l <= r)
{
int mid = (l + r) / 2;
if(k[0][mid] + k[1][i] <= m)
{
l = mid + 1;
tmp = mid;
}
else r = mid - 1;
}
ans += tmp + 1; //总方案数
}
cout << ans << endl;
return 0;
}