专栏文章

ABC412

vvanueber
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip0cmmv
此快照首次捕获于
2025/12/03 04:05
3 个月前
此快照最后确认于
2025/12/03 04:05
3 个月前
查看原文

C

题目分析

首先有一个很显然的贪心，如果当前骨牌的大小为 xx，我们一定会选择 ≤2x\le 2x 且最大的骨牌作为下一个，这样能使我们用更少的骨牌接近目标大小。
接下来找到这个值就行了，答案显然满足可二分性，直接二分即可。
时间复杂度上界是 Θ(nlog⁡n)\Theta(n \log n) 的，但事实上根据官方的题解，可以证明使用的骨牌个数的数量级是 Θ(log⁡n)\Theta(\log n)，这说明只需要 Θ(log⁡n)\Theta(\log n) 次二分查找，总时间复杂度可能是 Θ(log⁡2n)\Theta(\log^2 n) 的。

Code

CPP
#include <bits/stdc++.h>
#define int long long
#define umap unordered_map
#define vint vector<int>
#define ll long long
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define ull unsigned long long
#define uint unsigned int
#define rg register
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sqr(x) ((x)*(x))
using namespace std;
const int INF=0x3f3f3f3f;
inline int read(){
    int w=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        w=(w<<1)+(w<<3)+(ch^48);
        ch=getchar();
    }
    return w*f;
}
inline void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

const int N=2e5+10;
int n,a[N],T,b[N],cnt;
signed main(){
    #ifndef ONLINE_JUDGE
    //freopen("in.txt","r",stdin);
    #endif
    T=read();
    while(T--){
        cnt=0;
        cin>>n;
        rep(i,1,n) cin>>a[i];
        rep(i,2,n-1) b[++cnt]=a[i];
        sort(b+1,b+cnt+1);
        cnt=unique(b+1,b+cnt+1)-b-1;
        if(n==2){
            if(a[1]*2>=a[2]) cout<<2<<endl;
            else cout<<-1<<endl;
        }
        else{
            int now=a[1],p=0,ans=0;
            while(1){
                if(now*2>=a[n]) break;
                int l=p+1,r=cnt,res=-1;
                if(l>r) break;
                while(l<=r){
                    int mid=(l+r)>>1;
                    if(b[mid]<=2*now) l=mid+1,res=mid;
                    else r=mid-1;
                }
                if(res==-1) break;
                else{
                    p=res,now=b[res],++ans;
                }
            }
            if(now*2>=a[n]) cout<<ans+2<<endl;
            else puts("-1");
        }
    }
    #ifndef ONLINE_JUDGE
    fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
    #endif
    return 0;
}

D

题目分析

首先度数为 22 的图一定是一个环，考虑 N≤8N \le 8，直接全排列枚举最终的环是怎么样的，然后求出边有多少条是可以用到的，取操作次数最小值即可，时间复杂度 Θ(n!n2)\Theta(n!n^2).

E

题目分析

考虑加入 AkA_k 时答案能否改变，将 AkA_k 唯一分解得到 Ak=p1c1p2c2…pncnA_k = p_1^{c_1} p_2^{c_2} \dots p_n^{c_n}，那么必须有一个指数 cic_i 比之前所有的唯一分解更大。分两种情况：
  1. AkA_k 本身就是一个质数，此时 cic_i 项从 00 变为 11。
  2. Ak=piciA_k = p_i^{c_i}，这样才能使答案改变，证明：假设 Ak=t×piciA_k = t \times p_i^{c_i}，由于 pici≤Akp_i^{c_i} \le A_k，代表此前的 pip_i 的最高次就来到了 cic_i，加入 AkA_k 不能改变答案，矛盾！
问题变为求 [L,R][L,R] 之内的素数与判断 i∈[L,R]i \in [L,R] 是否能写成质数的整数次幂。
第一个可以用二次筛法，第二个根据结论一个数有且仅有一个 >N> \sqrt N 的质因子，这代表最小公倍数中他们的指数最多为 11，只需预处理出 ≤N\le \sqrt N 的质数的整数次幂即可。
时间复杂度的上界是 Θ(nlog⁡n)\Theta(n \log n)，事实上远远达不到。

Code

CPP
#include <bits/stdc++.h>
#define int long long
#define umap unordered_map
#define vint vector<int>
#define ll long long
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define ull unsigned long long
#define uint unsigned int
#define rg register
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sqr(x) ((x)*(x))
using namespace std;
const int INF=0x3f3f3f3f;
inline int read(){
    int w=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        w=(w<<1)+(w<<3)+(ch^48);
        ch=getchar();
    }
    return w*f;
}
inline void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

