做题记录（8月）

· · 个人记录

test 807

dice

题目大意

构造 n 个六面骰子使得所有朝上的数字的异或和为 k 的倍数

solution

注意到 d \leq 60，可以考虑使用64进制解决

对于一个 64 进制的数，如果每一位都是 k 或 0，那么这个数一定是 k 的倍数

具体构造方法：

6个数为：\overline{0}, \overline{k}, \overline{k0}, \overline{kk}, \overline{k00}, \overline{k0k} （64进制）

cut

题目大意

定义 mex 为一个集合 S 中没有出现的最小的非负整数，求将长度为 n 的序列剪成 k 段后的最大权值之和

solution

dp$ ,用 $f[i]$表示前 $i$ 个数的最大权值，不难发现 $f[i]=max(f[i-1],mex(i,j))$,时间复杂度为 $O(n^2)

发现权值最大为21，dp[i]又单调不降，所以在每次转移的时候可以枚举最后一段的 mex 值，时间复杂度可以做到 O(nV)

hamilton

solution

每个点入出度都为1,可以使用最大流

建图方法：S \rightarrow i ， i \rightarrow i + n ， i + n \rightarrow t

如果最后最大流等于 n，说明恰好找到，对于每个容量为 0 的边，记录下来，然后就可以把环找出来了。

否则，就说明无解。

test 809

genshin

题目大意

有 n个人已知他们的速度，听力和初始位置，选一个数使得每人都能听到你声音且最小化移动距离

solution

对于一个人能听到的范围为 [p_i-d_i,p_i + d_i]，我们记为 [L_i,R_i]。

花费可以表示为 \sum_{i=1}^{n}min(|c - L_i|,|c-R_i|)\times w_i

很明显它是一个单峰函数，线性函数可以使用二分，单峰函数可以考虑使用三分，枚举答案再 check

while(l<=r) {
        lc=l+(r-l)/3;
        rc=r-(r-l)/3;
        int lans=work(lc),rans=work(rc);
        if(lans<=rans) {
            ans=min(lans,ans);
            r=rc-1;
        } else {
            ans=min(ans,rans);
            l=lc+1;
        }
    }

arknights

solution

题目规定一个斜线最多出现一个棋子,但并不是很好处理，我么可以我们取出其黑色部分，然后旋转90度。

可以考虑 dp ,从两端同步向中间转移，时间复杂度 O(nk)

arena

观察条件 \text{mex}(a_l,a_{l+1},...,a_r)\le \text{med}(a_l,a_{l+1},...,a_r)。

从 mex 入手，假如 [0,d] 都在该区间出现过，那么 mex > d，不妨假设 med = d，这样求出来的区间就是答案区间的补集，容斥即可。

时间复杂度 $O(n)$ 。 ### 穹轨(rail) #### 题意 对于两个串 $S_1, S_2$，如果能够将 $S_1$ 的一个后缀移动到开头后变成 $S_2$，就称 $S_1$ 和 $S_2$ 循环相同。例如串 ababba 和串 abbaab 是循环相同的。 给出一个长度为 $n$ 的串 $S$，求满足下面条件的最大的 $L(L\leq \frac n 2)$：$S$ 的 $L$ 前缀和 $S$ 的 $L$ 后缀是循环相同的。 #### solution 考虑暴力怎么做，我们枚举在字符串的首位删去等量字符，然后求出剩余部分的最长相等前后缀，如果删去的两段相等，那么就对于答案有贡献。 定义$f[i]$表示删去$i$个字符后剩余部分的最长相等前后缀，那么就有这个限制： $f[i+1]+2 \geq f[i]$ 这个画个图就可以证明了，有了这个限制，我们就可以$O(n)$的求出$f$数组，对于判断相等就$hash$一下就好了。 # test 0811 ## perm 本题要我们统计有多少 $m$ 阶排列比自己的逆排列字典序小 设 $f_i$ 表示 $i$ 阶排列的数量是 $f_i$, 如果所有轮换大小不超过2，那么组成的排列 的逆排列就是自己 不难发现一个简单的递推式子，$f_n=f_{n-1}+(n-1)\cdot f_{n-2}

test 0812

网格行走(path)

题意

给定一个 n\cdot m 的网格，每个网格有一个权值 v 每次可以向下走或向又走，定义价值为所有经过点的 mex 值，你需要求出所有 行走路径中价值的最大值 。

solution

如果我们想要 mex 大于等于 d , 就需要经过 1-d 所在的所有点

考虑二分 d 。二分 d 之后我们可以将对应点直接排序，相邻点满足 x,y 不降即可，时间复杂度 O(nm\log nm)

lock

题意

给一个有四个拨圈的锁，这种密码锁被解锁当且仅当拨圈每四个对应位置之和相等。判断密码锁是否能打开

solution

虽然有四个拨圈，但其实只需要转动三个拨圈即可。

令 a_{1,i}+a_{2,i}+a_{3,i}+a_{4,i} = P，一个有 n 个这样的等式，将这 n 个等式加起来得到 sum = P \times n，P 就很容易求出来了。

