AtCoder Beginner Contest 237（C-E)

AtCoder Beginner Contest 237（C-E)

C - kasaka

题意：给定字符串S，询问是否在S串前任意个(可以是0个)字符‘a’是的新生成的S是个回文串

题解： 在S串前添加字符’a’使得S串最前面连续的a等于S串最后面连续的，然后check这个字符串是否为回文串就行。

AC代码：

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
typedef long long ll;

int main()
{    
    string s;
    cin >> s;
    int cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < s.size(); i ++ )
        if (s[i] == 'a') cnt1 ++;
        else break;
    
    for (int i = s.size() - 1; i >= 0; i -- )
        if (s[i] == 'a') cnt2 ++;
        else break;
    if (cnt1 == s.size())
    {
        puts("Yes");
        return 0;
    }
    int x = cnt2 - cnt1;
    if (x < 0) puts("No");
    else 
    {
        bool flag = true;
        for (int i = 0; i < (s.size() - x); i ++ )
        {
            if (s[i] != s[s.size() - 1 - x - i]) flag = false;
        }
        if (flag) puts("Yes");
        else puts("No");
    }
    return 0;
}

D - LR insertion（dfs）

题意：给定一个仅包含‘L’和’R’的长度为n的字符串。起初数组a中只有0，然后插入数字1~n到数组a中去，如果s[i] = L, 则表示将i插入到i - 1的左边，否者就插入到i - 1的右边，输出最终的a数组。

题解：根据题意我们可以发现对于当前的数i而言, 如果i左边没有数字就可以直接输出数字i，如果i左边有数字就得先输出i左边的数字，然后再对i左边的数再次进行上述 *** 作，这个过程可以用dfs来写。

AC代码：

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
char s[N];
bool ve[N][2];

void dfs(int x)
{
    if (ve[x][0]) dfs(x + 1);    // 左边有数字得先处理左边
    printf("%d ", x);
    if (ve[x][1]) dfs(x + 1);
}

int main()
{    
    int n;
    scanf("%d", &n);
    scanf("%s", s + 1);
    for (int i = 1; i <= n; i ++ )
    {
        if (s[i] == 'L') ve[i - 1][0] = true;
        else ve[i - 1][1] = true;
    }
    dfs(0);
    return 0;
}

E - Skiing（spfa)

题意：给定n个点和m条边以及这n个点的高度，对于从u点到v点，如果u点的高度大于等于v点的，则可以获得幸福值h[u]-h[v]，否者减少2 * (h[v] - h[u])的幸福值，求1号点出发能够获得的最大幸福值。

题解：可以将经过u->v获得的幸福值转化为u->v这条边的边权，这样这个问题就转化为从1出发能走的最长的路是多少，因为涉及到负权，因此迪杰斯特拉行不通，所以可以使用spfa来解决，并且这里是不会出现正环，在这里一个环肯定是为负的。

AC代码：

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
typedef long long ll;
typedef pair PII;
const int N = 2e5 + 10;
const ll INF = 1e18;
vector ve[N];
PII g[N];
int h[N];
bool st[N];
ll dist[N];

void spfa(int n)
{
    for (int i = 1; i <= n; i ++ ) dist[i] = -INF;
    queue p;
    p.push(1);
    st[1] = true;
    dist[1] = 0;
    while (p.size())
    {
        int x = p.front();
        p.pop();
        st[x] = false;
        for (int i = 0; i < ve[x].size(); i ++ )
        {
            int y = ve[x][i].first, val = ve[x][i].second;
            if (dist[y] < dist[x] + val)
            {
                dist[y] = dist[x] + val;
                if (!st[y])
                {
                    p.push(y);
                    st[y] = true;
                }
            }
        }
    }
    ll ans = -INF;
    for (int i = 1; i <= n; i ++ )
    {
        ans = max(ans, dist[i]);
    }
    printf("%lldn", ans);
    return;
}

int main()
{    
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);

    for (int i = 1; i <= m; i ++ )
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if (x == y) continue;
        ve[x].push_back({y, h[x] > h[y] ? (h[x] - h[y]) : (2 * (h[x] - h[y]))});  // 转化边权
        ve[y].push_back({x, h[y] > h[x] ? (h[y] - h[x]) : (2 * (h[y] - h[x]))});
    }
    spfa(n);
    return 0;
}

F - |LIS| = 3 （待明年补）
…

过年了，祝大家新年快乐！！！！

完结，如有错误，还请指正，感谢！！！