专栏文章

NTU-GPLT 题解

ZZaoly
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mippl1sc
此快照首次捕获于
2025/12/03 15:51
3 个月前
此快照最后确认于
2025/12/03 15:51
3 个月前
查看原文

L1-1 Issho ni Bando o Kumu

Ave Mujica 在第七集隐含了重组老乐队的想法，如果这件事真的成立了，那么千早爱音（就是你的答案）就相当于打了两年的工而一无所获，这件事也点燃了很多爱音厨的怒火。
这个图片也被制成了表情包，配文字：“你怎么还在这？”
CPP
#include <iostream>
using namespace std;
int main() {
    cout<<"Chihaya Anon"<<endl;
    return 0;
}

L1-2 风暴危机

注意圆周率并没有四舍五入到 3.1415933.141593，且本题要求在六位小数，在输出时需要额外注意。
CPP
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
    int r1, r2;
    cin>>r1>>r2;
    double pi = 3.141592;
    double ans = pi * (r2 * r2 - r1 * r1);
    cout<<fixed<<setprecision(6)<<ans<<endl;
    return 0;
}

L1-3 少吃点罚时吧！

总提交次数 = 剩余失败提交次数 + 通过题数，其中题目通过就代表交了一个正确的提交。
CPP
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
using namespace std;
#define int long long
signed main()
{
    int a,b,c;
    cin>>a>>b>>c;
    cout<<2*a-b+c<<endl;
    return 0;
}

L1-4 电脑密码

由于空格的存在，本题卡 getline。并且注意有些单词之间只有标点没有空格。
Python 选手注意换行符 \r\n 和 \n 的读入区别。
若读入的单词存在大写，直接输出 55，否则按照长度模 1010 计算。
C
#include<bits/stdc++.h>
using namespace std;
int main() {
    string str;
    int flag = 0;
    getline(cin,str);
    int len = 0;
    for (char ch : str) {
        if ((ch >= 'a' && ch<='z') || (ch>='A' && ch<='Z')) {
            len++;
            if(ch<='Z')flag = 1;
        } else if (len) {
            cout << (flag? 5 : len%10);
            flag = 0;
            len = 0;
        }
    }
    if (len) {
        cout << (flag?5:len%10);
    }
    return 0;
}

L1-5 帕鲁繁育说

构建一个繁育值数组，对其进行均分后上取整，然后从头扫描一遍数组获得差距最小值即可。
CPP
#include<bits/stdc++.h>
using namespace std;
vector<int> p(1000000);
void Task(int TestCase) {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }

    int x, y;
    cin >> x >> y;

    int son = 0, diff = 1e9, bp = (p[x] + p[y] + 1) / 2;
    for (int i = 1; i <= n; i++) {
        if (abs(p[i] - bp) < diff) {
            diff = abs(p[i] - bp), son = i;
        }
    }
    cout << son << '\n';
}
int main() {
    Task(1);
    return 0;
}

L1-6 破解数字锁

暴力枚举 100100～999999 这些数字，然后带入验证，并顺序将答案输出。
CPP
#include<bits/stdc++.h>
using namespace std;
int num[6], correct[6], mis[6];
vector<int> ans;
void Task(int TestCase) {
    for(int i = 1;i<=5;i++){
        cin>>num[i];
        cin>>mis[i];
        cin>>correct[i];
    }
    for(int i = 100; i<=999; i++){
        int ge = i%10;
        int shi = (i/10)%10;
        int bai = i/100;
        if(ge==shi || shi==bai || bai==ge)continue;
        int flag = 1;
        for(int j = 1; j<=5; j++){

            int cor = 0;int mi = 0;

            if(num[j]%10 == ge)cor++;
            else if((num[j]/10)%10 == ge || (num[j]/100) == ge)mi++;

            if((num[j]/10)%10 == shi)cor++;
            else if(num[j]%10 == shi || (num[j]/100) == shi)mi++;

            if((num[j]/100) == bai)cor++;
            else if((num[j]/10)%10 == bai || num[j]%10 == bai)mi++;

            if(correct[j] != cor || mis[j] != mi)flag=0;
        }
        if(flag)
            ans.push_back(i);
    }
    cout<<ans.size()<<endl;
    for(auto i:ans)cout<<i<<endl;
}
int main() {
    Task(1);
    return 0;
}

