2020 ICPC Shanghai Site

嘤嘤嘤。

A. Wowoear

B. Mine Sweeper II

solution

题面:给你两张 $n$ 行 $m$ 列只包含 “X” 与 “.” 的图,你每次可以选择一个位置使它变成另一个字符,最多变化 $\lfloor \frac{n\cdot m}{2} \rfloor$ 次。现希望两张图的每一个 “X” 附近九个位置的 “.” 的数量之和相等,问能否通过变化做到。

做法:尽量想将图二变成图一,若变化次数超过了,则将图二变成图一的反图即可。复杂度 $O(n\cdot m)$。

code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//2021.7.5 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1000+10;
namespace MAIN{
int n,m;
char a[N][N],b[N][N];
int sum;
inline void MAIN(){
n=read(),m=read();
for(res i=1;i<=n;i++)scanf("%s",a[i]+1);
for(res i=1;i<=n;i++)scanf("%s",b[i]+1);
for(res i=1;i<=n;i++)for(res j=1;j<=m;j++)sum+=(a[i][j]!=b[i][j]);
if(sum<=n*m/2){
for(res i=1;i<=n;i++)printf("%s\n",a[i]+1);
return;
}
for(res i=1;i<=n;i++)for(res j=1;j<=m;j++)a[i][j]=(a[i][j]=='X')?'.':'X';
for(res i=1;i<=n;i++)printf("%s\n",a[i]+1);
}
}

C. Sum of Log

solution

题面:给定 $X,Y$,求 $\sum_{i=0}^X \sum_{j=[i=0]}^Y [i\And j=0]\lfloor \log_2(i+j)+1 \rfloor$。

做法:$i\And j=0$ 即意味 $i+j$ 无进位,那么 $\lfloor \log_2(i+j)+1 \rfloor$ 就是最大的数的位数。因此做基础的数位 dp 即可。复杂度 $O(\log \max(X,Y))$。

code
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
//2021.7.5 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
int a[50],b[50],l;
int f[50][2][2][2];
int dp(res len,res lima,res limb,res ze){
#define g f[len][lima][limb][ze]
if(!len)return 1;
if(~g)return g;
g=0;
res mxa=lima?a[len]:1,mxb=limb?b[len]:1;
for(res i=0;i<=mxa;i++)for(res j=0;j<=mxb;j++){
if(i&&j)continue;
add(g,mul(dp(len-1,lima&&i==mxa,limb&&j==mxb,ze&&!i&&!j),(ze&&(i||j))?len:1));
}
return g;
}
inline void MAIN(){
res T=read();
while(T--){
res X=read(),Y=read();
for(l=1;X||Y;X>>=1,Y>>=1,l++)a[l]=X&1,b[l]=Y&1;
memset(f,-1,sizeof(f));
printf("%d\n",Add(dp(l-1,1,1,1),kcz-1));
}
}
}

D. Walker

solution

题面:两个人分别在 $[0,n]$ 的数轴的 $p_1,p_2$ 位置,两人行走的速度分别为 $v_1,v_2$。现希望两人合力踏遍这条数轴的所有位置,问最短时间。

做法:贪心地发现最优的路线只有三种,于是二分时间寻求答案即可。时间复杂度 $O(\log T)$。

code
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
//2021.7.5 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
#define ld long double
ld n,p1,v1,p2,v2;
inline ld cal(RG ld p,RG ld v,RG ld t){
if(v*t<p)return 0;
return max({p,v*t-p,(v*t+p)/2});
}
inline bool ck(RG ld t){
return cal(p1,v1,t)+cal(n-p2,v2,t)>n||cal(n-p1,v1,t)+cal(p2,v2,t)>n;
}
inline void MAIN(){
res T=read();
while(T--){
cin>>n>>p1>>v1>>p2>>v2;
RG ld l=0,r=INF;
for(res i=0;i<=120;i++){
RG ld mid=(l+r)/2;
if(ck(mid))r=mid;
else l=mid;
}
printf("%.12Lf\n",l);
}
}
}

E. The Journey of Geor Autumn

solution

题面:对于一个给定的 $k$,一个排列被称作好排列当且仅当对于 $\forall i>k, st. a_i> \min(a_{i-k},…,a_{i-1})$,求长度为 $n$ 的好排列的个数。

做法:考虑最小的数放在哪里,显然是在前 $k$ 个数的某个位置。假设该位置为 $x$,则前 $x-1$ 个数随意放,后 $n-x$ 个数又形成了一个新的好排列。于是令 $f(x)$ 为长度为 $n$ 的好排列的个数,则有转移式 $f(n)=\sum_{x=1}^k \binom{n-1}{x-1} (x-1)! f(n-x)=(n-1)!\sum_{x=1}^k \frac{f(n-x)}{(n-x)!}$。

稍作化简,有 $n\frac{f(n)}{n!}=\sum_{x=1}^k \frac{f(n-x)}{(n-x)!}$,于是维护一下 $\frac{f(n)}{n!}$ 的前缀和即可。时间复杂度 $O(n)$。

code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//2021.7.5 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e7+10;
namespace MAIN{
int n,k;
int g[N],sumg[N],fac[N],inv[N],pinv[N];
inline void MAIN(){
n=read(),k=read(),fac[0]=fac[1]=inv[0]=inv[1]=pinv[0]=pinv[1]=1;
for(res i=2;i<=n;i++)fac[i]=mul(fac[i-1],i),inv[i]=mul(inv[kcz%i],kcz-kcz/i);
for(res i=2;i<=n;i++)pinv[i]=mul(pinv[i-1],inv[i]);
for(res i=1;i<=k;i++)g[i]=1,sumg[i]=i;
for(res i=k+1;i<=n;i++)g[i]=mul(Add(sumg[i-1],kcz-sumg[i-k-1]),inv[i]),sumg[i]=Add(sumg[i-1],g[i]);
printf("%d\n",mul(g[n],fac[n]));
}
}

