牛客小白赛20
A.链接：https://ac.nowcoder.com/acm/contest/3282/A
来源：牛客网
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
KevenKevenKeven 特别喜欢斐波那契数列，已知 fib1=1fib_1=1fib1=1，fib2=1fib_2=1fib2=1，对于 n>=3n>=3n>=3，fibn=fibn−2+fibn−1fib_{n}=fib_{n-2}+fib_{n-1}fibn=fibn−2+fibn−1，并且他想知道斐波那契前 nnn 项平方和是多少？
为了防止答案过大，请将最后的答案模 1e9+71e9+71e9+7
输入描述:
第一行一个整数 nnn（1<=n<=1e181<=n<=1e181<=n<=1e18）
输出描述:
在一行中输出斐波那契数列的前 nnn 项平方和模 1e9+71e9+71e9+7
说明
12+12+22+32+52=401^2+1^2+2^2+3^2+5^2=4012+12+22+32+52=40
思路：只存了板子，具体证明见https://blog.csdn.net/lanchunhui/article/details/51840616
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <queue> #include<cstdlib> #define ll long long #define MOD 1000000007 using namespace std; struct nobe { ll a[2][2]; }; ll n; ll sum; nobe mut(nobe x,nobe y) { nobe res; memset(res.a,0,sizeof(res.a)); for(ll i=0;i<2;i++) for(ll j=0;j<2;j++) for(ll k=0;k<2;k++) res.a[i][j]=(res.a[i][j]+x.a[i][k]*y.a[k][j])%MOD; return res; } void quick(ll n) { nobe c,res; c.a[0][0]=1; c.a[0][1]=1; c.a[1][0]=1; c.a[1][1]=0; memset(res.a,0,sizeof(res.a)); for(ll i=0;i<2;i++) res.a[i][i]=1; while(n) { if(n&1) res=mut(res,c); c=mut(c,c); n=n>>1; } printf("%lld\n",((res.a[0][1]%MOD)*(res.a[0][1]%MOD+res.a[1][1]%MOD))%MOD); } int main() { ll i,t; while(scanf("%lld",&n)!=EOF) { quick(n); } return 0; }
B.最大边长
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
思路：画几个图易推得 ：（1）长边≥3*短边时，答案就是短边长 （2）否则判断长边/3和短边/2谁更大，因为要求整数
的原因和需满足上一个条件，所以短边/2能满足解
#include <bits/stdc++.h> using namespace std; typedef long long LL; int main() { unsigned long long a,b; unsigned long long sum = a * b; cin >> a >> b; if(a > b) { unsigned long long temp = a; a = b; b = temp; } if(b >= a*3) { cout << a << endl; } else { cout << max(b/3,a/2) << endl; } return 0; }
C题计算几何，纯模拟就好了
D.链接：https://ac.nowcoder.com/acm/contest/3282/D
来源：牛客网
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
给你 nnn 个字符串，每个字符串最多包含 A−ZA - ZA−Z 这26个字母，KevenKevenKeven 现在取了一些字符串，发现每个字母出现的次数都是 333 的倍数，KevenKevenKeven 现在想要知道在满足每个字母出现的次数都是 333 的倍数的前提下，最多能取多少个字符串。
输入描述:
第一行一个数字 nnn，表示字符串的个数（1<=n<=15）（1<=n<=15）（1<=n<=15）
接下来 nnn 行，每行一个字符串 sss（1<=strlen(s)<=10000）（1<=strlen(s)<=10000）（1<=strlen(s)<=10000）
输出描述:
在一行中输出 KevenKevenKeven 最多能取多少个字符串。
说明
取第一个字符串和第二个字符串。
思路：每次录入字符串后统计每个字母的数量，暴力求解即可 O(26*n*10000)
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 1e5 + 7; char a[maxn]; int n; int tot[30]; int main() { scanf("%d",&n); int ans = 0; for(int s = 1; s <= n; s++) { memset(a,0,sizeof(a)); scanf("%s",a); int len = strlen(a); for(int i = 0; i < len; i++) { tot[a[i] - 'A'+1]++; //printf("tot[%d]:%d\n",a[i]-'A'+1,tot[a[i]-'A'+1]); } int flag = 1; int pos = 0; for(int i = 1; i <= 26; i++) { if(tot[i] != 0) { if(tot[i] % 3 != 0) { flag = 0; } } } if(flag) { ans += s-pos; pos = s; //printf("ans:%d\n",ans); } } printf("%d\n",ans); return 0; }
E线段树
F进制转换
链接：https://ac.nowcoder.com/acm/contest/3282/F
来源：牛客网
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
KevenKevenKeven 今天上课刚刚学了 222 进制与 101010 进制的转化，但他觉得这个题目太简单了，于是他想加强一下这个题目，所以他考虑将 a−za - za−z 这26个小写字母分别表示 10−3510-3510−35，并且希望你将一个 sss 进制的数字 nnn 转化为 kkk 进制的数字。
输入描述:
输入保证 nnn 是一个 sss 进制数。
(1<s,k<=36，1<=n<=s200)(1<s,k<=36，1<=n<=s^{200})(1<s,k<=36，1<=n<=s200)
输出描述:
在一行中输出 nnn 在 kkk 进制下表示的数字。
输出
复制35
思路：C++不好做，Python暴力->十进制->答案要求的进制
s=input() n,m=map(int,input().split()) sum=0 Len=len(s); for i in range(0,Len): carry=s[i] sum*=n; num=0; if s[i]>'9': num=ord(s[i])-ord('a')+10 else : num=ord(s[i])-ord('0') sum+=num; s1="" while sum>0: num=sum%m; carry='0' if num>9: carry=str(chr(ord('a')+num-10)) else : carry=str(chr(ord('0')+num)) s1+=carry; sum=sum//m; print(s1[::-1])
G、LIS
H、好点
链接：https://ac.nowcoder.com/acm/contest/3282/H
来源：牛客网
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
在一个二维平面里，如果一个点 sss 的右上方没有点，即不存在 (x,y)(x,y)(x,y) 同时满足 x>=xs，y>=ysx>=x_s，y>=y_sx>=xs，y>=ys 这两个条件，KevenKevenKeven 认为这个点是“最好的点“。
现在 KevenKevenKeven 给你 nnn 个点，他希望你能够找出所有“最好的点“，并按照横坐标大小从小到大输出。
输入描述:
第一行一个整数 nnn ，表示点的数量（1<=n<=5e5）（1<=n<=5e5）（1<=n<=5e5）
接下来 nnn 行，每行两个整数 xi,yix_i,y_ixi,yi ，表示一个点的坐标。（−1e9<=x,y<=1e9）（-1e9<=x,y<=1e9）（−1e9<=x,y<=1e9）
输入保证不存在横坐标相等或纵坐标相等的点
输出描述:
按照横坐标大小，从小到大输出每个点的横纵坐标，每个点占一行。
说明
第三个点满足“最好的点“的定义。
思路：贪心。对于y降序排列的a数组，只要x更大就是好点
#include <algorithm> #include <cstring> #include <cstdio> #include <iostream> using namespace std; typedef long long LL; const int maxn = 5e5+7; template<class T>inline void read(T &res) { char c;T flag=1; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0'; while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag; } struct node { int x,y; }a[maxn]; bool cmp1(node a, node b) { return a.y < b.y; } bool cmp2(node a, node b) { return a.x < b.x; } node ans[maxn]; int main() { int n; read(n); for(int i = 1; i <= n; i++) { read(a[i].x),read(a[i].y); } sort(a+1, a+n+1, cmp1); for(int i = 1; i <= n; i++) { //printf("a:%d %d\n",a[i].x,a[i].y); } int cnt = 1; ans[cnt++] = {a[n].x,a[n].y}; int maxx = a[n].x; for(int i = n-1; i >= 1; i--) { //printf("maxx:%d\n",maxx); if(a[i].x > maxx) { ans[cnt++] = {a[i].x,a[i].y}; maxx = a[i].x; } } sort(ans+1, ans+cnt, cmp2); for(int i = 1; i < cnt; i++) { printf("%d %d\n",ans[i].x,ans[i].y); } return 0; }
链接：https://ac.nowcoder.com/acm/contest/3282/I
来源：牛客网
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
给定一个棋盘，已知棋盘的行数和列数是 n，mn，mn，m，每个整数坐标处都有一个糖果，KevenKevenKeven 初始在棋盘的左下角 (1,1)(1,1)(1,1) 出发，并且 KevenKevenKeven 每次只能跳 ”日” 字，假设 KevenKevenKeven 可以跳无数次，但不可以跳出棋盘，现在 KevenKevenKeven 想知道他能否拿到棋盘上的所有糖果。
输入描述:
在一行中给出两个数字 n，mn，mn，m，表示棋盘的大小 （1<=n,m<=2000)（1<=n,m<=2000)（1<=n,m<=2000)
输出描述:
若 KevenKevenKeven 能拿到棋盘上所有的糖果，则输出 "Yes"，否则，输出 "No"
备注:
#include <bits/stdc++.h> using namespace std; int main() { int a,b; cin >> a >> b; if((a >= 3 && b > 3) || (a > 3 && b >= 3) || (a == 1 && b == 1)) { puts("Yes"); } else puts("No"); return 0; }
J、数位DP
K、签到题没什么好说的
