比赛总结
这次比赛打得总算像样了。。。
做了A和B，都是wa了两次才ac，罚时有点惨
在正式和非正式选手里排名537名，在正式选手里排名450名
A. Diverse Permutation
题目链接
http://codeforces.com/contest/482/problem/A
题目大意
要你构造一个
1
,
2
,
.
.
.
n
的排列
a
[
]
，使得最终
|
a
[
i
]
−
a
[
i
+
1
]
|
的互不相同的值恰好有
k
种
思路
显然，
|
a
[
i
]
−
a
[
i
+
1
]
|
的互不相同的值最多时，构造的排列一定是
1
n
2
n
−
1
3
n
−
2
…
因此，我们可以先构造排列的前
K
个数字，这部分数字满足 1
n
2
n
−
1
3
n
−
2
…的特点，这样就出现了
K
−
1
种。然后剩下的部分，我们就单调递增或递减填入没填过的数字，这样就出现了第
K
种取值，也就是1
K
=
1
时特判下就好了
代码
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#define MAXN 1100000
using namespace std;
int n,K;
int tot=0;
int main()
{
scanf("%d%d",&n,&K);
if(K==1)
{
for(int i=1;i<=n;i++) printf("%d ",i);
printf("\n");
return 0;
}
K--;
int a=1,b=n+1;
printf("1 ");
int i=2;
for(int t=1;t<=(K-1);t++,i++)
printf("%d ",(i&1)?++a:--b);
bool flag=(i&1)?true:false;
for(;i<=n;i++)
if(flag) printf("%d ",++a);
else printf("%d ",--b);
printf("\n");
return 0;
}
B. Interesting Array
题目链接
http://codeforces.com/contest/482/problem/B
题目大意
要你构造一个长度为
n
的数列，满足
m
个要求。对于每个要求，要使得
[
L
i
,
R
i
]
区间内的数列数字的与和为
v
a
l
思路
我们首先讨论
v
a
l
≤
1
的情况
注意到，一个区间内的数列数字的与和为
1
，就必须满足这个区间里所有数字都是1，而一个区间内的数列数字的与和为
0
，只需要满足这个区间里有一个数字是0即可。假设一个与和为1的区间
[
L
i
,
R
i
]
和一个与和为0的区间
[
L
′
i
,
R
′
i
]
有交集，那么相交的那部分肯定是取1。
这个特点非常类似于或运算：重叠的那部分先是区间或了1，然后是区间或了0，最终得到了连续的一段1，于是问题转变为：给你一个初始全为0的序列，每次区间或某个数字，然后离线对每个询问检查一遍，每个询问对应的区间
[
L
i
,
R
i
]
的与和是否为
v
a
l
。并且要输出最终的序列
这个问题非常简单，直接维护一个支持区间修改、区间查询的线段树即可。维护区间或的lazy tag、以及区间与和标记。最终遍历一遍线段树的所有叶子节点即可
代码
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#define MAXN 110000
using namespace std;
int or_tag[MAXN<<2],andsum_tag[MAXN<<2]; //区间或标记，区间与和标记
void pushup(int o)
{
andsum_tag[o]=andsum_tag[o<<1]&andsum_tag[o<<1|1];
}
void pushdown(int o)
{
or_tag[o<<1]|=or_tag[o];
andsum_tag[o<<1]|=or_tag[o];
or_tag[o<<1|1]|=or_tag[o];
andsum_tag[o<<1|1]|=or_tag[o];
or_tag[o]=0;
}
void update(int o,int L,int R,int ql,int qr,int orval)
{
if(ql<=L&&R<=qr)
{
andsum_tag[o]|=orval;
or_tag[o]|=orval;
return;
}
pushdown(o);
int M=(L+R)>>1;
if(ql<=M) update(o<<1,L,M,ql,qr,orval);
if(qr>M) update(o<<1|1,M+1,R,ql,qr,orval);
pushup(o);
}
int query(int o,int L,int R,int ql,int qr)
{
if(ql<=L&&R<=qr)
{
return andsum_tag[o];
}
pushdown(o);
int M=(L+R)>>1,ans=1; //mlgb!!!不能拿ans=1然后and答案，这样的话可能会错！
if(qr<=M) return query(o<<1,L,M,ql,qr);
if(ql>M) return query(o<<1|1,M+1,R,ql,qr);
//cout<<"L: "<<L<<" R: "<<R<<" ans: "<<ans<<endl;
return query(o<<1,L,M,ql,qr)&query(o<<1|1,M+1,R,ql,qr);
}
void print(int o,int L,int R)
{
if(L==R)
{
printf("%d ",andsum_tag[o]);
return;
}
pushdown(o);
int M=(L+R)>>1;
print(o<<1,L,M);
print(o<<1|1,M+1,R);
}
struct Query
{
int L,R,val;
}querys[MAXN];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&querys[i].L,&querys[i].R,&querys[i].val);
update(1,1,n,querys[i].L,querys[i].R,querys[i].val);
}
for(int i=1;i<=m;i++)
{
if(query(1,1,n,querys[i].L,querys[i].R)!=querys[i].val)
{
printf("NO\n");
return 0;
}
}
printf("YES\n");
print(1,1,n);
return 0;
}
C. Interesting Array
题目链接
http://codeforces.com/contest/482/problem/C
题目大意
n个长为m的字符串，A会先从中随机选择一个串，让B去判断A选择的串是哪个串，每次B会随机地知道m位字母里未知的一位，问B确定答案的期望步数
思路
我们可以先预处理出
f
[
S
]
=
在
m
个下标中已经知道了集合
S
里的下标的概率，以及
c
n
t
[
S
]
=
在
m
个下标中已经知道了集合
S
里的下标，会找出多少个相同的字符串(只能找出一个字符串，就是0)。
答案就是
∑
f
[
S
]
c
n
t
[
S
]
n
为什么呢？假设A不是随机选取一个串，而是指定了一个串。假如当前B已知的字符的下标集合为
S
，若
c
n
t
[
S
]
=
0
，表明B同学不需要再询问了，直接结束，否则
c
n
t
[
S
]
>
=
2
，会找出至少2个暂时看起来一样的字符串，B同学至少还需要再走一步，这样的话步数会+1，对期望步数的答案的贡献为
f
[
S
]
∗
1
而如果A是指定了一个串呢？最终的期望步数就是
∑
n
i
=
1
指
定
第
i
个
串
的
期
望
步
数
n
，我们可以直接利用上一段的做法来求出
∑
n
i
=
1
指
定
第
i
个
串
的
期
望
步
数
：
c
n
t
[
S
]
>
=
2
时，会找出至少2个暂时看起来一样的字符串，B同学至少还需要再走一步，这样的话，对于这
c
n
t
[
S
]
个字符串，要将它们一一区分开来，每个字符串的判断步数都会+1，因此对期望步数之和的答案的贡献为
f
[
S
]
∗
c
n
t
[
S
]
代码
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#define MAXN 60
using namespace std;
typedef long long int LL;
int n,m;
char s[MAXN][MAXN];
LL cnt[1<<22]; //cnt[S]=集合S里每个下标对应字母均相同的字符串集合
double f[1<<22]; //f[S]=已经知道了集合S里的下标对应位置的字母的概率
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%s",s[i]);
m=strlen(s[0]);
for(int i=0;i<n;i++) //这里重复枚举也没事，|运算重复一次的话结果不会改变
for(int j=0;j<n;j++)
if(i!=j)
{
int tmp=0;
for(int k=0;k<m;k++)
if(s[i][k]==s[j][k])
tmp|=(1<<k);
cnt[tmp]|=((LL)1<<(LL)j);
}
for(int S=(1<<m)-1;S>=0;S--) //cnt[S],cnt[S'],若S'是S子集，则cnt[S']|=cnt[S]
for(int i=0;i<m;i++)
if(S&(1<<i))
cnt[S^(1<<i)]|=cnt[S];
double ans=0;
f[0]=1;
for(int S=0;S<(1<<m);S++)
{
int tot=0; //tot=集合S里已经确定的下标个数
for(int i=0;i<m;i++)
if(S&(1<<i))
tot++;
for(int i=0;i<m;i++)
if(!(S&(1<<i)))
{
f[S|(1<<i)]+=f[S]/(m-tot);
}
for(int i=0;i<n;i++)
if(cnt[S]&((LL)1<<(LL)i))
ans+=f[S];
}
printf("%.10lf\n",ans/(double)n);
return 0;
}