CSP J 复赛游记
2026-10-01 20:20:52
发布于：湖北
这个区忘了 ST 表，导致 S 初赛被周飞，所以只有 J 打了。
标题何意味.
由于和上一篇训练目的不同，所以单开。
9.24
P7909
时候不早了，随便挑个橙玩玩。
因为要找到最大的 ，如果 除以 的商下取整相等，则在满足 的情况下 越大越好，于是我们取 。否则， 最大值明显为 ，直接输出 即可。
代码
namespace yxdl1{
void solve(){
int n,l,r;
std::cin >> n >> l >> r;
if(l/n==r/n)std::cout << r%n;
else std::cout << n-1;
}
}
复杂度分析
略
9.25
中秋快乐各位。
13 天假期必须好好补一补 whk 了，也（打算）报了洛谷的课程。但先玩几天（
在酒店看一会 J/S 的题目讲解
9.26
是谁写了一沙滩的毕导。
晚上帮 cchu 调代码，顺便讲一下吧。题目是今晚 ABC 的 D。
这种类型的题目 ABC 似乎出烂了，AtCoder 你只是怕了。
显然 lazy tag 优化，直接线性创飞了。
然后你会收到 AC18，WA13 的好成绩。
下面给一组 hack：
1 4
1 1
2 b
1 1
1 1
相信大家都知道错在哪了，如果直接去判断当前格子的染色状态会很麻烦，复杂度也会炸。也就是说正着维护很难。
触发关键词了。
没错，正难则反。我们反着去处理查询，每次只要找到这个格子最后一次的有效染色即可。
代码
略
复杂度分析
略
9.28
florr 玩破防了，老实滚回来写题。
P1182
唔，一个简单的二分答案，所以我们确定三个点：
check函数- 二分边界
- 二分内容
二分内容不难想，题目要求我们求最小最大值，所以我们二分这个值。边界也比较简单，显然当我分为 段时答案最小，为 ；不分段时最大，为 ，那么边界就没问题了。
来看 check 函数。我们要在保证答案为 的情况下，所分段数不超过 。考虑 求分段数，若当前这一段大小超过 ，则划分新的一段。由于我们需要 维护静态区间和，所以使用前缀和数组。
那就做完了。
代码：
namespace yxdl1{
#define int long long
#define f(i,l,r) for(int i=l;i<=r;i++)
#define max(a,b) (a>b?a:b)
int n,m,a[100005]={},pre[100005]={};
bool check(int mid){
int t=0,now=0;
f(i,2,n){
if(pre[i]-pre[now]>mid){
now=i-1;
t++;
}
}return t>=m?1:0;
}
void solve(){
std::cin >> n >> m;
int l=0,r;
f(i,1,n){
std::cin >> a[i];
pre[i]=a[i]+pre[i-1];
l=max(l,a[i]);
}r=pre[n];
while(l<=r){
int mid=(l+r)>>1;
if(check(mid))l=mid+1;
else r=mid-1;
}std::cout << l;
}
}
复杂度分析
比较简单的分析，二分复杂度 ，check 函数复杂度 ，总复杂度 。其中 为 。
P14247
好神奇的题。
乍一看感觉条件三很难，尝试找规律。
看了一眼样例，没有给我们不合法的情况，猜测都是可以的。
从 开始看，发现随便填都符合条件，当时推到这就开智了。
显然我们构造的这个矩阵中只要包含一个 的由 组成的子矩阵即可满足条件三。
发现条件 要满足“恰有”，看看怎么放可以不出现第二个如上的子矩阵。我们假设 ，在上述条件下，我们可以在右侧与下侧全部填 ，右下角填 ，构造出来的矩阵是这样的：
1 2 5
2 4 5
5 5 6
那怎么往下扩展呢，看看 的情况，按照上述方法构造，矩阵如下：
1 2 5 7
3 4 5 7
5 5 6 7
7 7 7 8
发现，若 是一个合法的构造，考虑在其右，下侧最后一列（排）放入 ，最右下角放 。不管怎么圈，除了最左上角的子矩阵外，总是有且只有两个数重复。这样就满足了“恰有”这个条件，进而满足了所有条件。
代码
略
复杂度分析
显然为
10.1
P17288
高速上写的，脑子不清醒写了个石山。
直接模拟即可，思路不讲诗人都会吧。
代码
namespace yxdl1{
std::string a[100005]={},b[100005]={};
int cnt;
void solve(){
std::cin >> cnt;
std::string n,m;
std::cin >> n >> m;
int idx=0,is_sum=0;
std::string now;
for(int i=0;i<n.size();i++){
if(!(n[i]>='a' and n[i]<='z')){
now=n.substr(idx,i-idx);
char sum[10005]={};
int index=0,num=0;
while(!(n[i]>='a' and n[i]<='z') and i<n.size()){
sum[index++]=n[i++];
}for(int j=0;j<index;j++){
num=num*10+(sum[j]-'0');
}a[num]=now;
idx=i;
}
}idx=0;
for(int i=0;i<m.size();i++){
if(!(m[i]>='a' and m[i]<='z')){
now=m.substr(idx,i-idx);
char sum[10005]={};
int index=0,num=0;
while(!(m[i]>='a' and m[i]<='z') and i<m.size()){
sum[index++]=m[i++];
}for(int j=0;j<index;j++){
num=num*10+(sum[j]-'0');
}b[num]=now;
idx=i;
}
}for(int i=1;i<=cnt;i++){
std::cout << a[i] << b[i];
}
}
}
复杂度
，证明略
有帮助，赞一个