牛客小白月赛68

题目链接

A Tokitsukaze and New Operation

思路：

读入时将整数按字符串读入，直接模拟即可

代码：

#include <bits/stdc++.h>using namespace std;string solve()
{string a,b;cin >> a >> b;if(a.length() != b.length()) return "-1";string ans = "";for(int i = 0; i < a.length();i++){int x = (a[i] - '0') * (b[i] - '0');ans += to_string(x);}return ans;
}int main(){int t;cin >> t ;while(t--){cout << solve() << endl;}return 0;
}

B Tokitsukaze and Order Food Delivery

思路：

按题意模拟更新求最值

代码：

#include <bits/stdc++.h>using namespace std;int solve()
{int n , a , b;int ans = 2e9;cin >> n >> a >> b;for(int i = 0; i < n; i++){int k , x , y; cin >> k >> x >> y;for(int j = 0; j < k; j++){int z;cin >> z;int d = 0;if(z >= x) d += y;if(z >= a) d += b;ans = min(ans,max(z-d,0)) ;}}return ans;
}int main(){int t ;cin >> t;while(t--){cout << solve() << endl;}return 0;
}

C Tokitsukaze and Average of Substring

思路：

预处理 ‘a’ ~ ‘z’ 每种字母出现次数的前缀和，暴力枚举区间 [$l$,$r$]， 利用已知信息求出分子和分母，更新 $F$($l$，$r$)的最值。

代码：

#include <bits/stdc++.h>using namespace std;
const int N = 5010;
int sum[N][30];void solve()
{char s[5010];int n;scanf("%d",&n);scanf("%s",s+1);for(int i = 1; i <= n; i++){for(int j = 0; j < 26; j++) sum[i][j] = sum[i-1][j];sum[i][s[i]-'a']++;}double ans = 0;for(int l = 1; l <= n; l++){for(int r = l + 1; r <= n; r++){int up = 0;for(int j = 0; j < 26; j++){int d = sum[r][j] - sum[l-1][j];if(d >= 2) up += d * (d - 1) / 2;}ans = max(ans,up*1.0/(double )(r-l+1));}}ans = ans + 1e-8;printf("%.6f\n",ans);
}int main(){int t;cin >> t;while (t--){solve();}return 0;
}

D Tokitsukaze and Development Task

思路：

不难看出，四部分相互独立。先BFS预处理到达任意状态(10~300)的最小代价表 dis，对于每组询问，四部分的最小代价累加就是总的最小代价。

代码：

#include <bits/stdc++.h>using namespace std;
const int N = 5010;
int dis[510];
int dx[] = {1,-1,10,-10,100,-100};
void BFS()
{dis[10] = 1;queue<int>q;q.push(10);while (!q.empty()){int top = q.front();q.pop();if(!dis[300]) {dis[300] = dis[top] + 1;q.push(300);}if(!dis[10]){dis[10] = dis[top] + 1;q.push(10);}for(int i = 0; i < 6; i++){int xx = top + dx[i];if(xx < 10 || xx > 300) continue;if(dis[xx]) continue;dis[xx] = dis[top] + 1;q.push(xx);}}
}int main(){BFS();int t;scanf("%d",&t);while (t--){int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);int ans = dis[a] + dis[b] + dis[c] + dis[d] - 4;printf("%d\n",ans);}return 0;
}

E Tokitsukaze and Colorful Chessboard

思路：
对于一个 $n$ $\ast$ $n$ 的盘面，令 $S$ = $n$ $\ast$ $n$， 可得最优划分方案（$Ma{x}_a$，$Ma{x}_b$）=（$S$ $/$ $2$，$S$ $/$ $2$ $+$ $S$ % $2$），不妨令 b 为 a 和 b 中的较大者，满足 a ≤ $Ma{x}_a$ 且 b ≤ $Ma{x}_b$，就能放入这个盘面。题目要求盘面尽可能地小，因此二分答案求最小边长。

代码：

#include <bits/stdc++.h>
#define int long long using namespace std;bool check(int d, int a, int b)
{int L = d * d / 2;int R = d * d / 2;if((d * d)%2) R++;if(L >= a && R >= b) return true;else return false ;
}int solve()
{int a, b; cin >> a >> b;if(a > b) swap(a,b);int l = 1 , r = 1e9;while(l + 1 < r) {int mid = (l + r) >> 1;if(check(mid,a,b)) r = mid;else l = mid;}if(check(l,a,b)) r = l;return r;
}signed main()
{int t;cin >> t;while (t--){cout << solve() << endl;}
}

