A-乘积最大

题意

给定一个数字字符串，把字符串分成`K+1`个数，使这些数乘积最大。

分析

本题最佳解法应该是区间dp但本蒟蒻不会dp。只能暴力dfs了。
在串中插入*其性质和排列类似。可以参考蓝书P15递归实现排列型枚举。
对于在第i个位置插入*分成i之前的为一段，及i和i之后一段。

需要注意在数字相连时的边界情况。

AC代码

#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
const int maxn = 50;
string a;
int n, k;
int vis[maxn];
ll s[maxn];
ll ans = -1;

void dfs(int x) {
    if (x == k) {
        ll x = 1;
        int t = 0;
        memset(s, 0, sizeof(s));
        s[t] = a[0] - 48;
        for (int i = 1; i < n; i++) {
            if (vis[i - 1]) {
                s[++t] = (a[i] - '0');
            } else {
                s[t] = s[t] * 10 + (a[i] - '0');
            }
        }
        for (int i = 0; i <= t; i++) {
            x *= s[i];
        }
        ans = max(ans, x);
        return;
    }
    for (int i = 0; i < n - 1; i++) {
        if (vis[i])
            continue;
        vis[i] = 1;
        dfs(x + 1);
        vis[i] = 0;
    }
}

int main(void) {
    FAST_IO;
    cin >> n >> k;
    cin >> a;
    dfs(0);
    cout << ans << endl;
    return 0;
}

C-单词接龙

题目链接

题意

给定一个字符和一些字符串，按照字符串之间重叠的部分，连接字符串，求最长的连接长度。

分析

比较经典的DFS+字符串，比较考察细节，比如字符串的模拟操作、dfs回溯的处理。
有两种基本的思路：

对于字符串，本题数据较少，可以搜索时暴力处理。使用C++的string比较方便，但仍需要注意边界细节。(我写的时候在substr上调了好久，emmmm)
比较好的做法可以先预处理一个 $num$ 数组，其中 $num[i][j]$ 表示串i和串j之间可以连接的字符数。在DFS的时候使用 $num[i][j]$ 进行回溯等操作。

AC代码

方法1(string暴力)

#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;

int const maxn = 50;
int vis[maxn];
vector<string> v_str;
int ans = 0;

void dfs(string &s) {
    int flag = 0;
    for (int i = 0; i < (int)v_str.size(); i++) {
        if (vis[i] >= 2) continue;
        string &ts = v_str[i];
        int n = 0;
        int len1 = (int)s.length();
        int len2 = (int)ts.length();

        for (int j = 0; j < min(len1, len2); j++) {
            if (ts.substr(0, j + 1) == s.substr(len1 - j - 1)) {
                flag = 1;
                n = j + 1;
                break;
            }
        }
        if (n) {
            vis[i]++;
            auto temp = s;
            s = s + ts.substr(n);
            dfs(s);
            s = temp;
            vis[i]--;
        }
    }
    if (!flag) {
        ans = max((int)s.length(), ans);
    }
}

int main(void) {
    FAST_IO;
    int n;

    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        v_str.push_back(s);
    }    
    string s;
    cin >> s;
    dfs(s);
    cout << ans << endl;
    return 0;
}

方法2(预处理字符数)

#include <bits/stdc++.h>
using namespace std;

int n;
string dc[25];
int cd[25][25];
int cs[25];

int mincd(int x,int y)
{
    bool p=true;
    int ky=0;
    for(int k=dc[x].size()-1;k>=0;k--)
    {
        for(int kx=k;kx<dc[x].size();kx++)
        if(dc[x][kx]!=dc[y][ky++])
        {
            p=false;
            break;
        }

        if(p==true)
        return dc[x].size()-k;

        ky=0;
        p=true;
    }
    return 0;
}

char sta;
int ans=0;
int mans=0;

