2022-11-8总结

环

Description

对于一个长度为 $n$ 的 $01$ 串，下标从 $0$ 到 $n-1$ 。定义两种类型的操作：

A类型：选择一个 $x$，将序列循环右移 $x$ 位，也就是新序列的第 $(i+x) \bmod n$ 位对应原序列的第 $i$ 位。

B类型：选择一个 $x$ ，满足序列的第 $x$ 个位置位 $1$ ，且第 $(x+1) \bmod n$ 位不为 $1$ ，交换序列的第 $x$ 个位置和第 $(x+1) \bmod n$ 个位置的字符。

给定 $n,k,l$ 。请构造一个由 $l$ 个长度为 $n$ 的 $01$ 串构成的序列 $S$，下标从 $0$ 开始。使得序列中每个串恰好有 $k$ 个 $1$ 。且对于 $0 \le i < l-1$，$S_i$ 既可以通过一次A类型的操作，也可以通过一次B类型的操作，变为 $S_{i+1}$。

Input

第一行一个整数 $T$ 表示数据组数。

接下来 $T$ 行，每行三个整数 $n,k,l$。

Output

对于每组数据，如果无解输出"NO",有解输出一行"YES"，并输出 $l$ 行描述序列 $S$。多解任意输出一组。

Hint

$2 \le n,l \le 100$, $0 \le k \le n$, $1 \le T \le 10$。

Solution

首先，容易证明当 $k$ 与 $n$ 不互质时无解。 设 $S_i$ 中所有 $1$ 的位置的下标之和为 $W_i$ ，假设 $S_i$ 能够通过循环移位得到 $S_{i+1}$ ，那么必然存在整数 $x$ ，使得 $W_i+xk \equiv W_{i+1} \pmod n$ 。同时如果 $S_i$ 能够通过将一个 $1$ 右移一位得到 ，那么有 $W_i+1 \equiv W_{i+1} \pmod n$ ，由两式可以得到 $xk \equiv 1 \pmod n$ ，所以 $n, k$ 互质是解存在的必要条件。

当 $k$ 与 $n$ 互质时，容易给出一种构造。 因为 $k$ 与 $n$ 互质，所以 $k$ 一定存在模 $n$ 意义下的逆元，令 $S_0$ 的 $\frac{0}{k}, \frac{1}{k}, \cdots, \frac{k-1}{k}$ 位置处（这里和后面的位置均是指在模 $n$ 意义下）为 $1$ ，其余处为 $0$ 。同样的对于 $S_i$ ，我们令其 $\frac{i}{k}, \frac{i+1}{k}, \cdots, \frac{k+i-1}{k}$ 处为 $1$ ，其余处为 $0$ 。显然，从 $S_i$ 变成 $S_{i+1}$ 可以通过向右循环移位 $\frac{1}{k}$ 实现，同时发现 $\frac{i}{k} + 1 = \frac{k+(i+1)-1}{k}$ ，于是我们将 $S_i$ 的 $\frac{i}{k}$ 位置变成 $0$ ，将 $\frac{i}{k}+1$ 位置变成 $1$，即可用 $b$ 操作将 $S_i$ 变成 $S_{i+1}$ 。

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

int exgcd(int a, int b, int &x, int &y)
{
    if(!b) return x = 1, y = 0, a;
    int d = exgcd(b, a%b, y, x);
    y -= (a/b)*x; return d;
}
int inv(int a, int p)
{
    int x, y;
    exgcd(a, p, x, y);
    return (x%p+p)%p;
}

const int N = 105;

char s[N];

void solve();

#define gcd(a, b) __gcd(a, b)

int main()
{
    int t; cin >> t;
    while(t--) solve();
}

void solve()
{
    int n, k, l;
    cin >> n >> k >> l;
    if(gcd(n, k) != 1)
        return void(cout << "NO\n");
    cout << "YES\n";
    int invk = inv(k, n);
    for(int i = 1; i <= l; i++)
    {
        memset(s, '0', sizeof(s));
        for(int j = 0; j < k; j++)
            s[(i+j)*invk%n] = '1';
        s[n] = '\0';
        cout << s << '\n';
    }
    
}

DNA序列

Description

给定 $n$ 个只包含 “A”,“T”,“C”,“G” 字符串，每个字符串取一个非空前缀，然后将这些前缀按任意顺序链接起来，问能获得的字典序最小的字符串是什么。

Input

第一行一个整数 $n$，表示字符串个数。

接下来 $n$ 行，每行一个字符串。

Output

输出一行一个字符串。

Hint

$1 \le n, m \le 50$。

Solution

首先，每个字符串后面加一个很大的字符（例如"Z"）。

对于每个字符串 $s$ ，找到最短的前缀 $x$ 满足 $x^\infty < s$ ，然后将字符串 $s$ 分成 $x^y+z$ ，使得 $x$ 不是 $z$ 的前缀。

那么合并的顺序一定是按照 $x^\infty$ ，字典序升序然后相同按照 $z+'Z'$ 的字典序降序。

我们可以考虑是每次我们希望找个最小的 $x$ ，然后加入尽量多的 $x$，但是 $x$ 加完之后我们希望能加的字符尽量小，所以我们把尾巴字典序最小的放后面。

知道顺序之后，倒着枚举前缀的长度暴力贪心就行了。

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

const int N = 55;

int n;
string s[N];
string tmp, tmp1, tmp2, ans;

