学校周赛（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;
//二分答案h
while (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;
}