lqmm的DP功底不是很扎实，所以这次小白被C题卡住了，最后名次只有一百出头TAT。
A、牛牛冲钻五——>题目传送门
题意：题意很容易理解，直接看题就行；
题解：求一个WL串经过加减操作所获的的分数值，由于题目保证所有样例总和不超过1e5，直接模拟就好了；
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 100005;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
void solve(){
int n, k;
cin>>n>>k;
string s;
cin>>s;
int len = s.length();
ll ans = 0;
ll res = 0;
for(int i = 0; i<len; i++){
if(s[i] == 'W'){
res++;
if(res>=3) ans+=k;
else ans++;
}
else{
ans--;
res = 0;
}
// cout<<ans<<' '<<res<<endl;
}
cout<<ans<<endl;
}
int main()
{
//ios::sync_with_stdio(false), cout.tie(0), cin.tie(0);
int t;
scanf("%d", &t);
while(t--){
solve();
}
return 0;
} B、爱吃素——>题目传送门
题意：给定两个整数，求他们相乘后得到的数是不是素数（素数：只能被1和它本身整除的数）
题解：直接相乘判定肯定不可取，根据素数的定义，若他们相乘为素数，则a和b中必定有一个数为1，否则一定不是素数，此时两数相乘的值就变为另一个数的值，只要判断另一个数的值是否为素数就行；
时间复杂度为O(根号n)
bool is_prime(ll x)
{
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
return false;
return true;
}
void solve(){
ll a, b;
cin>>a>>b;
if(a == 1){
if(is_prime(b)){
puts("YES");
return;
}
}
if(b == 1){
if(is_prime(a)){
puts("YES");
return;
}
}
puts("NO");
}
int main()
{
//ios::sync_with_stdio(false), cout.tie(0), cin.tie(0);
int t;
scanf("%d", &t);
while(t--){
solve();
}
return 0;
} C、糟糕的打谱员——>题目传送门
就卡它手里了，当时没想到DP，一直用贪心去贪，导致比赛时F和G两个比较简单的题目没看，这是个教训；
题意：由两个人（0，1）下棋，给定每轮下棋的人和他们所下的位置（1～10），求最长子序列，子序列满足：每相邻两项下棋的人不同且下棋的位置不同；
题解：这个题乍一看会想到一个经典的DP问题——>最长公共子序***实是这个问题的衍生，维护两个数组：f数组和lo数组，f数组是DP数组，维护的是从1到i满足条件的最长公共子序列，lo数组是二维数组，维护的是上一个1～10的位置是谁下的棋子。从前往后枚举每次查找它的上一个与他不同的人下的不同的位置在哪，每次维护f[i]的最大值；
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100005;
int c[N], a[N], f[N], lo[2][11];
int main()
{
int t;
cin>>t;
while(t--){
memset(f, 0, sizeof f);
memset(lo, 0, sizeof lo);
int n;
cin>>n;
int ans = 0;
for(int i = 1; i<=n; i++){
scanf("%d%d", &c[i], &a[i]);
for(int o = 0; o<=1; o++){
if(c[i]!=o){
for(int j = 1; j<=10; j++){
if(j!=a[i]){
f[i] = max(f[i], f[lo[o][j]]+1);
}
}
}
}
ans = max(ans, f[i]);
lo[c[i]][a[i]] = i;
}
cout<<ans<<endl;
}
return 0;
} D、Mendeleev 1417——>题目传送门
题意：从n个人中随机选择一些人去出差，问所有方案中选择人数偶数和奇数的差；
题解：对于一个n,假设n为偶数，从中选择偶数个人的方案有组合数C[n][0]、C[n][2]、C[n][4]……C[n][n]，选择奇数个方案有组合数C[n][1]、C[n][3]……C[n][n-1]，而所有奇数和偶数的方案数的和恰好为C[n][0]到C[n][n]即为杨辉三角的第n层，通过组合数的性质得知差值恒为-1，实在不行多列出几组n找规律。
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 100005;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
void solve(){
int n;
scanf("%d", &n);
puts("-1");
}
int main()
{
//ios::sync_with_stdio(false), cout.tie(0), cin.tie(0);
int t;
scanf("%d", &t);
while(t--){
solve();
}
return 0;
} E、又一数区间问题——>题目传送门
题意：给定一个长度为n的数组（数组取值0～9），求数组中有多少个区间满足区间长度等于区间内所有数字的积。
题解：首先明白一点，满足条件的区间一定是包含1的，所以先维护一个nxt数组表示下一个不为1的数在哪个位置，如1123134的nxt数组值为33346678，此后遍历原数组，对于每一个点l维护一个值r最开始r=l；
每次查询完后r跳到下一个不为1的数的位置，即nxt[i]，每次要查询l到r范围是否满足等于积和l到下一个r的范围是否有足够多的1来满足类似于（11XXX11111）这种情况；
例如：111231151，当l为1的时候r最开始为1，此时满足，此后r为5的时候[1,5]（11123）不满足，查看下一个到的r值为8，此时1～8大于前面乘积的值，后面有足够的1，而且前面1～5相比于乘积更小，就可以得到一个111231的子串满足；
const int N = 100005;
int a[N], nxt[N];
int main()
{
int n;
scanf("%d", &n);
string s;
for(int i = 1; i<=n; i++){
scanf("%1d", &a[i]);
}
int x = n+1;
for(int i = n; i; i--){
nxt[i] = x;
if(a[i]!=1)x = i;
}
nxt[n+1] = 0x3f3f3f3f;
int ans = 0;
for(int l = 1; l<=n; l++){
x = 1;
for(int r = l; x<=n&&r<=n+1; r = nxt[r]){
x*=a[r];
if(r-l+1 == x) ans++;
if(nxt[r]-l>=x&&r-l+1<x) ans++;
}
}
cout<<ans<<endl;
return 0;
} F、一个经典概率问题——>题目传送门
题意：给定1e5条弦长，按照B和L的构造方法，问这些弦是由谁构造出来的；
题解：思路很简单，我们观察B和L的构造方法，L的构造方法是在半径中选的，B的构造方法是在整个圆中选择的，相较而言L的构造方法得到的弦方差肯定更小，但这里没有第二组数据做比较，画图计算，L的弦长平均值为单位圆半径中垂线交圆的长度，先求出平均弦长，再将给定弦长的平均值与之做比较，在某个小范围内的认为是L的构造，这某个小范围就要去尝试；
const int N = 100005;
double a[N];
int main()
{
int n;
scanf("%d", &n);
double sum = 0;
for(int i = 1; i<=n; i++){
scanf("%lf", &a[i]);
sum+=a[i];
}
double ans = sqrt(1-0.25)*2.0;
if(fabs(sum/n*1.0 - ans) < 0.2){
puts("L");
}
else {
puts("B");
}
return 0;
} G、又一构造子序列——>题目传送门
题意：题意很容易理解，就是自己用构造方法构造出满足字符串中恰好有n个yyc子序列的字符串， 无法在限制长度内构造的输出-1；
题解：题目有限制字符串的长度，所以按最短构造方法，对于一个yyc，后面每多一个c，就会多出c前面有多少个y的个数个yyc子序列，而每有x个y就有组合数C[x][2]乘后面c的个数个yyc，而对于所有组合数C[2][2]到C[n][2]的值可以先预处理出来，为a数组：1，3，6，10……，而此时对于任意一个数字n，把n用a数组的值凑出来（用尽可能少的数字），因为有1，所以一定可以凑出来且不会超过限制，而对于每一个a[i]在凑的过程中用了多少次，后面跟多少个c；
例如：7 = 6+1， 6为yyyyc，1为yyc，则可以把c放在第三个位置成为yycyyc即为所求；对于第一个c有两个y，对于第二个c有四个y；
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 100005;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
ll a[N];
struct lq{
int x, num;
}f[N];
int main()
{
ll ans = 1;
ll res = 2;
for(int i = 2; i<=100000; i++){
a[i] = ans;
ans+=res;
res++;
}
//ios::sync_with_stdio(false), cout.tie(0), cin.tie(0);
int t;
scanf("%d", &t);
while(t--){
ll n;
scanf("%lld", &n);
// int res = lower_bound(a+1, a+10000, n)-a;
int cnt = 0;
for(int i = 100000; i>=2; i--){
if(a[i]>n)continue;
f[++cnt].x = i;
f[cnt].num = n/a[i];
n = n%a[i];
}
string s = "";
int ans = 0;
f[cnt+1].x = 0;
for(int i = cnt; i; i--){
for(int j = 1; j<=f[i].x - f[i+1].x; j++){
s += 'y';
ans++;
}
for(int j = 1; j<=f[i].num; j++){
s += 'c';
ans++;
}
}
printf("%d\n", ans);
cout<<s<<endl;
}
return 0;
} 有任何问题欢迎评论区指出！
京公网安备 11010502036488号