void dfs(int p)
{
    bool jx=false;
    for(int i=1;i<=n;i++)
    {
        if(cs[i]>=2) continue;
        if(cd[p][i]==0) continue;
        if(cd[p][i]==dc[p].size() || cd[p][i]==dc[i].size()) continue;
        mans+=dc[i].size()-cd[p][i];
        cs[i]++;
        jx=true;
        dfs(i);   //接上
        mans-=dc[i].size()-cd[p][i];   //回溯
        cs[i]--;
    }
    if(jx==false)  
    ans=max(ans,mans);

    return ;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>dc[i];

    cin>>sta;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    cd[i][j]=mincd(i,j);

    for(int i=1;i<=n;i++){
        if(dc[i][0]==sta){
            cs[i]++;
            mans=dc[i].size();
            dfs(i);
            cs[i]=0;
        }
    }
    cout<<ans<<endl;
    return 0;
}

D-Cow Line

题目链接

题意

有一些人排队，允许进行以下四种操作：

A L ----- 从左边插入一人
A R ----- 从右边插入一人
D L N ----- 从左边走出N人
D R N ----- 从右边走出N人

问最后队伍中的序号。

分析

用双端队列 $deque$ 模拟入队出队，即可。复杂度 $O(N)$

AC代码

#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
deque<int> q;

int main(void) {
    FAST_IO;
    int n;
    cin >> n;
    string opt, dir;
    int num = 0, k;
    while (n--) {
        cin >> opt >> dir;
        if (opt == "A") {
            if (dir == "L") {
                q.push_front(++num);
            } else {
                q.push_back(++num);
            }
        } else {
            cin >> k;
            if (dir == "L") {
                for (int i = 0; i < k && !q.empty(); i++)
                    q.pop_front();
            } else {
                for (int i = 0; i < k && !q.empty(); i++)
                    q.pop_back();
            }
        }
    }
    while (!q.empty()) {
        cout << q.front() << endl;
        q.pop_front();
    }
    return 0;
}

G-Cow Digit Game

题目链接

分析

好像是道SG函数的博弈裸题，队友说套一下SG函数就好了。直接上代码吧。

AC代码

#include <bits/stdc++.h>
using namespace std;
int g, n;
bool sg[1000005];

int main()
{
    for(int i = 1; i <= 9; i++)
        sg[i] = true;

    for(int i = 10; i <= 1000000; i++)
    {
        int ma = 0, mi = 10, t = i;
        while(t)
        {
            int x = t % 10;
            if(x) mi = min(mi, x);
            ma = max(ma, x);
            t /= 10;
        }
        if(sg[i - ma] && sg[i - mi])
            sg[i] = false;
        else
            sg[i] = true;
    }

    cin >> g;
    for(int i = 0; i < g; i++)
    {
        cin >> n;
        if (sg[n]) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

I-旅行家的预算

题目链接

分析

一道操作比较繁琐的贪心+模拟。可以转换区间贪心。加入起点与终点共n+2个站点。
若当前在点i则需要考虑若在当前站点加多少油可以到达下一个便宜的站点。如果无法到达下一个便宜的站，那就需要加满油。

复杂度 $O(N^2)$

本题的N超级小。。

AC代码

#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;

int const maxn = 20;
struct node {
    double d, p;
    bool operator<(const node &obj) const {
        if (d == obj.d)
            return p < obj.p;
        return d < obj.d;
    }
}D[maxn];

int main(void) {
    FAST_IO;
    int n;
    double d, c, cd, p;

    cin >> d >> c >> cd >> p  >> n;
    D[0].p = p;
    for (int i = 1; i <= n; i++) {
        cin >> D[i].d >> D[i].p;
    }
    D[n + 1].d = d;
    D[n + 1].p = 0;
    sort(D + 1, D + 1 + n);
    double total = 0, oil = 0, x = 0;
    for (int i = 0; i <= n + 1; i++) {
        oil -= (D[i].d - x) / cd;//当前剩余的油量
        if (oil < 0) {
            total = -1;
            break;
        }
        int j = i + 1;
        while (D[j].p > D[i].p && j <= n) {//寻找比当前要便宜的站点
            j++;
        }
        double need = (D[j].d - D[i].d) / cd;
        need = min(c, need);
        double add = need - oil;
        if (add > 0) {
            total += add * D[i].p;
            oil += add;
        }
        x = D[i].d;
    }
    if (total == -1) {
        cout << "No Solution" << endl;
    } else {
        cout << fixed << setprecision(2) << total << endl;
    }

    return 0;
}

K-Hide and Seek

题目链接

题意

奶牛贝西和农夫约翰（FJ）玩捉迷藏，现在有N个谷仓，FJ开始在第一个谷仓，贝西为了不让FJ找到她，当然要藏在距离第一个谷仓最远的那个谷仓了。现在告诉你N个谷仓，和M个两两谷仓间的“无向边”。每两个仓谷间当然会有最短路径，现在要求距离第一个谷仓（FJ那里）最远的谷仓是哪个（所谓最远就是距离第一个谷仓最大的最短路径）？如有多个则输出编号最小的。以及求这最远距离是多少，和有几个这样的谷仓距离第一个谷仓那么远。

分析

只要求出1-N的单源最短路，遍历找出最大值就可。因为本题所有边的边权全是1，所以只要从1开始bfs遍历图就行了。复杂度O(N+M).

    // C++的STL里有一些直接的简单算法可用（以下算法复杂度均为O(N)）：
    //头文件 algorithm
    max_element(begin(), end(), cmp);  //找到序列最大值，返回其指针
    min_element(begin(), end(), cmp); //找到序列最小值，返回其指针
    count(begin(), end(), value) //统计序列中为value值的个数

AC 代码

#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
int const maxn = 50000 + 10;
struct node {
    int v, next;
}e[maxn << 1];
int head[maxn], cnt;
int dis[maxn], vis[maxn];
void add(int u, int v) {
    e[cnt].v = v;
    e[cnt].next = head[u];
    head[u] = cnt++;
}

void bfs() {
    queue<pair<int, int>> q;
    dis[1] = 0;
    vis[1] = 1;
    q.push(make_pair(1, 0));
    while (!q.empty()) {
        auto x = q.front();
        q.pop();
        int u = x.first;
        dis[u] = x.second;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].v;
            if (vis[v]) continue;
            vis[v] = 1;
            q.push(make_pair(v, x.second + 1));
        }
    }
}

