首页 > 其他分享 >wzOI 2023.8.31 题解

wzOI 2023.8.31 题解

时间:2023-09-08 10:55:34浏览次数:40  
标签:le int 题解 sum read 枚举 wzOI 2023.8 复杂度

2023-09-01 15:59:41

$$前言$$

太菜了,第一题都打成那样了没发现是 MST,第三题数据范围没有很仔细看,以为是乱搞(组合之类的)题就直接跳了。

不得不说这次比赛题目的一些思路还是挺妙的,一些想法确实我这种成分想不太到。

$$A$$

$$题意$$

给出了 \(m\) 个可以查询的区间 \([L_i,R_i]\) 和对应查询的代价 \(C_i\),表示查询 \([L_i,R_i]\) 的区间和需要的代价为 \(C_i\),问能否通过这些查询还原原序列(长度为 \(n\)),如果可以请输出最小代价。

$$非常暴力的想法$$

首先两个特殊情况的 \(20\) 分很好拿我们不说,当 \(n\le 5,m\le 10\) 时,显然我们可以通过枚举每个询问选或不选然后判断是否能还原来得到答案。

发现我们需要且只需要 \(n\) 个区间就可以还原(这个比较显然?),我想的是用搜索去更新新的可以被推出的区间。但是注意只有当两个区间左边对齐或者右边对齐时才能推出另外一个区间,所以搜索的时候搞一下就行,反正代码比正解长的多。

$$30pts\ Code$$

int n,m;
namespace subtask1{
    bool f[15][15],choose[15];
    struct Que{
        int l,r,c;
    }q[25];
    queue<PII>Q;
    bool check(){//判断这些边是否可行
        while(!Q.empty()){
            int l=Q.front().first,r=Q.front().second;
            Q.pop();
            for(int i=l;i<=r;i++){
                if(i<r&&(!f[i+1][r])&&f[l][i]&&f[l][r]){
                    f[i+1][r]=1;
                    Q.push({i+1,r});
                }
                if(i>l&&(!f[l][i-1])&&f[l][r]&&f[i][r]){
                    f[l][i-1]=1;
                    Q.push({l,i-1});
                }
            }
            for(int i=r+1;i<=n;i++){
                if((!f[r+1][i])&&f[l][r]&&f[l][i]){
                    f[r+1][i]=1;
                    Q.push({r+1,i});
                }
            }
            for(int i=l-1;i;--i){
                if((!f[i][l-1])&&f[i][r]&&f[l][r]){
                    f[i][l-1]=1;
                    Q.push({i,l-1});
                }
            }
        }
        for(int i=1;i<=n;i++)
            if(!f[i][i])return 0;
        return 1;
    }
    bool work(){
        if(m<n)return puts("Genshin Impact, Qi Dong!"),0;
        for(int i=1;i<=m;i++){
            int l=read(),r=read(),c=read();//记录一下所有边
            q[i]={l,r,c};
        }
        for(int i=1;i<=n;i++)choose[i]=1;//n个条件足矣
        reverse(choose+1,choose+1+m);//预处理permutation 数组
        ll ans=1e18;
        do{
            ll res=0;
            memset(f,0,sizeof(f));
            for(int i=1;i<=m;i++){
                if(choose[i])f[q[i].l][q[i].r]=1,res+=q[i].c,Q.push({q[i].l,q[i].r});//标记并处理队列
            }
            if(check()){//合理就记录
                ans=min(ans,res);
            }
        }while(next_permutation(choose+1,choose+1+m));
        if(ans>=1e17)puts("Genshin Impact, Qi Dong!");
        else cout<<ans;
        return 0;
    }
}
int f[5003][5003];
queue<PII>Q;
int main(){
    freopen("freopen.in","r",stdin);
    freopen("freopen.out","w",stdout);
    n=read(),m=read();
    if(n<=5)return subtask1::work();
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=m;i++){
        int l=read(),r=read(),c=read();
        f[l][r]=min(f[l][r],c);
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        if(f[i][i]>1e9)
            return puts("Genshin Impact, Qi Dong!"),0;
        ans+=f[i][i];
    }
    cout<<ans;
    return 0;
}

