Skip to content

Latest commit

 

History

History
779 lines (578 loc) · 16.7 KB

构造.md

File metadata and controls

779 lines (578 loc) · 16.7 KB
Raw

构造

C. Elemental Decompress

题意： 两个长度为n的不同排列，每次取两个排列中较大的数字最后得到一个新的长度为n的序列。现在给出一个长度为n的序列，问是否存在两个不同的排列可以得出这个序列。

解题思路： 运用映射的思想，初始每个数映射到自身。统计序列中一次都没有出现的数字和出现过两次的数字。没有出现过的数字一定是在比较中作为 “小数” 存在的，出现过两次的数字则是在比较中作为 “大数” 存在的，将它们排列后互相配对。

代码：

bool solve()
{
    int t1 = 0, t2 = 0;
    for (int i = 1; i <= n;i++)
        mp[i] = i;
    for (int i = 1; i <= n;i++){
        if(cnt[i]>2)
            return false;
        if(cnt[i] == 0)
            s[++t1] = i;
        if(cnt[i] == 2)
            b[++t2] = i;
    }
    if(t1!=t2)
        return false;
    sort(s + 1, s + t1 + 1);
    sort(b + 1, b + t2 + 1);
    for (int i = 1; i <= t1; i++){
        if(s[i]>b[i])
            return false;
        mp[b[i]] = s[i];
    }
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= n;i++){
        cnt[a[i]]++;
        if(cnt[a[i]] == 1)
            p[i] = a[i], q[i] = mp[a[i]];
        else
            p[i] = mp[a[i]], q[i] = a[i];
    }
    return true;
}

B. MKnez's ConstructiveForces Task

题意： 求构造一个长度为n的序列，序列中不含为零的元素，且序列中相邻两个元素的和等于整个序列的和。

解题思路： 当n是偶数时，构造为：[1 -1 1 -1 1 -1]。 当n是奇数时，构造一个和为-1的序列，设负数有(n-1)/2个，偶数有(n+1)/2个，设偶数的值为x，解方程-(x+1)(n-1)/2 + x(n+1)/2 = -1。

代码

void solve()
{
    int n;
    cin >> n;
    if(n==3)
        cout << "NO\n";
    else{
        cout << "YES\n";
        if(n&1){
            int m = (n + 1) / 2;
            int x = m - 2;
            cout << x << ' ';
            for (int i = 2; i <= n; i += 2)
                cout << -(x + 1) << ' ' << x << ' ';
        }
        else{
             for (int i = 1; i <= n;i+=2)
            cout << "1 -1 ";
      

        }
          cout << '\n';
    }

}

B. Alphabetical Strings

题意： 定义一种特殊的字符串，它是由以下方式构造而成的：按照字母表的顺序每次取出一个字母，将它放在现有字符串的前端或者后端。现在给出一个字符串，要求判断它是不是通过这种方式构造出来的。

解题思路： 一般用双端队列解决此类问题，将字符串加入到一个双端队列里，每次比较队列前端和后端的字母，将字典序大的字母弹出，按弹出顺序把字母放到一个字符串中，将它与 "abcdef..."进行比较。

代码：

bool solve()
{
    string s;
    cin >> s;
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < (int)s.size();i++){
        cnt[s[i] - 'a']++;
        if(cnt[i]>1)
            return false;
    }
    string ss;
    int i = 0, j = (int)s.size() - 1;
    while(i<j){
        if(s[i]>s[j]){
            ss.push_back(s[i]);
            i++;
        }
        else{
            ss.push_back(s[j]);
            j--;
        }
    }
    ss.push_back(s[i]);
    char cur = 'a';
    for (int i = (int)ss.size() - 1; i >= 0;i--){
        if(ss[i]!=cur)
            return false;
        cur++;
    }
    return true;
}

A. Hossam and Combinatorics

题意： 给定一个序列，任选序列中的两个元素，求它们差的绝对值，要求统计差的绝对值最小的不同序列有多少对。

解题思路： 统计最大数的个数a和最小数的个数b，答案即为2ab，任选的两个元素构成一个有序对，所以即使两个元素相同，次序不同算作一个新的组合。 要特别注意一种情况：整个序列元素是相同的，这种情况下答案就是n(n-1)。

代码：

