丙乙日寄

跨年2022，跟队友打了跨年场娱乐赛，rank 128，不敢说打的多好，因为单调栈，计算几何的题目都没A出来，但是对老年退役选手来说康复训练有这个结果也是不错滴。写一下题解，改补的题解补了。

A 兰子哥哥的一万粉丝女装照！！

关注B站账号观看视频讲解，官方给出了题解和代码
https://space.bilibili.com/414380929

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
long long a[MAXN], c[MAXN], h[MAXN], m, ans[MAXN], nowm, nowcnt, maxm;
int n;
// log_a(x)
int Mylog(long long a, long long x) {
    assert(a > 1);
    int ret = 0;
    while (x >= a)
        x /= a, ++ret;
    return ret;
}
bool i128leq(long long a, long long b, long long c, long long d) {
    __int128 _a = a, _b = b, _c = c, _d = d;
    return _a * _b <= _c * _d;
}
long long div_ceil(long long a, long long b) {
    return a / b + (!!(a % b));
}
long long cnt_to_nearest_log_number(long long a,
                                    long long h,
                                    long long nowcnt,
                                    long long limit) {
    if (nowcnt > limit)
        return -1;
    long long temp = a;
    while (i128leq(temp, a, limit, h) && temp <= nowcnt * h)
        temp *= a;
    if (temp <= nowcnt * h)
        return -1;
    long long ret = div_ceil(temp, h);
    assert(ret > nowcnt);
    return ret - nowcnt;
}

struct node {
    long long next_cnt;
    int id;
    long long cnt;
    node(long long next_cnt = 0, int id = 0, long long cnt = 0) {
        this->next_cnt = next_cnt;
        this->id = id;
        this->cnt = cnt;
    }
    friend bool operator<(node a, node b) { return a.next_cnt > b.next_cnt; }
};
priority_queue<node> q;
vector<pair<int, int> > v;
int main() {
    // freopen("192.in","r",stdin);
    scanf("%d%lld", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &c[i]);
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &h[i]);
    }
    for (int i = 1; i <= n; ++i) {
        maxm += Mylog(a[i], c[i] * h[i]);
    }
    if (maxm < m) {
        printf("QAQ,lan zi bu nv zhuang\n");
        return 0;
    }
    for (int i = 1; i <= n; ++i) {
        int mlg = Mylog(a[i], h[i]);
        if (mlg >= 1) {
            v.emplace_back(mlg, i);
            long long next_cnt_num =
                cnt_to_nearest_log_number(a[i], h[i], 1, c[i]);
            if (next_cnt_num != -1) {
                q.push(node(next_cnt_num, i, 1));
            }
        } else {
            long long next_cnt_num =
                cnt_to_nearest_log_number(a[i], h[i], 0, c[i]);
            if (next_cnt_num != -1) {
                q.push(node(next_cnt_num, i, 0));
            }
        }
    }
    sort(v.begin(), v.end());
    for (auto it = v.rbegin(); it != v.rend(); ++it) {
        if (nowm < m) {
            nowm += it->first;
            ans[it->second]++;
            nowcnt++;
        }
    }
    if (nowm >= m) {
        for (int i = 1; i <= n; ++i) {
            printf("%d%c", ans[i], i == n ? '\n' : ' ');
        }
        return 0;
    }
    while (nowm < m && !q.empty()) {
        node now = q.top();
        q.pop();
        ans[now.id] += now.next_cnt;
        now.cnt += now.next_cnt;
        now.next_cnt =
            cnt_to_nearest_log_number(a[now.id], h[now.id], now.cnt, c[now.id]);
        nowm++;

        if (now.next_cnt != -1) {
            q.push(now);
        }
    }
    /*
    for(int i=1;i<=n;++i)
    {
        cout<<Mylog(a[i],ans[i]*h[i])<<" cmp "<<Mylog(a[i],c[i]*h[i])<<endl;
        if(Mylog(a[i],ans[i]*h[i])!=Mylog(a[i],c[i]*h[i]))
        {
            cout<<"this error "<<a[i]<<" "<<c[i]<<" "<<h[i]<<endl;
        }
    }
    */
    assert(nowm >= m);
    for (int i = 1; i <= n; ++i) {
        printf("%d%c", ans[i], i == n ? '\n' : ' ');
    }
    return 0;
}

B acmer 上下一心

官方整活题，直接rand 24发过了，官方给的题解也很有思考价值

链接：https://ac.nowcoder.com/acm/contest/26086/B
来源：牛客网

输入1 黑盒将输出1
输入2 黑盒将输出2
输入4 黑盒将输出5
输出100000 黑盒将输出918

我们可以猜测第一项为1 第二项为2 第四项为5

这个时候就发挥我们的数学猜想：

递推式可不可能是dp[i]=dp[i-1]+dp[i-2]

然后在通过给定的100000大数来推测他的模数

最后我们可以测出不超过10个数的mod值，不管取那个mod都可以正确。