$$正解$$

不难发现 \(Sum_{l,r}=sum_{r}-sum_{l-1}\),其中 \(sum_{i}\) 是前 \(i\) 个数的和,知道了 \(sum_{r}-sum_{l-1}\),那此时如果有 \(sum_{R}-sum_{l-1}\),我们就可以得到 \(sum_{R}-sum_{r}\),而我们如果要求 \(a_i\),我们就得知道 \(sum_{i}-sum_{i-1}\)。这么神奇?像极了图。于是我们把 \(r\) 连向 \(l-1\),发现最终能求出求每个 \(sum_{i}-sum_{i-1}\) 其实就是求两两之间连不连通,而求达成联通的最小值,不就是最小生成树吗?然后我们对 \(0\sim n\) 的点跑个最小生成树即可。

为什么 \(0\) 也要在?因为跟 \(0\) 通才能得到 \(sum_i\),而 \(a_1\) 只能通过 \(sum_1-sum_0\) 也就是 \(sum_1\) 得到。

\[妙啊,太妙了。 \]

$$Code\ Prim$$

typedef pair<int,int> PII;
int n,m,dis[5003],tot,ans;
vector<PII>f[5003];
bool vis[5003];
priority_queue<PII>Q;
int main(){
    n=read(),m=read();
    for(int i=1,u,v,w;i<=m;i++)
        f[u=read()-1].push_back({v=read(),w=read()}),f[v].push_back({u,w});
    memset(dis,0x3f,sizeof(dis));
    Q.push({dis[1]=0,1});
    while(!Q.empty()&&tot<=n){
        int x=Q.top().second;
        Q.pop();
        if(vis[x])continue;
        vis[x]=1;tot++;
        ans+=dis[x];
        for(PII PI:f[x]){
            int y=PI.first,w=PI.second;
            if(dis[y]>w)Q.push({-(dis[y]=w),y});
        }
    }
    if(tot<=n)puts("Genshin Impact, Qi Dong!");
    else cout<<ans;
    return 0;
}

\[当然你也可以用后缀和,代码微调,结果一样。 \]

$$B$$

$$题意$$

给你 \(n\) 个互异质数 \(\{p_1,p_2\dots p_n\}\),用这些数来生成一个数集 \(A\),满足:

  • \(\forall x\in A\),\(x=p_1^{k_1}p_2^{k_2}\dots p_n^{k_n}\),其中 \(k_1,k_2,\dots,k_n \in N\)。
  • \(\forall x\in A,x\le R\)。

求 \(A\) 的最大元素和 \(|A|\),\(n\le25,R\le10^{18}\)。

$$暴力$$

先讲一个非常愚蠢的暴力,忘记了质数表示的数不会重新重复的情况,所以甚至用了一个 unordered_set 去重,然后果不其然只拿了 30 分就 T 了。

//30pts
int n;
ll R,a[35],maxx;
unordered_set<ll>S;
void dfs(ll x){
    S.insert(x);
    maxx=max(maxx,x);
    for(int i=1;i<=n;i++){
        if(x*a[i]>R)break;
        if(S.find(x*a[i])!=S.end())continue;
        dfs(x*a[i]);
    }
}
int main(){
    cin>>n>>R;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    dfs(1);
    printf("%lld\n%lld",maxx,S.size());
    return 0;
}

比较智慧(更接近正解)的暴力,枚举每个质数乘了几次,复杂度为 \(O(|A|)\)。

//70pts
void dfs(ll x,int w){
    if(w>n){
        maxx=max(maxx,x);
        cnt++;
        return;
    }
    while(x<=R){
        dfs(x,w+1);
        x*=a[w];
    }
}
//dfs(1,1);

$$正解$$

正解基本上也是暴力,只不过用了一种比较智慧的方法,使得复杂度比答案要小不少。

基本思想: \(\text{Meet in the Middle}\) 和二分。

现在关键在于我们怎样才能让复杂度不是答案,不能盲目枚举。

