王清楚

编辑于 2022-01-04 15:29

【题解】牛客2021跨年场精

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过了哈，但是这个题原本的想法灵感是在某纺大比赛中出了一个题他给定你3个数字让你输出答案。

大家可以感受一下几个数据然后猜猜看

input
    case 1:13 14 1
    case 2:2 3 5
    case 3:3 5 3
output
    case 1:14
    case 2:21
    case 3:13

然后当时一眼看出来之后一下秒了，但是不知道为什么直到赛后都没多少人过这个题，所以我便出了一下这个题

首先在题目中可以发现

链接：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、最大值求和

考虑reverse一下数组a, pos，再令pos[i] = n - pos[i] + 1，那么问题将会变为求 $\sum\limits_{r = 1} ^{n} \sum\limits_{l = 1} ^{pos[r]} f(l, r)$ 。

从头往后做，维护一个递减的单调栈stk（stk中存放的是下标），

假设当前栈的大小为sz，那么对于所有i in [1, sz]，都有j in (stk[i - 1], stk[i]]， $f(j, r) = a[stk[i]]$ 。

由此我们维护单调栈的时候，可以维护一个前缀答案，然后二分stk数组即可在单次 $O(\log n)$ 的时间内查找答案。

#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;
}

D、小红玩幂塔

引理：

若 $x=p_1^{q_1}*p_2^{q_2}*...*p_n^{q_n}$ （其中 $p_i$ 为素数），那么 $x$ 的因子数量是 $(q_1+1)*(q_2+1)*...*(q_n+1)$ 。

证明：

显然 $x$ 的某个因子一定是一个或多个 $p_i$ 的组合，其中幂可以从 $0$ 到 $q_i$ 中任意选择，共有 $q_i+1$ 种选项。根据乘法原理，总方案数为： $\Pi_{i=1}^n(q_i+1)$ 。证毕。

根据上述引理，我们要计算 $a↑↑n$ 的因子数量，即计算 $a^{a↑↑(n-1)}$ 的因子数量，可以先把 $a$ 写成 $p_1^{q_1}*p_2^{q_2}*...*p_n^{q_n}$ 的形式，那么也就是求：

$a^{a↑↑(n-1)}$

$=p_1^{q_1*a↑↑(n-1)}*p_2^{q_2*a↑↑(n-1)}*...*p_n^{q_n*a↑↑(n-1)}$

的因子数量，答案是：

$(q_1*a↑↑(n-1)+1)*(q_2*a↑↑(n-1)+1)*...*(q_n*a↑↑(n-1)+1)$

所以本题的关键就是如何算出 $a↑↑(n-1)$ 在模 $p$ 意义下的值。

如果 $a$ 和 $p$ 互素，则可以直接使用费马小定理进行降幂。但本题需要降 $n-1$ 次幂，所以要用到欧拉定理（费马小定理的一般形式）：

$a^n \equiv a^{n\%\phi(p)+\phi(p)}\ (mod\ p)$

其中 $\phi(p)$ 为欧拉函数，代表不超过 $p$ 且与 $p$ 互素的正整数数量。

参考代码：

#include<bits/stdc++.h>
using namespace std;

#define size 1000011
#define int long long
int phi[size];

void Init()
{
    memset(phi,0,sizeof(phi));
    phi[1]=1;
    for(int i=2;i<size;i++)
    if(!phi[i])
    for(int j=i;j<size;j+=i)
    {
        if(!phi[j])
        phi[j]=j;
        phi[j]=phi[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出
    }
}
int ksm(int a,int b,int p){
    int res=1;
    while(b){
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
int qs(int a,int b,int p){
    if(b==0)return 1;
    if(b==1||p==1) return a%p;
    return ksm(a,qs(a,b-1,phi[p])+phi[p],p);
}
signed main(){
 //   freopen("./兰子的跨年毒瘤题/11.in","r",stdin);
 //   freopen("./兰子的跨年毒瘤题/11.out","w",stdout);
    long long n,i,a,b,p=1000007;
    Init();
    cin>>a>>b;
    long long temp=qs(a,b-1,p);
   // cout<<temp<<endl;
    long long res=1;
    for(i=2;i*i<=a;i++){
        if(a%i==0){
            long long cnt=0;
            while(a%i==0)a/=i,cnt++;
            res=res*(cnt*temp%p+1+p)%p;
        }
    }
    if(a!=1)res=res*(temp+1+p)%p;
    cout<<res;
}

E、New Year and Chemistry

本来想作为一个 750 的 Div.2A 来着，但属实出成了阅读理解题（

Solution

我们考虑任意一种原子，我们把正确答案（即 $q$ 序列）填入后左右该种原子计量数之和必定相等，我们把这个数值记作 $x$ 。

那么我们把所有 $q_i$ 都变成 $k\cdot q_i(k\in \mathbb Z^*)$ ，于是我们发现对于这个原子，这个数值变成了 $k\cdot x$ ，当然左右仍然相等，符合要求。

所以我们得出了一个关键的结论：

数列 $a$ 合法当且仅当 $\forall i\in[1,n],\dfrac{a_i}{q_i}=k$ ，其中 $k$ 是定值。

由于反应前后不可能存在同种单质，所以任意一种原子都会影响到其他某一种原子，容易证明上述结论。

那么 $k$ 的值能取到多少呢？我们发现，由题目可知任意 $a_i\le u_i\Rightarrow kq_i\le u_i\Rightarrow k\le\dfrac{u_i}{q_i}$ 。

而这个关系式需要对任意 $i\in[1,n]$ 都成立，所以得出 $k\in\left[1,\min\limits_{1\le i\le n}\left(\dfrac{u_i}{q_i}\right)\right]$
容易发现 $k$ 的可能取值个数就是最终可能方案数，即 $ans=\min\limits_{1\le i\le n}\left(\dfrac{u_i}{q_i}\right)$

Code

注意开 long long。

#include <cstdio>

#define N 200010
#define ll long long
#define INF (1e18 + 10)
#define Min(a, b) ((a) > (b) ? (b) : (a))
using namespace std;
ll u[N], a[N];
int n;
ll ans = INF;
int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        ans = INF;
        scanf("%d", &n);
        for(int i = 1 ; i <= n ; i++)
            scanf("%lld", &a[i]);
        for(int i = 1 ; i <= n ; i++)
            scanf("%lld", &u[i]);
        for(int i = 1 ; i <= n ; i++)
            ans = Min(ans, (ll)u[i] / a[i]);
        printf("%lld\n", ans);
    }
    return 0;
}

F、Cherry Sigma

展开式子得：

$Cherry(x) = 1 + 2*2+3*3+4*4+......+x*x$

使用平方和公式得： $Cherry(x) = x*(x+1)*(2*x+1)/6$

注意取模即可

G、新年快乐

群友博弈游戏，当大家题目都写的差不多时，这个题就是最后的博弈了，由于题目是spj判断时间，但是提交按提交时间算，所以你可以延迟spj测评的时间，让你的提交时间提前，所以你可以用很多卡常博弈的方法来提交。

但是正解当然只有等到点后

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    cout<<"Happy New Year!"<<endl;
}

