两道CF题。

CF483C

Description

构造一个长度为 $n$ 的排列，使得集合 $\{|p_i-p_{i+1}|\}$ 的大小为 $k$。$n\leq10^5$。

Solution

构造题，乱搞。

考虑大小是 $1$ 非常好构造，$1,2,3,4,…,n$。（似乎没啥用）

于是考虑构造集合中元素是 $1,2,…,k$ 的一个排列。注意到 $n$ 很大的时候可以让差全部为 $1$，所以在前面构造一下就行。

即前两个数差为 $k$，第二个和第三个差为 $k-1$，以此类推（

手算：大小是 $2$ 可以用以下方式简单构造 $1,3,2,4,5,6,…,n$，大小是 $3$ 也很简单：$1,4,2,3,5,6,…,n$。

然后构造一个 $1,k+1,2,k,3,k-1…$ 的排列就好了，具体实现还是用的差递减来构造。（话说这个构造很眼熟啊，似乎和洛谷上一道构造题的第一问很像）

Code

#include <algorithm>
#include <cstdio>
#include <iostream>
using std::cin;
using std::cout;
using std::endl;

const int maxn = 1e5 + 10;

int n, k;
int a[maxn];

int main()
{
    cin >> n >> k;
    a[1] = 1;
    int i;
    for (i = 2; k >= 1; k--, i++)
    {
        if (i & 1)
            a[i] = a[i - 1] - k;
        else
            a[i] = a[i - 1] + k;
    }
    for (; i <= n; i++)
        a[i] = i;
    for (int i = 1; i <= n; i++)
        cout << a[i] << " ";
    cout << endl;
}

CF508D

Description

给出 $n$ 个长度为 $3$ 的字符串，求一个长度为 $n+2$ 的字符串，使其所有长度为 $3$ 的子串能与给定串一一对应。$n\leq10^5$。

Solution

这个模型以前见过，只需要搞欧拉路即可。（已经当定理背下来了）

要硬说的话，会想到两种建模：每个单词作为顶点，然后在点之间连有向边，找哈密顿路。这显然不行。。。

然后就是很好的建模了，把每个字母作为点，单词作为有向边，这样就变成找欧拉路，能高效求解。。。

这个模型目前还没见到其他应用，不过也记下来，万一有用呢。。。

回到本题，把两个字符当成一个点就行。

坑点：这题有大小写字母，还有数字，注意 ASCII 码的顺序：数字<大写字母<小写字母。我懒得写正经哈希，就直接乱搞了，不注意 ASCII 码顺序就容易 RE。。。

Code

我代码又慢又丑。。。

#include <algorithm>
#include <iostream>
#include <stack>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;

const int maxn = 100000;

inline int change(char a, char b) { return (a - '0') * 100 + (b - '0'); }
inline string p(int x)
{
    string s = "  ";
    s[1] = char(x % 100 + '0');
    s[0] = char(x / 100 + '0');
    return s;
}

int rd[maxn], cd[maxn];

std::vector<int> e[maxn];
inline void add_(int x, int y) { e[x].push_back(y), rd[y]++, cd[x]++; }
inline void add(const string &x) { add_(change(x[0], x[1]), change(x[1], x[2])); }

std::stack<int> ans;

int n;

void dfs(int x)
{
    while (e[x].size())
    {
        int v = e[x].back();
        e[x].pop_back();
        dfs(v);
    }
    ans.push(x);
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        add(s);
    }
    int cnt1 = 0, cnt2 = 0, ok = 1;
    int u = -1;
    for (char c = '0'; c <= 'z'; c++)
        for (char c2 = '0'; c2 <= 'z'; c2++)
        {
            int x = change(c, c2);
            if (abs(rd[x] - cd[x]) > 1)
            {
                ok = 0;
                break;
            }
            else if (cd[x] - rd[x] == 1)
                cnt1++, u = x;
            else if (rd[x] - cd[x] == 1)
                cnt2++;
        }

    if (!(cnt1 + cnt2 == 0 || (cnt1 == 1 && cnt2 == 1)))
        ok = 0;
    if (!ok)
    {
        cout << "NO" << endl;
        return 0;
    }

    if (u != -1)
        dfs(u);
    else
    {
        for (char c = '0'; c <= 'z'; c++)
            for (char c2 = '0'; c2 <= 'z'; c2++)
                if (cd[change(c, c2)])
                    u = change(c, c2);
        dfs(u);
    }

    if (ans.size() != n + 1)
    {
        cout << "NO" << endl;
    }
    else
    {
        cout << "YES" << endl;
        cout << p(ans.top())[0] << p(ans.top())[1];
        ans.pop();
        while (!ans.empty())
        {
            cout << p(ans.top())[1];
            ans.pop();
        }
        cout << endl;
    }
}