L1-7 好好书写

有一种方法是，可以把每一个单词根据大写/下划线拆开，全部降为小写后分成一组一组地存起来。然后根据输出要求将其一组一组地更改格式并拼接即可。
CPP
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
using namespace std;
vector<string> GetWords(const string &str) {
    vector<string> res;
    string temp;
    for (char ch : str) {
        if (('A'<=ch && ch<='Z') || ch == '_') {
            if (!temp.empty()) {
                res.push_back(temp);
                temp.clear();
            }
        }
        if (ch != '_') {
            if('A'<=ch && ch<='Z')ch = ch-'A'+'a';
            temp+=ch;
        }
    }
    if (!temp.empty()) {
        res.push_back(temp);
    }
    return res;
}

string Camel(const vector<string> &words) {
    string res;
    res += words.front();
    for (int i = 1; i < words.size(); i++) {
        string word = words[i];
        word[0] = toupper(word[0]);
        res += word;
    }
    return res;
}

string Pascal(const vector<string> &words) {
    string res;
    for (string word : words) {
        word[0] = toupper(word[0]);
        res += word;
    }
    return res;
}

string Snake(const vector<string> &words) {
    string res;
    res += words.front();
    for (int i = 1; i < words.size(); i++) {
        res += "_" + words[i];
    }
    return res;
}

void Task(int TestCase) {
    int n;
    string type;
    cin >> n >> type;
    for (int i = 1; i <= n; i++) {
        string str;
        cin >> str;

        vector<string> words = GetWords(str);
        if (type == "Camel") {
            cout << Camel(words) << '\n';
        } else if (type == "Pascal") {
            cout << Pascal(words) << '\n';
        } else {
            cout << Snake(words) << '\n';
        }
    }
}
int main()
{
    Task(1);
    return 0;
}

L1-8 远离那片花田

考虑到对于不同情况应该具有不同的飞行格式，我们优先将受蛊惑的平民及其周围的地块标记 N。
由于平民周围的地块都被标记，那么未被标记的地块周围只可能存在小路和花海。
随后检查每一个地块。忽略掉所有带有 N 标记的地块，在其他地块上验证花海的个数即可。八连通搜索。
CPP
#include<bits/stdc++.h>
using namespace std;
int vertical[8] = {0,1,1,1,0,-1,-1,-1};
int horizonal[8] = {1,1,0,-1,-1,-1,0,1};
void Task(int TestCase) {
    int n,m;
    cin >> n >> m;

    vector<vector<char>> mp(n+2,vector<char>(m+2,0)), fly(n+2,vector<char>(m+2,0));
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            cin>>mp[i][j];
        }
    }

    for(int i = 0;i<=m+1;i++)mp[0][i] = mp[n+1][i] = 'R';
    for(int i = 0;i<=n+1;i++)mp[i][0] = mp[i][m+1] = 'R';

    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            if (mp[i][j] == 'P'){
                fly[i][j] = 'N';
                for(int k = 0;k<8;k++)
                    fly[i+vertical[k]][j+horizonal[k]] = 'N';
            }
        }
    }
    for(int i = 1;i<=n;i++) {
        for (int j = 1; j <= m; j++) {
            if(mp[i][j] == 'F' && fly[i][j]!='N'){
                int cnt = 0;
                for(int k = 0;k<8;k++)
                    if (mp[i+vertical[k]][j+horizonal[k]] == 'R')cnt++;
                if(cnt >= 4)fly[i][j]='H';
                else fly[i][j]='N';
            }
            if(mp[i][j] == 'R' && fly[i][j]!='N'){
                int cnt = 0;
                for(int k = 0;k<8;k++)
                    if (mp[i+vertical[k]][j+horizonal[k]] == 'R')cnt++;
                if(cnt >= 4)fly[i][j]='L';
                else fly[i][j]='H';
            }
        }
    }
    for(int i = 1;i<=n;i++) {
        for (int j = 1; j <= m; j++)
            cout << fly[i][j];
        cout << endl;
    }
}
int main() {
    Task(1);
    return 0;
}