小沙：祝大家新年快乐啦~

H、将idea煎至两面金黄

如果仅煎一面，不翻面，那么煎 T 个单位时间之后，被煎面的成熟度提高
$ $\sum_{i=0}^T\sum_{i=0}^T$ $
设w1，w2分别为T(T > 0)，T - 1时刻被煎面 (仅煎一面) 提高的成熟度。该情况下选2个不同时刻t1，t2 (0 <= t1, t2 <= T)翻面煎一个单位时间再翻回。因为 F(t) = t，可使得 (t1 + t2) / 2 等于 小于w2 - w1 的任意正整数（0时刻翻面再翻回视为不翻面），所以想提高大于w1且小于等于w2的成熟度，需要T时间，暴力即可（偷懒。

代码：

#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

#include<iostream>
using namespace std;
int main()
{
    cout << "277777788888899" << endl;
}

K、dala mani mi movo？

是一个长度为 $12$ 的字符串，观察到其中 $a,e,p,y$ 各有两个，而 $h,n,r,w$ 各有一个。又因为是 $n$ 个人发 $n$ 轮，所以最后的情况必定是每个人 $12$ 张卡片。

那么我们取模之后分析（或者打表）可以得到如下结论：模 $gcd(12,n)$ 相同的收到卡片也相同

$gcd(12,n)=1$ 的时候，每个人恰好拿一套，因为 $12x \ mod \ n \ (x =1,2,...,n )$ 能遍历剩余系

$gcd(12,n)=2$ 的时候，有

$a,e,h,p,y,y *2$

$a,e,n,p,r,w *2$

两个种情况，但是拿到的糖果一样多

而只有当 $gcd(12,n)=3$ 的时候，

$h,p,e,e *3$

$a,y,w,a *3$

$p,n,y,r *3$

这时候第三种情况下会比前两种少1颗

$gcd(12,n)=4$ 时

$h,y,y *4$

$a,e,n *4$

$a,e,p *4$

$p,r,w *4$

一样多

$gcd(12,n)=6$ 的时候 $6$ 种情况分别为 $eh,aw,py,ep,ay,nr$ 各 $6$ 个。

$gcd(12,n)=12$ 的时候 $12$ 种情况是每个位置拿 $1$ 个字符 $12$ 次。

也就是说，当 $gcd(12,n)=3$ 的时候，除了 $3$ 的倍数位会少一颗；其他情况下，所有人拿到的糖果数量都是一致的。

所以只要不输出3的倍数，其他的都对

2024最新求职资料大礼包领取

大家都在关注

校招日程表笔试日历 ai模拟面试面试宝典剑指offer 知识点专项练习

已采纳

采纳

精彩回帖

精彩

全部评论

(5) 回帖

加载中...

话题同步到我的动态回帖

【题解】牛客2021跨年场精

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

B、acmer 上下一心

C、最大值求和

D、小红玩幂塔

E、New Year and Chemistry

Solution

Code

F、Cherry Sigma

G、新年快乐

H、将idea煎至两面金黄

I、公平公正的风行迷踪

J、Simple Number

K、dala mani mi movo？

这时候第三种情况下会比前两种少1颗

已采纳

精彩回帖

全部评论

本文相关内容

等你来战

热门推荐

【题解】牛客2021跨年场 精

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

B、acmer 上下一心

C、最大值求和

D、小红玩幂塔

E、New Year and Chemistry

Solution

Code

F、Cherry Sigma

G、新年快乐

H、将idea煎至两面金黄

I、公平公正的风行迷踪

J、Simple Number

K、dala mani mi movo？

这时候第三种情况下会比前两种少1颗

已采纳

精彩回帖

全部评论

本文相关内容

等你来战

热门推荐

【题解】牛客2021跨年场精