剩下三个拨圈的和为 T-a_{1,i}，由于拨圈是循环的，可以把第二行，第三行，第四行的数复制一遍放在后面。如果直接暴力拨动三行是会超时的，不如只拨动第二行和第三行，查找满足条件的解是否出现过。

test 0814

C. 你所热爱的就是你的生活(ll.cpp)

solution

直接爆搜肯定会超时，靠虑折半搜索，把区间 [1,n/2],[n/2+1,n] 分别搜索一次，得到两个集和 S,T，表示两个区间能凑成的总票价。再用双指针优化一下就可以跑过去了

test 0816

数学（math）

题意

<img src="https://s1.ax1x.com/2023/08/15/pPQnScd.png" alt="image-20230815171924641" style="zoom:50%;" />

子弹从点 N 射出，沿<u>水平方向</u>到达点 O，反射而出，在 M 处击中死者后脑勺。

你认为，若在射线 ON 上，有两个定点 A, B。 一定会<u>有且仅有一个点</u>P 在射线 OM 上使得 ∠APB 达到最大值。

现在我们需要你对于每一组询问求出 P 点坐标。

solution

有是2一道纯数学题，没有用到任何三角函数，单纯几何知识

如图构造一个圆EAB，此时∠AEB最大

不难发现 \DeltaEAO相似与 \DeltaOEB,得出 OE^2=OA\times OB

求出 OA的长度即可求出坐标

while(t--){
        double xa,xb,ya,yb,xm,ym;
        cin>>xa>>ya>>xb>>yb>>xm>>ym;
        double s=sqrt(xa*xb);
        double t=sqrt(xm*xm+ym*ym);
        double k=s/t;
        cout<<fixed<<setprecision(7)<<xm*k<<" "<<ym*k<<endl;
    }

test 0818

手语的（gnsi）

题意

给你一个平面。

给你三个正交矩形和一个点，问是否存在一个三角形，使得该三角形的三个顶点分别在三个正交矩形内，且该三角形的重心为给定点。

正交矩形：四条边都平行于坐标轴的矩形。

solution

众所周知，在重心为三角形三条中线的交点，在平面直角坐标系中，\Delta A B C A(x_1,y_1),B(x_2,y_2),C(x_3,y_3)的重心为三个顶点的算术平均数，即 G(\frac{x_1+x_2+x_3}{3},\frac{y_1+y_2+y_3}{3}),再结合样例说明就十分显而易见，那么只需将重心坐标分别乘三，然后计算三个矩形内的最小和最大坐标和，判断是否在这个合法区间内即可。

while(t--){
        minx=miny=maxx=maxy=0;
        for(int i=1;i<=3;i++){
            cin>>_x1[i]>>_x2[i]>>_y1[i]>>_y2[i];
            minx=minx+min(_x1[i],_x2[i]);
            maxx=maxx+max(_x1[i],_x2[i]);
            miny=miny+min(_y1[i],_y2[i]);
            maxy=maxy+max(_y1[i],_y2[i]);
        }
        int x,y;
        cin>>x>>y;
        x*=3;y*=3;
        if(x>=minx&&x<=maxx&&y>=miny&&y<=maxy)
            cout<<"heihei"<<endl;
        else cout<<"yiyandingzhen"<<endl;
    }

A. 序列(sequence)

solution

从 x 的视角来看，大于 x 的数必须是单调上升的一个序列

而小于 x 的数必须是单调下降的一个序列

我们可以记 f_i表示以 i 开头的单调上升序列的数量

显而易见，$ans=\sum_{i=1}^{n} f_i\cdot g_i$ ,复杂度可以做到$O(n^3) f_i=\sum _{j=i+1}^{n}f_j(a_j>a_i) g_i=\sum_{j=i+1}^{n}g_i(a_j<a_i)

最后在用树状数组维护，复杂度可以做到 O(N \log N)，可以通过

test 0819

序列II(quencese)

题意

你现在有一序列 A，里面有一个数 x。

设末尾的数是 y。你可以在 1 到 \lfloor\sqrt y\rfloor 中选取一个数 z 加到序列的末尾。

如此进行 114514 次操作，问一共有多少种可能的情况，答案对 998244353 取模。

solution

设 f_x 表示以 x 为开头的不同序列的数量，一个很显而易见的转移

f_x=\sum_{i=1}^{\lfloor\sqrt{x}\rfloor} f_i

时间复杂度 O(\sqrt n),数据范围是 10^{18} ,可以考虑再开一次根号

我们直接枚举第三个元素 A_3 ,假设 A_1=x,A_3=i ,显然 A_2\in [i^2,\sqrt x]

f_x=\sum_{i=1}^{\lfloor\sqrt[4]{x}\rfloor}(\lfloor\sqrt{x}\rfloor-i^2+1)\cdot f_i

时间复杂度 O(\sqrt[4]{n})