const int N=1e7+10;
int prime[N],np[N],cnt,L,R;
void init(int n){
    rep(i,2,n){
        if(!np[i]) prime[++cnt]=i;
        for(int j=1;j<=cnt&&prime[j]*i<=n;++j){
            np[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}
int g[N],not_p[N];
umap<int,int> f;
int ans=1;
bool check(int x){
    if(x<=1e7) return !np[x];
    return 0;
}
signed main(){
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    init(1e7);
    L=read(),R=read();
    for(int i=1;i<=cnt;++i){
        int l=((L+prime[i]-1)/prime[i])*prime[i],r=floor(1.0*R/prime[i])*prime[i];
        for(int j=l;j<=r;j+=prime[i]){
            if(check(j)) continue;
            not_p[j-L]=1;
        }
    }
    for(int i=1;i<=cnt;++i){
        if(prime[i]*prime[i]>R) break;
        for(int j=prime[i]*prime[i];;j*=prime[i]){
            f[j]=1;
            if(j>R/prime[i]) break;
        }
    }
    for(int i=L+1;i<=R;++i){
        if(!not_p[i-L]) ++ans;
    }
    for(int i=L+1;i<=R;++i){
        if(f[i]) ++ans;
    }
    write(ans);
    puts("");
    #ifndef ONLINE_JUDGE
    fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
    #endif
    return 0;
}

F

题目分析

推式子！记 ExE_x 为最外面袜子颜色为 xx 时结束游戏的期望次数，记 SS 为总数，那么：
Ex=Ax−1S−1×1+∑Ax<AyAyS−1(Ey+1)+∑Ax>AyAyS−1(Ex+1)E_x = \frac{A_x-1}{S-1} \times 1 + \sum_{A_x < A_y} \frac{A_y}{S-1} (E_y+1) + \sum_{A_x > A_y}\frac{A_y}{S-1} (E_x+1)
移项得到：
Ex=Ax−1+∑Ax<AyAy(Ey+1)+∑Ax>AyAyS−1−∑Ax>AyAyE_x = \frac{A_x-1+\sum_{A_x<A_y}A_y(E_y+1)+\sum_{A_x>A_y} A_y}{S-1-\sum_{A_x>A_y} A_y}
将袜子按 AA 从大到小排序求解，记 x1=∑Ax<AyAy(Ey+1),x2=∑Ax>AyAyx_1 = \sum_{A_x<A_y}A_y(E_y+1),x_2=\sum_{A_x>A_y} A_y，在求解过程中可以动态维护这两个变量的值以快速求解。
时间复杂度 Θ(nlog⁡n)\Theta(n \log n)。

Code

CPP
#include <bits/stdc++.h>
#define int long long
#define umap unordered_map
#define vint vector<int>
#define ll long long
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define ull unsigned long long
#define uint unsigned int
#define rg register
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sqr(x) ((x)*(x))
using namespace std;
const int INF=0x3f3f3f3f;
inline int read(){
    int w=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        w=(w<<1)+(w<<3)+(ch^48);
        ch=getchar();
    }
    return w*f;
}
inline void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

const int N=3e5+10,mod=998244353;
int n,a[N],c,sum,E[N];
struct node{
    int c,cnt;
    bool operator <(const node &b)const{
        return cnt>b.cnt;
    }
}b[N];
int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int x1,x2;
signed main(){
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    cin>>n>>c;
    for(int i=1;i<=n;++i) a[i]=read(),sum+=a[i];
    sum+=1;
    ++a[c];
    for(int i=1;i<=n;++i) b[i].cnt=a[i],b[i].c=i;
    sort(b+1,b+n+1);
    x1=0;
    x2=sum;
    for(int i=1;i<=n;++i){
        x2-=b[i].cnt;
        int x=b[i].c;
        int fz,fm;
        fz=b[i].cnt-1+x1+x2;
        fz%=mod;
        fm=sum-1-x2;
        fm%=mod,fm+=mod,fm%=mod;
        E[x]=fz*qpow(fm,mod-2)%mod;
        x1+=(b[i].cnt*(E[x]+1)%mod),x1%=mod;
    }
    cout<<E[c]<<endl;
    #ifndef ONLINE_JUDGE
    fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
    #endif
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...