A. Problem Generator
思路:暴力模拟,对于每个字母，如果不足m mm，就加入最终答案.
实现代码:
#include<bits/stdc++.h>
using namespace std;
#define N 2000005
#define mod 100003
typedef long long ll;
ll n, m, t, cnt, ans, sum1,sum2, maxx,k;
int x, y;
int a[N], b[N], c[N],dis[N];
bool vis[N];
vector<int>G[N];
typedef pair<int, int>pii;
priority_queue<pii, vector<pii>, greater<pii>>q;
struct node {
int a, b, c,flag;
}f[N];
int main()
{
cin >> t;
void solve();
while (t--) {
solve();
}
return 0;
}
void solve()
{
cin >> n >> m;
ans = 0;
string s;
cin >> s;
map<char, ll>p;
for (int i = 0; i < s.size(); i++) {
p[s[i]]++;
}
for (int i = 'A'; i <= 'G'; i++) {
ans += max((ll)0, m - p[i]);
}
cout << ans << endl;
}B. Choosing Cubes
思路:
我们只需要检査排完序之后比较在k位置的立方体ak与最喜欢的立方体af,的大小即可，如果ak>af，说明af的位置在k之前，一定会波删;如果ak< af，说明af的位置在k之后，一定不会被删;如果ak= af，检査ak+1，如果ak+1 = af，则有可能被删，否则一定被删。
实现代码:
#include<bits/stdc++.h>
using namespace std;
#define N 2000005
#define mod 100003
typedef long long ll;
ll n, m, t, cnt, ans, sum1,sum2, maxx,k;
int x, y;
int a[N], b[N], c[N],dis[N];
bool vis[N];
vector<int>G[N];
typedef pair<int, int>pii;
priority_queue<pii, vector<pii>, greater<pii>>q;
struct node {
int a, b, c,flag;
}f[N];
bool cmp(int x, int y) {
return x > y;
}
int main()
{
cin >> t;
void solve();
while (t--) {
solve();
}
return 0;
}
void solve()
{
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
cnt = a[m];
sum1 = sum2 = 0;
sort(a + 1, a + 1 + n, cmp);
for (int i = 1; i <= n; i++) {
if (cnt == a[i]) {
sum1 = i;
break;
}
}
for (int i = n; i >= 1; i--) {
if (cnt == a[i]) {
sum2 = i;
break;
}
}
if (k < sum1) {
cout << "NO" << endl;
return;
}
else if(k>=sum2){
cout << "YES" << endl;
return;
}
else {
cout << "MAYBE" << endl;
return;
}
}C. Sofia and the Lost Operations
思路:
若最后一个修改数存在于b数组中，那么只需要看这些修改的数能否把a数组中待修改的数全部覆盖即可，否则一定不存在。
实现代码:
#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
using namespace std;
#define N 2000005
#define mod 7777777
typedef long long ll;
int n, m, t, cnt, ans, sum1,sum, maxx;
int x, y;
int a[N], b[N],d[N];
bool vis[N];
map<int, int>k, dis;
int main()
{
cin >> t;
void solve();
int gcd(int x, int y);
while (t--) {
solve();
}
return 0;
}
void solve()
{
cin >> n;
sum = 0;
k.clear(), dis.clear();
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)
scanf("%d", &b[i]), dis[b[i]]++;
cin >> m;
for (int i = 1; i <= m; i++)
scanf("%d", &d[i]),k[d[i]]++;
if (!dis[d[m]]) {
cout << "NO" << "\n";
return;
}
if (dis.find(d[m]) == dis.end()) {
cout << "NO" << "\n";
return;
}
else {
bool flag = 1;
for (int i = 1; i <= n; i++) {
if (a[i] != b[i]) {
if (!k[b[i]]) {
flag = 0;
break;
}
k[b[i]]--;
}
}
if (flag) {
cout << "YES" << "\n";
return;
}
else {
cout << "NO" << "\n";
return;
}
}
}D. GCD-sequence
思路:
将删除前的gcd序列求出来，可以发现若要满足题意，必然需要找到gcd序列中递减的位置，并且删除与之相关的数（要记录前后两个数和他本身）。然后判断删除后的序列能否形成非递减即可。
(因为要找到递减的两个数,其原数列是三个连续数决定的,所以要记录者三个数)
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define N 2000005
#define mod 7777777
typedef long long ll;
int n, m, t, cnt, ans, num1, num2, num3, maxx;
int x, y;
int a[N], b[N],d[N];
bool vis[N];
map<int, int>k, dis;
vector<int>dp2, dp3;
int gcd(int a, int b) {
return b > 0 ? gcd(b, a % b) : a;
}
bool judge() {
for (int i = 1; i <n-2; i++) {
if (dp3[i] >= dp3[i - 1]) {
continue;
}
else {
return false;
}
}
return true;
}
int main()
{
cin >> t;
void solve();
while (t--) {
solve();
}
return 0;
}
void solve()
{
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
vector<int>dp1;
for (int i = 1; i < n; i++) {
dp1.push_back(gcd(a[i], a[i - 1]));
}
num1 = num2 = num3 = -1;
for (int i = dp1.size()-1; i >= 1; i--) {
if (dp1[i - 1] > dp1[i]) {
num1 = i + 1;
num2 = i;
num3 = i - 1;
break;
}
}
if (num1 == -1) {
cout << "YES" << endl;
return;
}
else {
dp2.clear(), dp3.clear();
for (int i = 0; i < n; i++) {
if (i == num1)
continue;
dp2.push_back(a[i]);
}
for (int i = 1; i < n-1; i++) {
dp3.push_back(gcd(dp2[i], dp2[i - 1]));
}
if (judge()) {
cout << "YES" << endl;
return;
}
dp2.clear(), dp3.clear();
for (int i = 0; i < n; i++) {
if (i == num2)
continue;
dp2.push_back(a[i]);
}
for (int i = 1; i < n - 1; i++) {
dp3.push_back(gcd(dp2[i], dp2[i - 1]));
}
if (judge()) {
cout << "YES" << endl;
return;
}
dp2.clear(), dp3.clear();
for (int i = 0; i < n; i++) {
if (i == num3)
continue;
dp2.push_back(a[i]);
}
for (int i = 1; i < n - 1; i++) {
dp3.push_back(gcd(dp2[i], dp2[i - 1]));
}
if (judge()) {
cout << "YES" << endl;
return;
}
cout << "NO" << endl;
}
}
