首页 > 其他分享 >多校A层冲刺NOIP2024模拟赛05

多校A层冲刺NOIP2024模拟赛05

时间:2024-10-11 17:11:46浏览次数:7  
标签:05 int 多校 long FILE using define NOIP2024 mod

咋是计数专场啊,讨厌计数!

就会一个签到题,恼了。

rank 21,T1 100pts,T2 0pts,T3 20pts,T4 0pts

dp设计状态不行。

T3典型的背包没看出来,T2简单dp不会设计状态。

有一些套路还是要学

好数(number)

签到题。

假设一个数\(a_i\)是好数,那么一定有\(a_i=a_x+a_y+a_z(x\le y\le z)\)

用一个bitset维护\(a_x+a_y\)是否出现,对于每一个数\(a_i\),查询是否存在一个数\(z\),使得\(a_i-a_z\)出现过即可。

时间复杂度\(O(n^2)\)

点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = infile("number.in"),*OutFile = outfile("number.out");
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 5e3 + 10,V = 2e5;
int n,a[N],ans = 0;
bitset<V*2+10> pd;
inline void solve(){
    cin>>n;rep(i,1,n,1) cin>>a[i];
    rep(i,1,n,1){
        rep(j,1,i-1,1) if(pd[a[i] - a[j] + V]){ans++;break;}
        rep(j,1,i,1) pd.set(a[i] + a[j] + V);
    }
    cout<<ans<<'\n';
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    solve();
}

SOS字符串(sos)

dp,记\(f_{i,j,k}\)表示前\(i-1\)个字符中已经出现了\(k\)个SOS,并且现在匹配到了SOS的第\(j(j\in\{0,1,2\})\)个字符。这样设计是\(O(n^2)\)的,但是由于\(k>3\)没有用,所以直接将\(k>3\)的转移到\(k=3\)即可。

\[f_{i,j,k}+=\begin{cases} f_{i-1,0,k}+f_{i-1,1,k}&j=1\\ f_{i-1,1,k}&j=2\\ f_{i-1,2,k-1}&j=0,k>0\\ f_{i-1,2,k}&j=0,k=3\\ 25\times f_{i-1,0,k}+24\times f_{i-1,1,k}+25\times f_{i-1,2,k}&j=0 \end{cases}\]

时间复杂度\(O(n)\)

点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    FILE *ErrFile = errfile("err.err");
#else
    FILE *Infile = infile("sos.in"),*OutFile = outfile("sos.out");
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 1e6 + 10,mod = 1e9+7;
ll n,f[N][4][4],ans;
inline void solve(){
    cin>>n;
    f[0][0][0] = 1;
    rep(i,1,n,1) rep(k,0,3,1){
        f[i][1][k] += f[i-1][1][k] + f[i-1][0][k];
        f[i][2][k] += f[i-1][1][k];
        if(k) f[i][0][k] += f[i-1][2][k-1];
        if(k == 3) f[i][0][k] += f[i-1][2][k];
        f[i][0][k] += 25*f[i-1][0][k] + 24*f[i-1][1][k] + 25*f[i-1][2][k];
        f[i][0][k]%=mod,f[i][1][k]%=mod,f[i][2][k]%=mod;
    }
    cout<<(f[n][0][3]+f[n][1][3]+f[n][2][3]) % mod<<'\n';
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    solve();
}

集训营的气球(balloon)

动态dp or 线段树维护dp?

赛时写的\(O(n^2q)\)的

80pts部分分:线段树维护dp