int main(void) {
    FAST_IO;
    memset(head, -1, sizeof(head));
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >>v;
        add(u, v);
        add(v, u);
    }
    bfs();
    int mx = *max_element(dis + 1, dis + 1 + n);
    int cont = count(dis + 1, dis + 1 + n, mx);
    int p = 0;
    for (int i = 1; i <= n; i++) {
        if (dis[i] == mx) {
            p = i;
            break;
        }
    }
    cout << p << " " << mx << " " << cont << endl;

    return 0;
}

L-回文数

题目链接

分析

模拟N进制加法，并判断回文。

AC代码

#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
int n;

string clac(string a) {
    string ans, b(a);
    reverse(b.begin(), b.end());
    ans.resize(a.length());
    int d = 0;
    for (int i = a.length() - 1; i >= 0; i--) {
        int x, y;
        if (isdigit(a[i])) {
            x = a[i] - '0';
        } else {
            x = a[i] - 'A' + 10;
        }
        if (isdigit(b[i])) {
            y = b[i] - '0';
        } else {
            y = b[i] - 'A' + 10;
        }
        int c = (x + y + d) % n;
        if (c < 10)
            ans[i] = c + '0';
        else {
            ans[i] = c - 10 + 'A';
        }
        d = (x + y + d) / n;
    }
    if (d > 0)
        ans.insert(ans.begin(), d < 10 ? d + '0' : d - 10 + 'A');
    return ans;
}

bool ok(string &s) {
    int len = (int)s.length();

    for (int i = 0; i < len / 2; i++) {
        if (s[i] != s[len - 1 - i]) {
            return false;   
        }
    }
    return true;
}

int main(void) {
    FAST_IO;
    string m;
    cin >> n >> m;
    int ans = 0;
    while (!ok(m)) {
        m = clac(m);
        ans++;
        if (ans > 30) {
            cout << "Impossible!" << endl;
            break;
        }
    }
    if (ans <= 30) cout << "STEP=" << ans << endl;

    return 0;
}

牛客假日团队赛9-部分题解

A-乘积最大

题意

分析

AC代码

C-单词接龙

题意

分析

AC代码

方法1(string暴力)

方法2(预处理字符数)

D-Cow Line

题意

分析

AC代码

G-Cow Digit Game

分析

AC代码

I-旅行家的预算

分析

AC代码

K-Hide and Seek

题意

分析

AC 代码

L-回文数

分析

AC代码