首页 > 其他分享 >G. Shuffling Songs

G. Shuffling Songs

时间:2024-04-01 23:33:06浏览次数:22  
标签:playlist right Shuffling int Songs test exciting songs

G. Shuffling Songs

Vladislav has a playlist consisting of $n$ songs, numbered from $1$ to $n$. Song $i$ has genre $g_i$ and writer $w_i$. He wants to make a playlist in such a way that every pair of adjacent songs either have the same writer or are from the same genre (or both). He calls such a playlist exciting. Both $g_i$ and $w_i$ are strings of length no more than $10^4$.

It might not always be possible to make an exciting playlist using all the songs, so the shuffling process occurs in two steps. First, some amount (possibly zero) of the songs are removed, and then the remaining songs in the playlist are rearranged to make it exciting.

Since Vladislav doesn't like when songs get removed from his playlist, he wants the making playlist to perform as few removals as possible. Help him find the minimum number of removals that need to be performed in order to be able to rearrange the rest of the songs to make the playlist exciting.

Input

The first line of the input contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 16$) — the number of songs in the original playlist.

Then $n$ lines follow, the $i$-th of which contains two strings of lowercase letters $g_i$ and $w_i$ ($1 \leq |g_i|, |w_i| \leq 10^4$) — the genre and the writer of the $i$-th song. Where $|g_i|$ and $|w_i|$ are lengths of the strings.

The sum of $2^n$ over all test cases does not exceed $2^{16}$.

The sum of $|g_i| + |w_i|$ over all test cases does not exceed $4 \cdot 10^5$.

Output

For each test case, output a single integer — the minimum number of removals necessary so that the resulting playlist can be made exciting.

Example

input

4
1
pop taylorswift
4
electronic themotans
electronic carlasdreams
pop themotans
pop irinarimes
7
rap eminem
rap drdre
rap kanyewest
pop taylorswift
indierock arcticmonkeys
indierock arcticmonkeys
punkrock theoffspring
4
a b
c d
e f
g h

output

0
0
4
3

Note

In the first test case, the playlist is already exciting.

In the second test case, if you have the songs in the order $4, 3, 1, 2$, it is exciting, so you don't need to remove any songs.

In the third test case, you can remove songs $4, 5, 6, 7$. Then the playlist with songs in the order $1, 2, 3$ is exciting.

 

解题思路

  因为前段时间有事好久没有写博客了,也没有怎么写题。挑个上场的 Div. 4 最后一题水水()

  数据范围的提示 "The sum of $2^n$ over all test cases does not exceed $2^{16}$." 就直接把做法贴脸上了,挺乐的()

  先定义符号 $a_i$ 和 $b_i$ 分别表示第 $i$ 首音乐的作者和流派。$g(i,j)=0/1$ 表示第 $i$ 首音乐能否与第 $j$ 首音乐相邻,直接暴力预处理即可。定义状态 $f(i,j)$ 表示由二进制集合 $i$ 中的音乐(即所有是 $1$ 位)构成的所有合法序列中(且最后一首音乐为 $j$),代价的最小值。其中代价指集合中要删除的元素数量。当然还有一个前提是 $i$ 的二进制下的第 $j$ 位要为 $1$。

  考虑状态转移,如果第 $j$ 首音乐不接在任何一首音乐的后面,那么代价就是 $\mathrm{popcount}(i)-1$,其中 $\mathrm{popcount}(i)$ 表示 $i$ 在二进制下为 $1$ 的位数。如果要接在第 $k$ 首音乐后面,有两个条件要满足:$i$ 的第 $k$ 位是 $1$ 且 $g(j,k) = 1$。代价就是 $f\left( i \oplus 2^{j}, k \right)$。因此状态转移方程就是 $$f(i,j) = \min\left\{{\mathrm{popcount}(i)-1, \, \min\limits_{\begin{array}{c} 0 \leq k < n \\ i \bmod 2^k = 0 \\ g(j,k) = 1 \end{array}}\left\{{f\left(i \oplus 2^{j}, k\right)}\right\}}\right\}$$

  AC代码如下,时间复杂度为 $O\left(n \sum{|a_i| + |b_i|} + n^2 2^n \right)$:

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

typedef long long LL;

const int N = 16, M = 1 << 16, INF = 0x3f3f3f3f;

string a[N], b[N];
int g[N][N];
int f[M][N];

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] == a[j] || b[i] == b[j]) g[i][j] = g[j][i] = 1;
            else g[i][j] = g[j][i] = 0;
        }
    }
    for (int i = 1; i < 1 << n; i++) {
        for (int j = 0; j < n; j++) {
            if (i >> j & 1) {
                f[i][j] = __builtin_popcount(i) - 1;
                for (int k = 0; k < n; k++) {
                    if (i >> k & 1 && g[j][k]) f[i][j] = min(f[i][j], f[i ^ 1 << j][k]);
                }
            }
            else {
                f[i][j] = INF;
            }
        }
    }
    int ret = n;
    for (int i = 0; i < n; i++) {
        ret = min(ret, f[(1 << n) - 1][i]);
    }
    cout << ret << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

 

参考资料

  Codeforces Round 937 (Div. 4) Editorial:https://codeforces.com/blog/entry/127664

标签:playlist,right,Shuffling,int,Songs,test,exciting,songs
From: https://www.cnblogs.com/onlyblues/p/18109645

相关文章

  • 算法题 - Shuffling Machine
    Introduction:Shufflingisaprocedureusedtorandomizeadeckofplayingcards.Becausestandardshufflingtechniquesareseenasweak,andinordertoavoid"insidejobs"whereemployeescollaboratewithgamblersbyperforminginadequatesh......
  • Songshan-Lake Cluster
                             SongshanLakeLaboratory        PlatformforDataDrivenComputationalMaterialsDiscovery                          TiangongSupercomputer----------------------------------......
  • Codeforces 1672 F1. Array Shuffling
    题意给一个n个数的数列a,a[i]<=n定义一个操作:每次可以交换任意位置的两个值;定义最优操作:对于任意一个原数列的一组排列,使其通过尽可能少的操作变回原数列;求构造一组原......
  • [Oracle] LeetCode 1010 Pairs of Songs With Total Durations Divisible by 60
    Youaregivenalistofsongswheretheithsonghasadurationoftime[i]seconds.Returnthenumberofpairsofsongsforwhichtheirtotaldurationinsecon......