struct node {
    string s1, s2, s3;
} a[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> s[i], a[i].s1 = s[i];
    
    for(int i = 1; i <= n; i++)
    {
        int len = s[i].size();
        for(int j = 0; j < len; j++)
        {
            tmp.clear();
            for(int k = 0; k < 50; k++)
                tmp += s[i][k%(j+1)];
            bool flag = true;
            for(int k = 0; k < len; k++)
                if(s[i][k] != tmp[k])
                    flag = false;
            if(flag or s[i] >= tmp)
            {
                s[i] = tmp.substr(0, j+1);
                break;
            }
        }
        a[i].s2 = s[i];
        int len1 = a[i].s1.size(), len2 = a[i].s2.size();
        for(int l = 0; l < len; l += len2)
        {
            int k = 0;
            for(; k < len2; k++)
                if(a[i].s1[k+l] != a[i].s2[k])
                    break;
            if(k >= len2) continue;
            for(k = l; k < len; k++)
                a[i].s3 += a[i].s1[k];
            break;
        }
        tmp.clear();
        for(int j = 0; j < 50; j++)
            tmp += a[i].s2[j%len2];
        a[i].s2 = tmp;
    }
    sort(a+1, a+n+1, [&](node a, node b){
        if(a.s2 != b.s2)
            return a.s2 < b.s2;
        else
            return a.s3+'Z' > b.s3+'Z';
    });
    
    for(int i = n; i >= 1; i--)
    {
        int len = a[i].s1.size();
        for(int j = 0; j < len; j++)
        {
            tmp1.clear();
            for(int l = 0; l <= j; l++)
                tmp1 += a[i].s1[l];
            tmp1 += tmp2;
            if(j == 0 or tmp1 < ans)
                ans = tmp1;
        }
        tmp2 = ans;
    }
    cout << ans << "\n";
}

探寻

Description

给定一棵 $n$ 个点， $n-1$ 条边的树，边带权，节点编号为 $0 \sim n-1$ ，其中根的编号为 $0$，一开始你在根上，第一次走一条边需要花与边权相同数目的钱，走过一次这条边后再走这条边就不需要花钱，如果钱不够则不能走，第一次走到一个点 $x$ 可以获得 $val_x$ 的钱，之后再到达 $x$ 就不会获得钱，标记其中一个叶子为目标节点，求出到达目标节点所需的最少的初始钱数。

Input

第一行一个整数 $n$。

接下来 $n-1$ 行，每行三个整数 $p_i, cost_i, val_i$，表示节点 $i$ 的父节点为 $p_i$，与父节点所连的边的边权为 $cost_i$，第一次走到节点 $i$ 可以获得 $val_i$ 的钱。

仅有一个叶子节点满足 $val_i = -1$ ，该节点为目标节点。

Output

一个整数表示最少的初始钱数。

Hint

$2 \le n \le 2 \times 10^5, 0 \le cost_i, val_i \le 10^9$。

Solution

每次只走一步的贪心显然是错的，因为没有考虑走完这一步后的情况，所以我们从 $x$ 走到 $y$ 的时候，需要考虑 $y$ 整棵子树内的情况。

我们将走一个子树内的连通块成为一个决策，一个决策有两个属性 $(need, get)$，代表使用这个决策的前提是有 $need$ 的钱，使用完这个决策后的收益是 $get$，只有 $get > 0$ 的决策才是有用决策。

设当前节点为 $x$ ，$y \in son_x$ ，只走 $x$ 这一个点的决策显然是 $(cost_x, val_x-cost_x)$，如果 $val_x -cost_x < 0$ ，那么就需要从 $y$ 中选择决策增加 $x$ 的收益，这个可以将决策按 $need$ 比较，用可并堆维护子树内的决策即可，时间复杂度 $O(n \log n)$。

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

typedef long long ll;
const int N = 2e5+10;
const ll INF = 1e18;

namespace edge {
    int to[N], next[N];
}
int head[N], ecnt;
inline void add_edge(int a, int b)
{
    ecnt++;
    edge::to[ecnt] = b;
    edge::next[ecnt] = head[a];
    head[a] = ecnt;
}

struct node { ll pre, get; };
bool operator < (node a, node b)
{
    if(a.pre != b.pre)
        return a.pre > b.pre;
    else
        return a.get > b.get;
}


int n;
ll val[N], cost[N];
__gnu_pbds::priority_queue<node> q[N];

void dfs(int x);

int main()
{
    cin >> n;
    cost[1] = INF; 
    for(int i = 2; i <= n; i++)
    {
        add_edge(read<int>()+1, i);
        read(val[i], cost[i]);
        if(val[i] == -1) val[i] = 2*INF;
    }
    
    dfs(1);
    ll ans = q[1].top().pre-INF;
    cout << ans << "\n";
    // 将 cost[1] 设为 INF, 并将目标节点的 val 设为 2*INF
    // 这样只有到达了目标节点才能补回 cost[1] 的花费
}

void dfs(int x)
{
    for(int i = head[x]; i; i = edge::next[i])
        dfs(edge::to[i]), q[x].join(q[edge::to[i]]);
    
    ll pre = cost[x], get = val[x]-cost[x];
    
    while(!q[x].empty() and (get < 0 or pre >= q[x].top().pre))
    {
        node tmp = q[x].top(); q[x].pop();
        if(pre+get <= tmp.pre)
            pre += tmp.pre-(pre+get);
        get += tmp.get;
    }
    if(get > 0) q[x].push({pre, get});
}