题目传送门
原本发在CSND上,如今搬到自己的博客上并顺便填坑,一直填坑一直爽。
作者是个打铁弱鸡,若各位大佬发现了错误请在评论指出。
A. 结果填空:有趣的数字
蓝桥杯标准的送温暖题,枚举每个数判断是否含有数字5并进行判素数后计数即可。
const int MAXN = 100000;
bool check(int n) {
while(n) {
if(n % 10 == 5) return true;
n /= 10;
}
return false;
}
bool prime(int n) {
if(n < 2) return false;
bool ret = true;
for(int i = 2; i * i <= n; i++) {
if(n % i == 0) ret = false;
}
return ret;
}
int main() {
int cnt = 0;
for(int i = 1; i <= MAXN; i++)
if(check(i) && prime(i)) cnt++;
cout << cnt << endl;
return 0;
}
B. 结果填空:爬楼梯
超级经典的dp,蓝桥杯日常经典题变形。
萌新可以先做牛客的这道题 传送门
- 通过暴力枚举我们可以发现当步数为1和2时,方案数为1 1 2 3 5 8 11,为斐波那契数列。但显然,暴力是没有前途的,下面介绍另一种方法。
- 定义$F(i)$为走到第$i$级台阶的方案数,则显然可得当 $i>2$ 时有$F(i) = F(i-1) + F(i-2)$。因为要走到第$i$级台阶,可以是由$i-1$级台阶上来也可以是由$i-2$级台阶上来,所以第$i$级的方案数应等于两者之和。
- 此题是一次最多可以上四级台阶,但第5级和第7级不能踩,则可以得到表达式$F(i) = F(i-1) + F(i-2)+ F(i-3) + F(i-4)$,并特判$F(5) = F(7) = 0$。
- 到这里就可以写出简单的递归程序了,但是只会写递归是没有前途的(手动滑稽),所以给出非递归的dp版,当然下面的版本完全可以预处理前四项来精简代码。
int a[117];
int main() {
a[0] = 1;
for(int i = 1; i <= 10; i++) {
if(i == 5 || i == 7) continue;
if(i - 1 >= 0) a[i] += a[i - 1];
if(i - 2 >= 0) a[i] += a[i - 2];
if(i - 3 >= 0) a[i] += a[i - 3];
if(i - 4 >= 0) a[i] += a[i - 4];
}
for(int i = 1; i <= 10; i++) cout << a[i] << endl;
return 0;
}
C. 结果填空:七巧板
和用直线划分平面的原理是一样的,每次新增的区域数是一个以1为首项公差为1的等差数列。
跳进了唯一的坑里:请在下图的基础上,图中一开始就有7个区域。
int ans, det;
int main() {
ans = 7, det = 6;
for(int i = 0; i < 5; i++) ans += det++;
cout << ans << endl;
return 0;
}
D. 结果填空:苹果
在网上看到的大多是贪心的写法,大致上都是在当前能选3就选3,不能选再和旁边的并用,但都存在反例。做的时候也考虑过贪心但未能成功证明,于是写了个暴力的递归来枚举所有的情况,稍微剪枝优化后时间在1s左右。此题个人认为此题应该是dp,但学艺不精没写出dp来。。。
int ans = 0;
int a[117] = {7, 2, 12, 5, 9, 9, 8, 10, 7, 10, 5, 4, 5, 8, 4, 4, 10, 11, 3, 8, 7, 8, 3, 2, 1, 6, 3, 9, 7, 1};
int sum[117];
void dfs(int idex, int num) {
if(idex == 30) {
ans = max(ans, num);
return;
}
if(sum[idex] / 3 + num < ans) return;//剪枝优化
//不共用
dfs(idex + 1, num + a[idex] / 3);
//往后共用
if(idex + 2 < 30) {
int min_num = min(a[idex], a[idex + 1]);
min_num = min(min_num, a[idex + 2]);//共用最多能分几个
for(int k = 1; k <= min_num; k++) {
for(int i = 0; i < 3; i++) a[idex + i] -= k;
dfs(idex + 1, num + a[idex] / 3 + k);
for(int i = 0; i < 3; i++) a[idex + i] += k;
}
}
}
int main() {
for(int i = 29; i >= 0; i--) sum[i] = sum[i + 1] + a[i];
dfs(0, 0);
cout << ans << endl;
return 0;
}
正确的姿势dp:从这位大佬这里学到了dp的解法,快去看看大佬的博客。
- 其实这个dp并不难,主要是没想清楚,画图能有效的帮助理解。
- 如上图所示,对于第$i$个篮子里的苹果凑齐三个一共有四种方式:往左共用、中间共用、往右共用和本身自己凑齐三个。
- 可以定义$dp[i][j][k][l]$表示前$i$个篮子的答案,则有状态转移方程$dp[i][j][k][l]=max(dp[i-1][m][j][k]+(a[i]-j-k-l)/3+j)$。
- 上式应满足$i+j+k\leq a[i]$,且$i,j,k\in[0,2]$。
- 可进一步优化成$dp[i][j][k]$省略第一种状态,详见代码。
int a[37] = {0, 7, 2, 12, 5, 9, 9, 8, 10, 7, 10, 5, 4, 5, 8, 4, 4, 10, 11, 3, 8, 7, 8, 3, 2, 1, 6, 3, 9, 7, 1};
int ans, dp[37][7][7];
int main() {
ans = 0;
memset(dp, negative_infinite, sizeof(dp));
dp[0][0][0] = 0;
for(int i = 1; i <= 30; i++) {
for(int j = 0; j < 3; j++) {
for(int k = 0; k < 3; k++) {
for(int l = 0; l < 3; l++) {
if(j + k + l <= a[i]) {
dp[i][k][l] = max(dp[i][k][l], dp[i - 1][j][k] + (a[i] - j - k - l) / 3 + j);
ans = max(ans, dp[i][k][l]);
}
}
}
}
}
cout << ans << endl;
return 0;
}
E. 结果填空:方阵
- 设点A坐标为$(x1,y1)$,点B坐标为$(x2,y2)$,当且仅当$gcd(x1-x2,y1-y2)=1$时AB连线上没有其它点。因为若不互质,则存在相似三角形可以找到其它点。
- 解法一:枚举所有可能的点对,判断x轴距离和y轴距离是否互斥,复杂度$o(n^4)$。
- 解法二:枚举所有可能的x轴距离和y轴距离,算出对答案的贡献求和,但要注意特判某一边为0的情况。
#define LL long long
LL n = 1000, k = 500 * 500, ans = 0;
int main() {
for(int i = 1; i < n; i++)
for(int j = 1; j < n; j++)
if(__gcd(i, j) == 1 && i * i + j * j <= k)
ans = (ans + 2 * (n - i) * (n - j) % mod) % mod;
ans = (ans + 2 * n * (n - 1) % mod) % mod;
cout << ans << endl;
return 0;
}
F. 程序设计:寻找重复项
题意简单明了,作为c++选手,直接使用了STL库。
- 解法一:Hash
- 解法二:维护一个有序序列,二分进行查找和插入,复杂度logn
- 对于萌新:各种库函数和板子当然可用,但不能依赖,不然岂不本末倒置。
#define LL long long
const int MAXN = 2e6;
LL a, b, c;
LL num[MAXN + 117];
unordered_set<int> s;
int main() {
num[0] = 1;
s.insert(1);
scanf("%lld%lld%lld", &a, &b, &c);
for(int i = 1; i <= MAXN; i++) {
num[i] = (a * num[i - 1] + num[i - 1] % b) % c;
if(s.count(num[i])) {
printf("%d\n", i);
break;
} else s.insert(num[i]);
if(i == MAXN) puts("-1");
}
return 0;
}
G. 程序设计:被袭击的村庄
- 题意是个坑点:
现在,给定上述的所有信息,我们想知道A村被袭击之后的道路、房屋、田地的总伤害,以及全村的总伤害。正确的应该是输出被袭击之后道路、房屋、田地耐久度为0的数量和全村的总伤害。 - 模拟题,维护一个decrement矩阵来记录耐久度的减少量。
- 对于每一发炮弹,更新对应伤害范围内的耐久度,对于高级炮弹还需特判溅射伤害。
#define LL long long
const int MAXN = 300 + 117;
int n, m, k;
LL a, b, c, w;
LL harm[MAXN][MAXN];//炮弹的范围伤害
LL decrement[MAXN][MAXN];//耐久度的减少量
int village[MAXN][MAXN];//村庄布局
int q, id, x, y;
LL road, house, field, sum;
int dx[8] = { -1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = { -1, 0, 1, -1, 1, -1, 0, 1};
bool check(int x, int y) {//判断坐标是否合法
if(x < 0 || x >= n) return false;
if(y < 0 || y >= m) return false;
return true;
}
void sputtering(int x, int y) {//往周围8个格子溅射伤害
for(int i = 0; i < 8; i++) {
if(check(x + dx[i], y + dy[i]))
decrement[x + dx[i]][y + dy[i]] += w;
}
}
void solve() {
int bex = x - k / 2, bey = y - k / 2;
for(int i = 0; i < k; i++) {
for(int j = 0; j < k; j++) {
if(check(bex + i, bey + j)) {
decrement[bex + i][bey + j] += harm[i][j];
if(id == 0) sputtering(bex + i, bey + j);
}
}
}
}
void pr() {
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(village[i][j] == 1) {
//road += min(decrement[i][j], a);
road += decrement[i][j] >= a;
sum += min(decrement[i][j], a);
} else if(village[i][j] == 2) {
//house += min(decrement[i][j], b);
house += decrement[i][j] >= b;
sum += min(decrement[i][j], b);
} else {
//field += min(decrement[i][j], c);
field += decrement[i][j] >= c;
sum += min(decrement[i][j], c);
}
}
}
cout << road << " " << house << " " << field << endl;
cout << sum << endl;
}
int main() {
cin >> n >> m;
cin >> a >> b >> c;
cin >> k >> w;
for(int i = 0; i < k; i++)
for(int j = 0; j < k; j++)
cin >> harm[i][j];
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cin >> village[i][j];
cin >> q;
while(q--) {
cin >> id >> x >> y;
x--, y--;
solve();
}
pr();
return 0;
}
H. 程序设计:字符串
- 此题需要前置技能点:模运算,即89%M = (8*10%M + 9*1%M)%M。
- 先假设进制为10进制,题意为给定一个数,至多交换两位数字使得到的数字是M的倍数。
题目中说到多解输出字典序最小,则容易想到枚举。考虑一下复杂度,枚举交换的位置需要o($n^2$),计算mod需要o($n^1$),总的复杂度o($n^3$)。 - 对多次取模操作进行优化,假设$a=123\%M,b=321\%M$,考虑123和321之间的关系:$321 = 123 - 1 \ast 100 - 3 \ast 1 + 3 \ast 100 + 1 \ast 1$,根据模运算则有$b = (a - 1 \ast 100 - 3 \ast 1 + 3 \ast 100 + 1 \ast1 )\%M$。即假设交换任意$i$位置和$j$位置的数,A为交换前的值,B为交换后的值,有$B = (A - i \ast {10^i} - j \ast {10^j} + i \ast {10^j} + j \ast {10^i})\%M$,复杂度O(1)。
- 最后,进制为26,需要预处理一下幂次的取模,以及注意减法运算时答案的取正。
const int MAXN = 2000 + 117;
char s[MAXN];
int len;
int a[MAXN];
int fact[MAXN];
int M;
int num, now;
void sub(int mul, int order) {//now=now-mul*26^order
int sum = fact[order];
sum = sum * mul % M;
now = ((now - sum) % M + M) % M;
}
void add(int mul, int order) {//now=now+mul*26^order
int sum = fact[order];
sum = sum * mul % M;
now = (now + sum) % M;
}
void init() {//预处理幂次
scanf("%s", s);
scanf("%d", &M);
fact[0] = 1;
for(int i = 1; i < MAXN; i++) fact[i] = fact[i - 1] * 26 % M;
len = strlen(s);
for(int i = 0; i < len; i++) {
a[i] = s[i] - 'A';
num = (num * 26 + a[i]) % M;
}
}
int main() {
init();
if(num == 0) puts("0 0");
else {
bool pr = false;
for(int i = 0; i < len && !pr; i++) {
for(int j = 0; j < len && !pr; j++) {
now = num;
sub(a[i], len - 1 - i);
sub(a[j], len - 1 - j);
add(a[i], len - 1 - j);
add(a[j], len - 1 - i);
if(now == 0) {
printf("%d %d\n", i + 1, j + 1);
pr = true;
}
}
}
if(!pr) puts("-1 -1");
}
return 0;
}
I. 程序设计:最短路
- 此题需要前置技能点:单源最短路Dij的堆优化,如果你会了Dij的堆优化,那么就可以做此题了。
- 题目要求从起点到每个点再回来的最短路径的总和。对于一个点,有:来回最短路 = 去最短路 + 回最短路
- 利用Dij可求得起点去每个点的最短路,回的最短路容易想到对每个点都用一遍Dij,但这种做法的复杂度$o(n^3)$。可以注意到,无论怎么样起点总是固定的,如若将所有的边都反向,则跑一遍Dij即可求得所有回来的最短路,如下图。
#define LL long long
const int MAXN = 6e4 + 117;
int t;
struct qnode {
int v;
LL c;
qnode(int _v = 0, LL _c = 0): v(_v), c(_c) {}
bool operator <(const qnode &r)const {
return c > r.c;
}
};
struct Edge {
int v;
LL cost;
Edge(int _v = 0, LL _cost = 0): v(_v), cost(_cost) {}
};
vector<Edge> E[2][MAXM];
bool vis[MAXN];
LL dist[2][MAXN];
void Dijstra(int flag, int n, int start) {
memset(vis, false, sizeof(vis));
for(int i = 1; i <= n; i++) dist[flag][i] = 1e18;
priority_queue<qnode> que;
while(!que.empty()) que.pop();
dist[flag][start] = 0;
que.push(qnode(start, 0));
qnode tmp;
while(!que.empty()) {
tmp = que.top();
que.pop();
int u = tmp.v;
if(vis[u]) continue;
vis[u] = true;
for(int i = 0; i < E[flag][u].size(); i++) {
int v = E[flag][tmp.v][i].v;
int cost = E[flag][u][i].cost;
if(!vis[v] && dist[flag][v] > dist[flag][u] + cost) {
dist[flag][v] = dist[flag][u] + cost;
que.push(qnode(v, dist[flag][v]));
}
}
}
}
void addedge(int flag, int u, int v, LL w) {
E[flag][u].push_back(Edge(v, w));
}
int n, m;
LL sum;
void init() {
sum = 0;
for(int i = 0; i < MAXM; i++) {
E[0][i].clear();
E[1][i].clear();
}
}
int main() {
scanf("%d", &t);
while(t--) {
init();
scanf("%d%d", &n, &m);
int u, v;
LL w;
while(m--) {
scanf("%d %d %lld", &u, &v, &w);
addedge(0, u, v, w);
addedge(1, v, u, w);
}
Dijstra(0, n, 1);
Dijstra(1, n, 1);
for(int i = 1; i <= n; i++) sum += dist[0][i] + dist[1][i];
printf("%lld\n", sum);
}
return 0;
}
J. 程序设计:迷宫
- 广搜模板题,注意以下细节即可。
- 传送门尽头是障碍物不能移动
- 传送门尽头是终点
- 传送门尽头是传送门构成链或者环
const int MAXN = 1000 + 117;
int n, m, q;
int enx, eny; //终点
int dx[4] = { -1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};
char s[MAXN][MAXN];//地图
bool gameover, f[MAXN][MAXN]; //访问标记
struct node { //传送门
int a, b;
int c, d;
} csm[117];
struct point { //点
int x, y;
int step;
} now, ne;
bool check_point(point p) {//点是否合法
if(p.x <= 0 || p.x > n) return false;
if(p.y <= 0 || p.y > m) return false;
if(s[p.x][p.y] == '*') return false;
if(f[p.x][p.y]) return false;
f[p.x][p.y] = true;
return true;
}
int check_node(point p) {//判断是否是传送门
for(int i = 0; i < q; i++)
if(p.x == csm[i].a && p.y == csm[i].b) return i;
return -1;
}
point to_node(point p, int id) {//到达传送门的尽头
p.x = csm[id].c;
p.y = csm[id].d;
if(p.x == enx && p.y == eny) {
gameover = true;
return p;
}
if(!check_point(p)) {
p.x = p.y = -1;
return p;
} else {
int node_id = check_node(p);
if(node_id != -1) return to_node(p, node_id);
return p;
}
}
void BFS() {//广搜迷宫
gameover = false;
memset(f, false, sizeof(f));
queue<point> q;
q.push({1, 1, 0});
f[1][1] = true;
while(!q.empty()) {
now = q.front();
q.pop();
int node_id = check_node(now);
if(node_id != -1) now = to_node(now, node_id);
if(now.x == enx && now.y == eny) gameover = true;
if(gameover) {
printf("%d\n", now.step);
break;
}
for(int i = 0; i < 4; i++) {
ne.x = now.x + dx[i];
ne.y = now.y + dy[i];
ne.step = now.step + 1;
if(check_point(ne)) q.push(ne);
}
}
if(!gameover) puts("No solution");
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
scanf("%d", &q);
for(int i = 0; i < q; i++)
scanf("%d%d%d%d", &csm[i].a, &csm[i].b, &csm[i].c, &csm[i].d);
scanf("%d%d", &enx, &eny);
BFS();
return 0;
}
版权属于:小影
本文链接:http://kindkidll.com/index.php/archives/15/
所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。 您可以自由的转载和修改,但请务必注明文章来源并且不可用于商业目的。