A New Year and the Christmas Ornament

$ans=3min(y,b-1,r-2)$。

B New Year and the Treasure Geolocation

给出 $n$ 组坐标和 $n$ 组偏移，每一个坐标对应一个偏移，顺序打乱，但是所有坐标加偏移得到的位置相同。

答案为 $x$ 和 $y$ 的均值。

C New Year and the Sphere Transmission

$n$ 个人组成一个环，从第 $1$ 个开始间隔 $k(1 \le k \le n)$ 报数，直到回到 $1$，定义 $f_k$ 表示这个循环节的编号之和，输出 $n$ 的所有可能 $f$。

编号为 $k$ 的路径是一个首项为 $1$ 的公差为 $\gcd(n,k)$ 的等差数列（由裴蜀定理容易知道），$O(1)$ 计算 $f_k$。因为只有 $n$ 的因子才对答案有贡献，质因数分解即可。

D New Year and the Permutation Concatenation

将 $1,2,\cdot\cdot\cdot,n$ 的所有排列按字典序连在一起，求长度为 $n$ 的连续子区间之和为 $\frac{n(n+1)}{2}$ 的个数。

将每个排列分成两块，前面 $k$ 个的排列的每一个对应了 $n-k$ 的排列，连续的 $(n-k)!$ 个两边连在一起对答案有贡献，$g(k)=\frac{n!}{k!}(k!-1)$，对 $g(k)$ 求和。

E New Year and the Acquaintance Estimation

$n+1$ 个点的图，给出前 $n$ 个点的度数序列，问第 $n+1$ 个点的所有可能取值。

根据握手定理可以知道最后一点度数的奇偶性，并且如果度数可以取到 $x,y(x < y)$，那么 $[ x, y ]$ 中都可以很容易构造出来。

因此可以二分上下界。

对于一个点的度数是否可行，可以应用 Erdos-Gallai Theorem 判定。

F New Year and the Mallard Expedition

一个人从左往右走，道路被分为很多条草地、水和山，在草地上速度为 $5m/s$，在水里游的速度为 $3m/s$，飞的速度为 $1m/s$，每走或游一米可以获得一点能量，飞行每一米都需要一点能量，求最小时间（所有路程能量都是在实数范围内取值）。

考虑贪心，在草上走路，在水里游，在山上飞。如果飞山时能量不足，就在之前补充能量。如果最后能量多余，能量的一半提供给草地和水里（消耗能量和没有获取能量）。能量兑换为路程时，必须要满足路程数的两倍不超过能量总数，因为飞山的时候可能会要求必须在草里获取能量。

感觉不知道自己在说啥了。。。

代码

A

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 100000 + 5;

int y, b, r;

int main(){
    cin >> y >> b >> r;
    int ans = min(y, min(b - 1, r - 2));
    cout << ans * 3 + 3;
    return 0;
}

B

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 100000 + 5;

int n, x[maxn], y[maxn], a[maxn], b[maxn];

int main(){
    scanf("%d", &n); 
    ll sumx = 0, sumy = 0;
    for (int i = 1; i <= n; i++) scanf("%d%d", x + i, y + i), sumx += x[i], sumy += y[i];
    for (int i = 1; i <= n; i++) scanf("%d%d", a + i, b + i), sumx += a[i], sumy += b[i];
    cout << sumx / n << ' ' << sumy / n;
    return 0;
}

C

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 100000 + 5;

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

ll n;

ll cal(ll g) {
    return n / g * (n - g + 2) / 2;
}

int main(){
    cin >> n;
    vector<int> d;
    for (ll i = 1; i * i <= n; i++) {
        if (n % i) continue;
        d.push_back(i);
        if (i != n / i) d.push_back(n / i);
    }
    set<ll> ans;
    for (int& x: d) {
        if (x == n) {
            ans.insert(1); continue;
        }
        ll g = gcd(n, x);
        ans.insert(cal(g));
    }
    for (ll x: ans) printf("%I64d ", x);
    return 0;
}

D

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int maxn = 100000 + 5;

int n;

int main(){
    cin >> n;
    ll x = 1, y = 0;
    for (ll i = n; i > 1; i--) x = x * i % mod, y = (x + y) % mod;
    // cout << x << ' ' << y << endl;
    cout << (n * x % mod - y + mod) % mod;
    return 0;
}

E

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 500000 + 5;

bool cmp(int x, int y) { return x > y; }
int n, a[maxn], b[maxn];
ll sum = 0;

int check(int x) {
    for (int i = 1; i <= n; i++) b[i] = a[i]; b[n + 1] = x;
    sort(b + 1, b + n + 2, cmp);
    int p = 0; for (int i = 1; i <= n + 1; i++) if (b[i] == x) p = i;
    ll sum = 0, s2 = 0; int j = n + 1;
    for (int i = 1; i <= n + 1; i++) {
        sum += b[i];
        while (j > i && b[j] <= i) s2 += b[j--];
        if (j < i) s2 -= b[i];
        if (sum > 1ll * i * (i - 1) + s2 + 1ll * i * max(j - i, 0)) {
            if (b[i] > x) return -1;
            else return 1;
        }
    }
    return 0;
}

int main(){
    scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", a + i), sum += a[i];
    sort(a + 1, a + 1 + n, cmp);
    sum %= 2;
    int l = 0, r = (n - sum) / 2, u = -1, d = -1;
    while (l <= r) {
        int m = l + r >> 1;
        if (check(2 * m + sum) == -1) l = m + 1;
        else r = m - 1, d = m;
    }
    l = d, r = (n - sum) / 2;
    while (l <= r) {
        int m = l + r >> 1;
        if (check(2 * m + sum) == 1) r = m - 1;
        else l = m + 1, u = m;
    }
    // cout << u << ' ' << d << endl;
    if (u == -1 || d == -1) return puts("-1"), 0;
    for (int i = d; i <= u; i++) printf("%d ", 2 * i + sum);
    return 0;
}

F

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 100000 + 5;

int n;
ll l[maxn];
char s[maxn];

int main(){
    scanf("%d", &n); 
    for (int i = 1; i <= n; i++) scanf("%I64d", l + i);
    scanf("%s", s + 1);
    ll ans = 0, sum = 0, tg = 0, tw = 0;
    int isw = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'G') {
            sum += l[i];
            tg += 2 * l[i];
            ans += 5 * l[i];
        } else if (s[i] == 'W') {
            sum += l[i];
            ans += 3 * l[i];
            isw = 1;
        } else {
            if (sum < l[i]) {
                if (isw) {
                    ans += 3 * (l[i] - sum);
                }
                else {
                    ans += 5 * (l[i] - sum);
                }
                sum = l[i];
            } 
            sum -= l[i];
            ans += l[i];
        }
        tg = min(sum, tg);
    }
    if (sum > 0) {
        ans -= 4 * tg / 2;
        ans -= 2 * (sum - tg) / 2;
    }
    // sum /= 2;
    // ans -= 4 * min(sum, tg);
    // sum -= min(sum, tg);
    // ans -= 2 * min(sum, tw);
    cout << ans;
    return 0;
}

跃迁引擎启动

Good Bye 2018