void solve()
{
    int n;
    cin >> n;
    rep(i, 1, n) cin >> a[i];
    sort(a + 1, a + n + 1);
    ll cnt1 = 1, cnt2 = 1;
    rep(i,2,n){
        if(a[i]==a[i-1])
            cnt1++;
        else
            break;
    }
    rev(i,n-1,1){
        if(a[i]==a[i+1])
            cnt2++;
        else
            break;
    }
    if(a[1]==a[n])
        cout << 1LL * (n) * (n - 1) << '\n';
    else
        cout << 1LL * cnt1 * cnt2 * 2 << '\n';
}

D. Co-growing Sequence

题意： 定义一个序列是growing的，它满足下列条件： ai+1&ai=ai 通俗解释就是在二进制表示下，靠后的元素一定包含了考前的元素出现的1位。 定义序列x1, x2, ... ,xn和序列y1, y2, ... ,yn是co-growing的，当且仅当：x1 xor y1, x2 xor y2, ... ,构成的数列是growing的。 给定序列[x]，要求找到字典序最小的序列[y]，使得这两个序列是co-growing的。

思路： yi中的1可以让xi中的1变成0，让xi中的0变成1。 yi中的0可以让xi中的1变成1，让xi中的0变成0。 （一个数与0做异或运算，保持原数不变） 可以看到我们应该在xi中为1的位上让yi为0，这样也与要求的字典序最小相符。 根据异或的性质，x xor y = z，y = x xor z。 让yi中的0尽量多->不消除xi中的1，自己体会代码吧。

代码：

void solve()
{
    cin >> n;
    int cnt = 1;
    for (int i = 1; i <= n;i++)
        cin >> a[i];
    for (int i = 2; i <= n;i++){
        int x = a[i] | a[i - 1];
        ans[cnt++] = (x ^ a[i]);
        a[i] = x;
    }
    for (int i = 0; i < cnt;i++)
        cout << ans[i] << ' ';
    cout << endl;
}

C. Different Differences

题意： 对于一个严格单调递增的序列[a]，定义它的“特别度”为序列a2-a1, a3-a2, 中不同元素的个数。 给定n和k，要求构造一个长度为k的序列，序列中元素的取值范围为1-n，该序列的“特别度”最大。

思路： 构造的序列中元素之间的差为等差数列，但要保证够k个。则尽量使得差为等差的序列最长，然后后面用差为1的数字补足k个，列出不等式，程序求解。

代码：

void solve()
{
    int n, k;
    cin >> k >> n;
    v.clear();
    int x = k-1;

    while(1){
        int res = x * (x + 1) - 2 * (x + 1);
        if(res<2*(n-k))
            break;
        else
            x--;
    }
    int now = 1, dis = 1;
    v.push_back(now);
    for (int i = 1; i <= x;i++){
        now += dis;
        v.push_back(now);
        dis++;
    }

    for (int i = 1; i <= (k - x - 1);i++)
        now++, v.push_back(now);

    for(auto x:v)
        cout << x << ' ';

    cout << '\n';

    return;
}

D. Watch the Videos

题意： 某人想看n部电影，所有电影的时长都为1分钟，第i部电影的大小为ai字节，每下载1字节需要1分钟，在观看一部电影前要先保证它已经被下载了。若要开始下载一部大小为s的电影，要保证磁盘的剩余空间大于等于s。 看完的电影可以被立即删除。 现在给出n（电影数量）和m（磁盘大小），以及一个长度为n的序列，表示每一部电影具体的大小，要求输出看完这些电影最少需要多少时间。

思路： 可以先下载一部较大的电影，然后下载一部小电影，同时观看大电影。看完以后立即删除下载下一部大电影，并用下载的时间观看下电影。可以发现除了最后下载的一部电影的观看时间无法被其它的下载时间覆盖掉，其它都可以在下载的时候完成观看。 所以初始化ans=1。当大电影无法与小电影组合下载时，它的观看时间也不能覆盖，总时间需要额外加1。

代码：

void solve()
{
    int n, k;
    cin >> k >> n;
    v.clear();
    int x = k-1;

    while(1){
        int res = x * (x + 1) - 2 * (x + 1);
        if(res<2*(n-k))
            break;
        else
            x--;
    }
    int now = 1, dis = 1;
    v.push_back(now);
    for (int i = 1; i <= x;i++){
        now += dis;
        v.push_back(now);
        dis++;
    }

    for (int i = 1; i <= (k - x - 1);i++)
        now++, v.push_back(now);

    for(auto x:v)
        cout << x << ' ';

    cout << '\n';

    return;
}

