【比赛记录】24.09.22

KSCD_ · 2024-09-23 09:30:29 · 个人记录

记录

A 题仿照 QOJ8336 写了个二分，但是由于 inf 精度爆了，同时有超过一半的数据包含 n=10^{18}，挂到 44。

B 题构造了一个多小时，但是忘记特判 k=1，同时有超过一半的数据包含 k=1 且 \frac nk 为奇数，挂到 38。

C 题想了主席树 + 二分的做法，还胡出来一个奇怪的矩形求和做法，最后都感觉很难写弃了，写了一个前缀和上二分，但是由于二分上界的 k 写成了 q，从 30 挂到 3。

D 题没太认真想，直接写了 40 的暴力，最后过了 53。（事实上赛后自己认真做想出的做法是假的，只能过 36）

所以比赛时边界和特判这种细节需要注意，避免挂分。/ll

题解

A. T386386 谜之阶乘

发现 20 的阶乘已经超过了 10^{18}，所以答案的长度不会超过 20。考虑枚举答案长度，显然在长度相同的前提下，开头越大，最终的乘积就越大。所以可以二分求出第一个不小于 n 的开头位置，再判断一下是否与 n 相等即可。

另外要防止溢出爆掉，只需要在乘法计算前用 __int128 判断一下，如果超过边界就返回边界即可。时间复杂度大概是 O(400\log VT)，但是由于暴力计算乘法会在爆掉时退出，极大地跑不满，可以通过。

#include<iostream>
#define int long long 
#define pii pair<int,int>
#define ll __int128
using namespace std;
const int P=2e18;
int n,ct;
pii ans[30];
bool check(int x,int y)
{
    ll te=x;
    te*=y;
    if(te>P) return true;
    return false;
}
int query(int l,int len)
{
    int res=1;
    for(int i=0;i<len;i++)
    {
        if(check(res,l+i)) return P;
        res*=(l+i);
    }
    return res;
}
void sol()
{
    cin>>n,ct=0;
    if(n==1) {cout<<-1<<'\n'; return;}
    for(int i=20;i>=2;i--)
    {
        int l=1,r=P,res=-1;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(query(mid,i)<=n) res=mid,l=mid+1;
            else r=mid-1;
        }
        if(res!=-1&&res!=1&&query(res,i)==n) ans[++ct]={res+i-1,res-1};
    }
    ans[++ct]={n,n-1},cout<<ct<<'\n';
    for(int i=1;i<=ct;i++) cout<<ans[i].first<<' '<<ans[i].second<<'\n';
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int TT; cin>>TT;
    while(TT--) sol();
    return 0;
}

B. T386254 子集

发现可以按照 k 个一组划分成 m=\frac nk 组，每组内等价于一个 1 到 k 的排列，只要把 m 组排列分别分到 k 个组里，使得每个组内的和相等即可。

不难注意到 m 为偶数时只需要正序逆序交替即可，下面讨论 m 为奇数的情况。此时若 k 为偶数，我觉得无解，不会证。