Codeforces Round 863 (Div. 3)
A. Insert Digit
题意:插入一个字母使得这个数字最大化
思路:只要从前往后便利就行
#include <iostream>
using namespace std;
void solve() {
int n, k;
cin >> n >> k;
bool x = true,y=false;
for (int i = 0; i < n; i++) {
char b;
cin >> b;
int a = b - '0';
if (a < k && x) {
cout << k;
x = false;
}
cout << a;
}
if (x) {
cout << k;
}
cout << "\n";
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
B. Conveyor Belts
题意:从(x1,y1)到(x2,y2)所需能量,每变换一次轨道需要能量
思路:确定是哪个轨道就行
#include <iostream>
#include <cmath>
using namespace std;
void solve() {
int n = 0, x1 = 0, x2 = 0, y1 = 0, y2 = 0;
cin >> n >> x1 >> y1 >> x2 >> y2;
int a1 = min(x1, min(n - x1 + 1, min(y1, n - y1 + 1)));
int a2 = min(x2, min(n - x2 + 1, min(y2, n - y2 + 1)));
cout << abs(a1 - a2) << "\n";
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
C. Restore the Array
*前面卡了一会因为以为a的长度是不确定的,但是他是确定的读题很重要!!!!!!!
题意:给你一个b数组他是由a数组两个相邻元素的最大值而决定且b的长度为n-1,a的长度为n
思路:
#include <bits/stdc++.h>
using namespace std;
const int MAX = 2e5 + 10;
int a[MAX];
void solve() {
int n;
cin >> n;
bool x = true;
for (int i = 1; i < n; i++) {
cin >> a[i];
}
a[0] = a[1];
a[n] = a[n - 1];
for (int i = 0; i < n; i++) {
cout << min(a[i], a[i + 1]) << " ";
}
cout << "\n";
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
D. Umka and a Long Flight
题意:给一个长方形他的边长是斐波那契数列(典中典就不描述了),然后给定一个坐标(x,y),问能否最后剩下这个坐标上的方形为1*1,分割的矩形中有个要求:有一个矩阵为正方形而且其边长是等于斐波那契的
思路:
ps:以上为题目给的图(讲真看了这图我觉得这个题目难度至少下降两个level)
按照斐波那契来分割矩形(边割边转(坐标问题画图理解就是了))
#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[55];
void fab() {
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= 45; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
}
bool cut(int n, int x, int y) {
if (n == 1) return true;
int mid = dp[n + 1] / 2;
if (y <= mid) y = dp[n + 1] - y + 1;
if (y <= dp[n]) return false;
return cut(n - 1, y - dp[n], x);
}
void solve() {
int n, x, y;
cin >> n >> x >> y;
if (cut(n, x, y)) cout << "Yes\n";
else cout << "NO\n";
}
signed main() {
int t;
cin >> t;
fab();
while (t--) {
solve();
}
return 0;
}
E. Living Sequence
题意:简单来说就是一旦数字里面有一个位数含有4就跳过
第一眼dp,第二眼1e12怎么dp,不会!gg
思路:没有4,就相当于将10进制变成了9进制,然后每个数组映射(太妙了kao)
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[22];
int x[10] = {0, 1, 2, 3, 5, 6, 7, 8, 9};
void solve() {
int n;
cin >> n;
int cnt = 0;
while (n) {
a[++cnt] = x[n % 9];
n /= 9;
}
for (int i = cnt; i > 0; i--) {
cout << a[i];
}
cout << "\n";
}
signed main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
后面的题慢慢补,每道题只有三位数太夸张