牛客OI周赛9-普及组

本文主要是介绍牛客OI周赛9-普及组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A题

B题

C题

A题

地址：https://ac.nowcoder.com/acm/contest/696/A

小Q挺喜欢撸串的，没错，字符串！

你给小Q送上了n个字符串

对于一个字符串s，如果在小Q撸掉(删除)任意个字符之后，"NowCoder"是其子串，则这个字符串s是可撸的。小Q最近切题切到手软，想撸串散散心。如果你给他呈现的字符串是可撸的，他会很开心，否则他会很桑心。

输入描述：

一个整数n，表示字符串的数量

接下来每行一个字符串sisi，表示小Q看到的第i个字符串

输出描述：

输出有n行，如果小Q开心他会说QAK，否则他会说QIE

这题目很简单，只要定义一个j，相等则j++ 这样一个一个往后检索，如果最后j等于NowCoder的长度则输出QAK

我定义了一个字符串数组，结果长度M定义到10000000，太大了然后就wa了出结果后改到100000 就过了

#include<iostream>
using namespace std;const int M = 100000;
string s[M];
int n;int main(){string s1 = "NowCoder";cin>>n;for(int i = 0; i<n; i++){cin>>s[i];} for(int k = 0; k<n; k++){int i = 0;int j = 0;while(i < s[k].length()) {if(s[k][i] == s1[j]){j++;}i++;}if(j == s1.length()){cout<<"QAK"<<endl;}else cout<<"QIE"<<endl;}return 0;
}

B题

地址：https://ac.nowcoder.com/acm/contest/696/B

题目描述：

如果一个数x满足的|x|二进制中1的个数>0的个数我们认为他是一个好的数。一个好的数的价值是1，而一个不好的数的价值是-1
比如|2|=|−2|=2(10)=10(2),|10|=|−10|=10(10)=1010(2)|2|=|−2|=2(10)=10(2),|10|=|−10|=10(10)=1010(2)

小L想知道一个序列AnAn的价值是多少

输入描述：

第一行有一个整数n，表示序列AnAn的长度

第二行有n个整数，第i个整数AiAi表示序列中第i个数是多少

输出描述：

输出仅一行，表示这个序列的价值是多少

这道题需要对二进制有所了解，我一看到二进制，就想到了bitset，但是我忽略了一个很重要的因素，那就是有的数可能是负数，应该用abs变成绝对值再进行运算还有一点就是数值范围比较大用int是不能全部通过的

以下是用bitset的AC代码：

#include<iostream>
#include<bitset>
#include<cmath>
using namespace std;const int M = 10000000;
long long n;
long long a[M];
long long ans = 0;long long solve(long long m){long long i = 0;while(pow(2, i) <= m)i++;return i;
}int main(){cin>>n;for(long long i = 0; i<n; i++){cin>>a[i];a[i] = abs(a[i]);}std::bitset<32> bit;for(long long i = 0; i<n; i++){bit = a[i];long long m = solve(a[i]);long long h = bit.count();long long  b = m - h;if(h > b)ans++;elseans--;}cout<<ans<<endl;return 0;
}

以下是不用bitset的AC代码：

一个数除以2 则二进制就是向前移动一位二进制末尾是0的话则这个数十进制是偶数若是1的话这个数十进制就是奇数

则可通过这个不用bitset写出而且感觉更简单

#include<iostream>
#include<cmath>
using namespace std;const int M = 100000+9;long long n;
long long a[M];int main(){cin>>n;long long ans = 0;for(long long i = 0; i<n; i++){cin>>a[i];long long a1 = 0, a0 = 0;a[i] = abs(a[i]);while(a[i] > 0){if(a[i] % 2 == 0)a0++;elsea1++;a[i] = a[i] / 2; }if(a1 > a0)ans++;elseans--;}cout<<ans<<endl;return 0;
}

C题

地址：https://ac.nowcoder.com/acm/contest/696/C

题目描述：自从上次小w被奶牛踹了之后，就一直对此耿耿于怀。
于是"cow"成为了小w的禁忌，而长得和"cow"很像的"owc"…凡是同时含有"c","w","o"的都进入了他的禁忌名单。
小G想给他送一幅幅长为n个字符的长诗，但是又怕触犯他的禁忌。所以他决定要是诗中出现了他的禁忌就宁可不送，可是...他一写起诗来就忘了一切。小G想知道他有多少种的诗可能不触犯他的禁忌

注：小G只会用小写字母写诗

输入描述：一行一个整数n表示诗的长度

输出描述：一行一个整数表示小G有多少种可能的诗不触犯小W的禁忌，由于可能数也许过大，请对109+7取膜后输出

这道题我所知道的有两种做法，其中一种很容易看出来，就是用dp解，dp[i][j]代表长度为i的诗里包含j种禁忌字母，我们可以算出n种长度j为0， 1， 2的dp大小然后相加

dpAC:

#include<iostream>
using namespace std;const int M = 100000+9;
const long long mod = 1e9+7;
long long dp[M][3];int main(){int n;cin>>n;dp[1][0] = 23;dp[1][1] = 3;dp[1][2] = 0;for(int i = 2; i<=n ;i++){dp[i][0] = (dp[i-1][0] * 23) % mod;dp[i][1] = (dp[i-1][0] * 3 + dp[i-1][1] * 24) % mod;dp[i][2] = (dp[i-1][1] * 2 + dp[i-1][2] * 25) % mod;}long long ans = (dp[n][0] + dp[n][1] + dp[n][2]) % mod;cout<<ans;return 0;
}

还有一种就是用容斥算法和快速幂解出，C(3,2)*pow(25,n)%mod - C(3,1)*pow(24,n)%mod + C(3,0)*pow(23, n)%mod

容斥AC：

#include<iostream>
using namespace std;const int M = 100000+6;
const long long mod = 1e9+7;
typedef long long ll;ll quickPow(ll a, ll b, ll c){ll ans = 1;while(b > 0){if(b&1){ans = ans * a % c;}a = a * a % c;b>>=1;}return ans;
}int main(){int n;cin>>n;ll ans;if(n < 3) ans = quickPow(26, n, mod); ans = (3*quickPow(25, n, mod) - 3*quickPow(24, n, mod) + quickPow(23, n, mod)+3*mod)% mod;cout<<ans;
}