A 小红的签到题
签到
代码:
#include<bits/stdc++.h> using namespace std; int main(){ int a,b,c; cin>>a>>b>>c; if(b * a <c){ printf("%d", b); } else{ printf("%d", c / a); } return 0; }
B 小红的ABC
题目大意:
找一组由 a,b,c 组成的字符串的最短回文子串的长度,没有输出-1
数据范围: 字符串长度不小于2,且不超过100
题解:
数据范围很小,直接暴力就行了
我这里分两层循环遍历,每次判断 i - j 中间的子串是不是回文数,
代码:
#include<bits/stdc++.h> using namespace std; int main(){ string k; cin>>k; int n = k.length(); int ans = 0x3f3f3f3f; for(int i = 0; i < n; i++){ for(int j = i + 1; j < n; j++){ int p1 = i; int p2 = j; int flag = 1; while(p1 < p2){ if(k[p1] != k[p2]){ flag = 0; break; } p1++; p2--; } if(flag){ ans = min(ans, j - i + 1); } } } if(ans == 0x3f3f3f3f){ printf("-1"); } else { printf("%d", ans); } return 0; }
C 小红的口罩
题目大意:
给出一个数组,和一个最大值,要求将数组的数相加,求出最多可以加多少次而不大于最大值。其中,每一个数被使用一次之后自己就会乘2。
题解:
优先队列,每次取出最小的数,然后把他的两倍插进去就行了。
代码:
#include<bits/stdc++.h> using namespace std; priority_queue<int, vector<int>, greater<int> > q; int main(){ int n,k; cin>>n>>k; long long now = 0; long long ans = 0; for(int i = 0; i < n; i++){ int x; scanf("%d", &x); q.push(x); } while(now < k){ int f = q.top(); q.pop(); now += f; q.push(f * 2); ans++; } printf("%lld", ans - 1); return 0; }
D 小红的数组
不会做,摆烂了=w=(等会了再填坑)
题目大意:
长度为 n 的正整数数组,给出一个k,要求求出所有的方案的数,分别让两个数字里的数相乘大于,等于,小于k。
题解:
先排序,
然后从0- n-1遍历,先用k除第i个数,然后二分查找出交界处。
二分太细节了,整了半天= =
下面是求了两个,然后用排列组合C^{2}_{n}
求总数然后减掉(因为第三个怎么搞都不对= =)
代码:
#include<bits/stdc++.h>
using namespace std;
long long nums[300005];
int main() {
long long n;
long long k;
scanf("%lld %lld", &n, &k);
for (int i = 0; i != n; i++) {
scanf("%lld", &nums[i]);
}
sort(nums, nums + n);
long long ans1 = 0, ans2 = 0;
for (int i = 0; i != n - 1; i++) {
long long kk = k / nums[i];
long long p1 = upper_bound(nums + i + 1, nums + n, kk) - nums;
long long p2 = lower_bound(nums + i + 1, nums + n, kk) - nums;
if (k % nums[i] == 0) {
ans1 += p1 - p2;
}
ans2 += n - p1;
}
printf("%lld %lld %lld\n", ans2, ans1, ((n * n - n) / 2) - ans1 - ans2);
return 0;
}
E 小红的rpg游戏
题目大意:
难以描述,直接引用原文得了。
小红正在玩一个游戏。游戏的地图是一个n*m的迷宫,迷宫有墙和道路,道路上可能会有一些怪物。
小红初始的血量是 h ,每当小红经过一个有怪物的道路时,小红就会和怪物战斗,击杀怪物并且消耗自己的血量。小红消耗的血量等同于该怪物的战斗力。请注意,如果小红血量为0则死亡。因此只有当小红当前血量大于怪物的战斗力时才可经过该点。
地图共有以下几种标识:
'.' 代表道路,小红可以经过。
'*' 代表墙体,小红不能经过。
'1'~'9' 数字,代表该位置是个道路,且上面有一个战斗力为该数字的怪物。
小红只可以上下左右四个方向移动。
小红想知道,自己从左上角到右下角的最短行走路线的距离是多少?
数据范围: 2≤n,m,h≤50
题解:
dfs+记忆直接做,血量就是vis多加一个参数就好了。
代码:
#include<bits/stdc++.h> using namespace std; const int dx[] = {-1,0,0,1}; const int dy[] = {0,-1,1,0}; queue<pair<int,int> > q; char mp[60][60]; int vis[60][60][60]; int n,m,h; int ans = 0x3f3f3f3f; void dfs(int xx, int yy, int bl, int fs){ vis[xx][yy][bl] = fs; if(xx == n && yy == m){ ans = min(ans, fs); return; } for(int i = 0; i < 4; i++){ int u = xx + dx[i]; int v = yy + dy[i]; if(u < 1 || u > n || v < 1 || v > m) continue; if(mp[u][v] == '*') continue; if(vis[u][v][bl] < fs && vis[u][v][bl] != -1) continue; vis[u][v][bl] = fs; if(mp[u][v] == '.'){ dfs(u,v, bl, fs + 1); continue; } int z = mp[u][v] - '0'; if(bl > z){ dfs(u, v, bl - z, fs + 1); } } return; } int main(){ memset(vis , -1, sizeof(vis)); cin>>n>>m>>h; char o; for(int i = 1; i <= n; i++){ scanf("%c", &o); for(int j = 1; j <= m; j++){ scanf("%c", &mp[i][j]); } } dfs(1,1, h, 0); if(ans == 0x3f3f3f3f){ printf("-1"); } else { printf("%d", ans); } return 0; }