Educational Codeforces Round 107 (Rated for Div. 2) C-D

Educational Codeforces Round 107 (Rated for Div. 2)

教育场, 出了三题, 终于结束掉分了

C题 Yet Another Card Deck

原题链接

题意

给定一个序列\(a\), \(q\)个询问, 每次询问数字\(i\)在\(a\)中从前到后最先出现在哪个位置,同时将该位置上的数放在第1位.

思路

维护一个数组\(mp[]\), \(mp[i]\)为\(i\)在\(a\)中最先出现的位置
对于每次询问\(op\):
先输出\(mp[op]\), 再依次更新所以的数字\(x\)的\(mp[x]\)

  1. \(mp[x] < mp[op]\), 将\(op\)加到序列前需要\(mp[x] = mp[x] + 1\)
  2. \(mp[x] > mp[op]\), 将\(op\)加到序列后\(mp[x]\)不变

时间复杂度:
\(3e5\)次询问, \(a_{i}\)的范围\(1 - 50\), 所以最差在\(3e5 \times 50\)
不会超时

代码

#include 
#include 
#include 
#include 

using namespace std;

const int N = 3e5 + 10;

int a[N];
int mp[60];

void solve()
{
    int n;
    memset(mp, 0x3f, sizeof mp);
    int q;
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i ++ ){
        scanf("%d", &a[i]);
        mp[a[i]] = min(i, mp[a[i]]);
    }
    int op;
    while (q -- ){
        scanf("%d", &op);
        printf("%d\n", mp[op]);
        for (int i = 1; i <= 50; i ++ )
            if (mp[i] == 0x3f3f3f3f)
                continue;
            else{
                if (mp[i] < mp[op])
                    mp[i]++;
            }
        mp[op] = 1;
    }
    return;
}


int main()
{
    solve();
    return 0;
}

D题 Min Cost String

原题链接

题意

求一个长度为\(n\)的字符串, 要求只使用26个字母的前\(k\)个, 要求构造所得的字符串中\(s_{i} = s_{j} 同时 s_{i + 1} = s_{j + 1}\)最少.

思路

初始化:\(s = 'a'\)
\(g[i][j]\)表示\(ij\)出现的次数(\(ij\)为对应的字母组合, 如\(12\)为\(ab\))
向后搜索:
\(dfs(cnt, fr)\): \(cnt\)记录搜索到第\(cnt\)位置, \(fr\)记录上一次选择的字母对应的数字
每一次搜索, 遍历26个字母, 找到最小的\(g[fr][i]\),即可找到当前位置的字母\(i\),同时\(g[fr][i] + 1\),再继续向后搜索.

代码

#include 
#include 
#include 

using namespace std;

const int N = 2e5 + 10;
int n, k;
string s;

int g[30][30];

void dfs(int cnt, int fr)
{
    if (cnt > n){

        return ;
    }
    int minn = 0x3f3f3f3f;
    int ne = 0;
    for (int i = 1; i <= k; i ++ ){
        if (g[fr][i] <= minn){
            minn = g[fr][i];
            ne = i;
        }
    }
    //cout << char('a' + ne - 1);
    s += char('a' + ne - 1);
    g[fr][ne] ++;
    dfs(cnt + 1, ne);
}

int main()
{
    
    cin >> n >> k;
    s = "a";
    dfs(2, 1);
    cout << s << endl;
    return 0;
}
codeforces练习赛

相关

标签