至于为什么给定918这个数字，因为我们暴力对拍之后，得到的第一个模数是

1097

可以得到一个答案为365的争取答案，并且k*366+365都是正确答案。寓意这不管是平年还是闰年，大家年年都可以想今天跨年一样找到写题的快乐。

#include <iostream>
using namespace std;
const int N = 1e5 + 7;
int mod = 919;
int dp[N];
void f() {
    dp[1] = 1, dp[2] = 2;
    for (int i = 3; i < N; i++)
        dp[i] = dp[i - 1] + dp[i - 2], dp[i] %= mod;
    if (dp[100000] == 918) {
        for (int i = 1; i < N; i++)
            if (dp[i] == 0) {
                cout << i;
                exit(0);
            }
    }
    mod++;
}
int main() {
    while (true)
        f();
}

当然你也可以这样过

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long *a=new long long;
    long long p=(long long&)a;
    mt19937 rng(p*time(0));
    for(int i=1;i<=10;i++)cout<<rng()%100001<<" ";
}

C 最大值求和(待补)

单调栈题目

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int a[N], p[N], stk[N], tot, n;
long long sum[N];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        p[i] = n - p[i] + 1;
    }
    reverse(a + 1, a + 1 + n);
    reverse(p + 1, p + 1 + n);
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        while (tot && a[stk[tot]] <= a[i]) {
            tot--;
        }
        stk[++tot] = i,
        sum[tot] = 1ll * (i - stk[tot - 1]) * a[i] + sum[tot - 1];
        int pos = lower_bound(stk + 1, stk + 1 + tot, p[i]) - stk;
        ans += sum[pos - 1] + 1ll * (p[i] - stk[pos - 1]) * a[stk[pos]];
    }
    cout << ans << "\n";
    return 0;
}

E New Year and Chemistry

直接贴代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 10;

int main() {
    ll n, q[maxn], u[maxn];
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> q[i];
        for (int i = 1; i <= n; i++)
            cin >> u[i];
        ll minn = 1e17;
        for (int i = 1; i <= n; i++) {
            minn = min(minn, u[i] / q[i]);
        }
        printf("%lld\n",minn);
    }
    return 0;
}

F Cherry Sigma

我们推的最后的公式是$\frac{1}{2}(x^3+x^2-\frac{1}{6}x(x+1)(2x+1)+\frac{1}{2}x(x+1))$， 题解给出的最后式子是$x(x+1)(2x+1)/6$

注意取模和乘法逆元的问题就行

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 10;
const int MOD = (int)1e9 + 7;
int inv[N];
void init(){
    inv[1] = 1;
    for(int i = 2; i < N; i ++){
        inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;
    }
}
int main(){
    init();
    int T;scanf("%d",&T);
    ll x;
    while(T--){
        ll ans=0;
        scanf("%lld",&x);
        ans=(((((x*x)%MOD*x)%MOD+(x*x)%MOD-(((x*(x+1))%MOD*(2*x+1)%MOD)*inv[6])%MOD+(x*(x+1)%MOD*inv[2])%MOD)*inv[2])%MOD+MOD)%MOD;
        printf("%lld\n",ans);
    }
    return 0;
}

H 将idea煎至两面金黄

题目暴力？？？？

#include <iostream>
#include <fstream>
#define min(x,y) (x)>(y)?(y):(x)
#define Happy 1
#define New *
#define Year 0
using namespace std;

signed main() {
    long long n, maxn = 0x3f3f3f3f3fll;
    cin >> n;
    for (int i = 1; i <= n * 2; ++ i) {
        for (int j = 1; j <= n; ++ j) {
            long long num;
            cin >> num;
            if (num <= 2022) maxn = min(maxn, 2022 - num);
            else maxn = min(maxn, 4294969318ll - num); // 4294967296 - num + 2022
        }
    }
    long long ans = 0;
    for (int i = 0; ; ++ i) {
        ans += i;
        if (ans >= maxn) {
            cout << i;
            break;
        }
    }
    return Happy New Year;
}

I 公平公正的风行迷踪(待补)

根据题意，即可看成一个以猎手为圆心的动圆在地图上扫描处于顶点的游侠，很容易可以想到，可将猎手作为动点，游侠作为定圆。那么，猎手运动就是射线，每次判断动点是否在圆内，或者射线与向量方向上最近圆的交点，即可得到下一步行动方向及路线，之后按照题意进行模拟即可。当然，精度非常重要，所以最好使用精度高的浮点数进行运算。

涉及计算几何的知识有：点在圆内（上），直线圆交。

J Simple Number

OEIS 牛逼

写一个程序模拟一下 f 函数和 g 函数，然后求出 a(n) 表示最小的数 a(n) 能使得 g(a(n))=n 的数 a(n)，求这个 a(1),a(2),a(3),a(4) 前几项，扔到 oeis 上搜一下，直接查找 a(11) 即是这个结果。

K dala mani mi movo？

只要不输出3的倍数都对

n=int(input())
print("1")