L2-1 什么都可以变成比赛？

本题难点在于快速计算名字到字符串 Zaoly\texttt{Zaoly} 的编辑距离。要解决这个问题，我们首先考虑当字符串 bb 长度很小时，如何求任意字符串 aa 到 bb 的编辑距离。
假设我们希望对字符串 aa 进行一系列插入、删除一个字符的操作来得到字符串 bb，取其中最短的操作序列，则此序列必不包含“删除先前插入的元素”操作，因此这些操作可以任意交换顺序。不妨假设删除字符操作在前，插入字符操作在后，则进行完所有删除操作后的字符串一定是 aa 的子字符串，也一定是 bb 的子字符串（注意这里的子字符串并不要求连续，例如“Zoy\texttt{Zoy}”也是“Zaoly\texttt{Zaoly}”的子字符串）。
因此，可以枚举 bb 的所有子字符串 cc，判断 cc 是否也为 aa 的子字符串。如果是，则计算 (len⁡(a)−len⁡(c))+(len⁡(b)−len⁡(c))(\operatorname{len}(a) - \operatorname{len}(c)) + (\operatorname{len}(b) - \operatorname{len}(c)) 的结果，以最小值更新答案即可。其中，len⁡\operatorname{len} 表示字符串长度。判断任意字符串 aa 是否为另一个任意字符串 bb 的子字符串，可以用双指针技巧贪心实现。最终答案即为 aa 到 bb 的编辑距离。时间复杂度 O((len⁡(a)+len⁡(b))⋅2len⁡(b))\mathcal O \bigl( (\operatorname{len}(a) + \operatorname{len}(b)) \cdot 2^{\operatorname{len}(b)} \bigr)。
这里取 b=Zaolyb = \texttt{Zaoly}，则只需要枚举 252^5 个字符串即可。
时间复杂度 O(25⋅∑(L+5))\mathcal O \bigl( 2^5 \cdot \sum (L + 5) \bigr)，其中 55 表示字符串 Zaoly\texttt{Zaoly} 长度为 55，252^5 表示字符串 Zaoly\texttt{Zaoly} 有 252^5 个子字符串，LL 表示名字长度，∑(L+5)\sum (L + 5) 表示所有名字的 L+5L + 5 值之和。
本题也可使用动态规划（DP）技巧求解，但这就是 L3 的难度了。如果使用此方法，则时间复杂度可降至 O(5⋅∑L)\mathcal O \bigl( 5 \cdot \sum L \bigr)。
方法一：
CPP
#include <iostream>
#include <string>
#include <vector>

using namespace std;

const int INF = 16;
const string zaoly = "Zaoly";
vector<string> zaoly_sub;

bool next_choice(vector<bool>& choice, int n)
{
    for (int i = n - 1; i > -1; --i)
    {
        if (!choice[i])
        {
            choice[i] = true;
            return true;
        }
        choice[i] = false;
    }
    return false;
}

bool contain_substring(const string& a, const string& b)
{
    int j = 0;
    for (int i = 0; i < (int)a.length(); ++i)
    {
        if (j >= (int)b.length())
            break;
        if (a[i] == b[j])
            ++j;
    }
    return j >= (int)b.length();
}

