补比赛——牛客OI周赛9-普及组

比赛地址

A 小Q想撸串

题目分析

普及T1水题惯例。字符串中找子串。

Code

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x = (x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
const int N = 1e5 + 7;
int n;
char s[N][107],st[10]="NowCoder";
int main()
{
    n = read();
    for(int i=1;i<=n;++i)
        cin>>s[i];
    int p,Len;
    for(int i=1;i<=n;++i) {
        p = 0 ,Len = strlen(s[i]);
        for(int j=0;j<Len;++j) {
            if(s[i][j] == st[p]) ++p;
        }
        if(p == 8) puts("QAK");
        else puts("QIE");
    }
    return 0;
}

B 小L的序列

题目分析

普及T2简单惯例。考察位运算知识，不会赶紧去学吧。

一般这个数据范围记得开long long,记得取绝对值（我就差点忘了）

Code

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#define int long long
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x = (x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
const int N = 1e5 + 7;
int n,a,ans;
signed main()
{
    n = read();
    int s1,s0;
    for(int i=1;i<=n;++i) {
        a = read(); a = abs(a);
        s1 = s0 = 0;
        while(a!=0) {
            if(a&1) s1++;
            else s0++;
            a >>= 1;
        }
        ans += (s1>s0 ? 1 : -1);
    }
    printf("%lld\n",ans);
    return 0;
}

C 小w的禁忌与小G的长诗

题目分析

这是这场比赛最难想的题了吧，反正我一开始是没有想到DP（一不小心告诉你我看了题解）。

定义状态

\(f[i][0]\) 是\(i\)长度的 无‘\(C\)’‘\(O\)’‘\(W\)’ 方案总数

\(f[i][1]\) 是\(i\)长度的 有‘\(C\)’无‘ \(O\)’‘\(W\)’方案总数

\(f[i][2]\) 是\(i\)长度的 有‘\(O\)’无‘ \(C\)’‘\(W\)’方案总数

\(f[i][3]\) 是\(i\)长度的 有‘\(W\)’无‘ \(C\)’‘\(O\)’方案总数

\(f[i][4]\) 是\(i\)长度的 有‘\(C\)’‘ \(O\)’ 无‘\(W\)’方案总数

\(f[i][5]\) 是\(i\)长度的 有‘\(C\)’‘ \(W\)’无‘\(O\)’方案总数

\(f[i][6]\) 是\(i\)长度的 有‘\(W\)’‘ \(O\)’无‘\(C\)’方案总数

有了状态方程是不是巨好推了qwq

\(f[i][0] = f[i-1][0] * 23\) （无C,O,W，每个位23种选择）

\(f[i][1]=(f[i-1][0]+f[i-1][1]*24)\) （f[ i-1 ][ 0 ] 表示在原i-1的基础上第i个点放‘C’，f[ i-1 ][ 1 ] 表示已经有‘C’了，不能选‘O’，‘W’，有24种选择）  
 

\(f[i][2]=(f[i-1][0]+f[i-1][2]*24)\) （同上）  
  
\(f[i][3]=(f[i-1][0]+f[i-1][3]*24)\) （同上）
  
\(f[i][4]=(f[i-1][1]+f[i-1][2]+f[i-1][4]*25)\) 原理和上面差不多; 
  
\(f[i][5]=(f[i-1][1]+f[i-1][3]+f[i-1][5]*25)\)
  
\(f[i][6]=(f[i-1][2]+f[i-1][3]+f[i-1][6]*25)\)

Code （我缩写了方程，大家可千万别学我）

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#define int long long
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x = (x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
const int N = 1e5 + 7;
const int MOD = 1e9 + 7;
int n,f[N][3],ans;
signed main()
{
    n = read();
    f[1][0] = 23;
    f[1][1] = 1;
    for(int i=2;i<=n;++i) {
        f[i][0] = (f[i-1][0]*23) % MOD;
        f[i][1] = (f[i-1][0]+f[i-1][1]*24) % MOD;
        f[i][2] = (f[i-1][1]*2+f[i-1][2]*25) % MOD;
    }
    ans = (f[n][0] + 3*f[n][1]%MOD + 3*f[n][2]%MOD) % MOD;
    printf("%lld",ans);
    return 0;
}

D 小K的雕塑

题目分析

又是一道DP，可见DP重要性。

首先去重，留去重数组长n，取k = min(n,k)

定义状态：设\(f[i][j]\) 为前i个数选了j个 的总f(t)值

\(f[i][j] = f[i-1][j] + f[i-1][j-1]\) （选i点 和 不选i点）

空间太大，承受不住，利用方程特性，滚动数组，留下一维。

Code

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#define int long long
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x = (x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
const int N = 1e6 + 7;
const int MOD = 1e9 + 7;
int n,k,ans;
int a[N],f[N];
signed main()
{
    n = read() ,k = read();
    for(int i=1;i<=n;++i)
        a[i] = read();
    sort(a+1,a+1+n);
    n = unique(a+1,a+1+n) -a-1;
    k = min(n,k);
    f[0] = 1;
    for(int i=1;i<=n;++i) {
        for(int j=k;j>=1;--j) {
            f[j] = (f[j]+f[j-1]*a[i]) % MOD;
        }
    }
    for(int i=0;i<=k;++i)
        ans = (ans+f[i]) % MOD;
    printf("%lld\n",ans);
    return 0;
}

感谢支持！