NC21886. μ‘s挑选比赛歌曲
描述
输入描述
首先输入一个输入两个正整数N，K，中间空格间隔，表示N个旋律（0<=N<=20），限制的大小和相似度为 K(1<=K<=40000)。接下来输入N段输入表示每首歌曲旋律的信息，每段信息占用2行，因此总共输入N*2行。每段信息的第一行输入一个M，表示接下来输入的旋律长度(0<=M<=40000)，然后接下来的第二行输入M个整数Pi代表这个旋律 （1<=Pi<=88）。
输出描述
输出最多能选择多少个旋律。
示例1
输入:
2 3 8 1 1 1 1 2 2 2 2 5 1 1 2 2 3
输出:
1
C++14(g++5.4) 解法, 执行用时: 1287ms, 内存消耗: 39668K, 提交时间: 2018-12-28 20:30:27
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=4e4+10,mod=1e9+7;
int n,m,k,t;
bool dp[1<<20];
bool ok[20][20];
int l[20],p[20][maxn];
unordered_map<unsigned long long,int>mp[20];
unsigned long long h[maxn],xp[maxn];
int main()
{
int i,j;
xp[0]=1;
for(i=1;i<maxn;i++)
xp[i]=xp[i-1]*233;
int kk;
scanf("%d%d",&n,&kk);
for(i=0;i<n;i++)
{
scanf("%d",&l[i]);
for(j=1;j<=l[i];j++)
scanf("%d",&p[i][j]);
if(l[i]<kk)i--,n--;
h[0]=0;
for(k=1;k<=l[i];k++)
{
h[k]=h[k-1]*233+p[i][k];
if(k>=kk)mp[i][h[k]-h[k-kk]*xp[kk]]=1;
}
}
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
h[0]=0;
bool flag=true;
for(k=1;k<=l[j];k++)
{
h[k]=h[k-1]*233+p[j][k];
if(k>=kk && mp[i].count(h[k]-h[k-kk]*xp[kk]))
{
flag=false;
break;
}
}
if(flag)ok[i][j]=ok[j][i]=true;
}
dp[0]=true;
int ret=0;
for(i=0;i<1<<n;i++)
{
if(dp[i]==false)continue;
ret=max(ret,__builtin_popcount(i));
for(j=0;j<n;j++)
{
if(i>>j&1)continue;
for(k=0;k<n;k++)
{
if(~i>>k&1)continue;
if(!ok[j][k])break;
}
if(k==n)dp[i|(1<<j)]=true;
}
}
printf("%d\n",ret);
return 0;
}
C++(clang++11) 解法, 执行用时: 1110ms, 内存消耗: 52804K, 提交时间: 2021-03-01 10:19:32
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e4+5,mod1=998244353,mod2=1e9+7;
const int base1=2333,base2=288383;
int n,k,len[N],no[N];
int s[25][N];
map<ll,int>vis;
void sol(int x)
{
ll sum1=0,sum2=0;
ll d1=1,d2=1;
for(int i=1;i<k;i++) d1=d1*base1%mod1,d2=d2*base2%mod2;
for(int i=1;i<=len[x];i++)
{
sum1=(sum1*base1%mod1+s[x][i])%mod1;
sum2=(sum2*base2%mod2+s[x][i])%mod2;
if(i>=k)
{
vis[sum1*2000000000+sum2]|=1<<x-1;
no[x]|=vis[sum1*2000000000+sum2];
sum1=(sum1-s[x][i-k+1]*d1)%mod1;
sum2=(sum2-s[x][i-k+1]*d2)%mod2;
sum1=(sum1+mod1)%mod1;
sum2=(sum2+mod2)%mod2;
}
}
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&len[i]);
for(int j=1;j<=len[i];j++)
scanf("%d",&s[i][j]);
if(len[i]<k)
i--,n--;
}
for(int i=1;i<=n;i++) sol(i);
for(int i=1;i<=n;i++) no[i]^=1<<i-1;
int ans=0,up=1<<n;
for(int i=1;i<up;i++)
{
bool flag=true;
for(int j=0;j<n;j++)
if((i>>j&1)&&(no[j+1]&i)){flag=false;break;}
if(flag) ans=max(ans,__builtin_popcount(i));
}
printf("%d\n",ans);
}