考虑把原素数分成合适大小的两组分开搜索,得到数集 \(A_s,A_t\),考虑怎么合并两个区间的答案,我们假设我们先处理出来的是 \(A_s\),那么 \(\forall x\in A_s,y\in A_t\),只要满足 \(xy\le R\),就可以对答案造成贡献,关注到我们求最大值不需要遍历所有元素,只需要求出最接近 \(R\) 的那个 \(xy\) 的大小即可,而数集大小怎么求?我们发现当我们对 \(A_s\) 排了序之后,只要 \(\le R/y\) 的值都能加入到数集中,这里只需要二分,然后取出 \(\le R/y\) 的第一个元素,把它乘上 \(y\) 看是否是最大值即可。复杂度 \(O(|A_s||A_t|\log |A_s|)\)。分组很重要,对复杂度影响很大,我们关注到小的质数构成的数集大小更大,所以要让小的质数的组稍微少一点,不能对半分。

$$Code$$

int n;
ll R,a[26],ans,cnt;
vector<ll>f;
void dfs1(ll x,int t){
    if(t>8||t>n)return f.push_back(x),void();//这里不对数量统计是因为下面当值为 1 时会统计一次。
    while(1){
        dfs1(x,t+1);
        if(x>R/a[t])break;//防止用乘法爆long long导致死循环
        x*=a[t];
    }
}
void dfs2(ll x,int t){
    if(t>n){
        auto w=--upper_bound(f.begin(),f.end(),R/x);//找大于这个值的第一个,然后减一就是第一个小于等于的,保证不会是 f.end()
        cnt+=w-f.begin()+1;
        ans=max(ans,x*(*w));
        return;
    }
    while(1){
        dfs2(x,t+1);
        if(x>R/a[t])break;
        x*=a[t];
    }
}
int main(){
    cin>>n>>R;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    dfs1(1,1);
    sort(f.begin(),f.end());//排序保证了后面的二分
    dfs2(1,9);//小组放8个
    cout<<ans<<endl<<cnt;
    return 0;
}

$$C$$

$$题意$$

\(n\) 个点 \(m\) 条边的无向图(无重边有自环),走一条边花 \(1\) 的时间,\(q\) 次询问,每次问你从 \(s\) 到 \(t\),到达时间在 \([l,r]\) 的方案数,两个方案不同,当且仅当花费时间不同或者某一时刻两种路线所在地点不同。

答案对 \(2333\) 取模。

\(n,q\le 40,m\le1000,l,r\le10^9,r-l\le200\)。

$$正解$$

看到范围和无脑方案数,想到矩阵快速幂。

简单的想个转移:

令 \(f_{t,u,v}\) 表示第 \(t\) 时间,从 \(u->v\) 的方案数。

那么显然有:

\[\large f_{t,u,v}=\sum_{k=1}^{n}f_{t-1,u,k}\times f_{t-1,k,v} \]

吐槽:这长得都像个矩阵乘法!!!!

因为 \(n\) 很小,\(t\) 巨大,所以直接用矩阵加速简单递推转移即可,因为 \(r-l\) 也非常小,暴力枚举即可,甚至不需要一些奇技淫巧。

$$Code$$

int n,m,q;
const int mod=2333;//模数太小,甚至不需要开 long long
struct Matrix{
    int a[41][41];
    Matrix(){memset(a,0,sizeof(a));}
    void build(){
        for(int i=1,u,v;i<=m;i++)
            a[u=read()][v=read()]=1,a[v][u]=1;
    }
    void init(){
        for(int i=1;i<=n;i++)a[i][i]=1;
    }
    Matrix operator *(const Matrix &w)const{
        Matrix ans;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                for(int k=1;k<=n;k++)
                    (ans.a[i][j]+=a[i][k]*w.a[k][j]%mod)%=mod;
        return ans;
    }
}ori;
Matrix qpow(Matrix x,int w){
    Matrix res;
    for(res.init();w;w>>=1,x=x*x)if(w&1)res=res*x;
    return res;
}
int main(){
    n=read(),m=read();
    ori.build();
    q=read();
    while(q--){
        int st=read(),en=read(),L=read(),R=read();
        Matrix res=qpow(ori,L);
        int ans=0;
        for(int i=L;i<=R;i++){
            (ans+=res.a[st][en])%=mod;
            res=res*ori;
        }
        printf("%d\n",ans);
    }
    return 0;
}