A2. Gardener and the Capybaras (hard version)

题意： 给你一个只含a、b的字符串，要求把它分割成三个字串s1、s2、s3，保证s2<s3且s2<s1或者s2>s3且s2>s1。

思路： 分类讨论（一生之敌）

E. Rectangular Congruence

题意： 素数n，n个整数b1, b2, b3, ..., bn。满足b在1到n之间。 要求构造一个n x n的矩阵，满足下列条件： $$ 0\leqslant a_{ij}<n $$

$$ a_{r_1,c_1}+a_{r_2,c_2}\not\equiv a_{r_1,c_2}+a_{r_2,c_1} $$

$$ a_{i,i}=b_i $$

思路：

移项，可以发现： $$ a_{r_1,c_1}-a_{r_1,c_2}\not\equiv a_{r_2,c_1}-a_{r_2,c_2} $$ 构造一个矩阵，每一行都是公差不同的等差数列即可

代码：

void solve() {
  int n;
  cin >> n;
    	//第i行公差为i
        for (int i = 0; i < n; i++)
        {
            int b;
            cin >> b;
            for (int j = 0; j < n; j++)
            {
                //不一定需要一个递增的等差数列，构造一个满足第三个条件即可
                cout << (i * (j - i + n) + b) % n << " ";
            }
            cout << "\n";
        }
}

D. Lucky Permutation

题意： 给定一个长度为n的排列，每次可以选择交换两个位置，求最少操作次数使得最后成为一个只有一个逆序对的排列。

思路： 只有一个逆序对的排列——存在只有一个相邻元素位置相反的排列。 对ai->i连边，这个图变成了若干个置换环。对于每一个大小为x的置换环，需要x-1次操作才能将序列排好序。 1，2，3，4，...，n——n个大小为1的环，对于环内部需要的操作时1-1=0。恢复成排列的交换次数是0。

只需统计出环的数量，n-x就是需要的操作数。

结果：必须存在一个逆序对，对于一个环中，假如环中存在相邻元素，可以节省下一次操作，ans--，如果任何一个环都不存在相邻元素，ans++。

代码：

vector<int> in;
map<int, int> v;
vector<vector<int>> g;
int ans, flag, cnt;
void dfs(int u)
{
    in[u] = 1;
    if(v[u])
        return;
    v[u] = 1;
    if(v[u+1]||v[u-1])
        flag = 1;
    for(auto v:g[u]){
        dfs(v);
    }
}
void solve()
{
    int n;
    cin >> n;
    v.clear(), in.clear();
    g.clear();
    in.resize(n+1), g.resize(n+1);
    for (int i = 1; i <= n;i++){
        int u;
        cin >> u;
        g[u].push_back(i);
    }

    ans = n, flag = 0, cnt = 0;

    for (int i = 1; i <= n;i++){
        if(in[i])
            continue;
        v.clear();
        dfs(i);
        cnt++;
    }
    if(flag)
        cout << ans - cnt - 1 << '\n';
    else
        cout << ans - cnt + 1 << '\n';
}

E2. Unforgivable Curse (hard version)

题意： 两个字符串s和t，对于s可以进行若干次下述操作：交换两个下标差为k或k+1的的字母，目标是将s变为t。判断是否存在一种可行的方案。

思路： 分类讨论：

  • s==t YES
  • s和t的字母种类不同 NO
  • k>=n NO
  • k*2<=n 一定可以

证明：要交换两个距离小于k的字母可以选择另一个字母作为中继点，要交换两个距离大于k+1的字母可以也可以选择一个字母作为中继点

  • k*2>n 不一定可以

想象把n分成两个部分，k+res，则res，k-res，k+res可划分整个字符串。 k-res中的数不能与任何其它字母交换。这部分的字母s和t必须相同。

启发者：TJ_Andeviking

代码：