int get_edit_distance(const string& name)
{
    int result = 0;
    result = INF;
    for (const string& sub : zaoly_sub)
        if (contain_substring(name, sub))
            result = min(result, (int)name.length() + (int)zaoly.length() - (int)sub.length() * 2);
    return result;
}

int main()
{
    int n = 0;
    vector<bool> choice(zaoly.length());
    do
    {
        string s;
        for (int i = 0; i < (int)zaoly.length(); ++i)
            if (choice[i])
                s.push_back(zaoly[i]);
        zaoly_sub.push_back(s);
    } while (next_choice(choice, zaoly.length()));
    cin >> n;
    for (int i = n; i > 0; --i)
    {
        int edit_distance = 0;
        string name;
        cin >> name;
        edit_distance = get_edit_distance(name);
        if (edit_distance == 0)
            cout << "Grand";
        else if (edit_distance <= 1)
            cout << "First";
        else if (edit_distance <= 3)
            cout << "Second";
        else if (edit_distance <= 6)
            cout << "Third";
        else
            cout << "Sorry";
        cout << '\n';
    }
}
方法二：
CPP
#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct Index2D
{
    Index2D(int m) : m(m) {}

    int operator()(int i, int j) const
    {
        return i * m + j;
    }

    int m;
};

const string zaoly = "Zaoly";

int get_edit_distance(const string& name)
{
    vector<int> distances((zaoly.length() + 1) * (name.length() + 1));
    Index2D idx(name.length() + 1);
    for (int i = 0; i < (int)zaoly.length(); ++i)
        distances[idx(i + 1, 0)] = i + 1;
    for (int j = 0; j < (int)name.length(); ++j)
        distances[idx(0, j + 1)] = j + 1;
    for (int i = 0; i < (int)zaoly.length(); ++i)
        for (int j = 0; j < (int)name.length(); ++j)
            if (zaoly[i] == name[j])
                distances[idx(i + 1, j + 1)] = distances[idx(i, j)];
            else
                distances[idx(i + 1, j + 1)] = min(distances[idx(i, j + 1)], distances[idx(i + 1, j)]) + 1;
    return distances[idx(zaoly.length(), name.length())];
}

int main()
{
    int n = 0;
    cin >> n;
    for (int i = n; i > 0; --i)
    {
        int edit_distance = 0;
        string name;
        cin >> name;
        edit_distance = get_edit_distance(name);
        if (edit_distance == 0)
            cout << "Grand";
        else if (edit_distance <= 1)
            cout << "First";
        else if (edit_distance <= 3)
            cout << "Second";
        else if (edit_distance <= 6)
            cout << "Third";
        else
            cout << "Sorry";
        cout << '\n';
    }
}

L2-2 编码与解码

我们将第 ii 段文本看成第 ii 号节点，那么源文件就是 11 号节点。如果有引用其他文本，则建立一条指向被引用文本的有向边。
不难发现文件可以解压，当且仅当 ii 号点出发能到达的节点集合，是一个有向无环图（DAG）。
无法解压的情况，就是图里存在环。于是我们可以 DFS 解压到这个文本时，给其标记 vis[i] = true，解压完毕 vis[i] = false。
递归解压它引用到的文本，如果中途发现引用的节点 vis 为 true 说明出现了环（本质上同，无向图找环）。
实时维护一个 string ans 用于存储已经解压的内容，一旦发现其长度超过 10610^6 则直接返回，否则最后输出 ans 即可。
这个字符串题有两个严重坑点：
  1. 空格的读入。若空格存在，应一个不落地输出。如果 cin 入一个字符串，则需要补充一个空格。
  2. 换行符的读入。题目要求 # 结尾，那么前面什么字符都可能产生。此时读入换行符需要额外注意，正确办法是每次按照字符读入，最后拼接成字符串。
