问题描述

小R有nn部电脑，每部电脑的电池容量分别为aiai​。她可以使用两种不同的充电方式来给电脑充电：

1. 普通充电：每单位时间为电脑充电xx单位的电量。
2. 闪充：每单位时间为电脑充电4x4x单位的电量。

现在，所有电脑的电量都为零。小R希望使用闪充给所有电脑充满电，计算她需要的总充电时间。请保留结果的小数点后两位。

测试样例

样例1：

输入：n = 4 ,x = 1 ,a = [2, 3, 4, 5]
输出：'3.50'

样例2：

输入：n = 3 ,x = 2 ,a = [4, 6, 8]
输出：'2.25'

样例3：

输入：n = 2 ,x = 1 ,a = [10, 5]
输出：'3.75'

代码：

string solution(int n, int x, vector<int> a) {
    int res = 0;
    for (int i = 0; i < n; i ++) res += a[i];
    double ans = 1.0 * res / (x * 4); 
    ostringstream oss;
    oss << fixed << setprecision(2) << ans;
    return oss.str();
}

解释：

1. 返回值问题：使用 ostringstream 将浮点数格式化为保留两位小数的字符串，并返回该字符串。
2. 浮点数格式化：使用 iomanip 库中的 fixed 和 setprecision 来格式化浮点数。

url: https://www.luogu.com.cn/problem/P4170

tag:
字符串，动态规划，枚举，区间DP

思路：
使用 f[i][j] 表示从i到j这个区间中如果要涂到规定的情况，最少需要的涂色次数。因为有区间，所以可以使用区间DP，对于每一各区间i到j来说如果第i个字符和第j个字符相同，则 f[i][j] 可以从 f[i][j - 1] 更新过来。如果不相同，则可以枚举这个区间中的每一个位置，将这个区间变为两个区间分别进行，由两个区间进行更新。初始状态，每个长度为1的区间，要达到规定的情况只需要涂一次就行。最后输出 f[0][n - 1] 即可。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 60;
int f[N][N];
int main()
{
    char s[60];
    cin >> s;
    int n = strlen(s);
    for (int i = 0; i < n; i ++) f[i][i] = 1;
    for (int l = 1; l < n; l ++)
    {
        for (int i = 0; i + l < n;  i++)
        {
            if (s[i] == s[i + l]) f[i][i + l] = f[i][i + l - 1];
            else
            {
                f[i][i + l] = f[i][i] + f[i + 1][i + l];
                for (int k = i + 1; k < i + l; k ++)
                    f[i][i + l] = min(f[i][i + l], f[i][k] + f[k + 1][i + l]);
            }
        }
    }
    cout << f[0][n - 1] << endl;
    return 0;
}

url: https://www.luogu.com.cn/problem/P1032

tag:
NOIP2002 提高组，字符串，bfs

思路：
因为是求最少的变换次数，所以可以用bfs。每次搜索都遍历字符串的每一个位置，将可以替换的地方都替换，然后判断是否出现过，没有出现过就加入队列。最后第一次出现字符串b的时候步数就是答案。

代码：

#include <iostream>
#include <queue>
#include <map>
#include <unordered_set>
using namespace std;

typedef pair<string, string> PSS;
typedef pair<string, int> PSI;

PSS mp[6];
string a, b;
queue<PSI> q;
unordered_set<string> st;
int idx = 0;

int bfs()
{
    q.push({a, 0});
    st.insert(a);

    while (!q.empty())
    {
        auto [current, step] = q.front(); q.pop();

        if (current == b) return step;

        if (step >= 10) continue;

        for (int i = 0; i < idx; i++)
        {
            string from = mp[i].first;
            string to = mp[i].second;
            size_t pos = current.find(from);
            while (pos != string::npos)
            {
                string newstr = current.substr(0, pos) + to + current.substr(pos + from.size());
                if (newstr.size() <= 20)
                {
                    if (!st.count(newstr))
                    {
                        st.insert(newstr);
                        q.push({newstr, step + 1});
                    }
                }
                pos = current.find(from, pos + 1);
            }
        }
    }
    return -1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> a >> b;
    string c, d;
    while (cin >> c >> d)
    {
        if (!c.empty() && idx < 6)
        {
            mp[idx++] = {c, d};
        }
    }
    int res = bfs();

    if (res != -1 && res <= 10)
        cout << res;
    else
        cout << "NO ANSWER!";

    return 0;
}

url: https://www.luogu.com.cn/problem/P7469

tag:
NOI Online 2021 提高组，字符串，哈希

思路：
用双重循环枚举每一个b中的字串，对于每一个枚举的字串，扫描一遍a，找出a中相同的子序，然后计算哈希值并存储，最后遍历结束，对哈希数组去重得出答案。

代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3010, BASE = 51971;
const long long M = 2005091020050911;
int n;
char a[N], b[N];
long long t[N * N];
int main()
{
    cin >> n >> a + 1 >> b + 1;
    for (int i = 1; i <= n ; i++)
    {
        long long v = 0; int p = 1;
        for (int j = i; j <= n; j ++)
        {
            while(p <= n && a[p] != b[j]) p ++;
            if (p > n) break;
            p ++;
            v = (1LL * v * BASE + b[j] - 'a' + 1) % M;
            t[++t[0]] = v;
        }
    }
    sort(t + 1, t + t[0] + 1);
    cout << unique(t + 1, t + t[0] + 1) - t - 1;
    return 0;
}