Codeforces Round #502 D. The Wu
12686 ワード
タイトルアドレス:http://codeforces.com/contest/1017/problem/D 集合や問い合わせに重複が多いため,前処理が可能であり,複雑度は4096*4096*12程度である.
1096 msのコード:
498ms
1096 msのコード:
#include
using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 4100;
int n,m,q;
int w[15];
int flag[N];
int ans[N][105];
char s[15];
int zhuanhuan(char a[])
{
int len = strlen(a);
//printf("%d
",len);
int sum = 0;
int x = 1;
for(int i = len - 1;i >= 0;--i)
{
if(a[i] == '1'){
sum += x;
}
x = x * 2;
}
return sum;
}
int main()
{
// char tmp[5] = "0110";
// printf("%d
",zhuanhuan(tmp));
while(~scanf("%d %d %d",&n,&m,&q))
{
for(int i = 0;i < n;++i)
{
scanf("%d",&w[i]);
}
memset(flag,0,sizeof(flag));
memset(ans,0,sizeof(ans));
for(int i = 0;i < m;++i)
{
scanf("%s",s);
flag[zhuanhuan(s)]++;
}
// for(int i = 0;i < 4;++i)
// {
// printf("%d ",flag[i]);
// }
// printf("
");
for(int i = 0;i < N;++i)
{
for(int j = 0;j < N;++j)
{
if(flag[j] != 0){
int sum = 0;
int p = i ^ j;
//printf("%d
",p);
for(int k = 0;k < n;++k)
{
//printf("%d %d
",k,p);
if((p & 1) == 0){
sum += w[n - k - 1];
}
p >>= 1;
}
//printf("i:%d j:%d flag[j]:%d sum:%d p:%d
",i,j,flag[j],sum,p);
// for(int k = sum;k <= 100;++k)
// {
// ans[i][k] += flag[j];
// }
if(sum <= 100){
ans[i][sum] += flag[j];
}
}
}
}
for(int i = 0;i < N;++i)
{
for(int j = 1;j <= 100;++j)
{
ans[i][j] += ans[i][j - 1];
}
}
for(int i = 0;i < q;++i)
{
char tmp[15];int k;
scanf("%s %d",tmp,&k);
printf("%d
",ans[zhuanhuan(tmp)][k]);
}
}
return 0;
}
498ms
#include
using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 4100;
int n,m,q;
int w[15];
int flag[N];
int ans[N][105];
char s[15];
int g[N];
int zhuanhuan(char a[])
{
int len = strlen(a);
//printf("%d
",len);
int sum = 0;
int x = 1;
for(int i = len - 1;i >= 0;--i)
{
if(a[i] == '1'){
sum += x;
}
x = x * 2;
}
return sum;
}
int main()
{
// char tmp[5] = "0110";
// printf("%d
",zhuanhuan(tmp));
while(~scanf("%d %d %d",&n,&m,&q))
{
for(int i = 0;i < n;++i)
{
scanf("%d",&w[i]);
}
memset(flag,0,sizeof(flag));
memset(ans,0,sizeof(ans));
memset(g,0,sizeof(g));
for(int i = 0;i < m;++i)
{
scanf("%s",s);
flag[zhuanhuan(s)]++;
}
// for(int i = 0;i < 4;++i)
// {
// printf("%d ",flag[i]);
// }
// printf("
");
// 1 wu , “wu”
for (int i = 0;i < N;i++)
{
for (int j = 0,k = 1;j < n;j++,k *= 2){
if ((i & k) != 0)
g[i] += w[n - j - 1];
}
}
for(int i = 0;i < (1 << n);++i)
{
for(int j = 0;j < (1 << n);++j)
{
if(flag[j] != 0){
int sum = 0;
int p = i ^ j;
sum = g[(1 << n) - p - 1];
//printf("i:%d j:%d sum:%d flag:%d
",i,j,sum,flag[j]);
if(sum <= 100){
ans[i][sum] += flag[j];
}
}
}
}
for(int i = 0;i < N;++i)
{
for(int j = 1;j <= 100;++j)
{
ans[i][j] += ans[i][j - 1];
}
}
for(int i = 0;i < q;++i)
{
char tmp[15];int k;
scanf("%s %d",tmp,&k);
printf("%d
",ans[zhuanhuan(tmp)][k]);
}
}
return 0;
}