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;
}
叨叨几句... NOTHING