链接
Educational Codeforces Round 57
A
由于题目保证有解,所以直接输出(l,2*l)就行了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
using namespace std;
int T,x,y;
template <typename T> void read(T&t) {
t=0;
bool fl=true;
char p=getchar();
while (!isdigit(p)) {
if (p=='-') fl=false;
p=getchar();
}
do {
(t*=10)+=p-48;p=getchar();
}while (isdigit(p));
if (!fl) t=-t;
}
int main(){
read(T);
while (T--){
read(x),read(y);
printf("%d %d\n",x,2*x);
}
return 0;
}
B
由于删除的是一个子串,所以最后留下的一定是个前缀或者后缀,那么我们就先暴力算出前缀的前多少位一样,后缀的最后多少位是一样的,设为a1和a2。
由于题目保证整个串中至少出现两种字符,所以$a1+a2$一定$\le n$
再看一下整个串的第一位和最后一位是否一样,如果相等,那么答案就是$(a1+1)*(a2+1)+1$
否则输出$a1+a2+1$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
using namespace std;
int n,a1,a2;
char s[N],pp;
template <typename T> void read(T&t) {
t=0;
bool fl=true;
char p=getchar();
while (!isdigit(p)) {
if (p=='-') fl=false;
p=getchar();
}
do {
(t*=10)+=p-48;p=getchar();
}while (isdigit(p));
if (!fl) t=-t;
}
int main(){
read(n);
scanf("%s",s+1);
pp=s[1];
a1=1;
for (int i=2;i<=n;i++){
if (s[i]==pp) a1++;
else break;
}
for (int i=n;i>=1;i--){
if (s[i]==s[n]) a2++;
else break;
}
if (s[n]==pp){
printf("%d",1ll*(a1+1)*(a2+1)%998244353);
}
else{
printf("%d",a1+a2+1);
}
return 0;
}
C
由于数据范围较小,我们考虑直接枚举正i边形是否可行。
判断的话要根据两个条件,
(1) $n*i%180==0$,我要是这个i边形内最小角的倍数
(2) $n*i<=(i-2)*180$,不能大于这个正i边形的最大内角1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
using namespace std;
int T,n;
template <typename T> void read(T&t) {
t=0;
bool fl=true;
char p=getchar();
while (!isdigit(p)) {
if (p=='-') fl=false;
p=getchar();
}
do {
(t*=10)+=p-48;p=getchar();
}while (isdigit(p));
if (!fl) t=-t;
}
int gcd(int a,int b){
while (a%b!=0){
int tmp=b;
b=a%b;
a=tmp;
}
return b;
}
int main(){
read(T);
while (T--){
read(n);
bool flag=0;
for (int i=3;i<=360;i++){
if (n*i%180==0&&n*i<=(i-2)*180){
flag=1;
printf("%d\n",i);
break;
}
}
if (!flag) puts("-1");
}
return 0;
}
D
考虑直接dp,f[i][j]表示到了第i个字符,hard这个结构只拥有前j个字符的最小代价,显然j的范围是$[0,3]$。
转移的话看下第i个是不是”h”,”a”,”r”,”d”中的一个,如果是的话要花这个代价删除,直接看代码吧。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
using namespace std;
int n;
int a[N];
LL f[N][5];
char c[N];
template <typename T> void read(T&t) {
t=0;
bool fl=true;
char p=getchar();
while (!isdigit(p)) {
if (p=='-') fl=false;
p=getchar();
}
do {
(t*=10)+=p-48;p=getchar();
}while (isdigit(p));
if (!fl) t=-t;
}
int main(){
read(n);
scanf("%s",c+1);
for (int i=1;i<=n;i++) read(a[i]);
for (int i=1;i<=n;i++){
f[i][0]=f[i-1][0];
for (int j=1;j<=3;j++) f[i][j]=min(f[i-1][j],f[i][j-1]);
if (c[i]=='h') f[i][0]=f[i-1][0]+a[i];
else if (c[i]=='a') f[i][1]=f[i-1][1]+a[i];
else if (c[i]=='r') f[i][2]=f[i-1][2]+a[i];
else if (c[i]=='d') f[i][3]=f[i-1][3]+a[i];
//printf("%lld %lld %lld %lld\n",f[i][0],f[i][1],f[i][2],f[i][3]);
}
LL minn=1e18;
for (int j=0;j<=3;j++) minn=min(minn,f[n][j]);
printf("%lld",minn);
return 0;
}
E
考场上没来得及看,待更
F
由于期望的线性性,我们可以把整个期望的贡献分成三类,-1对-1,其他数字与其他数字,-1与其他数字。
对于第一类贡献,令$f[i]$表示$[1,i]$的排列,逆序对数量的期望,考虑加入第i+1个数,放在最前面会产生i的贡献,向后移一位贡献-1,一共有i+1个位置可以放,分别能产生i,i-1,i-2…0的贡献,所以$f[i+1]=f[i]+\frac{(i+1)*i}{2*(i+1)}$,化简为通项式可得$f[i]=\frac{i*(i-1)}{4}$
对于第二类贡献,直接树状数组求逆序对可得。
对于第三类贡献,我们实际上就是考虑每个-1填每个数贡献的和,注意这里的贡献不能直接加。
设-1的个数为tot,我们确定了这一位,贡献为x,剩下(tot-1)位不管怎么取对贡献没有影响,所以$x*((tot-1)!)$是最后的贡献,再除以$tot!$就是期望,即$\frac{x}{tot}$。
但是这个贡献并不好算,我们考虑每个已经确定的数对-1的贡献,显然是我前面-1的个数乘上比我大的没取的数的个数,加上我后面-1的个数乘上比我小的没取的数的个数,把每一位的这个贡献sigma起来,乘以一个总-1数tot的逆元加到最后答案里就好了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
using namespace std;
template <typename T> void read(T&t) {
t=0;
bool fl=true;
char p=getchar();
while (!isdigit(p)) {
if (p=='-') fl=false;
p=getchar();
}
do {
(t*=10)+=p-48;p=getchar();
}while (isdigit(p));
if (!fl) t=-t;
}
int n,tot,ans,jc=1,res,inv;
int a[N],T[N],sum[N];
bool vis[N];
const int P=998244353;
inline void add(int x){
for (int i=x;i<=n;i+=i&-i) T[i]++;
}
inline int query(int x){
int ret=0;
for (int i=x;i;i-=i&-i) ret+=T[i];
return ret;
}
int ksm(int a,int b){
if (b==0) return 1;
int ret=1;
while (b>1){
if (b&1) ret=1ll*ret*a%P;
b>>=1;
a=1ll*a*a%P;
}
return 1ll*a*ret%P;
}
signed main(){
read(n);
for (int i=1;i<=n;i++){
read(a[i]);
if (a[i]==-1) tot++,jc=1ll*jc*tot%P;
else vis[a[i]]=1;
}
ans=1ll*tot*(tot-1)%P*ksm(4,P-2)%P;
res=tot;
inv=ksm(tot,P-2);
for (int i=n;i>=1;i--){
if (a[i]!=-1) ans=(ans+query(a[i]-1))%P,add(a[i]);
}
for (int i=1;i<=n;i++){
sum[i]=sum[i-1];
if (!vis[i]) sum[i]++;
}
for (int i=1;i<=n;i++){
if (a[i]==-1) res--;
else{
ans=(ans+(1ll*sum[a[i]]*res%P+1ll*(tot-sum[a[i]])*(tot-res)%P)%P*inv%P)%P;
}
}
printf("%lld",ans);
return 0;
}
G
第一感是dp,以f[i][j]表示已经确定了前i个数,前一半与后一半的差为j的方案数,但是这个差值可能会非常大,这个状态存不下。
考虑生成函数。
例如能去0,2,3,5,9,我们就用多项式$x^0+x^2+x^3+x^5+x^9$来表示,令这个多项式的n/2次幂为f,那么f中$x^k$的系数就可以表示组成k的方案数了。
至于多项式的幂次可以不用分治+NTT
考虑NTT第一步的本质,就是把系数表达式转化成点值表达式。众所周知点值是可以直接乘的,那么直接把NTT过的点值快速幂后NTT回来就行了。
最后的答案就是每一项系数的平方的和1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
using namespace std;
template <typename T> void read(T&t) {
t=0;
bool fl=true;
char p=getchar();
while (!isdigit(p)) {
if (p=='-') fl=false;
p=getchar();
}
do {
(t*=10)+=p-48;p=getchar();
}while (isdigit(p));
if (!fl) t=-t;
}
const int P=998244353;
int n,k,x,ans,lim;
int f[N],R[N],b[N];
int ksm(int a,int b){
int ret=1;
while (b>1){
if (b&1) ret=1ll*ret*a%P;
b>>=1;
a=1ll*a*a%P;
}
return 1ll*ret*a%P;
}
inline void NTT(int *f,int G){
for (int i=0;i<lim;i++){
if (i>R[i]) swap(f[i],f[R[i]]);
}
for (int i=1;i<lim;i<<=1){
int w0=ksm(G,(P-1)/(i<<1));
for (int j=0;j<lim;j+=(i<<1)){
int w=1;
for (int k=j;k<j+i;k++){
int t=1ll*f[k+i]*w%P;
f[k+i]=(f[k]-t+P)%P;
f[k]=(f[k]+t)%P;
w=1ll*w*w0%P;
}
}
}
}
int main(){
read(n),read(k);
lim=4194304;
for (int i=0;i<lim;i++) R[i]=(R[i>>1]>>1)|((i&1)*lim>>1);
for (int i=1;i<=k;i++){
read(x);
f[x]=1;
}
NTT(f,3);
for (int i=0;i<lim;i++){
b[i]=ksm(f[i],n/2);
}
NTT(b,ksm(3,P-2));
int inv=ksm(lim,P-2);
for (int i=0;i<lim;i++) b[i]=1ll*b[i]*inv%P;
for (int i=0;i<lim;i++){
ans=(ans+1ll*b[i]*b[i]%P)%P;
}
printf("%d",ans);
return 0;
}