int f(int i) {
    if(g[i] != 0) return g[i];
    if(i == 1) return 1;
    int s = 0;
    for(int j = 1; j <= sqrt(i); j++) s = (s + f(j)) % mod;
    return g[i] = s;
}
int get2(int n) {
    int num = sqrt(n);
    return sum[num];
}
int get(int n) {
    int p = sqrt(n); 
    int q = sqrt(p);
    int ans = 0;
    q--;
    for(int i = 1; i <= q; i++) 
        ans = (ans + get2(i * i) * (2 * i + 1) % mod) % mod;
    q++;
    ans = (ans + (p - q * q + 1) * get2(q * q) % mod) % mod;
    return ans;
}
signed main() {
    cin >> T;
    for(int i = 1; i <= 100000; i++) {
        sum[i] = sum[i - 1] + f(i);
    }   
    while(T--) {
        cin >> n;
        cout << get(n) << endl;
    }

数学(math)

题意

给定 n, 求出正整数对 (x, y) 的对数, 满足 xy + 1|x^2 + y^2，1 ≤ x ≤ y ≤ n。

solution

一道纯数学题 ，要用韦达定理来证明

韦达定理:

ax^2+bx+c=0 \\ x_1+x_2=-\frac{a}{b} \\ x_1x_2=\frac{a}{c} xy + 1|x^2 + y^2$,可以假设 $x^2+y^2=k(xy+1 )$,$k\in \mathbb Z

多个未知数的高次方程不难想到用主元法，我们以 x 为主元再降幂排列后可以的到

x^2-kxy+y^2-k=0

利用韦达定理易知

x_1+x_2=-\frac{a}{b}=kxy

所以一组解为(x,x^3)另一组结尾 (y,ky-x)

test 0822

A. 压轴题（hard）

水题，暴力打表后发现答案都是 p^x 次方，用类似并查集的方式合并一下，统计答案就行了

B. 极端题（extreme）

题意

给定一个数列，每次可以把一个数分拆成两个正整数，求它的每个子数组变成不降数列的最小操作数之和

solution

​

test 0823

A. 简化题面 (statement)

题意

对一个数进行操作把这个数字按照不降序进行排列，之后把所有的前导零去掉。 对 [L,R] 里的数都进行操作，最后能得到多少不同的数。

看见题目里面的区间 [L,R]，很容易就会想到去采用一般数位 dp 套路中差分的方式。但仔细过后会发现不好统计前缀数量。所以要考虑采用别的思路解决问题。 仔细观察答案的数量，用搁板法考虑零到九分别分配多少位置数量发现答案的总数最多是 C_{27}^{9}。数量级在 5\times10^6 以内。 可以通过暴搜搜索出所有的分配情况，然后用 check 的方式判断该方式组成的数字会不会在区间 [L,R] 之内。 搜索的方式如下：

void dfs(int u,int left){
    if(u==9){
        nums[u]=left;
        if(check(len,true,true)){
            ans++;
        }
        return;
    }
    for(int i=0;i<=left;i++){
        nums[u]=i;
        dfs(u+1,left-i);
    }
}

搜索出了答案我们可以考虑如何做到快速判断答案的是否正确。我采用数位 dp 的思路，定义状态为 f[pos][limit1][limit2] 分别表示从高位处理到低位的位置,直接记忆化搜索就完毕

B. 题面不长(nothing)

题意

给定 n,k 和 m。对于每个大小在 [1, n] 中的 x，求每个元素大小在 [1, n] 中，平均数为 x 且相同元素不超过 k 个的可重集的数量，对 m 取模。 > > 1\le n, k\le100，m 为质数。

solution

如果集合中的平均数为 x ,集合数量为 cnt ,那集合中的元素和就为 x\cdot cnt,我们先令 x=0，于是问题变成了在 [1 - x, n - x] 中选出一些数，这些数和为 0 且重复元素个数不超过 k。

要让和为 0， 可以选 0 个到 k 个，前 x-1 个数的绝对值的和等于后 n-x 个数的绝对值的和。

令 dp_{i, j} 表示前 i 个数和为 j 的方案数

可以用前缀和优化的多重背包求出 dp_{i, j}

ans=(k+1) * \sum_{j = 0}^{\frac {n*k*(n+1)} {2}} dp_{i - 1, j} * dp_{n - i, j} - 1

时间复杂度 O(n^{2}k)。

C. 题面很短 (short)

题意

对于字符串 s，定义 f(s) 为 s+rev(s)，其中 rev(s) 表示 s 的反串。例如，f(\text{mea})=\text{meaaem} 。

给定字符串 t。求出最短的字符串 s，使得 s 经过若干次 s\rightarrow f(s) 后 s 能够变成 t。其中 s\rightarrow f(s)表示将 s 变成 f(s)。

solution

签到题，每次二分后进行比对就行，数据很水

string fz(string a) {
    int cnt=0;
    string b="";
    for(int i=a.size()-1; i>=0; i--) {
        b+=a[i];
    }
    return b;
}

​