Codeforces Round #653 (Div. 3)
Required Remainder
Thinking(binary search)
既然是找最大值问题，我又懒得去推式子，于是我直接就上了一个二分，二分写法比结论稍微繁琐了一点吧，但是还是挺好想的。
根据题意，我们的任务就是找到一个最大的数，满足(ans = k * x + y <= n)，于是我们就可以通过二分枚举(k)，来得到我们的答案。通过题目给定的(x, y, z)的范围，我们可以确定二分的区间最多不过(0 ~ 1^9)。
Coding
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-7;
inline ll read() {
ll f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (48 ^ c);
c = getchar();
}
return f * x;
}
const int N = 1e6 + 10;
char str[N];
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int _ = read();
while(_--) {
ll x = read(), y = read(), n = read();
ll l = 0, r = 1e9 + 10;
while(l < r) {
ll mid = l + r + 1 >> 1;
if(mid * x + y <= n) l = mid;
else r = mid - 1;
}
printf("%lld
", l * x + y);
}
return 0;
}
Multiply by 2, divide by 6
Thinking
判断能否通过0个或者多个乘二的操作，使数字变成6的倍数。我们想想6的两个质因子(2, 3)，要想达到这个目的，对于初始的(n)，只可能有这两种质因子，否则我们一定达不到我们的目标。于是我们可以先对(n)，进行(2, 3)的质因数提取，假设得到的(2)的因子个数是(num2)， (3)的因子个数是(num3)，因为我们是同时消去(2, 3)因子的，并且只能增加或者不增加(2)的因子个数，所以只有当(num2 <= num3)时，才能保证我们可以消去所有的(2, 3)因子，最后变成(1)。
Coding
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-7;
inline ll read() {
ll f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (48 ^ c);
c = getchar();
}
return f * x;
}
const int N = 1e6 + 10;
char str[N];
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int _ = read();
while(_--) {
ll n = read();
int num2 = 0, num3 = 0;
while(n % 3 == 0) {
n /= 3;
num3++;
}
while(n % 2 == 0) {
n /= 2;
num2++;
}
//最后n不是1说明还存在其他的质因子。
if(n != 1 || num2 > num3) puts("-1");
else printf("%d
", num3 + num3 - num2);
}
return 0;
}
Move Brackets
Thinking(Stack)
我们先找到所有的符合匹配的括号，最后就只剩下一种非法的括号了，以这种形式存在() ()形成()))))((((()这样的排列，所以我们只需要将其后面的移到前面去，或者前面的移到后面去，任选一种进行操作，因此我们的花费将会是最后无法匹配的括号的对数，也就是栈中的元素的一半。
Coding
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-7;
inline ll read() {
ll f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (48 ^ c);
c = getchar();
}
return f * x;
}
const int N = 1e6 + 10;
char str[N];
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int _; cin >> _;
while(_--) {
int n; cin >> n;
stack<char> stk;
for(int i = 1; i <= n; i++) {
char temp; cin >> temp;
if(stk.empty() || stk.top() == temp || temp == '(') stk.push(temp);
else stk.pop();
}
printf("%d
", stk.size() / 2);
}
return 0;
}
Zero Remainder Array
Thinking
对于给定的序列，我们需要的就是(x pmod k = (1, 2 …… k - 2, k - 1))，这样的数，才能使我们的序列变成都是(k)的倍数，假定(k = 4)，数组中存在两个数分别为(3, 7)， 他们有一个共同点(3 pmod k = 7 pmod k)，也就是说我们在(x pmod k)从(0 -> k - 1)，的一趟循环中，最多只能使其中的一个数变成(a_i pmod k = 0)，想必看到这里应该就搞懂了这道题了，我们就是要找到(a_i pmod k)后出现的次数最多的非零数，当有多个出现次数相同的数时我们取(a_i pmod k)的最小值，因为那个最小值一定是当(x)足够大的时候才会满足条件。
Coding
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-7;
inline ll read() {
ll f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (48 ^ c);
c = getchar();
}
return f * x;
}
const int N = 2e5 + 10;
int a[N];
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int _ = read();
while(_--) {
int n = read(), k = read();
for(int i = 1; i <= n; i++) {
a[i] = read();
a[i] %= k;
}
sort(a + 1, a + 1 + n, greater<int> ());
int now_num = 1, ansn = a[1], num = 1;
for(int i = 2; i <= n && a[i] != 0; i++) {
if(a[i] == a[i - 1]) now_num++;
else now_num = 1;
if(now_num >= num) ansn = a[i], num = now_num;
}
if(ansn == 0){
puts("0");
continue;
}
// cout << num << " " << ansn << endl;
printf("%lld
", 1ll * k * (num - 1) + k - ansn + 1);
}
return 0;
}
Reading Books (easy version)
Thinking(Sort, greedy)
题意这里就不说明了，对于给定的条件，我们要同时满足(Alice and Bob)都要读至少(k)本书，所以我们可以指定一个策略，不管这本书是(Alice or Bob)喜欢，还是他们两同时喜欢，我们都同时增加(Alice and Bob)的当前的书的数量，因此在之前我们就需要对书本分类(Alice)喜欢的数组a，(Bob)喜欢的数组b，两个人都喜欢的数组c。接下来就时对这三个数组分别按照元素大小从小到大进行排序
当我们当前枚举的(a_i + b_j <= c_k)时我们显然贪心的选择(a_i, b_j)这两本书，所以我们的总花费将会变成(ans += a_i + b_j)，否则的话我们将会选择(c_k)，花费将变成(ans += c_k)。
当我们第一个点枚举完了后，大致存在三种情况(a)不可选，(b)不可选，(c)不可选。
所以接下来的枚举我们必须分类讨论了当(a || b)，不可选的时候，我们要达到条件只能通过选择(c)来进行。否则的话我们就只能选择(a, b)两个组合选取了。
Code
#include <bits/stdc++.h>
#define mp make_pair
// #define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-7;
inline ll read() {
ll f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (48 ^ c);
c = getchar();
}
return f * x;
}
const int N = 2e5 + 10;
struct Node {
int value, fa, fb;
void input() {
value = read(), fa = read(), fb = read();
}
void out() {
printf("%d %d %d
", value, fa, fb);
}
bool operator < (const Node & t) const {
return value < t.value;
}
}a[N], b[N], c[N], in;
//结构体就是数组的用处，不用管。是我自己一开始思路想的有点复杂，然后就写了这么一个结构体。
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n = read(), k = read(), na = 0, nb = 0, nc = 0;
for(int i = 1; i <= n; i++) {
in.input();
if(in.fa && in.fb) c[++nc] = in;
else if(in.fa) a[++na] = in;
else if(in.fb) b[++nb] = in;
//一定要注意特判 0 0的情况。
}
// cout << na << " " << nb << " " << nc << endl;
sort(a + 1, a + 1 + na);
sort(b + 1, b + 1 + nb);
sort(c + 1, c + 1 + nc);
int pa = 1, pb = 1, pc = 1, flag = 0;
int numa = 0, numb = 0;
ll ans = 0;
while(pa <= na && pb <= nb && pc <= nc) {
if(a[pa].value + b[pb].value <= c[pc].value) {
ans += a[pa].value + b[pb].value;
pa++, pb++;
}
else {
ans += c[pc].value;
pc++;
}
numa++, numb++;
if(numa >= k && numb >= k) {
flag = 1;
break;
}
}
// cout << ans << " " << numa << " " << numb << endl;
if(flag) {
printf("%lld
", ans);
return 0;
}
if(pa > na || pb > nb) {
while(pc <= nc) {
ans += c[pc].value;
pc++;
numa++, numb++;
if(numa >= k && numb >= k) {
flag = 1;
break;
}
}
}
else {
while(pa <= na && pb <= nb) {
ans += a[pa].value + b[pb].value;
pa++, pb++;
numa++, numb++;
if(numa >= k && numb >= k) {
flag = 1;
break;
}
}
}
if(flag) {
printf("%lld
", ans);
return 0;
}
puts("-1");
return 0;
}