锐客网

  1. 首页 > it技术 > >

集训队每周一赛 2020-05-27（打表+二分+素数+字符串进制）

比赛


第十四次周赛

  • A 好数(Div.2)
    • 题目
    • 题解
  • B 哥德巴赫猜想(Div.2)
    • 题目
    • 题解
  • C 字母王国(Div.1)
    • 题目
    • 题解
  • D 函数最大值(Div.1)
    • 题目
    • 题解
  • E 小静与妈妈(Div.1)
    • 题目
    • 题解

A 好数(Div.2) 题目
假如整数n除以m，结果是无余数的整数，那么我们称 m 就是 n 的因子。
假如一个 他的因子只包含2 、3 、5 ，我们则称 x 是一个好数。
小A 想知道大于或等于 n 的最小的好数是多少？
输出描述
第1行：一个数 T ，表示后面用作输入测试的数的数量。(1<=T<=10000)
第2 ~ T+1 行：每行 1个数 n (1<=n<=1e18)
输入描述
【集训队每周一赛 2020-05-27（打表+二分+素数+字符串进制）】共 T 行，每个样例输出 1 个数，输出大于等于n 的最小的只包含因子 2、3 、5 的 数
示例：
Input：
4
1
13
17
22
Output：
2
15
18
24
题解 打表用数组存储只包含因子 2、3 、5 的 数，排序后二分lower_bound(a,a+cnt,n)找到第一个大于或等于n的数。数组存储的第一个数是1，可以去掉。
#include #include #define ll long long using namespace std; int t,cnt; ll n,pos,N=1e18,a[1000005]; void dabiao() { cnt=0; for(ll i=1; i>t; dabiao(); while(t--) { cin>>n; pos=lower_bound(a,a+cnt,n)-a; cout<

B 哥德巴赫猜想(Div.2) 题目
哥德巴赫猜想可以表述为：任意一个大于等于4 的偶数都可以写成两个质数之和。
现在给定一个偶数 n ，请你将 n 分解成两个质数 p1,p2 ， 可能存在多种分解方
式，请输出 min(p1,p2) 最小的一种，即 10 可分解成 5 和 5 ，但在本题你应该输
出 3 和 .7
输入描述：
一个偶数n(4<=n<=1e5)
输出描述：
输出一个形如 n=p1+p2 的表达式，其中 p1,p2 为质数，且在 n 的所有分解方
案中 min(p1,p2) 是最小的
示例：
Input：
10
Output：
10=3+7
题解 做过类似的题
#include #include int prime(int x) { int i; for(i=2; i<=sqrt(x); i++) { if(x%i==0) return 0; } return 1; } int main() { int n,i; scanf("%d",&n); printf("%d=",n); for(i=2; i<=n/2; i++) { if(prime(i)&&prime(n-i)) { printf("%d+%d\n",i,n-i); break; } } return 0; }

C 字母王国(Div.1) 题目
作为天下第一魔法师的你来到了字母王国，字母王国里没有阿拉伯数字，他们用字
母代表数字。
他们会把一个字符串当成一个 进制数，一个小写字母相当于一个阿拉伯数字，
a~ 0 , b ~ 1 , c ~ 2 ,…, y ~ 24，z ~ 25,例如 zb就是十进制的 651;
如今，你来到字母王国，通过一些交易得到了一些钱币 (字符串)，而你可以施展一
次法术，令字母王国的所有人对字母的认知发生变化，换句话说，你可以重新定义
字母与数字的等价关系，让 a~z 每个字母重新唯一对应一个 0 ~ 25的数字 , 来令
到你此时身上拥有的钱币金额最大化。
注意法术具有一个约束条件，就是你施展法术后的每张钱币不应该有前置0 。
即当你拥有一张钱币为 az 时，你不能让 a=0 ;
输入描述：
多组样例输入
每个样例，第一行为一个整数n,代表你身上携带的钱币数量.
以下有n 行，每行一个字符串si ，代表一张钱币
输出描述：
对于每个样例，输出你在不违反约束条件情况下，将你当前拥有的钱币变成的最大
金额，输出形如Case #x: y，其中 x 为样例序号， y 为本样例的答案
示例：
Input
2
ab
az
4
ac
bc
ac
bc
1
a
Output
Case #1: 1347
Case #2: 2640
Case #3: 25
题解 读完题就跳过，不会做进制运算，还要考虑长度和进位
a ~ z对应0 ~ 25，且不重复。并且不能出现前导0，所以需要标记字符串第一个出现的字母，不能为0并且判断是否出现过，记录字母出现的位置，将所有字母的位置进行排序，按顺序存入数字，将钱币由26进制转为10进制，所有钱币数量和要求小于1e6，对答案取模。
#include #include #include #define ll long long using namespace std; int cas=1,n,maxlen; const int maxn=100010,mod=1e9+7; int num[26][maxn],base[maxn],sum[maxn]; int v[26],rate[26]; char str[maxn]; int cmp(int a, int b) { for(int i=maxn-1; i>=0; i--) { if(num[a][i]!=num[b][i]) { return num[a][i]1) v[str[0]-'a'] = 1; reverse(str, str+len); for(int j=0; j= mod) sum[str[j]-'a']-= mod; } maxlen=max(maxlen,len); } for(int i=0; i<26; i++) { for(int j=0; j=0; i--) { if(rate[i]!=pos) { ans+=(ll)(dic--)*sum[rate[i]]%mod; ans%=mod; } } printf("Case #%d: %lld\n", cas++, ans%mod); } }

D 函数最大值(Div.1) 题目 集训队每周一赛 2020-05-27（打表+二分+素数+字符串进制）
文章图片

集训队每周一赛 2020-05-27（打表+二分+素数+字符串进制）
文章图片

集训队每周一赛 2020-05-27（打表+二分+素数+字符串进制）
文章图片

题解 E 小静与妈妈(Div.1) 题目 集训队每周一赛 2020-05-27（打表+二分+素数+字符串进制）
文章图片

集训队每周一赛 2020-05-27（打表+二分+素数+字符串进制）
文章图片

题解

    推荐阅读


    上一篇：CTF|第12届全国大学生信息安全竞赛线上初赛Web场景 Write Up

    下一篇：CTF|BUUCTF学习记录Web合集