NC50448. 德育分博弈政治课
描述
输入描述
第一行输入 n,Q。
接下来 n 行，每行输入一个长度为 6 的字符串，每个字符都在‘1’~‘9’。
接下来 Q 行，每行一个字符串，每个字符都在‘1’~‘9’。且 Q 个字
符串的总长度不超过 2000000。
1<=n<=500000,1<=Q<=100。
输出描述
对于每一回合，若德育分获胜，输出“dyf”。
若政治课获胜，输出“zzk”。
示例1
输入:
3 3 137628 987654 123456 288 2288 333
输出:
dyf zzk zzk
C++14(g++5.4) 解法, 执行用时: 259ms, 内存消耗: 736K, 提交时间: 2019-10-29 19:17:26
#include<bits/stdc++.h>
using namespace std;
int n,q,m;
int cnt[1000001];
int w[1000001];
char s[1000001];
int main()
{
cin>>n>>q;
for(int i=0;i<n;i++)
{
int a=0;
cin>>s;
for(int j=0;j<6;j++)
{
a|=1<<(s[j]-'1');
}
cnt[a]++;
}
for(int i=0;i<512;i++)
{
for(int j=0;j<512;j++)
{
if(i&j)
{
w[i]+=cnt[j];
}
}
}
while(q--)
{
int c[10]={};
cin>>s;
m=strlen(s);
bool dyf=true;
for (int i = 0; i < m; i++)
{
c[s[i] - '1']++;
}
for(int i=0;i<512;i++)
{
int now=0;
for(int j=0;j<9;j++)
{
if(i>>j&1)
{
now+=c[j];
}
}
if(w[i]<now)
{
dyf=false;
}
} puts(dyf ? "dyf" : "zzk");
}
}
C++11(clang++ 3.9) 解法, 执行用时: 257ms, 内存消耗: 612K, 提交时间: 2019-10-14 11:24:43
#include<bits/stdc++.h>
using namespace std;
int n,q,m;
int cnt[1000001];
int w[1000001];
char s[1000001];
int main()
{
cin>>n>>q;
for(int i=0;i<n;i++)
{
int a=0;
cin>>s;
for(int j=0;j<6;j++)
{
a|=1<<(s[j]-'1');
}
cnt[a]++;
}
for(int i=0;i<512;i++)
{
for(int j=0;j<512;j++)
{
if(i&j)
{
w[i]+=cnt[j];
}
}
}
while(q--)
{
int c[10]={};
cin>>s;
m=strlen(s);
bool dyf=true;
for (int i = 0; i < m; i++)
{
c[s[i] - '1']++;
}
for(int i=0;i<512;i++)
{
int now=0;
for(int j=0;j<9;j++)
{
if(i>>j&1)
{
now+=c[j];
}
}
if(w[i]<now)
{
dyf=false;
}
} puts(dyf ? "dyf" : "zzk");
}
}