点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = infile("balloon.in"),*OutFile = outfile("balloon.out");
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 1e6 + 10,mod = 1e9 + 7;
namespace IO{
    char buf[1<<23],*p1,*p2;
    #define gc() (p1==p2&&(p2=(p1=buf)+fread_unlocked(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
    #define pc putchar_unlocked
    template<class T>
    inline void read(T &x){
        x = 0;
        char s = gc();
        for(;s < '0' || s > '9';s = gc());
        for(;'0' <= s && s <= '9';s = gc()) x = (x<<1)+(x<<3)+(s^48);
    }
    template<class T,class... Args>
    inline void read(T &x,Args&... argc){read(x);read(argc...);}
    template<class T>
    inline void write(T x){
        static int sta[20],top = 0;
        do{sta[++top] = x%10,x /= 10;}while(x);
        do{pc(sta[top--]+'0');}while(top);
    }
}using namespace IO;
template#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = infile("tree.in"),*OutFile = outfile("tree.out");
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    mt19937 rnd((ull)(new char));
    cout<<299<<'\n';
}
<class T>
inline int Mod(T x){return x>mod?x-mod:x;}
int n,c,q,a[N],b[N],pos[N],fa[N<<1];
struct Segment_Tree{
    struct segment_tree{
        int ls,rs,dp[21],tot;
        #define ls(k) tree[k].ls
        #define rs(k) tree[k].rs
        #define dp(k) tree[k].dp
        #define tot(k) tree[k].tot
    }tree[N<<1];
    int tot = 0,rt;
    inline void pushup(int k){
        rep(i,0,c-1,1) dp(k)[i] = 0;
        int ls = ls(k),rs = rs(k);
        rep(i,0,c-1,1) rep(j,0,c-i-1,1)
            dp(k)[i+j] = Mod(dp(k)[i+j]+1ll*dp(ls)[i]*dp(rs)[j]%mod);
        tot(k) = 1ll*tot(ls)*tot(rs)%mod;
    }
    void build(int &k,int l,int r){
        k = ++tot;
        if(l == r){
            dp(k)[0] = b[l],dp(k)[1] = a[l],tot(k) = a[l]+b[l],pos[l] = k;
            return;
        }
        int mid = (l + r) >> 1;
        build(ls(k),l,mid);build(rs(k),mid+1,r);
        fa[ls(k)] = fa[rs(k)] = k;
        pushup(k);
    }
    inline void update(int p,int x,int y){
        int k = pos[p];
        dp(k)[0] = y,dp(k)[1] = x,tot(k) = x+y;
        k = fa[k];
        while(k) pushup(k),k = fa[k];
    }
}T;
inline void solve(){
    read(n,c);
    rep(i,1,n,1) read(a[i]);rep(i,1,n,1) read(b[i]);
    T.build(T.rt,1,n);read(q);
    while(q--){
        int p,x,y;read(p,x,y);
        T.update(p,x,y);
        int ans = T.tot(1);
        rep(i,0,c-1,1) ans = Mod(ans - T.dp(1)[i] + mod);
        write(ans),pc('\n');
    }
}
signed main(){
    // cin.tie(nullptr)->sync_with_stdio(false);
    // cout.tie(nullptr)->sync_with_stdio(false);
    solve();
}

正解是回退背包。

设\(f_{i,j}\)表示前\(i\)个人已经有\(j\)个人买一血气球。

考虑有dp方程\(f_{i,j} = f_{i-1,j-1}\times a_i+f_{i-1,j}\times b_i\)

那么回退的方程就是\(f_{i,j} = (f_{i,j}-f_{i-1,j-1}\times inv(a_i))*inv(b_i)\)

其中\(inv(x)\)表示\(x\)的逆元。

回退的时候反着做就行,然后\(ans=tot-\sum\limits_{i=0}^{c-1}f_{n,i}\),其中\(tot=\prod\limits_{i=1}^na_i+b_i\)

点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = infile("balloon.in"),*OutFile = outfile("balloon.out");
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 1e6 + 10,mod = 1e9 + 7;
namespace IO{
    char buf[1<<23],*p1,*p2;
    #define gc() (p1==p2&&(p2=(p1=buf)+fread_unlocked(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
    #define pc putchar_unlocked
    template<class T>
    inline void read(T &x){
        x = 0;
        char s = gc();
        for(;s < '0' || s > '9';s = gc());
        for(;'0' <= s && s <= '9';s = gc()) x = (x<<1)+(x<<3)+(s^48);
    }
    template<class T,class... Args>
    inline void read(T &x,Args&... argc){read(x);read(argc...);}
    template<class T>
    inline void write(T x){
        static int sta[20],top = 0;
        do{sta[++top] = x%10,x /= 10;}while(x);
        do{pc(sta[top--]+'0');}while(top);
    }
}using namespace IO;
template<class T>
inline int Mod(T x){return x>mod?x-mod:x;}
template<class T>
inline T power(T a,int b,int mod){
    int res = 1;
    for(;b;b >>= 1,a = 1ll*a*a%mod) if(b&1) res = 1ll*res*a%mod;
    return res;
}
template<class T>
inline int inv(T x){return power(x,mod-2,mod);}
int n,c,q,a[N],b[N],f[21],tot;
inline void solve(){
    read(n,c);
    rep(i,1,n,1) read(a[i]);rep(i,1,n,1) read(b[i]);
    read(q);
    tot = f[0] = 1;
    rep(i,1,n,1){
        drep(j,c-1,1,1) f[j] = Mod(1ll*f[j-1]*a[i]%mod+1ll*f[j]*b[i]%mod);
        f[0] = 1ll*f[0]*b[i]%mod;
        tot = 1ll*tot*(a[i]+b[i])%mod;
    }
    while(q--){
        int p,x,y;read(p,x,y);
        tot = 1ll*tot*inv(a[p]+b[p])%mod*(x+y)%mod;
        int invb = inv(b[p]);
        f[0] = 1ll*f[0]*invb%mod;
        rep(i,1,c-1,1) f[i] = 1ll*(f[i] - 1ll*f[i-1]*a[p]%mod+mod)*invb%mod;
        drep(i,c-1,1,1) f[i] = Mod(1ll*f[i-1]*x%mod+1ll*f[i]*y%mod);
        f[0] = 1ll*f[0]*y%mod;
        a[p] = x,b[p] = y;
        int ans = tot;
        rep(i,0,c-1,1) ans = Mod(ans-f[i]+mod);
        write(ans),pc('\n');
    }
}
signed main(){
    // cin.tie(nullptr)->sync_with_stdio(false);
    // cout.tie(nullptr)->sync_with_stdio(false);
    solve();
}