void solve()
{
    int n,k;
    cin >> n >> k;
    string s, t;
    cin >> s >> t;
    string ss(s), tt(t);
 
    sort(range(ss));
    sort(range(tt));
 
    if(s==t){
        cout << "YES" << '\n';
        return;
    }
 
    if(ss!=tt) {
        cout << "NO" << '\n';
        return;
    }
 
    if(k>=n) {
        cout << "NO" << '\n';
        return;
    }
 
    if(k==n-1){
        swap(s.front(), s.back());
        if(s==t)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    else{
        if(k*2<=n)
            cout << "YES\n";
        else{
            for (int i = n-k+1; i <= k;i++){
                if(s[i-1]!=t[i-1]){
                    cout << "NO\n";
                    return;
                }
            }
            cout << "YES\n";
        }
    }
 
    return;
}

C. Make It Permutation

题意：

把一个数组构造为一个排列，可以使用两种操作：

  • 删除一个数，代价为c
  • 插入一个数，代价为d

给出n个数，求把它们整合成一个排列的最小代价

注意是可能有重复的数字的

思路：

代码：

void solve()
{
    int n;
    long long c, d;
    cin >> n >> c >> d;
    vector<int> a(n);
    for (int j = 0; j < n; j++){
      cin >> a[j];
    }
    map<int, int> mp;
    for (int j = 0; j < n; j++){
      mp[a[j]]++;
    }
    long long ans = n * c + d;
    int cnt = 0;
    //mp以后key是按从小到大的顺序出现
    for (pair<int, int> P : mp){
      cnt++;
        //新的方案：删掉后面的所有数字+插入不足的数
      ans = min(ans, (n - cnt) * c + (P.first - cnt) * d);
    }
    cout << ans << endl;
}

C. Restore the Array

题意：

有一个长度为n的数列a，由 $$ b_i=max(a_i,a_i+1) $$ 得到数列b，现在给出数列b，求构造一个符合要求的序列a

思路：

代码：

void solve()
{
    int n;
    cin >> n;

    vector<int> a(n - 1), b;

    for(auto &x:a)
        cin >> x;

    b.push_back(a[0]);

    for (int i = 0; i < n - 2;i++)
        b.push_back(min(a[i], a[i + 1]));

    b.push_back(a.back());

    for(auto x:b)
        cout << x << ' ';
    cout << '\n';
}

E. Living Sequence

题意：

image-20230405142221356

思路：

排除数位中所有的4，也就是将10进制改为9进制。

代码：

void solve()
{
    ll k;
    cin >> k;

    vector<int> res;
    while(k){
        int d = k % 9;
        if(d>=4)
            d++;
        res.push_back(d);
        k /= 9;
    }
    reverse(range(res));

    for(auto x:res)
        cout << x ;
    cout << '\n';

    return;
}

C. Sequence Master

题意：

image-20230405151201595

img

思路：

意识到这个条件是很苛刻的，能满足这个条件的数列很少。

n=1的时候，答案就是两个数字之差。

n=2时，

  • 4个2
  • 4个0
  • 3个-1和1个2

n%2=0时，

  • 全是0
  • 2n-1个-1和1个n

n%2=1时，

  • 全是0

代码：

void solve()
{
    int n;
    cin >> n;
    vector<int> a(2 * n);
    for (int i = 0; i < 2 * n; ++i) {
        cin >> a[i];
    }
    if (n == 1) {
        cout << abs(a[1] - a[0]) << '\n';
        return;
    }
    long long res = 0;
    for (int i = 0; i < 2 * n; ++i) {
        res += abs(a[i]);
    }
    if (n == 2) {
        long long cur = 0;
        for (int i = 0; i < 2 * n; ++i) {
            cur += abs(a[i] - 2);
        }
        res = min(res, cur);
    }
    if (n % 2 == 0) {
        long long total = 0;
        for (int i = 0; i < 2 * n; ++i) {
            total += abs(a[i] + 1);
        }
        for (int i = 0; i < 2 * n; ++i) {
            res = min(res, total - abs(a[i] + 1) + abs(a[i] - n));
        }
    }
    cout << res << '\n';
}

C. Pull Your Lock

题意：

image-20230405200312210

思路：

image-20230405200803466

代码：

void solve()
{   
    ll n, x, p;
    cin >> n >> x >> p;

    for (ll i = 1; i <= min(p, n * 2);i++)
        if((i*(i+1))/2%n==(n-x)%n){
            cout << "Yes\n";
            return;
        }

    cout << "No\n";
    return;
}

D. Accommodation

题意：

image-20230405203410048

思路：

单人间：有多少1就有多少户人；

双人间：可以有4种情况：00，01，10，11。当双人间选择为11的时候会影响到最终的人数。即使得总人数-1。

最少人数：尽可能多的选择11的双人间；最多人数：尽可能少选择11的双人间。

image-20230405203901256

代码：