F Tokitsukaze and New RenKinKama

思路：
先做一次任意交换（也可以交换自身，等于不交换），两重循环( O($n$*$n$ ))，
这时候会有两种情况：
（1）如果经过某次交换，序列恰好能成优环，solve函数返回长度为 1 的操作序列
（2）如果经过某次交换，序列仍为劣环，必然存在至少一条劣边 e ，e两侧的点{x,y}中必然有一个要与其他点进行交换，才有可能使劣e边成为优边E，进而可能促使优环的出现。总之，第二次操作必然要修复某一条劣边（这里可以用反证法想一下）。

一点儿细节：
对于每次交换，可以O (1) 的判断新生成的环是否为优环。
优边权值记为 0 ，劣边权值记为 1 ，环的权值 exd 就是边的总权值。显然，每次交换操作只会改动很少的几条边，因此不必遍历整个环，通过改动后Exd的值就能判断环上的边是否全优（Exd = 0 时 ，全是优边，出现优环）

总的时间复杂度 $O$ $($$n^3$$)$

代码：

#include <bits/stdc++.h>using namespace std;const int N = 305;
int n,k;
bool check(int *a)
{for(int i = 1; i <= n; i++){int las = i - 1;if(las == 0)las = n;if(abs(a[i]-a[las]) > k) return false ;}return true;
}bool modify(int f, vector<pair<int,int>> &op, int *a)
{int exd = 0;for(int i = 1; i <= n; i++){int las = i - 1;if(las <= 0) las = n;exd += (abs(a[i]-a[las]) > k);}for(int i = 1; i <= n; i++){if(i == f) continue;int m1 = i;int l1 = i - 1 <= 0 ? n : i - 1;int r1 = i + 1 > n ? 1 : i + 1;int m2 = f;int l2 = f - 1 <= 0 ? n : f - 1;int r2 = f + 1 > n ? 1 : f + 1;int Exd = exd;if(m1 == l2 || m1 == r2){if(m1 == l2){Exd -= (abs(a[m1] - a[l1]) > k);Exd -= (abs(a[r2] - a[m2]) > k);Exd += (abs(a[m2] - a[l1]) > k);Exd += (abs(a[r2] - a[m1]) > k);}else {Exd -= (abs(a[m2] - a[l2]) > k);Exd -= (abs(a[r1] - a[m1]) > k);Exd += (abs(a[m1] - a[l2]) > k);Exd += (abs(a[r1] - a[m2]) > k);}}else {Exd -= (abs(a[m1] - a[l1]) > k);Exd -= (abs(a[r1] - a[m1]) > k);Exd -= (abs(a[m2] - a[l2]) > k);Exd -= (abs(a[r2] - a[m2]) > k);Exd += (abs(a[m2] - a[l1]) > k);Exd += (abs(a[r1] - a[m2]) > k);Exd += (abs(a[m1] - a[l2]) > k);Exd += (abs(a[r2] - a[m1]) > k);}if(Exd == 0){op.push_back({f,i});return true;}}return false ;
}
vector<pair<int,int>> solve()
{int a[N];cin >> n >> k;for(int i = 1; i <= n; i++){cin >> a[i];}vector<pair<int,int>>op;for(int i = 1; i <= n; i++){for(int j = i; j <= n; j++){op.push_back({i,j});swap(a[i],a[j]);if(check(a)) return op;else {int f = 1;for(int t = 1; t <= n; t++){if(t == 1) {if(abs(a[t] - a[n]) > k) {f = t;break;}}else{if(abs(a[t] - a[t-1]) > k){f = t;break;}}}int m1 = f - 1 , m2 = f;if(m1 <= 0) m1 = n;if(modify(m1,op,a)) return op;if(modify(m2,op,a)) return op;}swap(a[i],a[j]);op.pop_back();}}vector<pair<int,int>> re;return re;
}int main(){//freopen("in.txt","r",stdin);int t;cin >> t;while (t--){vector<pair<int,int>> ans = solve();if(ans.empty()) cout << -1 << endl;else {cout << ans.size() << endl;for(auto it : ans){cout << it.first << " " << it.second << endl;}}}return 0;
}