首页 > 其他分享 >20241010 模拟赛

20241010 模拟赛

时间：2024-10-12 11:33:54浏览次数：7  
标签：cnt 20241010 int ll mxn top 模拟 define

想看题的戳这里

A. 植物收集

难度：绿
先讲一下 \(O(n^3)\) 的暴力：
枚举一下要用多少个 \(k\)。将价格排序，假设要用 \(x\) 个 \(k\)，则每个数会对其右边 \(x\) 个数产生贡献，按价格从小到大计算贡献。
优化一下，每次增加一个 \(k\)，则每株植物最多往右边贡献 \(1\) 个，所以每次往右边枚举一个数，复杂度 \(O(n^2)\)。
还能优化！观察一下，发现对于每个 \(x*k\) 的贡献可以三分！再加上ST表，时间复杂度达到 \(O(n\ log\ n)\)。

#include<bits/stdc++.h>
#define ll long long
#define mxn 200010
using namespace std;
ll a[mxn],n,k,st[mxn][21],lg[mxn],ans;
void init(){
    memset(st,0x7f,sizeof(st));
    for(int i=1;i<=n;i++)lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    for(int i=1;i<=n;i++)st[i][0]=a[i];
    for(int i=1;(1<<i)<=n;i++)
        for(int j=1;j+(1<<i)-1<=n;j++)
            st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
    return;
}
ll get(ll x){
    ll ret=0;
    for(int i=x+1;i<=x+n/2;i++){
        ll logg=lg[x+1]-1;
        ret+=min(st[i-x][logg],st[i-(1<<logg)+1][logg]);
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    freopen("collect.in","r",stdin);
    freopen("collect.out","w",stdout);   
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        ans+=a[i];
        a[i+n]=a[i];
    }
    n*=2;
    init();
    ll l=0,r=n/2-1;
    while(l<r){
        ll lmid=l+(r-l)/3,rmid=l+(r-l)/3*2;
        if(lmid==rmid)break;
        if(get(lmid)+k*lmid>get(rmid)+k*rmid)l=lmid;
        else r=rmid;
    }
    for(ll i=l;i<=r;i++)        
    ans=min(ans,get(i)+k*i);
    cout<<ans;
    return 0;
}

B. 美丽子区间

难度：绿
利用容斥原理，有：

美丽子区间数 = 区间数 - 最大值在开头的子区间数 - 最大值在结尾的子区间数 - 最小值在开头的子区间数 - 最小值在结尾的子区间数 + 最大值在开头最小值在结尾的子区间数量 + 最大值在结尾最小值在开头的子区间数量

对于减掉的部分，可以用单调栈计算；而加回去的部分，可以用树状数组解决，具体看代码。

