首页 > 其他分享 >[45] (多校联训) A层冲刺NOIP2024模拟赛05

[45] (多校联训) A层冲刺NOIP2024模拟赛05

时间:2024-10-11 17:50:31浏览次数:11  
标签:05 int res 45 tot soscnt 联训 ans now

这是什么

午休,大黄突然走进来

大黄:闪电特效!

其他人:?

大黄:5k!

其他人:???

大黄:

【闪电特效】【闪电特效】
男人中的男人
【闪电特效】【闪电特效】
雄性中的雄性
【闪电特效】【闪电特效】
巅峰!
【闪电特效】【闪电特效】

A.好数

简单变形一下

\[f_i+f_j+f_k=c \]

\[f_j+f_k=c-f_i \]

然后 \(f_j+f_k\) 是可以 \(n^2\) 维护的,所以你直接把这玩意丢桶里

直接在桶里查 \(c-f_i\) 就行了

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[5001];
int cnt2[1000001];
const int dx=500000;
int ans,ans2;
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;++i){
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=n;++i){
            for(int j=1;j<=i-1;++j){
                if(cnt2[a[i]-a[j]+dx]){
                    ans2++;
                    break;
                }
            }
        for(int k=1;k<=i;++k){
            cnt2[a[i]+a[k]+dx]=true;
        }
    }
    cout<<ans2;
}

B.SOS 字符串

赛时打的记搜不够优,所以没怎么拿分

我的思路是记一下字符串里有多少通配符,最后快速幂一块乘起来,赛后发现自己就像若智一样,这么写既浪费时间又拖慢记忆化

所以,设 \(f_{i,0/1/2,k}\) 表示当前考虑到第 \(i\) 位,在最近的一个 SOS 中未填(\(0\)),填到第一个 S(\(1\)),填到 O ,并且已经填完了 \(k\) 个 SOS 的方案数,直接按这个思路转移即可

注意点

  • 这题卡掉了 map 的记
  • \(k\ge 3\) 的情况本质是一样的,所以不要再去考虑 \(k\gt 3\) 的情况了,转移的时候直接对 \(3\) 取 \(\min\)

分讨都在注释里了

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int p=1e9+7;
int n;
int ans[]={
0,
//0
0,0,0,0,0,0,0,0,1,104,6757,351205,15973496,664272712,899139165,727408931,230839283,110517859,10938323,18380962,801591834,538331878,360540447,210225942,551547105,929157669,272821968,705926995,775855957,92872414,973270409,391860935,335059301,85671406,897860651,44139736,589503918,625697165,907940909,65840028,296877522,118994829,791306555,545227129,339582817,556088554,498324683,790874686,448130225,415804878,265383931,350869320,508306396,230852520,207518131,393727895,10918291,217898849,356629754,725800340,721470986,818807886,418275274,98166057,166836105,700350963,284803896,926512861,894412347,395302972,592929019,126921505,647951981,929483993,943743437,633413084,615394211,839148006,505351030,635923265,581764455,628567567,602039917,894182098,22633948,459519338,392370752,266609453,230295067,470625000,553777871,371352394,924404107,267364811,494994623,656969894,411339471,219584748,278697715,
//1-99
386050963,938717640,475120605,760806437,753435202,314937563,851110504,797356893,245785631,262365753,833638573,356358070,487921967,794091475,326352338,473729558,565259085,171901369,335540820,814721033,161257365,217687425,155138438,808186780,386518022,83983404,717178046,78856463,235246882,499975775,733374510,215560962,110112138,900818712,197816052,679749741,695794560,543244371,289768441,371534780,751829883,510022775,825226346,407146882,671249767,392207831,889684111,972461673,42143586,173024277,930675066,714500895,313370867,972865022,223928126,923599447,178339933,889909549,40600138,975842829,849125694,668460497,952095956,598470711,655030486,322257610,772694338,624583367,4058244,987656118,585739412,576086511,325923294,813523092,122889315,110009872,706599969,267933649,400120157,886092645,943382227,712297353,218809367,496788446,84125031,637155241,142014530,438296963,902423764,422839788,724584421,920976540,92270597,170789534,937908052,738236019,394787814,710269016,541613082,88290832,325997693
//100-200
};
inline int power(int a,int t){
    int base=a,ans=1;
    while(t){
        if(t&1){
            ans=ans*base%p;
        }
        base=base*base%p;
        t>>=1;
    }
    return ans;
}
int f[1000001][4][5];
int dfs(int now,int sta,int soscnt){
    if(now>n){
        return (soscnt>=3)%p;
    }
    if(f[now][sta][soscnt]){
        return f[now][sta][soscnt];
    }
    int res=0;
    if(sta==2){
        res=(res+dfs(now+1,0,soscnt))%p;   //O
        res=(res+dfs(now+1,0,soscnt==3?3:soscnt+1))%p;   //S
        res=(res+24*dfs(now+1,0,soscnt))%p;   //*
    }
    if(sta==1){
        res=(res+dfs(now+1,2,soscnt))%p;   //O
        res=(res+dfs(now+1,1,soscnt))%p;   //S
        res=(res+24*dfs(now+1,0,soscnt))%p;   //*
    }
    if(sta==0){
        res=(res+dfs(now+1,0,soscnt))%p;   //O
        res=(res+dfs(now+1,1,soscnt))%p;   //S
        res=(res+24*dfs(now+1,0,soscnt))%p;   //*
    }
    return f[now][sta][soscnt]=res%p;
}
signed main(){
    freopen("sos.in","r",stdin);
    freopen("sos.out","w",stdout);
    cin>>n;
    cout<<dfs(1,0,0);
}

