第十届蓝桥杯省赛游记
date: 2019-03-26 19:11:31
上周周天刚打的蓝桥杯
趁着还没忘赶紧写个博客记一下(
填空题
1. 平方和
求1-2019的所有(包含2或0或1或9的)元素的平方和
用long long保险点吧,没了。
答案应该是2658417853
#include <bits/stdc++.h>
#define LL long long
using namespace std;
bool gao(LL x) {
do {
int ret = x % 10;
if (ret == 2 || ret == 0 || ret == 1 || ret == 9)
return true;
x /= 10;
} while (x);
return false;
}
int main() {
LL ans = 0ll;
for (LL i = 1ll;i <= 2019ll;i++)
if (gao(i)) ans += (i*i);
cout << ans << endl;
return 0;
}
//2658417853
2. 递推数列
求第20190324项的后四位
唔,边算边模,然后滚动一下?
答案4659
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL mod = 10000;
int main() {
LL a = 1,a1 = 1,a2 = 1,a3 = 1;
for (LL i = 4;i <= 20190324;i++)
a = (a1 + a2 + a3) % mod,a3 = a2,a2 = a1,a1 = a;
cout << a << endl;
return 0;
}
//4659
3. 走迷宫
字典序D<L<R<U,让输出从(0,0)到(29,49)的字典序最小的路径。
唔,很简单的bfs
DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
186步。
#include <bits/stdc++.h>
using namespace std;
struct Node {
int x,y,step;
string s;
Node(){}
Node(int a,int b,int c,string d) {x = a,y = b,step = c,s = d;}
};
char s[55][55];
bool vis[55][55];
int dx[4] = {1,0,0,-1};
int dy[4] = {0,-1,1,0};
queue<Node> q;
int bfs(int x,int y) {
while (!q.empty()) q.pop();
q.push(Node(0,0,0,""));
vis[0][0] = 1;
while (!q.empty()) {
Node f = q.front(); q.pop();
for (int i = 0;i < 4;i++) {
int tx = f.x + dx[i],ty = f.y + dy[i];
if (tx < 0 || ty < 0 || tx >= 30 || ty >= 50 || vis[tx][ty] || s[tx][ty] == '1') continue;
vis[tx][ty] = 1;
string t;
switch(i) {
case 0 : t = "D";break;
case 1 : t = "L";break;
case 2 : t = "R";break;
case 3 : t = "U";break;
}
Node ret = Node(tx,ty,f.step+1,f.s+t);
if (tx == 29 && ty == 49) {
cout << ret.s << endl;
return ret.step;
}
q.push(ret);
}
}
return -1;
}
int main() {
// freopen("C:\\Users\\SHP\\Desktop\\maze.txt","r",stdin);
// freopen("C:\\Users\\SHP\\Desktop\\out.txt","w",stdout);
for (int i = 0;i < 30;i++)
scanf("%s",s[i]);
cout << bfs(0,0) << endl;
return 0;
}
/**
DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
186
*/
4. 求雨
7*7的矩阵放入1-49的全排列,取每行的中位数的中位数,问最大的值是多少。
这个……最开始看到有点慌来着
想想感觉也没那么难
我们假设,每一行都是从左到右升序的,并且中位数从上到下也是升序的(升序不升序无所谓,关键是方便看)
最中间的黑色格子就是我们要的数字。
我们能看出来,右下部分的黄色格子肯定比黑色的格子值大,左上角的绿色格子肯定比黑色的格子值小。
所以我们贪心的把除了右下角外最大的数字34放入黑色格子并进行验证。(不可能比34大)
发现34填进去之后可以做到满足要求与已知不矛盾。
所以,我们的答案就是34。
5. RSA
这题稍微有点难,需要点数论知识。
(很奇怪为什么公式块不好用了)
题目:
唔,虽然是C++组但是感觉与其花时间搞这个不如用Java痛快点。
标算应该是这样的:
但是……太麻烦了
需要写慢速加,还要写exgcd逆元、欧拉函数……
所以当然Java啦!
import java.math.*;
public class Main {
public static BigInteger divide(BigInteger a) {
BigInteger n = new BigInteger("1001733993063167141");
for (BigInteger i = BigInteger.valueOf(3);i.multiply(i).compareTo(n) <= 0;i = i.add(BigInteger.valueOf(2))) {
if (n.mod(i).compareTo(BigInteger.ZERO) == 0)
return n.divide(i);
}
return n;
}
public static void main(String[] args) {
BigInteger n = new BigInteger("1001733993063167141");
BigInteger c = new BigInteger("20190324");
BigInteger d = new BigInteger("212353");
BigInteger p = divide(n);
System.out.println("p = " + p);
BigInteger q = n.divide(p);
System.out.println("q = " + q);
BigInteger pq = (p.subtract(BigInteger.ONE)).multiply(q.subtract(BigInteger.ONE));
System.out.println("(p-1)*(q-1) = " + pq);
BigInteger e = d.modInverse(pq);
System.out.println("e = " + e);
System.out.println("(d * e) % ((p-1)*(q-1)) = " + d.multiply(e).mod(pq));
System.out.println("ans = " + c.modPow(e,n));
}
}
结果是:
p = 1123984201
q = 891234941
(p-1)*(q-1) = 1001733991047948000
e = 823816093931522017
(d * e) % ((p-1)*(q-1)) = 1
ans = 579706994112328949
代码题
1. 二叉树
给一颗完全二叉树的层序遍历序列,求各层和的最大值。
唔,非常简单的感觉。
我们观察每一层的起点和终点:
(层,起点,终点)
(1,1,2-1)
(2,2,4-1)
(3,4,8-1)
…
(i,1<<(i-1),(1<<i)-1)
所以比较显然,我们可以一层层的枚举了,最开始设最大值是第一层的值,一层层的往下搜。因为一共就1e5,所以最多19层。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL a[1000005];
int main() {
LL n;
cin >> n;
for (LL i = 1;i <= n;i++)
scanf("%lld",&a[i]);
LL ans = a[1],level = 1;
for (LL i = 1;i <= 19;i++) {
LL sum = 0,beg = (1<<(i-1)),ed = (1<<i)-1;
ed = min(ed,n);
for (LL j = beg;j <= ed;j++)
sum += a[j];
if (ans < sum) ans = sum,level = i;
if (ed == n) break;
}
cout << level << endl;
return 0;
}
2. 外卖
唔,用分组的优先队列做的。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
priority_queue <LL,vector<LL>,greater<LL> > q[100005];
int main() {
LL n,m,t,s,id;
cin >> n >> m >> t;
for (LL i = 1;i <= m;i++) {
scanf("%lld%lld",&s,&id);
q[id].push(s);
}
LL cnt = 0;
for (LL i = 1;i <= n;i++) {
if (q[i].empty()) continue;
LL pre = q[i].top(),sum = 2; q[i].pop();
bool in = false;
while (!q[i].empty()) {
LL tmp = q[i].top(); q[i].pop();
if (tmp == pre) sum += 2;
else sum += (3 - tmp + pre),pre = tmp;
if (sum < 0) sum = 0;
if (sum > 5) in = true;
else if (in && sum <= 3) in = false;
}
sum -= (t - pre);
if (sum < 0) sum = 0;
if (sum > 5) in = true;
else if (in && sum <= 3) in = false;
if (in) cnt++;
}
cout << cnt << endl;
return 0;
}
3. 修改数组
考场上没写出来,只写了暴力骗分(
据说标算并查集
但是出来之后听dalaos叽里呱啦说了一通是set+lower_bound就可以水过的东东(
嘛,感觉非常遗憾,还是不太熟悉这种操作
4. 糖果
考场上的想法就是
首先肯定可以压状态用一个数表示
然后……想
这个……有点像线性基?
虽然线性基是异或,能改改成或的吗emmm
滴……没思路了
是IDA*可做的题
果然这题就超出能力范围了(
5. 组合数
首先需要会一个叫Lucas定理的东东
暑假看到这个觉得可能八百年不会碰这个东西所以就没仔细看(
然后这道题果然就碰钉子了
是一个数位dp
emmmm
好毒啊
总结一哈
非常难受,菜爆了
QAQ
希望能学会更多的姿势然后下次体验更好(