记第一场CF赛，完成3道题
A题 Required Remainder
题意：给你 x、y、n 求最大的k (k<=n) 使得k%x==y
做法：二分x的倍数即可，水
寻找最大整除数，一开始while循环找，直接TLE2
#include<bits/stdc++.h>
using namespace std;
int main() {
int t, x, y,n; cin >> t;
while (t--) {
cin >> x >> y >> n;
cout << (n - y) / x * x + y << endl;
}
return 0;
}
B题 Multiply by 2, divide by 6
题意：给你一个数n 每次两个操作：乘2 除6 求最少的操作 得到1
做法：循环整除6，每次+1，然后循环整除3，每次加2
#include<bits/stdc++.h>
using namespace std;
int main() {
long long a, n, k, t;
cin >> t;
while (t--) {
cin >> a;
k = 0, n = 0;
while (a % 6 == 0) { a /= 6; ++k; }
while (a % 3 == 0) { a /= 3; k+=2; }
if (a != 1)k = -1;
cout << k << endl;
}
}
C. Move Brackets
题意：给你只包含'(' ')' 的字符串，每次操作可以选择一个字符 要么移到最后面 要么移到最前面，求最少的操作使得字符串是括号匹配的字符串
做法：先统计 '(' 个数，遇 ')' k> 0时 k--
#include<bits/stdc++.h>
using namespace std;
int main() {
int t,n, k; char c; cin >> t;
while (t--) {
k = 0;
cin >> n; while (n--) {
cin >> c;
if (c == '(')k++;
else if (k > 0)--k;
}
cout << k << endl;
}
}
第四题开始就没做出来了，记录dalao们的题解
D. Zero Remainder Array
题意：给你n长度的整数数组 a ，一个x 每次操作可以选择一个 下标i 让a[i]+=x 然后x自增1 操作2是 不选择下标 单独的x自增1
做法：a[i]对k取模 得到离k（k-a[i]%k）的距离，统计离k距离相同数量最多的，num 和 mx 答案就是 (num-1)*k+mx+1；
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int t; cin >> t;
while (t--) {
ll n, k, ans = 0, a;
cin >> n >> k;
map<ll, ll>mp;
for (int i = 0; i < n; ++i)cin >> a, mp[(k - (a%k)) % k]++;
for (auto it : mp)
if (it.first) ans = max(ans, (it.second - 1) * k + it.first + 1);
cout << ans << '
';
}
return 0;
}
E1. Reading Books (easy version)
题意：给n本书，以及一个K 每本书 可能是 （Alice 喜欢 Bob 不喜欢）（Alice 不喜欢 Bob 喜欢）（Alice 不喜欢 Bob 不喜欢） 每本书有一个阅读时间t[i] 每次只能选择一本书进行阅读。现在要求ALICE 和Bob 都至少读k本自己喜欢的书，并且时间消耗最少。
做法：
三种情况分开保存，（Alice 喜欢 Bob 不喜欢）a数组， （Alice 不喜欢 Bob 喜欢）b数组，（Alice 不喜欢 Bob 不喜欢）c数组
对a数组 b数组分别选前k个，不足k个从c里面选。都满k个后 再从c里面选共同的 同时去掉 a里面、b里面得到 的两个最大值。
#include <cstdio>
#include <algorithm>
#define maxn 200010
using namespace std;
int a[maxn],b[maxn],c[maxn],an,bn,cn;
int main(){
int n,k,i,t,x,y,ans=0;
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++){
scanf("%d%d%d",&t,&x,&y);
if(x==1&&y==1)c[++cn]=t;
else if(x==1)a[++an]=t;
else if(y==1)b[++bn]=t;
}
sort(a+1,a+1+an);
sort(b+1,b+1+bn);
n=min(an,bn);
for(i=1;i<=n;i++)
c[++cn]=a[i]+b[i];
sort(c+1,c+1+cn);
if(cn<k) printf("-1
");
else{
for(i=1;i<=k;i++)ans+=c[i];
printf("%d
",ans);
}
return 0;
}
E2
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
pli av[200001], bv[200001], cv[200001], dv[200001];
int main() {
int n, k, m;
scanf("%d %d %d", &n, &m, &k);
int aa = 0, bb = 0, cc = 0, dd = 0;
ll as = 0, bs = 0, cs = 0, ds = 0;
for (int i = 0; i < n; i++) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
if (b == 1 && c == 1) av[aa++] = {a, i};
else if (b == 1) bs += a, bv[bb++] = {a, i};
else if (c == 1) cs += a, cv[cc++] = {a, i};
else ds += a, dv[dd++] = {a, i};
}
sort(av, av + aa); sort(bv, bv + bb);
sort(cv, cv + cc); sort(dv, dv + dd);
int mai = -1, mbi = -1, mci = -1, mdi = -1;
int bi = bb, ci = cc, di = dd, q;
ll ans = 1e18, ret;
for (int i = 0; i <= aa; i++) {
if (i) as += av[i-1].first;
q = max(0, k - i);
for (int j = 0; j < 3; j++) {
if (bi < bb) bs += bv[bi++].first;
if (ci < cc) cs += cv[ci++].first;
if (di < dd) ds += dv[di++].first;
}
if (q > bb || q > cc || (i + 2*q) > m || i+bb+cc+dd < m) continue;
while (i+bi+ci+di > m) {
ll bt = (bi>q?bv[bi-1].first:-1e18);
ll ct = (ci>q?cv[ci-1].first:-1e18);
ll dt = (di>0?dv[di-1].first:-1e18);
if (bt >= ct && bt >= dt) bs -= bv[--bi].first;
else if (ct >= bt && ct >= dt) cs -= cv[--ci].first;
else ds -= dv[--di].first;
}
ret = as + bs + cs + ds;
if (ans > ret) {
ans = ret;
mai = i, mbi = bi, mci = ci, mdi = di;
}
}
if (ans > 1e17) return !printf("-1");
printf("%lld
", ans);
for (int i = 0; i < mai; i++) printf("%d ", av[i].second + 1);
for (int i = 0; i < mbi; i++) printf("%d ", bv[i].second + 1);
for (int i = 0; i < mci; i++) printf("%d ", cv[i].second + 1);
for (int i = 0; i < mdi; i++) printf("%d ", dv[i].second + 1);
}
F. Cyclic Shifts Sorting
题意：给你n长度 整数数组 a[i] 每次选择一个下标i 然后对(i,i+1,i+2)进行向右移动 i+2移到i。问最少的操作使得这个数组是递增的数组，如果不能得到则输出-1
做法：
复杂模拟，每次找到最小的那个值，然后不断的反转 移到前面去，进行n-2轮后 得到两种情况：
第一种：1 2 3 4 5 有序
第二种：1 2 3 5 4 无序。
对于第二种则需要将 5 4 的位置倒一下 选择n-2下标：
1 2 4 3 5
接着对 4 3 倒一下：
1 3 2 4 5
此时发现 只有前面出现两个相同的时候才可以得到有序的数组。
例如：
1 2 3 3 5 4 => 1 2 3 4 3 5 => 1 2 3 3 4 5
#include <bits/stdc++.h>
using namespace std;
int n, t[502], p, w;
vector<int> sol;
void q(int a) {
sol.push_back(a);
swap(t[a+2], t[a]), swap(t[a+1], t[a+2]);
}
int main()
{
cin >> w;
while(w--) {
cin >> n, sol.clear();
for (int i=1; i<=n; i++) cin >> t[i];
for (int i=1; i<=n-2; i++) {
p=i;
for (int j=i; j<=n; j++) if (t[j]<t[p]) p=j;
if (p==n) p-=2, q(p);
if ((p-i)%2) q(p-1), p++;
while (p>i) p-=2, q(p);
}
if (t[n]<t[n-1]) for (int i=1; i<=n-2; i++) if (t[i]==t[i+1]) {
for (int j=i; j<=n-2; j++) q(j), q(j);
break;
}
if (t[n-2]==t[n]) q(n-2);
if (t[n]<t[n-1]) cout << -1 << "
";
else {
cout << sol.size() << "
";
for (int i=0; i<sol.size(); i++) cout << sol[i] << " ";
cout << "
";
}
}
return 0;
}