连通子树与树的重心(tree)

看懂题意也不会打的暴力,咋还是回退背包啊。

分两种情况讨论。

  1. 树有两个重心,分别记为\(a,b\)

    将两个重心中间的边断开,生成两颗分别以\(a,b\)为根的树。

    记\(f_{x,i}\)表示以\(x\)为根的子树中包含\(x\)且有\(i\)个节点的连通块有多少个,这个树形背包解决。

    最后答案为\(\sum\limits_{i=1}^{min(siz_u,siz_v)}f_{u,i}\times f_{v,i}\)

    时间复杂度\(O(n^2)\)

  2. 树只有一个重心,记为\(a\)

    和情况1一样,还是求出\(f\)数组,考虑容斥。

    发现\(f_{x,i}\)表示包含\(x\)且大小为\(i\)的连通块数量,只需要求出最大子树大小\(>\frac{i}{2}\)的个数即可。

    发现如果有一个子树\(Subtree_t\)的大小为\(k\)且\(k>i/2\),那么\(t\)一定只有一个,枚举即可。

    但是如果直接减去\(f_{x,i-k}\times f_{t,k}\)会寄,因为\(f_{x,i-k}\)包含了取\(Subtree_t\)的情况。

    那么怎么消去这个的贡献呢?

    这是一个背包问题,而且物品的次序无关,直接退背包即可。

    时间复杂度\(O(n^2)\)

点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = infile("tree.in"),*OutFile = outfile("tree.out");
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 5e3 + 10,mod = 10007;
int n,siz[N],w[N],c[2],cnt,f[N][N],g[N][N];
vector<int> edge[N];
#define eb emplace_back
#define add(u,v) edge[u].eb(v)
void dfs(int x,int fa){
    siz[x] = 1,w[x] = 0;
    for(int y:edge[x]){
        if(y == fa) continue;
        dfs(y,x);siz[x] += siz[y];w[x] = max(w[x],siz[y]);
    }
    w[x] = max(w[x],n-siz[x]);
    if(w[x] <= n/2) c[c[0]!=0] = x,++cnt;
}
void DP(int x,int fa){
    siz[x] = 1,f[x][0] = f[x][1] = 1;
    for(int y:edge[x]){
        if(y == fa) continue;
        DP(y,x);siz[x] += siz[y];
        drep(i,siz[x],1,1)rep(j,1,min(siz[y],i-1),1){
            f[x][i] = (f[x][i]+1ll*f[y][j]*f[x][i-j]%mod)%mod;
        }
    }
}
inline void solve2(){
    DP(c[0],c[1]);DP(c[1],c[0]);
    int ans = 0;
    rep(i,1,min(siz[c[0]],siz[c[1]]),1) ans = (ans + 1ll*f[c[0]][i]*f[c[1]][i]%mod)%mod;
    cout<<ans<<'\n';
}
inline void solve1(){
    int x = c[0],ans = 0;
    DP(x,0);
    rep(i,1,n,1) ans = (ans + f[x][i]) % mod;
    for(int y:edge[x]){
        rep(i,1,n,1){
            g[y][i] = f[x][i];
            rep(k,1,min(i,siz[y]),1)
                g[y][i] = (g[y][i] - g[y][i-k]*f[y][k]%mod+mod)%mod;
        }
    }
    rep(i,1,n,1) for(int y:edge[x]) rep(k,(i+1)/2,min(i,siz[y]),1)
        ans = (ans - f[y][k]*g[y][i-k]%mod+mod)%mod;
    cout<<ans<<'\n';
}
inline void solve(){
    cin>>n;
    rep(i,1,n-1,1){int u,v;cin>>u>>v;add(u,v);add(v,u);}
    dfs(1,0);
    memset(siz,0,sizeof siz);
    if(c[1]) solve2();else solve1();
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    solve();
}

