A. Food for Animals：
题目链接：
题面：
?
题意：
有a包狗粮，b包猫粮，c包猫狗都吃粮，有x只狗，y只猫，问能否给每只动物都分配一包粮
思路：
如果x-a + y-b <= c就输出YES，否则NO
代码：
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long
int main(){
int t;
cin >> t;
while(t--){
int a, b, c, x, y;
cin >> a >> b >> c >>x >> y;
int ans = x - a;
int cnt = y - b;
ans = max(0, ans);
cnt = max(0, cnt);
if(ans + cnt <= c){
cout << "YES" << endl;
}else{
cout << "NO" << endl;
}
}
return 0;
}B. Make It Increasing
题目链接：
题面：
题意：?
有n个数，可以任选一个数x变成x/2，问能否变成一个递增序列，如果可以输出操作次数，不可以输出-1
思路：
从后往前遍历，如果这个数大于等于后面的那个数，那么这个数就/2，累加，如果后面那个数为0，就不能变成一个递增序列
代码：
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long
int arr[35];
int main(){
ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--){
ll num = 0;
int n;
cin >> n;
for(int i = 0; i < n; i++){
cin >> arr[i];
}
bool f = 0;
for(int i = n - 2; i >= 0; i--){
while(arr[i] >= arr[i + 1]){
if(arr[i] == 0){
f = 1;
break;
}else{
arr[i] /= 2;
num++;
}
}
}
if(f){
num = -1;
}
cout << num << endl;
}
return 0;
}C. Detective Task
题面链接：
题面：
?题意：
一个人有一幅画，他邀请了n个人去参观这幅画，每次只能由一个人参观，最后一个人出来的时候发现画被偷了，然后他去询问n个人，每个人的回答有
1.画还在 ‘1’
2.画不在 ‘？’
3.不知道
小偷可以随便说，其他人只能说真话或者不知道
问有几个人可能是小偷
思路：
如果这个人是小偷，那么他前面不能有人说画不在，后面也不能有人说画还在
可以用二分函数，直接查找
代码：
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long
vector<int> ve[5];
int main(){
ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--){
string s;
cin >> s;
if(s.length() == 1){
cout << 1 << endl;
}else{
for(int i = 0; i < 3; i++){
ve[i].clear();
}
for(int i = 0; i < s.length(); i++){
if(s[i] == '0'){
ve[0].push_back(i);
}else if(s[i] == '1'){
ve[1].push_back(i);
}else{
ve[2].push_back(i);
}
}
int num = 0;
for(int i = 0; i < s.length(); i++){
int ans = lower_bound(ve[1].begin(), ve[1].end(), i + 1) - ve[1].begin();
int cnt = lower_bound(ve[0].begin(), ve[0].end(), 0) - ve[0].begin();
if(ans == ve[1].size() && cnt == ve[0].size()){
num++;
}else if(ans == ve[1].size() && ve[0][cnt] >= i){
num++;
}
}
cout << num << endl;
}
}
return 0;
}D. Vertical Paths
题目链接：
题面：
题意：?
思路：?
只要按照从父节点到子节点的顺序遍历即可
按照层序遍历下来即可，用vector记录下来就可以
代码：
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long
vector<int> ve[200005], vee, vv[200005];//ve存父节点，vee存层序遍历，vv存每条路径
bool vis[200005];
bool f = 0;
int num = 0;
int sum = 0;
void dfs(int x){
vv[num].push_back(x);
vis[x] = 1;
sum++;
if(ve[x].size() == 0){
f = 1;
return ;
}
for(int i = 0; i < ve[x].size(); i++){
int v = ve[x][i];
if(vis[v] == 0){
dfs(v);
if(f){
return ;
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
int cnt = 0;
while(t--){
if(cnt != 0){
cout << endl;
}
vee.clear();
cnt++;
int n;
cin >> n;
for(int i = 1; i <= n; i++){
ve[i].clear();
vis[i] = 0;
}
int p = 0;
for(int i = 1; i <= n; i++){
int a;
cin >> a;
if(a == i){
p = a;
}else{
ve[a].push_back(i);
}
}
queue<int> q;
q.push(p);
while(!q.empty()){
int x = q.front();
q.pop();
vee.push_back(x);
for(int i = 0; i < ve[x].size(); i++){
int v = ve[x][i];
q.push(v);
}
}
num = 0;
sum = 0;
for(int i = 0; i < n; i++){
if(sum == n){
break;
}
int x = vee[i];
if(!vis[x]){
vv[num].clear();
f = 0;
dfs(x);
num++;
}
}
cout << num << endl;
for(int i = 0; i < num; i++){
cout << vv[i].size() << endl;
for(int j = 0; j < vv[i].size(); j++){
if(j != 0){
cout << " ";
}
cout << vv[i][j];
}
cout << endl;
}
}
return 0;
}E. Replace With the Previous, Minimize
题面链接：
题面：
?
题意：?
有k次操作，每次可以选择所有的同种字母，把他们变成前一个字母如'c' - 'b','a' - 'z'，问能变成的字典序最小的字符串
思路：
要求字典序最小的，我们从前往后遍历，如果是‘a’后面的字符就往‘a'变，然后就可以求出每种字母能变成的最小字母
代码：
#include<bits/stdc++.h>
using namespace std;
bool vis[30];
int main(){
ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--){
memset(vis, 0, sizeof(vis));
int n, k;
cin >> n >> k;
string s;
cin >> s;
for(int i = 0; i < n; i++){
char c = s[i];
while(c > 'a' && k > 0 && vis[c - 'a'] == 0){
k--;
vis[c - 'a'] = 1;
c--;
}
}
for(int i = 0; i < n; i++){
int a ;
for(int j = s[i] - 'a'; j >= 0; j--){
a = j;
if(vis[j] == 0){
break;
}
}
cout << char(a + 'a');
}
cout << endl;
}
return 0;
}
