Codeforces Round #671 (Div. 2) (A - B、D1题）

比赛链接：https://codeforces.com/contest/1419

https://codeforces.com/contest/1419/problems

A. Digit Game

Example

input

4
1
2
1
3
3
102
4
2069

output

2
1
1
2

题意：

Raze and Breach参加比赛，给定一个 位的数字（从高位到低位 ~ )，Raze只能标记奇数位的数字，而Breach只能标记偶数的值，如果存在当仅剩一个未标记的数字时，比赛结束。 如果最后一位数字是奇数，则Raze获胜，否则Breach获胜。

#include<bits/stdc++.h>
using namespace std;
int _, n; string s;
void solve() {
    cin >> n >> s;
    bool f1 = false, f2 = false;
    for (int i = 0; i < n; i += 2)if ((s[i] - '0') % 2 == 1)f1 = true;
    for (int i = 1; i < n; i += 2)if ((s[i] - '0') % 2 == 0)f2 = true;
    if (n % 2) puts(f1 ? "1" : "2");
    else puts(f2 ? "2" : "1");
}
int main() {
    //freopen("in.txt", "r", stdin);
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> _; while (_--)solve();
}

B. Stairs

Example

input

4
1
8
6
1000000000000000000

output

1
2
1
30

思路：

待补

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll _, n, ans, now;
void solve() {
    cin >> n;
    ans = 2, now = 0;
    while ((ans - 1) * ans / 2 <= n)n -= (ans - 1) * ans / 2, now++, ans *= 2;
    cout << now << endl;
}
int main() {
    //freopen("in.txt", "r", stdin);
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> _; while (_--)solve();
}

D1. Sage’s Birthday (easy version)

https://codeforces.com/problemset/problem/1419/D1

现在有 n 个数，对 a[] 重新排序，使得好数最多

好数的定义：在数组中比相邻的两个数都小，则称为好数，当然数组最左边和最右边的数不能称之为好数

可以保证在数组 a 中，所有的数都是不相同的

观察好数定义，要在数组中相邻的两个数都小，利用样例举例

5
1 2 3 4 5 （这个时候即使乱序也没事，需要sort）
如果我们先从2开始放入b[]，间隔2
会得到：
2 x 4 x 5
然后再从1开始：
2 1 4 3 5
b[]符合好数定义

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
int n; long long a[N + 10], b[2 * N + 1];
int main() {
    //freopen("in.txt", "r", stdin);
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i)cin >> a[i];
    sort(a + 1, a + 1 + n); int idx = 1;
    cout << (n - 1) / 2 << endl;
    for (int i = 2; i <= n; i += 2)b[i] = a[idx++];
    for (int i = 1; i <= n; i += 2)b[i] = a[idx++];
    for (int i = 1; i < idx; ++i)cout << b[i] << " ";
    cout << endl;
}