竞赛讨论区 > 【题解】牛客2021跨年场

【题解】牛客2021跨年场

头像
王清楚
编辑于 01-04 15:29 APP内打开
赞 1 | 收藏 4 | 回复13 | 浏览2252

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,那么问题将会变为求

从头往后做,维护一个递减的单调栈stkstk中存放的是下标),

假设当前栈的大小为sz,那么对于所有i in [1, sz],都有j in (stk[i - 1], stk[i]]

由此我们维护单调栈的时候,可以维护一个前缀答案,然后二分stk数组即可在单次的时间内查找答案。

#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、小红玩幂塔

引理:

(其中 为素数),那么 的因子数量是

证明:

显然 的某个因子一定是一个或多个 的组合,其中幂可以从 中任意选择,共有 种选项。根据乘法原理,总方案数为:。证毕。

根据上述引理,我们要计算 的因子数量,即计算 的因子数量,可以先把 写成 的形式,那么也就是求:

的因子数量,答案是:

所以本题的关键就是如何算出 在模 意义下的值。

如果 互素,则可以直接使用费马小定理进行降幂。但本题需要降 次幂,所以要用到欧拉定理(费马小定理的一般形式):

其中 为欧拉函数,代表不超过 且与 互素的正整数数量。

参考代码:

#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

我们考虑任意一种原子,我们把正确答案(即 序列)填入后左右该种原子计量数之和必定相等,我们把这个数值记作

那么我们把所有 都变成 , 于是我们发现对于这个原子,这个数值变成了 ,当然左右仍然相等,符合要求。

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

数列 合法当且仅当 ,其中 是定值。

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

那么 的值能取到多少呢?我们发现,由题目可知任意

而这个关系式需要对任意 都成立,所以得出
容易发现 的可能取值个数就是最终可能方案数,即

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

​ 展开式子得:

​ 使用平方和公式得:

​ 注意取模即可

G、新年快乐

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

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

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

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

H、将idea煎至两面金黄

如果仅煎一面,不翻面,那么煎 T 个单位时间之后,被煎面的成熟度提高
$$
w1w2分别为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?

是一个长度为的字符串,观察到其中各有两个,而各有一个。又因为是个人发轮,所以最后的情况必定是每个人张卡片。

那么我们取模之后分析(或者打表)可以得到如下结论:模相同的收到卡片也相同

的时候,每个人恰好拿一套,因为能遍历剩余系

的时候,有

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

而只有当的时候,

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

一样多

的时候种情况分别为个。

的时候种情况是每个位置拿个字符次。

也就是说,当的时候,除了的倍数位会少一颗;其他情况下,所有人拿到的糖果数量都是一致的。

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

6条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