P4141.消失之物

直接做 \(q\) 遍 DP 的话,有很多都是重复计算的

考虑怎么才能只做一遍 DP

我们在做 DP 的时候,如果选了 \(i\),转移为

f[j]+=f[j-w[i]]

所以当我们不选 \(i\) 的时候,从答案里减掉的贡献即为

f[j]-=f[j-w[i]]

乍一看不是很对,实际上直接无脑减确实是不对的,但是只要满足转移和撤销是反着来的,那么,后更新的就会先被撤销,那么就一定是正确的了(当然,如果你开两维就可以很好地避免动这个脑子)

为什么要在最终状态上撤?其实在这里撤和在转移到 \(i\) 撤是一样的,虽然答案增加了,但是两个版本的答案的差并没变

#include<bits/stdc++.h>
using namespace std;
const int p=10000;
int n,m;
int w[2001];
int f[2001];
int g[2001];
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&w[i]);
    }
    memset(f,0,sizeof f);
    f[0]=1;
    for(int i=1;i<=n;++i){
        for(int j=m;j>=0;--j){
            if(j>=w[i]) f[j]=(f[j]+f[j-w[i]])%p;
        }
    }
    for(int i=1;i<=n;++i){
        memcpy(g,f,sizeof f);
        for(int j=w[i];j<=m;++j){
            g[j]=(g[j]-g[j-w[i]]+p)%p;
        }
        for(int j=1;j<=m;++j){
            cout<<g[j]%10;
        }
        cout<<'\n';
    }
}
二维写法
#include<bits/stdc++.h>
using namespace std;
const int p=10000;
int n,m;
int w[2001];
int f[2001][2001];
int g[2001];
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&w[i]);
    }
    memset(f,0,sizeof f);
    f[0][0]=1;
    for(int i=1;i<=n;++i){
        for(int j=0;j<=m;++j){
            if(j>=w[i]) f[i][j]=(f[i][j]+f[i-1][j-w[i]])%p;
            f[i][j]=(f[i][j]+f[i-1][j])%p;
        }
    }
    for(int i=1;i<=n;++i){
        memcpy(g,f[n],sizeof f[n]);
        for(int j=w[i];j<=m;++j){
            g[j]=(g[j]-g[j-w[i]]+p)%p;
        }
        for(int i=1;i<=m;++i){
            cout<<g[i]%10;
        }
        putchar('\n');
    }
}

C.集训营的气球

和上一个题类似,这个题无非就是加一个重新 DP 的过程

设 \(f_i\) 表示有 \(i\) 个人选了强制选的那个,正难则反,我们可以求出不合法的方案书,再用总方案去减

总方案很好求,\(tot=\prod\limits(a_i+b_i)\),剩下的不合法方案数直接套模板

总方案数的修改 \(tot'=\frac{tot'}{a_i\times b_i}\times(a_i'\times b_i')\)

背包的转移

\[f_j=f_{j-1}\times a_i+f_j\times b_i \]

(这个转移就是考虑到当前人,他选择 \([1,a_i]\) 内的任意一个就会贡献一个强制选,否则不会)

撤销

无非就是除以原来的方案数,乘上现在的方案数

除以原来的方案数

\[f_i=\frac{f_i-f_{i-1}\times a_p}{b_p} \]

乘上现在的方案数,和前面转移是一样的,这就是撤销后的恢复操作

要注意的是 \(f_0\) 作为起始值需要单独转移

除法直接用逆元处理即可

(\(p\) 为修改位置)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int p=1e9+7;
int power(int a,int t){
    int base=a,ans=1;
    while(t){
        if(t&1){
            ans=ans*base%p;
        }
        base=base*base%p;
        t>>=1;
    }
    return ans;
}
int a[1000001],b[1000001];
/* not satisfied the request

 f_i record the number that has f_i people choose balloon
 
 ans = tot - sum{f_i} */