CPP
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 2;
char s[10][N], ans[N * 10];
int n, len[10], tot;
bool vis[10];
void solve(int num)
{
    vis[num] = true;
    for (int i = 1; i <= len[num]; ++i)
        if (s[num][i] == '*')
        {
            i++;
            if (!vis[s[num][i] - '0'])
            {
                solve(s[num][i] - '0');
            }
            else
            {
                printf("#\n");
                exit(0);
            }
        }
        else
            ans[++tot] = s[num][i];
    if (tot > 1e6)
    {
        printf("#\n");
        exit(0);
    }
    vis[num] = false;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("\n%c", &s[i][1]);
        int j = 1;
        while (s[i][j] != '#')
            scanf("%c", &s[i][++j]);
        len[i] = j - 1;
    }
    solve(1);
    printf(ans + 1);
}

L2-3 朋友悖论

要使第 ii 个人很孤独，则 kk 必须严格大于第 ii 个人的朋友数量，且小于或等于第 ii 个人所有朋友的朋友数量的最小值。
为了求出每个人的朋友数量，可以枚举边，递增其连接的两个顶点的度数；为了求出每个人所有朋友的朋友数量的最小值，可以枚举边，用其连接的每个顶点的度数分别更新另一个顶点的“朋友的朋友数量的最小值”。
于是，对于所有第 ii 个人，我们就得到了一个区间 (Li,Ri](L_i, R_i]，表示 kk 必须满足 Li<k≤RiL_i < k \le R_i 才能让第 ii 个人很孤独。于是原问题便转化成：对于每个 k=1,2,…,Nk = 1, 2, \dots, N，求出满足 Li<k≤RiL_i < k \le R_i 的整数 ii 的个数。
但是这里区间个数可能很多，区间长度也可能很长，因此用暴力法可能超时，必须优化。一种优化的方法是，先维护差分数组，对于每个区间，在左端点加 11，右端点减 11，再用前缀和还原。
所有测试用例的总时间复杂度 O(∑(N+M))\mathcal O \bigl( \sum (N + M) \bigr)。
CPP
#include <array>
#include <iostream>
#include <vector>

using namespace std;

void min_update(int& dest, int other)
{
    if (other < dest)
        dest = other;
}

void test_case()
{
    int n = 0, m = 0;
    cin >> n >> m;
    vector<array<int, 2>> edges(m);
    for (int i = 0; i < m; ++i)
    {
        cin >> edges[i][0] >> edges[i][1];
        --edges[i][0];
        --edges[i][1];
    }
    vector<int> friend_ns(n);
    for (auto [u, v] : edges)
    {
        ++friend_ns[u];
        ++friend_ns[v];
    }
    vector<int> min_friend_ns_among_friends(n, n);
    for (auto [u, v] : edges)
    {
        min_update(min_friend_ns_among_friends[u], friend_ns[v]);
        min_update(min_friend_ns_among_friends[v], friend_ns[u]);
    }
    vector<int> friend_paradox_ns(n + 1);
    for (int i = 0; i < n; ++i)
    {
        if (min_friend_ns_among_friends[i] <= friend_ns[i])
            continue;
        ++friend_paradox_ns[friend_ns[i] + 1];
        if (min_friend_ns_among_friends[i] + 1 <= n)
            --friend_paradox_ns[min_friend_ns_among_friends[i] + 1];
    }
    for (int k = 1; k <= n; ++k)
        friend_paradox_ns[k] += friend_paradox_ns[k - 1];
    for (int k = 1; k <= n; ++k)
    {
        if (k > 1)
            cout << ' ';
        cout << friend_paradox_ns[k];
    }
    cout << '\n';
}

int main()
{
    int tests = 0;
    cin >> tests;
    while (tests > 0)
    {
        test_case();
        --tests;
    }
    return 0;
}

L2-4 证明修改器

