学校周赛（1）

A - Short Sort

题目：

思路：

本条题目只允许改一处地方，只有三个字母，我们可以直接枚举所有移动过的结果，同时使用哈希去记录其值，对于每一个输入我们都寻找是否有这个值记录，有则输出YES否则NO

代码：

#include<iostream>
#include<map>
using namespace std;
int main(){map<string,int> h;//初始化哈希h["abc"]=1;h["acb"]=1;h["cba"]=1;h["bac"]=1;int n;cin>>n;while(n--){string str;cin>>str;if(h[str]==1) cout<<"YES"<<endl;else  cout<<"NO"<<endl;}return 0;
}

B - Good Kid

题目：

思路：

本题当中的数值全为正数，要想乘积最大则只需要最小值变大即可，因此首先对数组进行排序，将最小的数字+1，然后相乘即可。

代码：

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
int main(){int t;cin>>t;while(t--){int n;cin>>n;int sum;vector<int> a(n);for(int i=0;i<n;i++) cin>>a[i];sort(a.begin(),a.end());sum=++a[0];for(int i=1;i<n;i++) sum*=a[i];cout<<sum<<endl;}return 0;
}

C - Target Practice

题目：

思路：

本题遍历五个环并乘以相应的值即可，五个环我们可以发现是完全对称的状态，我们可以通过不断缩小环即可。

代码：

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
int solve(){string cnt[10];for(int i=0;i<10;i++) cin>>cnt[i];//完全对称int k=1;int sum=0;for(int top=0;top<5;top++){int c=0;for(int i=top;i<10-top;i++) if(cnt[i][top]=='X') c++;//i 0-9 j=0 第一列 for(int i=top+1;i<10-top-1;i++) if(cnt[10-top-1][i]=='X') c++;//i 9 j 1-8 最后一行for(int i=top;i<10-top;i++) if(cnt[i][10-top-1]=='X') c++;//i 0-9 j=9 最后一列for(int i=top+1;i<10-top-1;i++) if(cnt[top][i]=='X') c++;//i 0 j 1-8第一行 sum+=c*k; k++;}return sum;
}
int main(){int t;cin>>t;while(t--){int ans=solve();cout<<ans<<endl;}return 0;
}

D - 1D Eraser

题目：

思路：

本题问最小多少次能够将其染成W，只需要我们每次遇到B时，都进行k个染色即可

代码：

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
int solve(){int ans=0;int n,k;cin>>n>>k;string str;cin>>str;for(int i=0;i<n;){if(str[i]=='B'){ans++;i+=k;} else i++;} return ans;
}
int main(){int t;cin>>t;while(t--){int ans=solve();cout<<ans<<endl;}return 0;
}

E - Building an Aquarium

题目：

思路：

本题考察的时二分，我们可以假设答案h初始值为0，然后将其慢慢上移，直到满足条件，此处不难看出h具有单调递增的特点，因此我们使用二分进行搜索答案，对于我们搜索出的二分只有当高度为h时所需水量小于等于我们提供的水量才能够满足我们的条件，满足条件则记录，最终取其最大值。

优化：当我们判断水是否满足时，可以先做一个排序，因为高度越小的所需要的水量越多，同时减少由于要遍历所带来的更多的判断步骤。

代码：

#include<iostream>
#include<vector>
using namespace std;typedef long long ll;void solve()
{int n, w;cin >> n >> w;vector<ll> a(n);for (int i = 0; i < n; i ++)cin >> a[i];
//此处排序，减少判断次数sort(a.begin(), a.end());ll l = 0, r = 2e9 + 1;
//二分答案hwhile (l < r){ll h = (l + r + 1) >> 1;ll t = 0;for (int i = 0; i < n; i ++)if (a[i] < h)t += h - a[i];else break;if (t <= w) l = h;else r = h - 1;}cout << r << endl;
}int main()
{int T; cin >> T;while (T --) solve();return 0;
}

F - Money Trees

题目：

思路：

本题考查的前缀和+滑动窗口，我们可以在统计统计前i个的和，那么窗口中的和则为 第r个 - 第l-1个，其次我们可以通过前缀和的思想来考虑哪一段树可以摘（r~r-b[r]），对于每一段我们通过滑动窗口的思想来确定边界。

代码：

#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long void to_do() {ll n, k, ans = 0, sum = 0;cin >> n >> k;vector<ll> cnt_num(n + 1), a(n + 1);vector<ll> cnt_h(n + 1);for (int i = 1; i <= n; i++) {cin >> a[i];cnt_num[i] = cnt_num[i - 1] + a[i];//前缀和,某个连续部分的和为cnt_num[r]-cnt_num[l-1]}for (int i = 1; i <= n; i++) cin >> cnt_h[i];ll l = 0, l_max=0;vector<int> b(n + 1);//可摘树的长度int idx = 0;for (int r = 1; r <= n; r++){//记录可摘树的长度if (r == 1|| cnt_h[r - 1] % cnt_h[r]){b[r] = 0;}else{b[r] = b[r - 1] + 1;}int l = max(r - b[r], idx);ll res = cnt_num[r] - cnt_num[l - 1];if (res <= k){ans = max(ans, r - l + 1ll);}else{while (res > k){res -= a[l];l++;}idx = l;ans = max(ans, r - l + 1ll);}}cout << ans << endl;
}
int main()
{int t; cin >> t;while (t--) to_do();return 0;
}