牛客小白月赛68【A-E】

链接
传送门

A.Tokitsukaze and New Operation【模拟】

分析
根据题意模拟就行，合理运用STL可以简化代码。
实现

#include <bits/stdc++.h>
#define ll long long
#define ls (u << 1)
#define rs (u << 1 | 1) 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair<int, int> PII;
void solve() {string a, b;cin >> a >> b;int n = a.size(), m = b.size();if (n != m) {cout << -1 << '\n';return;}string ans;for (int i = 0; i < n; i++) {ans += to_string((a[i] - '0') * (b[i] - '0'));//to_stirng函数可以使得int转换为string类型}cout << ans << '\n';
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while (T--) {solve();}
}

B.Tokitsukaze and Order Food Delivery【模拟、特判】

分析
这题看似唬人，其实不难，因为这里只说了取一道菜所以只需暴力取最优的即可。
实现

#include <bits/stdc++.h>
#define ll long long
#define ls (u << 1)
#define rs (u << 1 | 1) 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair<int, int> PII;
void solve() {int n, a, b;cin >> n >> a >> b;int ans = inf;while (n--) {int k, x, y;cin >> k >> x >> y;while (k--) {int c;cin >> c;if (c >= a && c >= x) {c = max(0, c - b - y);} else if (c >= a) {c = max(0, c - b);} else if (c >= x) {c = max(0, c - y);}ans = min(ans, c);}}cout << ans << '\n';
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while (T--) {solve();}
}

C.Tokitsukaze and Average of Substring【暴力、前缀】

分析
这里n的范围是5000，我们可以直接枚举两端，对26个字母统计前缀字符数，即可，时间复杂度O(n^2*26)，注意可能卡map，这里用数组。
实现

#include <bits/stdc++.h>
#define ll long long
#define ls (u << 1)
#define rs (u << 1 | 1) 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair<int, int> PII;
const int N = 5005;
char s[N];
int cnt[26][N];
void solve() {int n;scanf("%d", &n);for (int i = 1; i <= n; i++) {for (int j = 0; j < 26; j++) {cnt[j][i] = 0;}}scanf("%s", s + 1);for (int i = 1; i <= n; i++) {char ch = s[i];for (int j = 0; j < 26; j++) {if (ch - 'a' == j) cnt[j][i] = cnt[j][i - 1] + 1;else cnt[j][i] = cnt[j][i - 1];//继承前缀}} 
//	for (int i = 0; i < 26; i++) {
//		for (int j = 1; j <= n; j++) {
//			cout << cnt[i][j] << ' ';
//		}
//		cout << '\n';
//	}double ans = 0;for (int i = 1; i <= n; i++) {for (int j = i; j <= n; j++) {int sum = 0;for (int k = 0; k < 26; k++) {int c = cnt[k][j] - cnt[k][i - 1];sum += c * (c - 1) / 2;//统计相同的对数}ans = max(ans, 1.0 * sum / (j - i + 1));}}printf("%.6lf\n", ans);
}
int main() {
//	ios::sync_with_stdio(false);
//	cin.tie(0);int T = 1;cin >> T;while (T--) {solve();}
}

D.Tokitsukaze and Development Task【记忆化搜索】

分析
首先300的数目步数最多300，总共有8种更新方法，求最小操作次数，但是这里组数有点多，考虑用记忆化搜索，总时间复杂度为O(n^2).
实现

#include <bits/stdc++.h>
#define ll long long
#define ls (u << 1)
#define rs (u << 1 | 1) 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair<int, int> PII;
const int N = 5005;
int go[6] = {1, -1, 10, -10, 100, -100};
int dp[305];
bool vis[305];
void bfs(int tar) {for (int i = 10; i <= 300; i++) vis[i] = 0;vis[10] = 1;queue<PII> q;q.push({10, 0});while (!q.empty()) {int x = q.front().first, s = q.front().second;if (x == tar) {//找到目标值就弹出，先进先出，所以步数是最小的dp[tar] = s;return;}q.pop();for (int i = 0; i < 8; i++) {int nx;if (i < 6) nx = x + go[i];else if (i == 6) nx = 10;else nx = 300;if (nx < 10 || nx > 300 || vis[nx]) continue;vis[nx] = 1;int ns = s + 1;q.push({nx, ns});}}
}
void solve() {int a, b, c, d;
//	cin >> a;
//	bfs(a);
//	cout << dp[a] << '\n';cin >> a >> b >> c >> d;if (dp[a] == -1) bfs(a);if (dp[b] == -1) bfs(b);if (dp[c] == -1) bfs(c);if (dp[d] == -1) bfs(d);cout << dp[a] + dp[b] + dp[c] + dp[d] << '\n';  
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;for (int i = 11; i <= 305; i++) dp[i] = -1;//0也算，所以初始化-1while (T--) {solve();}
}

E.Tokitsukaze and Colorful Chessboard【预处理，二分】

分析
为了更加充分地利用空间，我们需要紧凑地使用格子，所以把棋盘分成奇数格和偶数格使用，预处理平方数，可以得到所有奇数格的数目和偶数格的数目，如果平方数是偶数则两者一样多否则奇数多1个，我们查询的两个数较大的那一个放在奇数格上，利用二分，但是，此时另一个数可能不行，因为如果说这个数是对应的平方数是奇数，而两者又是一样大的话，是无法放入的，例如：n=3,b[3]=5,c[3] = 4, x = y = 5,必须往右挪一格（可能前面有需要几格的，但是不多）到y符合，在向右挪的时候由于单调性，x始终符合。注意爆int。
实现

#include <bits/stdc++.h>
#define ll long long
#define ls (u << 1)
#define rs (u << 1 | 1) 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 5;
int go[6] = {1, -1, 10, -10, 100, -100};
ll a[N], b[N], c[N];
void solve() {ll x, y;cin >> x >> y;if (x < y) swap(x, y);int n = 1e5;int p = lower_bound(b + 1, b + 1 + n, x) - b;
//	cout << b[p] << '\n';while (c[p] < y) p++;//稍微挪一格左右cout << p << '\n'; 
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;int m = 1e5;for (int i = 1; i <= m; i++) a[i] = 1ll * i * i;//这里爆intfor (int i = 1; i <= m; i++) {b[i] = (a[i] + 1) / 2;c[i] = a[i] - b[i];}
//	cout << b[70000] << '\n';
//	for (int i = 1; i <= 5; i++) cout << c[i] << '\n';while (T--) {solve();}
}