首先，把题目转化成以下问题：
给出某程序一系列变量的声明和使用情况。规定变量在使用前必须声明，已声明的变量不能再次声明。已知程序的行为非法，但只要改动其中一个操作的变量编号，就可以把程序的行为变得合法。请给出一种修改方法，指出修改的操作编号和修改后的新变量编号。
原问题中，公理相当于变量声明；证明语句中的 Bi,1B_{i, 1} 和 Bi,2B_{i, 2} 相当于变量使用，而 Bi,3B_{i, 3} 相当于变量声明。
转化之后，我们可以得出以下结论：
  • 涉及重复声明变量的操作最多只有 22 个。如果超过 22 个，则不可能只改动一处就能修正。
  • 最多只有 11 个变量未声明即使用。如果超过 11 个，则不可能只改动一处就能修正。
然后考虑三种情况：
  • 有变量重复声明，但没有变量未声明即使用。
  • 有变量未声明即使用，但没有变量重复声明。
  • 有变量重复声明，也有变量未声明即使用。
对于有变量重复声明，但没有变量未声明即使用的情况，只要改动之后的声明操作，把声明的变量改成在整个程序中都未声明的任意变量即可。
对于有变量未声明即使用，但没有变量重复声明的情况，检查以下两个条件是否同时满足：
  • 在第一个未声明的使用操作之前有声明操作，满足其声明的变量在整个程序中都未使用过。
  • 未声明即使用的变量在整个程序中都未声明。
如果有，则改动那个声明操作，把声明的变量改成未声明即使用的变量即可。如果没有，则说明未声明的使用操作只有一个（否则无法只改动一处就修正），把未声明即使用的变量改成先前已声明的任意变量即可（注意要满足原问题的要求“Bi,1B_{i, 1}、Bi,2B_{i, 2}、Bi,3B_{i, 3} 互不相等”，如果跟同一个语句的另一个前提冲突了，就要换一个）。
对于有变量重复声明，也有变量未声明即使用的情况，选择其中一个声明操作，把声明的变量改成未声明即使用的变量即可。选择哪个操作来改呢？如果在两个声明操作之间没有未声明的使用操作，则选择后一个操作即可。如果有，则不能选后一个，否则有变量未声明即使用的问题仍未解决；但又必须选一个（否则无法只改动一处就修正），就只能选前一个了。
最后，把结论转化回原问题的结论即可。
时间复杂度 O(N+M)\mathcal O(N + M)。
CPP
#include <array>
#include <iostream>
#include <vector>

using namespace std;

const int V_MAX = 100'000;

bool proved[V_MAX], used[V_MAX];

int main()
{
    int n = 0, m = 0, rp = 0, uwp = 0, uwp_j = 0;
    /*
       rp = repeated proof
       uwp = use without proof
    */
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        --a[i];
    }
    cin >> m;
    vector<array<int, 3>> b(m);
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < 3; ++j)
        {
            cin >> b[i][j];
            --b[i][j];
        }
    rp = -1;
    uwp = -1;
    for (int i = 0; i < n; ++i)
        proved[a[i]] = true;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < 3; ++j)
            if (j < 2)
            {
                if (!proved[b[i][j]])
                {
                    uwp = i;
                    uwp_j = j;
                }
                else
                    used[b[i][j]] = true;
            }
            else
            {
                if (proved[b[i][j]])
                    rp = i;
                else
                    proved[b[i][j]] = true;
            }
    if (rp != -1 && uwp == -1)
    {
        int unproved = 0;
        for (unproved = 0; unproved < V_MAX; ++unproved)
            if (!proved[unproved])
                break;
        cout << rp + 1 << " 3 " << unproved + 1;
    }
    else if (rp == -1 && uwp != -1)
    {
        int pwu = 0; // pwu = proof without use
        for (pwu = 0; pwu < uwp; ++pwu)
            if (proved[b[pwu][2]] && !used[b[pwu][2]])
                break;
        if (pwu < uwp && !proved[b[uwp][uwp_j]])
            cout << pwu + 1 << " 3 " << b[uwp][uwp_j] + 1;
        else
        {
            cout << uwp + 1 << ' ' << uwp_j + 1 << ' ';
            if (a[0] != b[uwp][1 - uwp_j])
                cout << a[0] + 1;
            else
                cout << a[1] + 1;
        }
    }
    else
    {
        int pp = 0; // pp = previous proof
        bool pu = false; // pu = previously used
        for (pp = 0; pp < rp; ++pp)
            if (b[pp][2] == b[rp][2])
                break;
        for (int i = pp + 1; i <= rp; ++i)
            if (b[i][0] == b[uwp][uwp_j] || b[i][1] == b[uwp][uwp_j])
            {
                pu = true;
                break;
            }
        if (!pu)
            cout << rp + 1;
        else
            cout << pp + 1;
        cout << " 3 " << b[uwp][uwp_j] + 1;
    }
    cout << '\n';
}