#include<bits/stdc++.h>
#define ll long long
#define mxn 200010
using namespace std;
ll n,a[mxn],tre[mxn],ans;
ll big[mxn],sml[mxn],l[mxn],r[mxn];
ll stk[mxn],top;
vector<ll> lft[mxn];
void add(ll x){
    while(x<=n)tre[x]++,x+=(x&-x);
    return;
}
ll query(ll x){
    ll ret=0;
    while(x)ret+=tre[x],x-=(x&-x);
    return ret;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    freopen("interval.in","r",stdin);
    freopen("interval.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    ans=n*(n+1)/2;
    for(int i=n;i;i--){
        while(top&&a[stk[top]]<a[i])
            big[stk[top]]=i,top--;
        stk[++top]=i;
    }
    while(top)big[stk[top--]]=0;
    for(int i=n;i;i--){
        while(top&&a[stk[top]]>a[i])
            sml[stk[top]]=i,top--;
        stk[++top]=i;
    }
    while(top)sml[stk[top--]]=0;
    for(int i=1;i<=n;i++)l[i]=min(sml[i],big[i])+1;
    for(int i=1;i<=n;i++){
        while(top&&a[stk[top]]<a[i])
            big[stk[top]]=i,top--;
        stk[++top]=i;
    }
    while(top)big[stk[top--]]=n+1;
    for(int i=1;i<=n;i++){
        while(top&&a[stk[top]]>a[i])
            sml[stk[top]]=i,top--;
        stk[++top]=i;
    }
    while(top)sml[stk[top--]]=n+1;
    for(int i=1;i<=n;i++)r[i]=max(sml[i],big[i])-1;
    for(int i=1;i<=n;i++)ans-=r[i]-l[i]+2;
    for(int i=1;i<=n;i++)lft[l[i]].push_back(i);
    for(int i=1;i<=n;i++){
        for(int j=0;j<lft[i].size();j++)
            add(lft[i][j]);
        ans+=query(r[i])-query(i-1);
    }
    cout<<ans;
    return 0;
}

C. 字符序列

难度：蓝
原题UOJ516。
神奇计数dp+矩阵乘法。
设 \(dp_{i,j}\) 为字符串 \(1\sim i\) 位，以字符 \(j\) 为结尾的子序列数，其中 \(j\) 为 \(a\sim z\)。
又设 \(lst_j\) 为字符 \(j\) 上一次出现的位置。
所以有 \(dp_{i,j}=\sum\limits_{k=a}^z dp_{lst_k,k}\)
发现这玩意是可以省一维的，即有 \(dp_i=\sum\limits_{k=a}^z dp_{lst_k}\)。
但是这样还不够，因为字符串长度会达到 \(2^n\) 级别，空间时间双爆炸。
设 \(t(i)\) 为进行依次进第 \(i\sim n\) 次操作得到的字符串，于是有 \(t(i)=t(i+1)+s_i+t(i+1)\)。
用一个矩阵乘法，可以达到 \(O(n)\) 级别。

#include<bits/stdc++.h>
#define ll long long
#define mxn 510
#define mod 1000000007
using namespace std;
ll n,ans;
char st[mxn];
struct matrix{
    ll a[30][30];     
    void init(){
        for(int i=0;i<=26;i++)
            a[i][i]=1;
    }
    matrix(){memset(a,0,sizeof(a));}
};
matrix operator *(const matrix &a,const matrix &b){
    matrix c;
    for(int k=0;k<=26;k++)
        for(int i=0;i<=26;i++)
            for(int j=0;j<=26;j++)
                c.a[i][j]=(a.a[i][k]*b.a[k][j]%mod+c.a[i][j])%mod;
    return c;
}
matrix get(char c){
    matrix ret;
    for(int i=0;i<=26;i++){
        ret.a[i][i]=1;
        if(i==c-'a')
            for(int j=0;j<=26;j++)
                ret.a[i][j]=1;
    }
    return ret;
}
matrix res;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
	freopen("subseq.in","r",stdin);
	freopen("subseq.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>st[i];
    res.init();
    for(int i=n;i;i--)res=res*get(st[i])*res;
    for(int i=0;i<=25;i++)ans=(ans+res.a[i][26])%mod;
    cout<<ans;
    return 0;
}

D. 网络攻防

难度：蓝-紫
首先，\(k=1\) 的时候tarjan算割边数就行了。
对于 \(k=2\)，我们先从这张图中抽出一棵生成树。这样有三种情况：

\(1.\) 删除两条非树边，贡献为 \(0\)。

\(2.\) 删一条树边，一条非树边。

若树边为桥边，则另外一条怎么选都行。
若不是，则该非树边应为生成树上唯一覆盖了这条边的非树边。
这里的覆盖是这样的：

其中，黑色边为树边，红色边为非树边，打勾的边是被覆盖的边。

\(3.\) 删两条树边。

若树边中存在桥边，无脑删就行了。
若不存在，则删除边 \(a,b\) 后图不连通的条件为覆盖了边 \(a\) 的非树边集 \(S_a\) 与覆盖了边 \(b\) 的非树边集 \(S_b\) 满足 \(S_a=S_b\)。可以自行手推一下。

于是，就有一个问题：怎么判断 \(S_a=S_b\)？对于这种边的相等问题，一般是用哈希解决。

#include<bits/stdc++.h>
#define ll long long
#define mxm 200010
#define mp make_pair
#define pll pair<long long,long long>
#define pb push_back
using namespace std;
ll n,m,k,val[mxm];
ll vis[mxm],edgevis[mxm];
ll istre[mxm],ans;
ll ndcnt[mxm],ndval[mxm];
ll sumcnt[mxm],sumval[mxm];
ll cnt_bridge,cnt_tre,cnt_cover1;
map<ll,ll> hsh;
vector<pll> t[mxm],tre[mxm];
void dfs1(int u){
    vis[u]=1;
    for(int i=0;i<t[u].size();i++){
        int v=t[u][i].first,edgeid=t[u][i].second;
        if(!vis[v]){
            edgevis[edgeid]=istre[edgeid]=1;
            tre[u].pb(mp(v,edgeid));
            tre[v].pb(mp(u,edgeid));
            dfs1(v);
        }
        else if(!edgevis[edgeid]){
            edgevis[edgeid]=1;
            ndcnt[u]++,ndcnt[v]--;
            ndval[u]+=val[edgeid],ndval[v]-=val[edgeid];
        }
    }
    return;
}
void dfs2(int u,int f){
    sumcnt[u]=ndcnt[u],sumval[u]=ndval[u];
    for(int i=0;i<tre[u].size();i++){
        int v=tre[u][i].first,edgeid=tre[u][i].second;
        if(v==f)continue;
        dfs2(v,u);
        sumcnt[u]+=sumcnt[v];
        sumval[u]+=sumval[v];
        if(sumcnt[v]==1)cnt_cover1++;//对于生成树中每条边,只被一条非树边覆盖的边的数量
        if(sumval[v]==0)cnt_bridge++;//生成树中桥的数量
        if(istre[edgeid])cnt_tre++;//生成树中边的数量
        hsh[sumval[v]]++;
    }
    return;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    freopen("attack.in","r",stdin);
    freopen("attack.out","w",stdout);
    srand(time(0));
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        val[i]=rand();
        t[u].pb(mp(v,i));
        t[v].pb(mp(u,i));
    }
    dfs1(1);
    dfs2(1,0);
    hsh[0]=0;
    if(k==2){
        ans+=cnt_cover1;//一树一非(无桥)
        ans+=cnt_bridge*(m-cnt_tre);//一树一非(有桥)
        ans+=cnt_bridge*(cnt_tre-cnt_bridge);//两树(一桥一不桥)
        ans+=cnt_bridge*(cnt_bridge-1)/2;//两树(两桥)
        for(pll p:hsh)
            ans+=p.second*(p.second-1)/2;//两树(无桥)
        //注意这里的map是要用一个pair遍历的
    }    
    cout<<ans+cnt_bridge;//加上k=1时的割边
    return 0;
}

