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；
}