F. Fountains

G. Fibonacci

solution

题面:求 $\sum_{i=1}^n \sum_{j=i+1}^n g(f_i,f_j)$,其中 $g(x,y)=1$ 当且仅当 $x\cdot y$ 为偶数,其余情况 $g(x,y)=0$,$f_i$ 为 $f_1=1,f_2=1$ 的斐波那契数列。

做法:容易发现 $f_i$ 为偶数当且仅当 $3|i$,所以原式等于 $\sum_{i=1}^n \sum_{j=i+1}^n [3|i]+[3|j]-[3|i\And 3|j]$,于是就结束了。复杂度 $O(1)$。

code
1
2
3
4
5
6
7
8
9
10
//2021.7.5 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
inline void MAIN(){
res n=read(),p=n/3;
printf("%lld\n",1ll*n*p-(1ll*p*p+p)/2);
}
}

H. Rice Arrangement

solution

题面:一个长度为 $n$ 的菜盘,有些位置有人,有些位置有菜。你可以旋转菜盘,使得所有菜位置 $+1$ 或者 $-1$ ,一个人可以吃一盘菜。求最短旋转次数使得所有人吃到菜。

做法:大胆猜测人与菜的对应是按序的,通过调整法发现这是正确的。实现的时候注意菜盘可以顺时针转也可以逆时针转,不过逆时针等价于 $n-$ 顺时针转,所以就做好了。时间复杂度 $O(k^2)$。

code
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
//2021.7.5 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e3+10;
namespace MAIN{
int a[N],b[N];
int c[N];
int k;
inline void MAIN(){
res T=read();
while(T--){
kcz=read(),k=read();
for(res i=1;i<=k;i++)a[i]=read();
for(res i=1;i<=k;i++)b[i]=read();
sort(a+1,a+k+1),sort(b+1,b+k+1);
for(res i=1;i<=k;i++)a[i+k]=a[i];
RG LL ans=INF;
for(res p=1;p<=k;p++){
//1 -> p
for(res i=1;i<=k;i++)c[i]=Add(a[i+p-1],kcz-b[i]);
sort(c+1,c+k+1),ans=min({ans,1ll*c[k],1ll*kcz-c[1]});
for(res i=1;i<k;i++)ans=min({ans,1ll*kcz-c[i+1]+2ll*c[i],1ll*c[i]+2ll*(kcz-c[i+1])});
}
printf("%lld\n",ans);
}
}
}

I. Sky Garden

solution

题面:有 $n$ 个同心圆 $m$ 条线,第 $i$ 个圆半径为 $i$,线平分圆。求所有交点间最短距离的和。

做法:

code
1
2


J. Octasection

K. Traveling Merchant

L. Traveling in the Grid World

solution

题面:有一张 $(0,0)$ 到 $(n,m)$ 的格点图,可以从 $(x,y)$ 直接到 $(p,q)$ 当前仅当这条线段没经过其它格点,求 $(0,0)$ 到 $(n,m)$ 的最短线段长度和。

做法:

code
1
2


M. Gitignore

solution

题面:给出若干棵有根树,其中一部分的叶子必须删除,一部分的叶子不能删除。删除一个节点等价于删除这个子树的所有叶子,问最少的删除次数。

做法:贪心来看,自根向下搜索,当前子树能删就删一定是最优的。时间复杂度 $O(\sum len)$。

注意读入时不同节点的名字可以相同,所以要连着前面读入。

code
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
//2021.7.5 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e3+10;
namespace MAIN{
int n,m;
string s,t;
map<string,int> M;
int tot;
vector<int> G[N];
int a[N],ax;
int fa[N];
int fl[N],Fl[N];
void dfs(res x){
for(auto tox:G[x]){
dfs(tox);
if(Fl[tox])Fl[x]=1;
if(fl[tox])fl[x]=1;
}
}
int ans;
void Dfs(res x){
if(fl[x]&&!Fl[x]){ans++;return;}
for(auto tox:G[x]){
Dfs(tox);
}
}
inline void MAIN(){
res T=read();
while(T--){
for(res i=1;i<=tot;i++)fl[i]=Fl[i]=fa[i]=0,G[i].clear();
M.clear();
n=read(),m=read(),tot=ans=0;
for(res o=1;o<=n;o++){
cin>>s,ax=0;
res sz=int(s.size());
for(res i=0;i<sz;i++){
t+=s[i];
if(s[i]=='/'){
if(!M.count(t))M[t]=++tot;
a[++ax]=M[t];
}
}
if(!M.count(t))M[t]=++tot;
a[++ax]=M[t],fl[M[t]]=1;
for(res i=ax;i>1;i--)fa[a[i]]=a[i-1];
t="";
}
for(res o=1;o<=m;o++){
cin>>s,ax=0;
res sz=int(s.size());
for(res i=0;i<sz;i++){
t+=s[i];
if(s[i]=='/'){
if(!M.count(t))M[t]=++tot;
a[++ax]=M[t];
}
}
if(!M.count(t))M[t]=++tot;
a[++ax]=M[t],Fl[M[t]]=1;
for(res i=ax;i>1;i--)fa[a[i]]=a[i-1];
t="";
}
for(res i=1;i<=tot;i++)if(fa[i])G[fa[i]].pb(i);
for(res i=1;i<=tot;i++)if(!fa[i])dfs(i);
for(res i=1;i<=tot;i++)if(!fa[i])Dfs(i);
printf("%d\n",ans);
}
}
}