int f[21];
int n,c,q;
int tot;
signed main(){
    freopen("balloon.in","r",stdin);
    freopen("balloon.out","w",stdout);
    scanf("%lld %lld",&n,&c);
    for(int i=1;i<=n;++i){
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=n;++i){
        scanf("%lld",&b[i]);
    }
    tot=f[0]=1;
    // do dp at first status
    for(int i=1;i<=n;++i){
        for(int j=c-1;j>0;--j){
            f[j]=(f[j-1]*a[i]+f[j]*b[i])%p;
            /* f the ith people don't choose,
                then there's f_j to f_j,
                otherwise f_{j-1} to f_j*/
        }
        f[0]=(f[0]*b[i])%p;
        /*
        still nobody choose
        */
        tot=(tot*(a[i]+b[i]))%p;
    }
    scanf("%lld",&q);
    while(q--){
        int id,x,y;
        scanf("%lld %lld %lld",&id,&x,&y);
        tot=tot*power(a[id]+b[id],p-2)%p*(x+y)%p;
        /*cal the new tot*/
        int inv=power(b[id],p-2);
        f[0]=f[0]*inv%p;
        /*cal the new f_0*/
        for(int i=1;i<=c-1;++i){
            f[i]=(f[i]-f[i-1]*a[id]%p+p)*inv%p;
        }
        /*undo the dp*/
        for(int i=c-1;i>0;--i){
            f[i]=(f[i-1]*x+f[i]*y)%p;
        }
        /*redo the dp*/
        f[0]=f[0]*y%p;
        a[id]=x;b[id]=y;
        int ans=tot;
        for(int i=0;i<=c-1;++i){
            ans=(ans-f[i]+p)%p;
        }
        cout<<ans<<'\n';
    }
}
推歌

ギャンビット 雄之助feat.初音未来

ショーケース

固定された姿のままで

悲しむマネキンな自分の

提唱する感傷など

投げ捨てろ

還元なき逃走には

リスクが付き物

結局はあいつらが

嫌いなだけなのさ

関係ない人も

敵に見えてたんだ

Fighting back 依存気味の

借り木を取り除いて

横やりばかりな

妄執へと言い聞かせる

Dancing Doll 終わるのには

早いと気付けたなら

踊り続ける

その足で蹴り飛ばせ

力の限り

Face is handmade

このハッタリ堪えがたい

Nightmare maze

性別や姿がどうしたんだ

苦しむPrideたちがEnemyは

ほんの一部だけだと指を差す

結局は知って欲しい

火打ちを奪われて

消えかけの意志で

当たり散らした

本当は何回も

思ったことがある

取り返す勇気と

自信さえあればとずっと

乾坤一擲

推して参れ

Free Phase

Don't come back here

Don't come back here

逆を向いた月が

夜闇に呑まれようと

鋭く尖らせて

Gambit 犠牲の上

目覚めた今があれば

あらゆる過去など

餌にしてもお釣りがくる

Fighting back 塗り潰した

切り目を引き直せ

感情は渡さない

あいつらに渡さない
这是什么

huge on the front

i can't view a beautiful laopo

标签:05,int,res,45,tot,soscnt,联训,ans,now
From: https://www.cnblogs.com/HaneDaCafe/p/18458901

相关文章

  • 多校A层冲刺NOIP2024模拟赛05
    咋是计数专场啊,讨厌计数!就会一个签到题,恼了。rank21,T1100pts,T20pts,T320pts,T40ptsdp设计状态不行。T3典型的背包没看出来,T2简单dp不会设计状态。有一些套路还是要学好数(number)签到题。假设一个数\(a_i\)是好数,那么一定有\(a_i=a_x+a_y+a_z(x\ley\lez)\)用一个b......
  • 多校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来设......
  • Boc-Val-Ala-PAB-PNP|CAS号:1884578-00-0多肽化合物
    Boc-Val-Ala-PAB-PNP是一种多肽化合物,其中包含了多个保护基团和特定的氨基酸序列。下面是对该化合物的详细解析:基本信息英文名:Boc-Val-Ala-PAB-PNPCAS号:1884578-00-0分子式:C27H34N4O9分子量:558.58结构式:分子结构1.**Boc**(叔丁氧羰基):  -这是一种常用的氨基酸N端......
  • 学习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......
  • [AGC054D] (ox) 题解
    感觉看到交换就应该要想到逆序对。思路一个前置小知识,我们把一个排列用相邻交换复原的最小次数是逆序对数量。考虑没有ox的情况。我们顺着扫一遍字符串。把左括号正一,右括号看作负一,当前缀和小于零以后,我们把后面最近的左括号提过来,这样可以构造出交换次数最少的合法括号串......
  • 20222305 2024-2025-1 《网络与系统攻防技术》实验一实验报告
    网络攻防实验报告姓名:田青学号:20222305实验日期:2024/09/29—2024/10/09实验名称:缓冲区溢出和shellcode指导教师:王志强1.实验内容本周学习内容总结:学习了系统安全(缓冲区溢出是重点)主要内容:漏洞简介:定义以及安全漏洞。BOF(缓冲区溢出):直接原因-没有严格的内存越界检查......
  • 05-蓝图(Blueprints)
    Flask的蓝图(Blueprints)是一种组织代码的机制,允许你将Flask应用分解成多个模块。这样可以更好地组织应用逻辑,使得应用更具可维护性和可扩展性。每个蓝图可以有自己的路由、视图函数、模板和静态文件,这样可以将相关的功能分组。通过使用蓝图,你可以将Flask应用拆分成多个模块,......