$$D$$

$$题意$$

给定一个长度为 \(n\) 的 \(01\) 序列 \(a\)。

求区间长度为区间和倍数的子区间个数。

即求:

\[\large \sum_{1\le l,r\le n}[sum(l,r)|(r-l+1)] \]

\(n\le 10^5\)。

$$正解$$

暴力太好打了,不说了。

因为这题是 jca 本鸡出的,那么枚举一下算法:数学,根号,数据结构。

再看一眼数据范围:\(n\le10^5\)。

长得就不像数据结构,如果出数学那肯定会开到 \(10^6\),而且他说了 \(std\) 跑了很久说明复杂度基本上卡满了,那想必是我根本不会的根号算法了啊,直接打个暴力滚了。

赛后发现解法非常有趣。

\[\text{令 }\large k=\dfrac{r-(l-1)}{sum_{r}-sum_{l-1}}\\ ksum_r-r=ksum_{l-1}-(l-1) \]

所以有枚举 \(k\) 然后用桶存算贡献,但是如果直接枚举复杂度为 \(O(n^2)\),和暴力无异,甚至空间复杂度也是 \(O(n^2)\)。但是不难发现当 \(k\) 比较大的时候情况会变少,表现在数组上就是值变小变稀疏,所以考虑对 \(k\) 进行根号分治。

设阈值为 \(B\),当 \(k\le B\) 时直接用桶算贡献,\(x\) 相同的数的贡献为 \(\dbinom{x}{2}\),时空复杂度都为 \(O(nB)\)。

当 \(k>B\) 时,我们关注到 \(k\) 的定义:

\[\dfrac{r-(l-1)}{sum_{r}-sum_{l-1}}=k>B\\r-(l-1)>B(sum_{r}-sum_{l-1})\\sum_{r}-sum_{l-1}=\dfrac{r-(l-1)}{B}\le\dfrac{n}{B} \]

于是,我们可以枚举 \(t=sum_{r}-sum_{l-1}\),然后 \(O(n)\) 算贡献。

我们枚举 \(l-1\) 的位置,然后双指针确定 \(r\) 的范围 \([L,R]\),那么贡献为 \([L-(l-1),R-(l-1)]\) 中 \(t\) 的倍数,可以 \(O(1)\) 求。

注意:\(\dfrac{r-(l-1)}{t}=k>B\iff r>Bt+(l-1)\),判一下,防止算重。

$$Code$$

ll ans;
queue<int>Q;
int n,sum[100005],sq,buc[45000005];
int main(){
    sq=sqrt(n=read());
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+read();
    for(int k=1;k<=sq;k++){//用 unordered_map T 了所以换 queue
        for(int i=0;i<=n;i++)buc[sum[i]*k-i+n]++,Q.push(sum[i]*k-i+n);//+n 防止负下标
        while(!Q.empty())ans+=1ll*buc[Q.front()]*(buc[Q.front()]-1)>>1,buc[Q.front()]=0,Q.pop();//有重没关系
    }
    for(int t=1;t<=n/sq;t++){//枚举 t
        int L=0,R=0;//双指针,因为 r 区间肯定是不会变小的
        for(int l=0;l<n;l++){//枚举 l-1
            while(sum[L]-sum[l]<t&&L<=n)L++;
            if(L>n)break;
            while(sum[R]-sum[l]<=t&&R<=n)R++;//[L,R)
            int ll=max(L-l,t*sq+1),rr=R-1-l;//代入公式
            if(ll<=rr)ans+=rr/t-(ll-1)/t;//判一下,计算贡献
        }
    }
    cout<<ans;
    return 0;
}

标签:le,int,题解,sum,read,枚举,wzOI,2023.8,复杂度
From: https://www.cnblogs.com/NBest/p/17687002.html