标签:05,int,多校,long,FILE,using,define,NOIP2024,mod
From: https://www.cnblogs.com/hzoi-Cu/p/18458895

相关文章

  • 多校A层冲刺NOIP2024模拟赛05
    多校A层冲刺NOIP2024模拟赛05\(T1\)A.好数(number)\(100pts/100pts\)枚举两数之和,开个桶维护即可。点击查看代码inta[5010];unordered_map<int,bool>s;intmain(){ freopen("number.in","r",stdin); freopen("number.out","w",stdout)......
  • 多校 A 层冲刺 NOIP2024 模拟赛 05
    多校A层冲刺NOIP2024模拟赛05T1好数(number)签到题首先\(O(nV)\)的背包暴力是显然的,注意到本题只需要合法性,状态只有\(0/1\),上\(bitset\)优化转移即可。时间复杂度\(O(\frac{nV}{w})\)。T2SOS字符串(sos)签到题计数题难点在不重不漏,而本题则主要是不重。考虑一种好的......
  • ETA6005Q3Q 2.5A带动态路径管理的单节锂电开关型充电器
    2.5A带动态路径管理的单节锂电开关型充电器  ETA6005是一款充电电流达2.5A的单节锂电开关型充电。其集成了动态路径管理功能,内部路径的开关内阻仅50mohm,允许系统在没有电池的情况下,仍然可以在适配器存在是维持系统正常工作。ETA6005有特有的2级充电设定可通过引脚的0,1来设......
  • 学习011-08-05 Boolean Properties(布尔属性)
    BooleanProperties(布尔属性)InXAF,thefollowingcontrolscandisplayBooleanandNullableBooleanproperties:在XAF中,以下控件可以显示布尔和Nullable布尔属性:Acheckboxcontrol(default).复选框控件(默认)。Adrop-downcontrolthatdisplaysBooleanvaluesa......
  • PAT甲级1005 Spell It Right
    介绍Givenanon-negativeintegerN,yourtaskistocomputethesumofallthedigitsofN,andoutputeverydigitofthesuminEnglish.InputSpecification:Eachinputfilecontainsonetestcase.EachcaseoccupiesonelinewhichcontainsanN(≤10的1......
  • 2023杭电多校4
    2023杭电多校4a-bProblem题目大意:每个物品都有a,ba,ba,b两个值,......
  • 10.10日noip多校联考总结
    10.10日noip多校联考总结T1感觉就是个dij再多记录一个换乘次数然后就像普通dij一样跑就行了。但是必须得将换乘次数放进dis数组中当成一个状态记录下来,不能只记录在堆中,不然做法会假。T2发现m=0的部分分就是用一个数据结构维护区间最大子段和。m=1/2就是同时维护一个最大值......
  • [AGC054D] (ox) 题解
    感觉看到交换就应该要想到逆序对。思路一个前置小知识,我们把一个排列用相邻交换复原的最小次数是逆序对数量。考虑没有ox的情况。我们顺着扫一遍字符串。把左括号正一,右括号看作负一,当前缀和小于零以后,我们把后面最近的左括号提过来,这样可以构造出交换次数最少的合法括号串......
  • 2024牛客暑假多校第三场 - A. Bridging the Gap 2
    思路全在注释里了:#include<cstdio>#include<cmath>#include<algorithm>usingnamespacestd;constintN=5e5+5;intn,l,r,a[N];boolSolve(){ //打工次数:一个人能将其他人运过去的次数=一个人能过去以后能往返的次数 scanf("%d%d%d",&n,&l,&r); intmin_go=c......
  • 20222305 2024-2025-1 《网络与系统攻防技术》实验一实验报告
    网络攻防实验报告姓名:田青学号:20222305实验日期:2024/09/29—2024/10/09实验名称:缓冲区溢出和shellcode指导教师:王志强1.实验内容本周学习内容总结:学习了系统安全(缓冲区溢出是重点)主要内容:漏洞简介:定义以及安全漏洞。BOF(缓冲区溢出):直接原因-没有严格的内存越界检查......