标签：cnt,20241010,int,ll,mxn,top,模拟,define
From： https://www.cnblogs.com/nagato--yuki/p/18455536

相关文章

  • 105th 2024/10/11 模拟赛总结61
    傲慢，凭什么傲慢T1开幕雷击，认为水飞了”一眼CDQ板子啊“然后十五分钟时直接开打主要原因绝对是因为昨天场切了T1，所以飘起来了还是应该稳重一点，起码模几个不同数据再下定论实际上也真是水题，相当于板子了自己对排列不够熟悉，真的没想到是直接全局-部分正难则反？从没用上过自以......
  • 104th 2024/10/8 模拟赛总结60
    T1有感觉，因为AB组一起打，所以下意识认为是水题（实际上也不算难？）就直接开始想从深向浅直接扫一遍，能转就转显然错，从浅向深扫一遍同样不对，因为不知道往上转移的顺序比如，设该点为x，是0，有的儿子可能转移到x，其子树内转移的次数比另一个儿子多，所以就要优先它不好处理，看到数据，给了一档2e5，一......
  • CSP-S 模拟赛 28
    CSP-S模拟赛28T1签到题。对\(b\)分解质因数后便容易求解。T2考虑枚举\(\gcd(S)\)的取值\(x\)，则\(\operatorname{lcm}(S)=m-x\)。那么同时变形\(\gcd\)和\(\operatorname{lcm}\)变为\(\gcd(S)=1,\operatorname{lcm}(S)=\dfrac{m-x}{x}\)。那么对于\(\gcd\)......
  • CSP-S 模拟赛 29
    CSP-S模拟赛29T1\(n\le18\)显然是状压dp。考虑设状态\(dp_{i,j}\)表示状态为\(i\)，最终的\(a\)为\(j\)时的最大代价及方案数。转移是简单的。优化是观察到最终的\(a\in(\maxa_i,\maxa_i+1)\)。那么这一维便可以用\(0/1\)来设。于是时间复杂度\(O(2^nn)\).......
  • CSP-S 模拟赛 37
    CSP-S模拟赛37T1口胡题。显然尽量靠近中间更优，且选端点一定不劣，于是依据结论将中点设为所有端点的中位数。代码：#include<bits/stdc++.h>#defineN300005#defineintlonglongusingnamespacestd;intn;intl[N],r[N];intrk[N<<1];intpos[N];intans;signe......
  • 多校A层冲刺NOIP2024模拟赛05
    A.好数（number）很容易想到\(n^3\)枚举两个，看第三个是否出现，扩展一下，枚举一个，看剩下需要的和是否出现过，提前处理出两两的和和最早能合出这个数的位置，复杂的\(O(n^2)\)点击查看代码#include<bits/stdc++.h>constintmaxn=5000+10;usingnamespacestd;intn,a[maxn],cnt,......
  • CSP-S 模拟赛 36
    CSP-S模拟赛36T1由于\(a_i\le10^5\)，那么考虑枚举这个\(\gcd\)，考虑求\(f(i)\)表示答案，那么\(\operatorname{ans}=\sumi\timesf(i)\)。然而式子中有\(\gcd\)，于是考虑求\(g(i)\)表示\(i\mid\gcd\)的方案数，然后\(f(i)=g(i)-\sum_{j>i,i\midj}f(j)\)。对于\(g(i)\)......
  • CSP-S 模拟赛35
    CSP-S模拟赛35T1其实是傻逼题。常见的套路是枚举右端点，动态维护左端点的贡献。发现右端点移动一位只会对一种颜色有影响，那么考虑线段树维护区间的答案，区间加减每个颜色即时的贡献即可。代码：#include<bits/stdc++.h>#defineN1000005#defineM8005#defineintlonglong......
  • 『模拟赛』多校A层冲刺NOIP2024模拟赛05
    Rank烂。A.好数（number）签，唐，没签上。考虑之前几次类似的题方法都是选\(k-1\)的方案存起来以使总复杂度除以一个\(n\)，故考虑记共\(n^2\)个两两组合之和，枚举当前点\(i\)前面的点，找是否有值为它们的差的组合，复杂度\(\mathcal{O(n^2)}\)，用map记再挂个\(\logn\)。赛......
  • 多校A层冲刺NOIP2024模拟赛05
    T1、好数（number）签到题把选三个数相加拆为选择一个数，然后看前面有没有能用两个数组合出答案。$O(n^2)$。码(#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<int,int>pii;#definemkmake_pair#de......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99