锐客网

  1. 首页 > it技术 > >

数论and数学|牛客练习赛51-记录

字符串贪心数论and数学

正题 【数论and数学|牛客练习赛51-记录】比赛链接:https://ac.nowcoder.com/acm/contest/1083#question
成绩 数论and数学|牛客练习赛51-记录
文章图片

可怜的 z y c T 3 zycT3 zycT3被 n = 0 n=0 n=0卡了半天，这里感谢一下排雷
总结 比赛状态较好，后面没有 T 6 T6 T6的题解
T 1 : a b c T1:abc T1:abc 题目大意
给出一个字符串，求有多少个 a b c abc abc子序列
解题思路
用三个数组分别表示 a a a的个数， a b ab ab的个数， a b c abc abc的个数即可
c o d e code code

#include #include #include using namespace std; char s[110000]; long long n,a,b,c; int main() { scanf("%s",s+1); n=strlen(s+1); for(int i=1; i<=n; i++){ if(s[i]=='a') a++; if(s[i]=='b') b+=a; if(s[i]=='c') c+=b; } printf("%lld",c); }

T 2 : T2: T2: 子串查询 题目大意
给出一个字符串， q q q个询问，每次询问一个字符串求它是否是前面那个字符串的子序列。
解题思路
用 a i , j a_{i,j} ai,j?表示第 i i i个开始 j j j字符最早出现在哪里，然后一个一个跳就好了
时间复杂度 O ( 26 n + ∑ ∣ q ∣ ) O(26n+\sum |q|) O(26n+∑∣q∣)
c o d e code code
#include #include #include using namespace std; const int N=1e5+100; int n,t,a[N][26]; char s[N],q[60]; int main() { scanf("%d%d",&n,&t); scanf("%s",s+1); memset(a,127/3,sizeof(a)); for(int i=n; i>=1; i--){ for(int j=0; j<26; j++) a[i][j]=a[i+1][j]; a[i][s[i]-'a']=i; } while(t--){ scanf("%s",q+1); int m=strlen(q+1),now=1,flag=0; for(int i=1; i<=m; i++){ now=a[now][q[i]-'a']+1; if(now>n+1){flag=1; break; } } if(flag) printf("NO\n"); else printf("YES\n"); } }

T 3 : T3: T3:勾股定理 题目大意
给一个正整数 n n n，求两个正整数 a , b a,b a,b可以和 n n n组成勾股数。
解题思路
先考虑若 n n n为奇数我们有 a 2 ? b 2 = n 2 a^2-b^2=n^2 a2?b2=n2
( a + b ) ( a ? b ) = n 2 (a+b)(a-b)=n^2 (a+b)(a?b)=n2
若 a = b + 1 a=b+1 a=b+1那么有 ( b + 1 + b ) ( b + 1 ? b ) = n 2 (b+1+b)(b+1-b)=n^2 (b+1+b)(b+1?b)=n2
2 b + 1 = n 2 2b+1=n^2 2b+1=n2
那么当 n n n为奇数时都有解。
那我们看偶数若 a 2 ? b 2 = n 2 a^2-b^2=n^2 a2?b2=n2我们有 ( 2 a ) 2 ? ( 2 b ) 2 = ( 2 n ) 2 (2a)^2-(2b)^2=(2n)^2 (2a)2?(2b)2=(2n)2
那么我们可以每次将 n n n除 2 2 2到奇数为止然后计算出 a , b a,b a,b再乘回去。
但是特殊的是当 n = 2 k n=2^k n=2k时我们将 n n n除到 4 4 4然后用 3 , 5 3,5 3,5来进行匹配即可。
c o d e code code
#include #include #include #include #define ll long long using namespace std; ll n,a,b,z; int main() { scanf("%lld",&n); if(n<=2) return printf("-1")&1; if((n*n)&1) printf("%lld %lld\n",n*n/2,n*n/2+1); else{ while(!(n&1)&&n>4){ n=n/2; z++; } a=n*n/2; b=n*n/2+1; if(n==4) a=3,b=5; while(z--) a*=2,b*=2; printf("%lld %lld\n",a,b); } }

T 4 : T4: T4:羊吃草 题目大意
若干个区间，每次询问一段区间，求这段区间内每个点匹配一个区间最多能匹配到多少个。
解题思路
就是区间配点的问题，和jzoj6274-[NOIP提高组模拟1]梦境【贪心,堆】这题一样，这里不过多称述
c o d e code code
#include #include #include #include using namespace std; const int N=410; priority_queue q; struct node{ int l,r; }a[N]; int L,R,n,m; bool cMp(node x,node y) {return x.l

T 5 : T5: T5:数列 题目大意
将一个每个值都非0的序列，求一个序列使得 a i = a i ? 1 + 1 ( i > 1 ) a_i=a_{i-1}+1(i> 1) ai?=ai?1?+1(i>1)的情况最多
解题思路
我们可以将这个数列分成若干段连续铺满的区间，然后每段长度为 l l l的区间贡献为 l ? 1 l-1 l?1，然后价格为 ( l + 1 ) ? l 2 \frac{(l+1)*l}{2} 2(l+1)?l?
我们考虑贪心，因为一段长度为 l l l的区间贡献为 l ? 1 l-1 l?1，我们可以视为第一个没有贡献，然后我们假设已经知道了要分成 k k k段，然后我们让序列长度提前减去 k k k那么这样一段长度为 l l l的区间贡献就是 l l l了，那我们只需要价值最少就好了，这个我们可以均摊即可。
然后 k k k我们进行枚举，时间复杂度 O ( n ) O(n) O(n)
c o d e code code
#include #include #include using namespace std; int n,m,N; int main() { scanf("%d%d",&n,&m); N=n; for(int i=1; i<=n; i++){ int k=n/i,cost=k*(k+1)/2*i+n%i*(k+1); if(cost<=m){ int z=0,s=1; while(z

    推荐阅读


    上一篇：Spring Cloud 2020 年路线图（二季度Spring Boot 2.3、四季度Spring Cloud Ilford）

    下一篇：iOS 释放内存/指针清空（release/=nil）深度讨论