L3-1 最小大小数

注意到原数也是原数的一个“大小数”，所以答案一定不会超过原数。又因为原数不超过 1018−110^{18} - 1，小于 263−12^{63} - 1，所以可以放心使用 6464 位有符号整数存储和计算。
若直接枚举，则所有测试用例的时间复杂度是 O(T⋅2N)\mathcal O \bigl( T \cdot 2^N \bigr)，会超时，因此考虑使用动态规划（DP）技巧求解。
令 dpi\textit{dp}_i 表示只取十进制数字串 AA 最低 ii 位 Ai−1…A0‾\overline{A_{i - 1} \dots A_0} 时本题的答案。显然，dp1=A0\textit{dp}_1 = A_0。
当 i≥2i \ge 2 时，有
dpi≔min⁡{Ai−1…A0‾,min⁡j∈{0,1,…,i−2}k∈{j+1,j+2,…,i−1}{Ai−1…Ak‾Ak−1…Aj‾⋅dpj}}\textit{dp}_i \coloneqq \min \left\{ \begin {aligned} & \overline {A_{i - 1} \dots A_0}, \\ & \min_{\begin {aligned} \scriptstyle j & \scriptstyle \in \{ 0, 1, \dots, i - 2 \} \\ \scriptstyle k & \scriptstyle \in \{ j + 1, j + 2, \dots, i - 1 \} \end {aligned}} \biggl\{ \overline {A_{i - 1} \dots A_k}^{\overline {A_{k - 1} \dots A_j}} \cdot \textit{dp}_j \biggr\} \end {aligned} \right\}
其中，第一项 Ai−1…A0‾\overline{A_{i - 1} \dots A_0} 表示不进行“大小数变换”的情况；第二项表示进行“大小数变换”的情况，此时枚举从最高位到最低位看第一个指数出现在哪几位。计算第二项时，枚举整数 jj 和 kk（0≤j<k≤i−10 \le j < k \le i - 1），考虑第 kk 到 i−1i - 1 位上的数都不上移，而第 jj 到 k−1k - 1 位上的数都上移的情况，此时第 00 到 j−1j - 1 位可以用先前计算出的 dpj\textit{dp}_j 替代。
需要注意整数的乘法和乘方运算不要溢出。如果计算结果会超过原数，则应中止计算。
所有测试用例的总时间复杂度 O(∑N3)\mathcal O \bigl( \sum N^3 \bigr)，可以通过本题。
如果想要进一步优化运行时间，则需要更深的观察。注意到，表达式中不能出现底数和指数都至少为三位数的情况，否则计算出的结果必然超过原数。也就是说，底数和指数至少有一个不超过两位数。因此，只需枚举以下两种情况即可：
  • 一种是底数不超过两位数，即 0≤j≤i−20 \le j \le i - 2，max⁡(j+1,i−2)≤k≤i−1\max(j + 1, i - 2) \le k \le i - 1 的情况；
  • 另一种是指数不超过两位数，即 0≤j≤i−20 \le j \le i - 2，j+1≤k≤min⁡(j+2,i−1)j + 1 \le k \le \min(j + 2, i - 1) 的情况。
