小白月赛20
A.链接：https://ac.nowcoder.com/acm/contest/3282/A
来源：牛客网
斐波那契
时间限制：C/C++ 1秒，其他语言2秒
空间限制：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
示例1
输入
复制
5
输出
复制
40
说明
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
include
include
include
include
include
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++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
KevenKevenKeven 有一个矩形，长为 aaa，宽为 bbb，他希望将三个边长相等并且边长是正整数的正方形放在矩形里面，并且希望这三个正方形不能重叠，问正方形的最大边长是多少？
输入描述:
第一行，两个正整数，aaa、bbb，表示矩形的长和宽（1<=a,b<=1e181<=a,b<=1e181<=a,b<=1e18）
输出描述:
在一行中输出一个整数，表示正方形的最大边长。
示例1
输入
复制
2 6
输出
复制
2
示例2
输入
复制
1 1
输出
复制
0
备注:
如果矩形中不能放下三个边长相等并且边长是正整数的正方形，输出0
思路：画几个图易推得 ：（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
来源：牛客网
3的倍数
时间限制：C/C++ 1秒，其他语言2秒
空间限制：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 最多能取多少个字符串。
示例1
输入
复制
3
AB
AABBCCC
BB
输出
复制
2
说明
取第一个字符串和第二个字符串。
思路：每次录入字符串后统计每个字母的数量，暴力求解即可 O(26n10000)
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++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
KevenKevenKeven 今天上课刚刚学了 222 进制与 101010 进制的转化，但他觉得这个题目太简单了，于是他想加强一下这个题目，所以他考虑将 a−za - za−z 这26个小写字母分别表示 10−3510-3510−35，并且希望你将一个 sss 进制的数字 nnn 转化为 kkk 进制的数字。
输入描述:
第一行一个字符串 nnn，
第二行两个整数 s,ks,ks,k，表示 nnn 是 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 进制下表示的数字。
示例1
输入
复制
1001
2 10
输出
复制
9
示例2
输入
复制
z
36 10
输出
复制
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++ 1秒，其他语言2秒
空间限制：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）
输入保证不存在横坐标相等或纵坐标相等的点
输出描述:
按照横坐标大小，从小到大输出每个点的横纵坐标，每个点占一行。
示例1
输入
复制
3
1 1
2 2
3 3
输出
复制
3 3
说明
第三个点满足“最好的点“的定义。
思路：贪心。对于y降序排列的a数组，只要x更大就是好点
include
include
include
include
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=res10+c-'0';res=flag;
}</class>
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++ 1秒，其他语言2秒
空间限制：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"
示例1
输入
复制
4 4
输出
复制
Yes
说明
KevenKevenKeven 可以走到所有的点上并且拿到所有的糖果。
示例2
输入
复制
3 3
输出
复制
No
说明
棋盘如图所示，KevenKevenKeven 一开始在左下角 (1,1)(1,1)(1,1) ，此时 KevenKevenKeven 除了中间的点 (2,2)(2,2)(2,2) 无法走到，其他点都可到达。
备注:
若Keven现在在黄色的点上，那么他可以跳到图中的8个红色点处。
思路：画一下或者bfs打个表发现结论成立的充要条件，再不济2000也可以直接bfs暴力
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、签到题没什么好说的
拼多多集团-PDD成长空间 486人发布