Codeforces Round #690 (Div. 3)
B. Last Year's Substring
题意
让你在字符串中删除一段连续的区间是否能凑齐2020
思路
如果要删除一段连续的区间那么直接讨论所有情况，因为2020只有4个字符。
全在左，全在右....
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
void solve() {
int n; cin >> n;
string str; cin >> str;
int f = 0;
if (str[0] == '2' && str[n - 1] == '0' && str[n - 2] == '2' && str[n - 3] == '0') f = 1;
if (str[0] == '2' && str[1] == '0' && str[2] == '2' && str[3] == '0') f= 1;
if (str[n - 1] == '0' && str[n - 2] == '2' && str[n - 3] == '0' && str[n - 4] == '2') f = 1;
if (str[0] == '2' && str[1] == '0' && str[n - 1] == '0' && str[n - 2] == '2') f = 1;
if (str[0] == '2' && str[1] == '0' && str[2] == '2' && str[n - 1] == '0') f = 1;
if (f) cout << "YES
";
else cout << "NO
";
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
C. Unique Number
题意
给你一个数x的各个位的和，让你找到最小的这个数，各个位和为x
思路
dfs，后来看到了学长写的循环，倒序相加，给每次加的数都乘以10就可以保证倒序。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
//#define int long long
const int N = 2e5 + 10;
void solve() {
int x; cin >> x;
if (x > 45) {
cout << -1 << endl;
return ;
}
int tot = 0, q = 9, res = 0, b = 1;
while (x) {
int mi = min(q, x);
res = res + b * mi;
b *= 10;
x -= mi;
q --;
}
cout << res << endl;
}
signed main() {
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
D. Add to Neighbour and Remove
题意
给你n个数，让你在最少的合并操作下，将元素变为全部一样
思路
我的思路：
枚举第一个合并的长度，因为他肯定是连续的，然后根据这个长度确定一个和，继续往后枚举其他的
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int a[3005], sum[3005];
void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + a[i];
int f = 0, cnt = 1e9 + 10, c = 0;
for (int len = 1; len <= n; ++len) {
c = 0;
int l = 1, r = l + len - 1;
int t = sum[r] - sum[l - 1];
c += (r - l);
while (l + 1 <= n) {
l = r + 1, r = l;
int tot = 0;
while (tot < t && r <= n) {
tot = sum[r] - sum[l - 1];
++r;
}
--r;
if (tot > t) break;
c += (r - l);
if (r == n && t == tot) {
cnt = min(cnt, c);
break;
}
}
}
if (cnt == 1e9 + 10) cnt = n - 1;
cout << cnt << endl;
}
signed main() {
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
大佬的思路：
这个值一定是总和的因子，那么我们枚举这个因子即可
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N];
int n; int s = 0;
int check(int x) {
int cur = 0;
for (int i = 1; i <= n; ++i) {
cur += a[i];
if (cur == x) {
cur = 0;
}
if (cur > x) break;
}
if (cur == 0) return n - s / x;
return n - 1;
}
void solve() {
cin >> n;
s = 0;
for (int i = 1; i <= n; ++i) cin >> a[i], s += a[i];
int ans = n - 1;
for (int i = 1; i * i <= s; ++i) {
if (s % i == 0) {
ans = min({ans, check(i), check(s / i)});
}
}
cout << ans << endl;
}
signed main() {
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
E1. Close Tuples (easy version)
题意
给你n个数，让你选3个且其最大值最小值差小于等于2，问你有多少种可能
思路
排序后枚举每个值作为最小值的可能，然后相加
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long LL;
const int mod = 1e9 + 7;
LL f(LL x) {
return x * (x - 1) / 2;
}
int a[N];
void solve() {
int n, m, k; cin >> n;
m = 3, k = 2;
for (int i = 1; i <= n; ++i) cin >> a[i];
sort(a + 1, a + 1 + n);
LL ans = 0;
for (int i = 1; i <= n; ++i) {
int l = i + 1, r = upper_bound(a + 1, a + 1 + n, a[i] + k) - a;
ans = ans + f(r - l);
}
cout << ans << endl;
}
signed main() {
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
E2. Close Tuples (hard version)
题意
给你n个数你要选m个且其最大值最小值之差不超过k
思路
枚举每个数作为最小的数的可能，然后求和
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long LL;
const int mod = 1e9 + 7;
int qmi(int a, int k) {
int res = 1;
while(k) {
if(k & 1) res = (LL)res * a % mod;
k >>= 1;
a = (LL)a * a % mod;
}
return res;
}
int fact[N], infact[N];
void init(int n) {
fact[0] = infact[0] = 1;
for(int i = 1; i <= n; i ++) {
fact[i] = (LL)fact[i - 1] * i % mod;
infact[i] = qmi(fact[i], mod - 2);
}
}
int C(int a, int b) {
if (b > a) return 0;
return (LL)fact[a] * infact[a - b] % mod * infact[b] % mod;
}
int a[N];
void solve() {
int n, m, k; cin >> n >> m >> k;
for (int i = 1; i <= n; ++i) cin >> a[i];
sort(a + 1, a + 1 + n);
LL ans = 0;
for (int i = 1; i <= n; ++i) {
int l = i + 1, r = upper_bound(a + 1, a + 1 + n, a[i] + k) - a;
ans = (ans + C(r - l, m - 1)) % mod;
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
init(N - 5);
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
F. The Treasure of The Segments
题意
给你n个区间，每个区间有[l,r]，问你最少要删除多少个区间才能使剩下的区间中的一个区间和所有剩下的区间都相交
思路
如果一个区间和其他区间有交集那么分为两种情况
- 这个区间的左端点小于等于相交区间的右端点
- 这个区间的右端点大于等于相交区间的左端点
我们对一个区间的左端点和右端点分开，然后分别进行排序，枚举每一个区间作为可能去判断。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
struct LINE {
int l, r;
}line[N];
void solve() {
int n; cin >> n;
vector<int>l, r;
for (int i = 1; i <= n; ++i) {
cin >> line[i].l >> line[i].r;
l.push_back(line[i].l);
r.push_back(line[i].r);
}
sort(l.begin(), l.end());
sort(r.begin(), r.end());
int ans = 0x3f3f3f3f;
for (int i = 1; i <= n; ++i) {
int idl = upper_bound(l.begin(), l.end(), line[i].r) - l.begin();
int idr = lower_bound(r.begin(), r.end(), line[i].l) - r.begin();
ans = min(ans, n - idl + idr);
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T = 1;
cin >> T;
while (T--) {
solve();
}
}