Rudolf and k Bridges
Problem - E - Codeforces
题意
给定一个n * m的二维矩阵，每个点有一个值，代表成本。
对于任意要建造桥的一行 i ，需要建造一些支架并满足以下条件：
- (i, 1) 必须安装一个支架
- (i, m) 必须安装一个支架
- 任意相邻支架之间的距离不大于 d 。
需要连续建造 k 座桥，需要保证最小化成本。
解题思路
对于每一行来说，就是一个经典的滑动窗口优化 dp ，最后在找到成本最小的连续的 k 行就可以。
代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back
typedef long long ll;
typedef pair<int,int> PII;
const int N = 1e6 + 10, inf = 1 << 30;
void solve() {
int n, m, k, d;
cin >> n >> m >> k >> d;
vector<ll> cost(n);
for (int i = 0; i < n; i ++ ) {
vector<ll> a(m);
for (int i = 0; i < m; i ++ ) cin >> a[i];
deque<ll> q;
q.push_front(0);
vector<ll> dp(m);
dp[0] = 1;
//滑动窗口
for (int j = 1; j < m; j ++ ) {
while (q.size() && j - q.front() - 1 > d) q.pop_front();
dp[j] = dp[q.front()] + a[j] + 1;
while (q.size() && dp[q.back()] >= dp[j]) q.pop_back();
q.push_back(j);
}
cost[i] = dp[m - 1];
}
//求出最小的连续k
vector<ll> v;
for (int i = 0; i + k - 1 < n; i ++ ) {
ll ans = 0;
for (int j = i; j <= i + k - 1; j ++ ) {
ans += cost[j];
}
v.pb(ans);
}
sort(v.begin(), v.end());
cout << v[0] << endl;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin >> t; while (t -- )
solve();
return 0;
}
Rudolf and k Bridges
Problem - B - Codeforces
题意
给定一个2 * n 的网络，只有0 和 1两个字符，现在要从左上角走到右下角，根据路程上的数字组成字符串。
需要找到字典序最小的字符串。并且输出有多少个最小。
解题思路
字典序，先保证字符串长度最小，也就是只有一步是向下走的。
当第一次向下走是 0 ，向右走是 1 的时候，向下，此时就是字典序最小的路径。
然后找个数，就从此点向左移动，只要向左和向上是相同的，那就同样是最小的一种可能。
代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back
typedef long long ll;
typedef pair<int,int> PII;
const int N = 1e6 + 10, inf = 1 << 30;
void solve() {
int n;
cin >> n;
string a, b;
cin >> a >> b;
int idx = n - 1;
for (int i = 0; i < n; i ++ ) {
if (a[i + 1] > b[i]) {
idx = i;
break;
}
}
for (int i = 0; i <= idx; i ++ ) {
cout << a[i];
}
for (int i = idx; i < n; i ++ ) {
cout << b[i];
}
cout << endl;
int cnt = 1;
while (idx >= 0 && a[idx] == b[idx - 1]) {
cnt ++ ;
idx -- ;
}
cout << cnt << endl;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin >> t; while (t -- )
solve();
return 0;
}
Informatics in MAC
### [Problem - B - Codeforces](https://codeforces.com/contest/1935/problem/B)
#### 题意
给定一个长度为 n 的数组 a，需要把他分成 k (k > 1) 字段，使得每个字段上的 MEX都相等。
MEX 不属于该数组的最小的非负整数。
#### 解题思路
最优解就是分成两个子段，保证两个子段内的MEX 相等即可。
也就是先找出整个数组的MEX，那么要保证两个子数组的 MEX 都是这个整个数组的MEX，因为如果一个数不存在，作为最小的未出现的最小数，那么两个子段内一定也未出现。必有一个子段的MEX是这个值，要保证相等，就是要保证另一个子段的MEX也是这个值。
#### 代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back
typedef long long ll;
typedef pair<int,int> PII;
const int N = 1e6 + 10, inf = 1 << 30;
void solve() {
int n;
cin >> n;
vector<int> a(n);
vector<bool> have(n);
for (int i = 0; i < n; i ++ ) {
cin >> a[i];
if (a[i] < n) {
have[a[i]] = 1;
}
}
int count = 0;
while (have[count]) {
count ++ ;
}
int l1, r1, l2, r2;
map<int,int> mp;
l1 = 0, r2 = n - 1;
for (int i = 0; i < n; i ++ ) {
if (a[i] < count) mp[a[i]] ++ ;
if (mp.size() == count) {
r1 = i;
break;
}
}
l2 = r1 + 1;
map<int,int> mp2;
for (int i = l2; i < n; i ++ ) {
if (a[i] < count) mp2[a[i]] ++ ;
}
if (mp2.size() == count) {
cout << 2 << endl;
cout << l1 + 1 << " " << r1 + 1 << endl;
cout << l2 + 1 << " " << r2 + 1 << endl;
return ;
}
cout << -1 << endl;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin >> t; while (t -- )
solve();
return 0;
}
Yet Another Coin Problem
Problem - B - Codeforces
- 小清新题面，使我的思路一坨
题意
给定一个整数 n 。现在有五种不同的硬币，分别是 1， 3， 6， 10， 15。需要找出最少的硬币数量，使得总价值相加正好是 n 。
解题思路
初见，或许可以莽过去？直接用尽量用最大的。
复写，5个数，或许dfs？然后并不能穷举所有情况
终见，尽量用15是没错的。问题是其他如何分配。一顿分析，得出以下结论：
- 1的数量最多2个，因为3个就可以被3给替代。
- 3的数量最多1个，因为2个3就可以被6替代。
- 6的数量最多4个，因为5个6可以被2个15替代。
- 10的数量最多2个，因为3个10就可以被2个15替代。
- 再多的数量，通过取余就可以分析出来。
似见过，又没见过的类型的题。
代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back
typedef long long ll;
typedef pair<int,int> PII;
const int N = 1e6 + 10, inf = 1 << 30;
void solve() {
int n;
cin >> n;
int res = inf;
for (int i = 0; i <= 2; i ++ ) {
for (int j = 0; j <= 1; j ++ ) {
for (int k = 0; k <= 4; k ++ ) {
for (int u = 0; u <= 2; u ++ ) {
int ans = n - 1 * i - 3 * j - 6 * k - 10 * u;
if (ans >= 0 && ans % 15 == 0) {
res = min(res, i + j + k + u + ans / 15);
}
}
}
}
}
cout << res << endl;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin >> t; while (t -- )
solve();
return 0;
}
Turtle Tenacity: Continual Mods
Problem - D - Codeforces
题意
给定一个长度为 n 的数组，判断是否可以通过重排使得从左到右取余的结果不等于 0.
解题思路
贪心的像，如果最小的数只有一个，那么最后的结果就是这个最小的数。
如果最小的数不止一个，只需要变出一个更小的数即可。也就是存在一个数不能整除这个最小的数。
代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back
typedef long long ll;
typedef pair<int,int> PII;
const int N = 1e6 + 10, inf = 1 << 30;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i ++ ) {
cin >> a[i];
}
sort(a.begin(), a.end());
if (a[0] != a[1]) {
cout << "YES" << endl;
return ;
}
for (int i = 0; i < n; i ++ ) {
if (a[i] % a[0]) {
cout << "YES" << endl;
return ;
}
}
cout << "NO" << endl;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin >> t; while (t -- )
solve();
return 0;
}
