2022牛客寒假算法基础集训营1题解AHFIDBKG

2022牛客寒假算法基础集训营1题解AHFIDBKG

文章目录

A 九小时九个人九扇门 dpH 牛牛看云 思维F 中位数切分 思维I B站与各唱各的 数学D 牛牛做数论 数学B 炸鸡块君与FIFA22 倍增/分块/线段树K 冒险公社 dpG ACM is all you need总结
比赛链接

---

A 九小时九个人九扇门 dp

题目链接
题意：
一个数字的数字根是指：将该数字各数位上的数字相加得到一个新的数，直到得到的数字小于 10 10 10 为止.。设置小于 10 10 10 的数字，其数字根就为其本身。
k k k 个人能够打开门上数字为d的一扇数字门，当且仅当这 k k k 个人的腕表数字之和的数字根恰好为 d d d。
( 1 < = n < = 1 e 5 , 1 < a i < = 1 e 9 ) (1<=n<=1e5,1(1<=n<=1e5,1

题解：
状态
d p [ i ] [ j ] dp[i][j] dp[i][j] 表示考虑了前 i i i 个数，选择了一些数字使得数字根为 j j j 的方案数

转移方程
不加当前位使得数字根为 j j j 的方案数为上一位继承来
d p [ i ] [ j ] + = d p [ i − 1 ] [ j ] ; dp[i][j] += dp[i - 1][j]; dp[i][j]+=dp[i−1][j];
加上当前位使得数字根为 f ( a [ i ] ∗ 10 + j ) f(a[i]*10+j) f(a[i]∗10+j) 的方案数为上一位继承来
d p [ i ] [ f ( a [ i ] ∗ 10 + j ) ] + = d p [ i − 1 ] [ j ] ; dp[i][f(a[i]*10+j)] += dp[i - 1][j]; dp[i][f(a[i]∗10+j)]+=dp[i−1][j];
当前位的方案数+1
d p [ i ] [ f ( a [ i ] ) ] + + ; dp[i][f(a[i])]++; dp[i][f(a[i])]++;

#include
using namespace std;
#define int long long
const int N=1e6+100; 
const int M=998244353;
int t;
int a[N];
int b[N];
int f[10][N];
int fun(int n) {
	if(n<10) return n;
	while(n>=10) {
        int m=0;
        while(n) {
            m+=n%10;
            n/=10;
        }
        n=m;
	}
	return n;
}
signed main() {
	t=1;
	while(t--) {
		int n;
		cin>>n;
		for(int i=1; i<=n; i++) {
			cin>>a[i];
			a[i]=fun(a[i]);
			for(int j=0; j<=9; j++) {
				int tmp=fun(a[i]*10+j);
				f[j][i]+=f[j][i-1]%M;
                f[tmp][i]=(f[tmp][i]+f[j][i-1])%M;
			}
			f[a[i]][i]++;
		}
		for(int i=1; i<=9; i++) {
			cout< 
H 牛牛看云 思维 
题目链接
 题意：
 求
 
    
     
      
       
        n
       
      
      
       n
      
     
    n 
    
     
      
       
        n
       
      
      
       n
      
     
    n
 
    
     
      
       
        Σ
       
      
      
       Σ
      
     
    Σ 
    
     
      
       
        Σ
       
      
      
       Σ
      
     
    Σ 
    
     
      
       
        ∣
       
       
        a
       
       
        i
       
       
        +
       
       
        a
       
       
        j
       
       
        −
       
       
        1000
       
       
        ∣
       
      
      
       ∣ai+a j −1000∣
      
     
    ∣ai+aj−1000∣
 
    
     
      
       
        i
       
      
      
       i
      
     
    i=1 
    
     
      
       
        j
       
      
      
       j
      
     
    j=
    
     
      
       
        i
       
      
      
       i
      
     
    i
 
    
     
      
       
        (
       
       
        0
       
       
        <
       
       
        a
       
       
        i
       
       
        <
       
       
        =
       
       
        1000
       
       
        ,
       
       
        n
       
       
        <
       
       
        =
       
       
        1000000
       
       
        )
       
      
      
       (0(0 
题解：
 因为这个 
    
     
      
       
        n
       
      
      
       n
      
     
    n 很打，
    
     
      
       
        a
       
       
        i
       
      
      
       ai
      
     
    ai很小
 就从 
    
     
      
       
        a
       
       
        i
       
      
      
       ai
      
     
    ai 入手
 记录 
    
     
      
       
        a
       
       
        i
       
      
      
       ai
      
     
    ai 的个数枚举 
    
     
      
       
        a
       
       
        i
       
      
      
       ai
      
     
    ai
 直接计算答案
 假如
    
     
      
       
        a
       
       
        i
       
       
        =
       
       
        =
       
       
        a
       
       
        j
       
      
      
       ai==aj
      
     
    ai==aj ans=自己和自己+自己和别人 
    
     
      
       
        /
       
       
        2
       
      
      
       /2
      
     
    /2 (因为 
    
     
      
       
        j
       
      
      
       j
      
     
    j 是从 
    
     
      
       
        i
       
      
      
       i
      
     
    i 开始的 所以 
    
     
      
       
        /
       
       
        2
       
      
      
       /2
      
     
    /2
 
    
     
      
       
        a
       
       
        i
       
       
        !
       
       
        =
       
       
        a
       
       
        j
       
      
      
       ai!=aj
      
     
    ai!=aj ans=
    
     
      
       
        c
       
       
        n
       
       
        t
       
       
        [
       
       
        a
       
       
        i
       
       
        ]
       
       
        ∗
       
       
        c
       
       
        n
       
       
        t
       
       
        [
       
       
        a
       
       
        j
       
       
        ]
       
       
        /
       
       
        2
       
      
      
       cnt[ai]*cnt[aj]/2
      
     
    cnt[ai]∗cnt[aj]/2
 
vector g[N];
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0); cout.tie(0);
    int n;cin>>n;
    for(int i=1; i<=n; i++) {
        int x; 
        cin>>x;
        g[x].push_back(i);
    }
    int ans=0;
    int a, b;
    for(int i=0; i<=1000; i++) {
        for(int j=i; j<=1000; j++) {
            int a=g[i].size();
            int b=g[j].size();
            if(i==j) {
                ans+=(a+a*(a-1)/2)*abs(i+i-1000);
            } else {
                ans+=a*b*abs(i+j-1000);
            }
        }
    }
    cout< 
F 中位数切分 思维 
题目链接
 题意：
 给定一个长为 
    
     
      
       
        n
       
      
      
       n
      
     
    n 的数组 
    
     
      
       
        a
       
      
      
       a
      
     
    a 和一个整数 
    
     
      
       
        m
       
      
      
       m
      
     
    m，求最多可以划分成多少段，使得每一段的中位数都大于等于
    
     
      
       
        m
       
      
      
       m
      
     
    m。
    
     
      
       
        (
       
       
        1
       
       
        <
       
       
        a
       
       
        i
       
       
        ,
       
       
        m
       
       
        <
       
       
        =
       
       
        1
       
       
        e
       
       
        9
       
       
        ,
       
       
        1
       
       
        <
       
       
        =
       
       
        n
       
       
        <
       
       
        =
       
       
        1
       
       
        e
       
       
        5
       
       
        )
       
      
      
       (1(1 题解：
 原数组大于等于m的记为1，记录 
    
     
      
       
        c
       
       
        n
       
       
        t
       
       
        1
       
      
      
       cnt1
      
     
    cnt1 个
 小于的记为-1，记录 
    
     
      
       
        c
       
       
        n
       
       
        t
       
       
        2
       
      
      
       cnt2
      
     
    cnt2 个
 当一段的 
    
     
      
       
        s
       
       
        u
       
       
        m
       
       
        >
       
       
        =
       
       
        1
       
      
      
       sum>=1
      
     
    sum>=1 的时候这一段中位数就 
    
     
      
       
        >
       
       
        =
       
       
        m
       
      
      
       >=m
      
     
    >=m
 然后就去拿 
    
     
      
       
        1
       
      
      
       1
      
     
    1 的去中和 
    
     
      
       
        −
       
       
        1
       
      
      
       -1
      
     
    −1, 最大的段数就是先把负数中和了使得 
    
     
      
       
        s
       
       
        u
       
       
        m
       
       
        =
       
       
        =
       
       
        0
       
      
      
       sum==0
      
     
    sum==0 再加上一个
    
     
      
       
        1
       
      
      
       1
      
     
    1，假如
    
     
      
       
        c
       
       
        n
       
       
        t
       
       
        1
       
       
        −
       
       
        c
       
       
        n
       
       
        t
       
       
        2
       
       
        <
       
       
        =
       
       
        0
       
      
      
       cnt1-cnt2<=0
      
     
    cnt1−cnt2<=0则不存在，不然段数为 
    
     
      
       
        c
       
       
        n
       
       
        t
       
       
        1
       
       
        −
       
       
        c
       
       
        n
       
       
        t
       
       
        2
       
      
      
       cnt1-cnt2
      
     
    cnt1−cnt2个 。
 
#include 
#define int long long
using namespace std;
const int N=1e5+5;
const double eps=1e-4;
int n, m;int a[N];
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0); cout.tie(0);
    int t;
    cin>>t;
    while(t--) {
         cin>>n>>m;
         int p=0;
         for(int i=1; i<=n; i++) {
            cin>>a[i];
            if(a[i]>=m) p++;
         }
         if(p-(n-p)>0) cout< 
I B站与各唱各的 数学 
题目链接
 题意：
 分子为欧拉函数
 
 
 
题解：
 打表呜呜呜
 最小值是
 
 下一个数是210
 就发现是素数的乘积
    
     
      
       
        2
       
       
        ,
       
       
        2
       
       
        ∗
       
       
        3
       
       
        ,
       
       
        2
       
       
        ∗
       
       
        3
       
       
        ∗
       
       
        5
       
      
      
       2,2*3,2*3*5
      
     
    2,2∗3,2∗3∗5
 因为素数乘积的数不是素数，那么他的因子也少
 那么
    
     
      
       
        H
       
       
        (
       
       
        x
       
       
        )
       
      
      
       H(x)
      
     
    H(x)就大
 因为素数 
    
     
      
       
        x
       
      
      
       x
      
     
    x 的欧拉函数等于 
    
     
      
       
        x
       
       
        −
       
       
        1
       
      
      
       x-1
      
     
    x−1，那么最大值就是范围内最大的素数的
    
     
      
       
        H
       
       
        (
       
       
        x
       
       
        )
       
       
        =
       
       
        (
       
       
        x
       
       
        −
       
       
        1
       
       
        )
       
       
        /
       
       
        x
       
      
      
       H(x)=(x-1)/x
      
     
    H(x)=(x−1)/x
 
    
     
      
       
        p
       
       
        s
       
       
        :
       
      
      
       ps:
      
     
    ps:牛客题解上说 
    
     
      
       
        1
       
       
        e
       
       
        9
       
      
      
       1e9
      
     
    1e9 以内最大的两个素数间隔是 
    
     
      
       
        282
       
      
      
       282
      
     
    282 就直接暴力找
 
#include 
using namespace std;
#define int long long
const int N=1e5+5;
bool vis[1000005];
int pri[1000005], cnt, n;
void get_prime(int n) {
    vis[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            pri[++cnt] = i;
            for (int j = 2 * i; j <= n; j += i) {
                vis[j] = 1;
            }
        }
    }
}
int xiao[N];
signed main() {
    get_prime(100005);
    ios_base::sync_with_stdio(0), cin.tie(0); cout.tie(0);
    xiao[0]=1;
    for(int i=1; i<=cnt; i++) {
         xiao[i]=xiao[i-1]*pri[i]; 
         if(xiao[i]>=1e9) break;
    }
    cnt=10;
    int t; cin>>t;
    while(t--) {
        int n;
        cin>>n;
        if(n==1) {
            cout<<-1<=1; i--)  {
            if(xiao[i]<=n)  {
				cout<=1; i--) {
                int q=0;
                for (int j=2; j<=sqrt(i); j++) {
                    if (i%j==0) {
                        q=1;
                        break;
                    }
                }
                if(!q) {
                    cout< 
D 牛牛做数论 数学 
题目链接
 
题意：
 有 
    
     
      
       
        n
       
      
      
       n
      
     
    n 位人在翻唱一首共 
    
     
      
       
        m
       
      
      
       m
      
     
    m 句的歌曲，人不交流。一句歌词被所有人唱或者没被人唱这句歌词无效，让成功唱出的句子数尽可能多，求期望唱成功的句子数量对1e9 +7取模的结果。
 
    
     
      
       
        (
       
       
        1
       
       
        <
       
       
        =
       
       
        t
       
       
        <
       
       
        =
       
       
        1
       
       
        e
       
       
        4
       
       
        ,
       
       
        1
       
       
        <
       
       
        =
       
       
        n
       
       
        ,
       
       
        m
       
       
        <
       
       
        =
       
       
        1
       
       
        e
       
       
        9
       
       
        ,
       
       
        )
       
      
      
       (1<=t<=1e4,1<=n, m<=1e9,)
      
     
    (1<=t<=1e4,1<=n,m<=1e9,)
 
题解：
 
    
     
      
       
        m
       
      
      
       m
      
     
    m 句歌词相互独立
 设唱的概率为 
    
     
      
       
        p
       
       
        i
       
      
      
       pi
      
     
    pi 不唱的概率为 
    
     
      
       
        (
       
       
        1
       
       
        −
       
       
        p
       
       
        i
       
       
        )
       
      
      
       (1-pi)
      
     
    (1−pi)
 那么答案就是失败的概率就是
    
     
      
       
        (
       
       
        p
       
       
        1
       
       
        ∗
       
       
        p
       
       
        2
       
       
        ∗
       
       
        p
       
       
        3
       
       
        ∗
       
       
        .
       
       
        .
       
       
        .
       
       
        ∗
       
       
        p
       
       
        n
       
       
        )
       
      
      
       (p1*p2*p3*...*pn)
      
     
    (p1∗p2∗p3∗...∗pn)+
    
     
      
       
        (
       
       
        1
       
       
        −
       
       
        p
       
       
        1
       
       
        )
       
       
        ∗
       
       
        (
       
       
        1
       
       
        −
       
       
        p
       
       
        2
       
       
        )
       
       
        ∗
       
       
        .
       
       
        .
       
       
        .
       
       
        ∗
       
       
        (
       
       
        1
       
       
        −
       
       
        p
       
       
        n
       
       
        )
       
      
      
       (1-p1)*(1-p2)*...*(1-pn)
      
     
    (1−p1)∗(1−p2)∗...∗(1−pn)
 那么成功的概率就是
    
     
      
       
        1
       
       
        −
       
       
        (
       
       
        p
       
       
        1
       
       
        ∗
       
       
        p
       
       
        2
       
       
        ∗
       
       
        p
       
       
        3
       
       
        ∗
       
       
        .
       
       
        .
       
       
        .
       
       
        ∗
       
       
        p
       
       
        n
       
       
        )
       
      
      
       1-(p1*p2*p3*...*pn)
      
     
    1−(p1∗p2∗p3∗...∗pn)+
    
     
      
       
        (
       
       
        1
       
       
        −
       
       
        p
       
       
        1
       
       
        )
       
       
        ∗
       
       
        (
       
       
        1
       
       
        −
       
       
        p
       
       
        2
       
       
        )
       
       
        ∗
       
       
        .
       
       
        .
       
       
        .
       
       
        ∗
       
       
        (
       
       
        1
       
       
        −
       
       
        p
       
       
        n
       
       
        )
       
      
      
       (1-p1)*(1-p2)*...*(1-pn)
      
     
    (1−p1)∗(1−p2)∗...∗(1−pn)
 最大化成功就是最小化石板就要使得pi都为
    
     
      
       
        1
       
       
        /
       
       
        2
       
      
      
       1/2
      
     
    1/2 其实是猜的不过可以验算几个
 那么答案就等于
    
     
      
       
        m
       
       
        ∗
       
       
        (
       
       
        1
       
       
        −
       
       
        (
       
       
        1
       
       
        /
       
       
        2
       
       
        
         )
        
        
         n
        
       
       
        ∗
       
       
        2
       
       
        )
       
      
      
       m*(1-(1/2)^n*2)
      
     
    m∗(1−(1/2)n∗2)
 
#include 
using namespace std;
#define int long long
#define ll long long
const int N=1e5+5;
const int M=1e9+7;  
ll ksm(ll a,ll p){ll res=1;while(p){if(p&1){res=res*a%M;}a=a*a%M;p>>=1;}return res;}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0); cout.tie(0);
    int t;cin>>t;
    while(t--) {
        int n, m;
        cin>>n>>m;
        cout<<(m%M*(ksm(2, n-1)%M-1+M)%M*ksm(ksm(2, n-1)%M, M-2)%M)%M< 
B 炸鸡块君与FIFA22 倍增/分块/线段树 
题目链接
 【补】
 题意：
 打游戏胜利将使得分加一、失败使分减一、平局使分不变。若你当前的排位分是 
    
     
      
       
        3
       
      
      
       3
      
     
    3 的整倍数（包括0倍），则若下一局游戏失败，你的排位分将不变（而不是减一）
 给定一个游戏结果字符串和若干次询问，你需要回答这些询问。
 
    
     
      
       
        (
       
       
        1
       
       
        <
       
       
        =
       
       
        l
       
       
        ,
       
       
        r
       
       
        <
       
       
        =
       
       
        n
       
       
        ，
       
       
        q
       
       
        <
       
       
        =
       
       
        2
       
       
        e
       
       
        5
       
       
        ,
       
       
        0
       
       
        <
       
       
        =
       
       
        s
       
       
        <
       
       
        =
       
       
        1
       
       
        e
       
       
        9
       
       
        )
       
      
      
       (1<=l, r<=n，q<=2e5,0<=s<=1e9)
      
     
    (1<=l,r<=n，q<=2e5,0<=s<=1e9)
 
题解：
 
    
     
      
       
        n
       
       
        ,
       
       
        q
       
      
      
       n,q
      
     
    n,q 很大就想到要预处理
 每次询问每段的答案发现只和首位的初始值%3的值有有关
 那么预处理从每一位开始以初始值为 
    
     
      
       
        0
       
       
        ,
       
       
        1
       
       
        ,
       
       
        2
       
      
      
       0, 1, 2
      
     
    0,1,2开始向后进行 *** 作，但是不能 
    
     
      
       
        n
       
       
        ∗
       
       
        n
       
      
      
       n*n
      
     
    n∗n
 所以就想到暴力分块
 假如在同一个分块里就直接暴力模拟
 不在的话
 就在一整块和另一块以%3的值结果来转移
 
#include 
#define int long long
using namespace std;
const int N = 2e5+5;
char str[N];
int d[N][5];//dij代表第i块以j为首值处理后的结果
int bl[N], l[N], r[N];
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0); cout.tie(0);
    int n, q;
    cin>>n>>q;
    cin>>str+1;
    int B=sqrt(n);
    for(int i=1; i<=n; i++) bl[i]=(i+B-1)/B;
    for(int i=1; i<=bl[n]; i++) l[i]=r[i-1]+1, r[i]=r[i-1]+B;
    r[bl[n]]=n;
    for(int i=1; i<=bl[n]; i++) {
        d[i][0]=d[i][1]=d[i][2]=0;
        for(int j=l[i]; j<=r[i]; j++) {
            if(str[j]=='W') {
                d[i][0]++, d[i][1]++, d[i][2]++;
            }else if(str[j]=='L') {
                if(d[i][0]%3) d[i][0]--;
                if((d[i][1]+1)%3) d[i][1]--;
                if((d[i][2]+2)%3) d[i][2]--;
            }
        }
    }
    while(q--) {
        int le, re, s;
        cin>>le>>re>>s;
        if(bl[le]==bl[re]) {
            for(int i=le; i<=re; i++) {
                if(str[i]=='W') {
                    s++;
                }else if(str[i]=='L') {
                    if(s%3) s--; 
                }
            }
            cout< 
待补
 
K 冒险公社 dp 
题目链接
 
G ACM is all you need 
题目链接
 
 
总结 
 Qwq
欢迎分享，转载请注明来源：内存溢出
原文地址:https://54852.com/zaji/5713563.html