heyZzz's OI Blog

思路 我们注意到答案串一定是若干个可以变成一个可以做出 $k$ 个合法的括号序列的长度 $\le n$ 的序列再补上若干个 )。 显然，设答案串 $s$ 有 $k$ 对括号在最外层，那么合法子串个数为 $\frac{k(k+1)}{2}$。我们就可以构造了！ 这样就可以在不浪费括号的情况下将答案串分成多个括号串。 设 $dp_i$ 为构造出 $i$ 个合法子串（即 $k$）所需的最小括号对数。 状态转移就是：$dp_i=dp_{i-\frac{j(j+1)}{2}}+j$。 我们先把这部分预处理出来。 如果 $2dp_k>n$ 则说明无解，否则在 dp 数组上递归构造（如果$dp_i=dp_{i-\frac{j(j+1)}{2}}+j$，那么就转移）。 代码： 1234567891011121314151617#include<bits/stdc++.h>#define int long longusing namespace std;int T,n,k,dp[100005];void print(int x){ if(!x) return; ...

用 BFS。 思路 我们可以使用一个长度为 $3\times3$ 的 string 来表示状态，每一种状态可以进行旋转（左上，右上，左下，右下）。 我们可以用 map 来记录状态。 预处理一下即可。 代码： 12345678910111213141516171819202122#include<bits/stdc++.h>#define int long longusing namespace std;map<string,int> mp; int T,n; char c;signed main(){ cin>>T; queue<string> q; //bfs q.push("123456789"),mp["123456789"]=1; while(q.size()){ string u=q.front(),v[4]={u,u,u,u}; q.pop(); v[3][4]=u[5],v[3][5]=u[8],v[3][7]=u[4],v[3][...

思路 因为对于任意分店 $i$ 和 $j(1\le i,j\le2025)$，它们的客流量上限 $A_i$ 和 $A_j$ 的乘积不得超过 $ij+2025$。 所以，对于任意分店 $i$，$A_i\le\sqrt{i^2+2025}$。 我们直接打表： 1for(int i=1;i<=2025;i++) cout<<(int)sqrt(i*i+2025)<<' '; 发现在 $i\ge1013$ 时 $A_i \le i$。 那么当 $1\le i<1013\le j\le2025$ 时，$A_iA_j=A_ij,A_iA_j\le ij+2025$。 两边同除 $j$：$A_i\le i+\frac{2025}{j}$。 发现：$A_i\le i+\lfloor\frac{2025}{j}\rfloor$。 由于 $1013\le j\le2025$，所以，$A_i\in[1,i+1]$。 所以我们可以得出： $A_1$ 有 $2$ 种选择； $A_k$ 为了不与 $A_1$~$A_{k-1}$ 选的重复，总是有 $i+...

前言 作者是 xxs，考不了 CSP。 做法 照题意模拟即可。 就是将所有人的成绩和序号放在一个结构体中，再排序。 再求出第 $i$ 行第 $j$ 列是名次为几的人即可。 如下图： 1 8 9 16 2 7 10 15 3 6 11 14 4 5 12 13 用 dfs 跑一遍，再在图中找序号为 $1$ 的名次，输出行和列。 代码： 12345678910111213141516171819202122232425#include<bits/stdc++.h>#define int long longusing namespace std;int n,m,d[15][15],tot,x;//d 序号矩阵，tot 当前序号，x 编号为 1 的数排好序之后的位置。struct stu{int x,id;}a[105];bool cmp(stu x,stu y){return x.x>y.x;};void dfs(int x,int y){ //dfs 求出序号矩阵。 if...