XJTU ICPC Team Selection - Summer 2021 - Day3

A: Appearance Analysis

1s

Description

给你一个这样的窗户照片：
################
#....#++++#+...#
#....#++.+#+...#
#....#.++.#++.+#
#....#....#++++#
################
#....#.+..#++++#
#..++#.+..#++.+#
#+...#....#.++.#
#+...#..++#....#
################
“#”是窗玻璃边缘，“+”表示有色的，“.”表示无色的
保证每片玻璃一样大
求有多少片不同的玻璃（旋转后完全重合算相同，不能翻转）
行、列数\(\leq 111\)

Solution

模拟

B: Bipartite Blanket

3s

Description

给你一个二分图 \(n\)个白点 \(m\)个黑点 ，每个点有点权。
从里面选出若干黑点和若干白点使得它们可以完美匹配且点权之和大于等于\(t\)，问有多少种选法
\(1\leq n,m\leq 20\)

C: Convex Contour

1s

Description

有一排连着的\(n\)个单位正方形，每个正方形里面有下面图形中的一个：

• 填满单位正方形的正方形
• 内切圆
• 以单位正方形下底为边的正三角形
  求这一列图形的凸包

Solution

可能是个计算几何题但我拿解析几何做的
考虑两种情况

1. 全是三角形：答案是\(2n+1\)
2. 不全是：
   找到左边第一个不是三角形的和右边第一个不是三角形的
   它们之间的一定是两条线段
   它们两侧的分两种情况：
   • \(x\)个三角形+正方形
   • \(x\)个一串三角形+圆形
     具体怎么算直接贴代码吧

double calc(int x,bool b){//b=true表示圆，false表示正方形
    if(x==0) return b?pi/2:2;
    if(b){
        long double OP2=x*x+(D-1)*(D-1)/4;
        long double AP=sqrt(OP2-0.25);
        long double alpha=atan((D-1)/(2*x)),beta=acos(0.5/sqrt(OP2));
        long double AB=(pi/2-alpha-beta)*0.5;
        return AB+AP+x+1.5;
    }
    else
        return x+2+sqrt(  (x-0.5)*(x-0.5) + (1-D/2)*(1-D/2)  );
}

D: Dancing Disks

E: Easy Equation

F: Free Figurines

1s

Description

给你\(n\)个俄罗斯套娃，从\(1\)到\(n\)依次增大。只能把小的放大的里面。不在任何其他套娃里的套娃是自由的。你可以：

• 把一个自由的套娃放进一个更大的空的自由的套娃中
• 打开一个非空的自由的套娃并把直接位于其中的套娃拿出来
  一组套娃的状态可以用一个数组表示：p[i]表示套娃i外层的套娃，自由的套娃对应的p[i]=0。
  告诉你初始状态和结束状态，求最少需要几步到达结束状态

Solution

定义操作 free(x)--将套娃\(x\)变为自由的 :
1.若p[x]不自由,free(p[x])
2.p[x]=0
首先，将所有初始状态和结束状态不同的套娃变为自由的。
其次，从小到大，将所有当前状态和结束状态不同的套娃直接变为结束状态（若其结束状态对应的p[i]不自由则还要先free(p[i])）。

G: Geohash Grid

H: Hangar Hurdles

8s

Description

你正在评估一些关于一个巨型飞机仓库的建设计划。飞机仓库的地面可以表示为n行n列的网格图，其中每个格子要么是空的，要么有障碍物。行从上到下依次被编号为1到n，列从左到右依次被编号为1到n。

存放飞机零件的大型集装箱能在飞机仓库的地面上自由移动是很重要的。我们可以将每个集装箱看作一个以某个格子为中心的边平行于坐标轴的正方形。对于一个奇数k，一个尺寸为k的集装箱是一个包含k行k列的正方形。一个集装箱的坐标为其中心格子的坐标。集装箱可以向上下左右移动，但不能碰到障碍物，且不能移出仓库的边界。

给定q对格子A_k和B_k，对于每对格子，请找到能从A_k移动到B_k的集装箱的最大尺寸，注意这个尺寸也要是一个奇数。（转自洛谷）
\(1\leq n\leq 1000\) ， \(1\leq q\leq 300000\)

Solution（非正解）

先bfs预处理每个点能容纳的最大箱子尺寸
然后枚举箱子尺寸：并查集维护对于当前尺寸能联通的格子，对于每组询问，若能到达则更新答案。

I: Invisible Integers

J: Jazz Journey

K: Key Knocking

1s

Description

定义一段01串's[0:3n]'的权重为：\(1+\sum_{1\leq i<3n} s[i]!=s[i-1]?1:0\)
你可以这样修改字符串：选定两个相邻的字符，将它们都取反。
请你通过至多\(n\)次操作使字符串的权重达到至少\(2n\)。
\(1\leq n\leq 100000\)

Solution

从左到右扫一遍，若找到"111x"或"000x"则将最后的"1x"或"0x"取反。
若整个字符串结尾是"000"或"111"，则改为"011"或"100"。
再从左到右扫一遍，若找到"0011"或"1100"则改为"0101"或"1010"，若修改次数达到上限则停止。
可以证明 前两步通过至多\(\lfloor\frac{n}{2}\rfloor\)次将权重提至至少\(\lfloor\frac{3n}{2}\rfloor\)
第三步每次可以将权重提高至少\(1\)，若修改次数达到上限则权重达到至少\(2n\)。若未达到上限说明已经不存在"0011"或"1100"可以证明此时权重也达到了\(2n\)。

L: Lost Logic