相关文章

  • CF1103C 题解
    2023-09-0514:52:07solution找路径很好找,我们随便跑个dfs树找个深度\(\ge\frac{n}{k}\)的路径输出即可。可是怎么找\(k\)个长度不是\(3\)的倍数的环呢?既然我们跑了dfs树,那么就没有横叉边,对于叶子节点非树边只有返祖边,然后一看这个很奇怪的条件——保证每个点度数大......
  • CF1851 部分题解
    2023-07-3019:35:02前言因为我实在是太菜了,没时间也不会做最后两题,所以这里只有前\(5\)道签到题的题解。之后我有时间看了后两题的题解再来更新吧~A先不用看那么多七七八八的,搞清楚下面几点即可:高度不能相同。高度差得被整除。高度差不能太大。好了,然后就可以\(AC\)......
  • 暑假集训Day19 比赛题解
    2023-08-0516:22:13总结这次打下来,由于T2贪心不够完全,T3模拟\(5\)个时不是最优,T4想到暴力做法但是来不及打,加之全都是捆绑测试点,导致我T2,T3虽然加起来有不少点对了,但是还是判全错,最后也只剩下T1的100。感觉这次前三题也不难,都是可做的,T4的30pts暴力也很白给,但......
  • 暑假集训 Day17 模拟赛题解
    2023-08-0318:18:03前言好家伙,很少完整订正一场比赛,可能是因为这个比赛相对来说确实不难吧(至少正解不难)。总结与反思这场比赛其实没有我想象的那么难,只是觉得题目可能不简单,就没有往简单的思路想,反而是被之前讲过的题疑惑,以为要用到一些很奇特的算法,结果打完以后看了题解再结......
  • UVA10368 题解
    2023-08-0615:18:08solution双倍经验这种有限轮游戏的博弈通常都是有两种状态,必胜态和必败态。对于必胜态,指的是从它可以转移到必败态。对于必败态,指的是从它不论如何只能转移到必胜态。对于每个玩家都采取最优策略的有限游戏,我们通常只需要关注必胜态与必败态之间的转移即......
  • 【题解】AtCoder Regular Contest 162
    A.EkidenRace题目描述:有\(n\)个人参加了往返赛跑,每个人有一个编号\(1\)到\(n\)。已知以下信息:如果按照往路的成绩排序,那么任何两个人的成绩都不相同。同时第\(i\)个人在往路中排名第\(i\)。如果按照往返的成绩排序,那么任何两个人的成绩都不相同。同时第\(i\)个人......
  • P9189 [USACO23OPEN] Custodial Cleanup G 题解
    Description奶牛旅馆可以被看作一个\(N\)个节点\(M\)条边的无向简单图,其中每个房间有一个颜色\(C_i\),以及一个钥匙,颜色为\(S_i\),FJ最初在\(1\)号节点,手上一把钥匙都没有。FJ可以进行无数次以下操作:捡起当前房间的钥匙。(FJ可以同时手持多个钥匙)将部分或全部手......
  • All Pairs Maximum Flow题解
    前置知识:1.P3376【模板】网络最大流2.P4897【模板】最小割树(Gomory-HuTree)Ebola有一句很著名的话如果你乱搞过了我请你抽烟那么这道题肯定不能普通的dinic直接水过去,不然就不是紫题了,那么直接祭出最小割树,复杂度\(O(Tn^3m)\),但是因为dinic跑不满,所以是可以过的。......
  • [题解] AtCoder Beginner Contest 308 A~G
    AtCoderBeginnerContest308A~GA.NewSchemevoidMain(){vector<i64>a(8);for(auto&x:a)cin>>x;if(!is_sorted(a.begin(),a.end())&&!all_of(a.begin(),a.end(),[](auto&x){returnx%25!=0||!(100......
  • CF1374E2 Reading Books(hard version) 题解
    CF1374E2ReadingBooks(hardversion)这道题是在CF1374E1ReadingBooks(easyversion)的基础上出的,而且仅仅增加了一个\(m\)的限制,下面的做法也是基于简单版的思路而想到的。建议先尝试简单版,然后尝试此题。题意简述:有\(n\)本书,每本书有一个阅读时间\(t_i\),和属性\(......