补比赛——牛客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;
}感谢支持！
投递哈啰出行等公司10个岗位 >