如果使用此方法，则所有测试用例的总时间复杂度可降至 O(∑N2)\mathcal O \bigl( \sum N^2 \bigr)。
方法一：
CPP
#include <iostream>
#include <string>
#include <vector>

using namespace std;
using LL = long long;

const LL INF = 1'000'000'000'000'000'000;

LL concat_integer(const vector<LL>& a, LL from, LL to)
{
    LL mult = 0, result = 0;
    mult = 1;
    for (LL i = from; i < to; ++i)
    {
        result += a[i] * mult;
        mult *= 10;
    }
    return result;
}

LL powi(LL base, LL exp)
{
    LL result = 0;
    if (base <= 1)
        return base;
    result = 1;
    while (exp > 0)
    {
        if (result >= INF / base)
            return INF;
        result *= base;
        --exp;
    }
    return result;
}

LL multiply(LL x, LL y)
{
    if (x >= INF / y)
        return INF;
    return x * y;
}

void min_update(LL& target, LL value)
{
    if (value < target)
        target = value;
}

void test_case()
{
    LL n = 0;
    cin >> n;
    string a_str;
    cin >> a_str;
    vector<LL> a(n);
    for (LL i = 0; i < n; ++i)
        a[i] = a_str[n - i - 1] - '0';
    vector<LL> dp(n + 1);
    dp[0] = 1;
    for (LL i = 1; i <= n; ++i)
    {
        dp[i] = concat_integer(a, 0, i);
        for (LL from = 0; from <= i - 2; ++from)
            for (LL to = from + 1; to <= i - 1; ++to)
                min_update(dp[i], multiply(powi(concat_integer(a, to, i), concat_integer(a, from, to)), dp[from]));
    }
    cout << dp[n] << '\n';
}

int main()
{
    LL tests = 0;
    cin >> tests;
    while (tests > 0)
    {
        test_case();
        --tests;
    }
}
方法二：
CPP
#include <iostream>
#include <string>
#include <vector>

using namespace std;
using LL = long long;

const LL INF = 1'000'000'000'000'000'000;

LL concat_integer(const vector<LL>& a, LL from, LL to)
{
    LL mult = 0, result = 0;
    mult = 1;
    for (LL i = from; i < to; ++i)
    {
        result += a[i] * mult;
        mult *= 10;
    }
    return result;
}

LL powi(LL base, LL exp)
{
    LL result = 0;
    if (base <= 1)
        return base;
    result = 1;
    while (exp > 0)
    {
        if (result >= INF / base)
            return INF;
        result *= base;
        --exp;
    }
    return result;
}

LL multiply(LL x, LL y)
{
    if (x >= INF / y)
        return INF;
    return x * y;
}

void min_update(LL& target, LL value)
{
    if (value < target)
        target = value;
}

void test_case()
{
    LL n = 0;
    cin >> n;
    string a_str;
    cin >> a_str;
    vector<LL> a(n);
    for (LL i = 0; i < n; ++i)
        a[i] = a_str[n - i - 1] - '0';
    vector<LL> dp(n + 1);
    dp[0] = 1;
    for (LL i = 1; i <= n; ++i)
    {
        dp[i] = concat_integer(a, 0, i);
        for (LL from = 0; from <= i - 2; ++from)
            for (LL to = max(from + 1, i - 2); to <= i - 1; ++to)
                min_update(dp[i], multiply(powi(concat_integer(a, to, i), concat_integer(a, from, to)), dp[from]));
        for (LL from = 0; from <= i - 2; ++from)
            for (LL to = from + 1; to <= min(i - 1, from + 2); ++to)
                min_update(dp[i], multiply(powi(concat_integer(a, to, i), concat_integer(a, from, to)), dp[from]));
    }
    cout << dp[n] << '\n';
}

int main()
{
    LL tests = 0;
    cin >> tests;
    while (tests > 0)
    {
        test_case();
        --tests;
    }
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...