如何让洛谷管理在审核题解的时候有乐子看？
chen_zhe
·
2022-07-13 17:33:42
·
个人记录
同学们好。我们开始上课了！今天我们要讲的题目是……
那个不听话的，给我出去！
今天我们要讲的题目是
[AGC020D] Min Max Repetition
我们来看看题面
A と BB を正の整数として、 f(A,\ B)f(A, B) を以下の条件を満たす文字列と定めます。
f(A,\ B)f(A, B) の長さは A\ +\ BA + B である。
f(A,\ B)f(A, B) はちょうど AA 個の A とちょうど BB 個の B を含む。
f(A,\ B)f(A, B) の部分文字列であって同じ文字からなるもの（例: AAAAA、BBBB）のうち最長のものの長さは、上記の二つの条件が満たされるという前提のもとで最小である。
f(A,\ B)f(A, B) は、上記の三つの条件が満たされるという前提のもとで辞書順最小の文字列である。
例えば、 f(2,\ 3)f(2, 3) = BABAB、 f(6,\ 4)f(6, 4) = AABAABAABB となります。
次の QQ 個のクエリに答えてください。「 f(A_i,\ B_i)f(A
i
, B
i
) の C_iC
i
文字目から D_iD
i
文字目までの部分文字列（最初の文字を 11 文字目とする）を求めよ。」
输入格式
Input is given from Standard Input in the following format:
源代码复制
Q
A_1 $ $ B_1 $ $ C_1 $ $ D_1
A_2 $ $ B_2 $ $ C_2 $ $ D_2
:
A_Q $ $ B_Q $ $ C_Q $ $ D_Q
输出格式
For each query ii in order of input, print a line containing the substring of f(A_i,\ B_i)f(A
i
, B
i
) from position C_iC
i
to position D_iD
i
(1-based).
题意翻译
多组询问。每个询问给定四个整数，A,B,C,DA,B,C,D，求一个满足这个条件的字符串：
长度为A+BA+B，由AA个字符A和·BB个字符B构成。
在此基础上，连续的相同字符个数的最大值最小
在此基础上，字典序最小
输出这个字符串的第CC位到第DD位。
这是一道
看不清楚吗？
# 大！水！题！
题目中有三个要求。我们要怎么看呢？
**~~（小明：拿眼睛看）~~**
**~~（你给我爬出去）~~**
### 不！是一个一个看！
要求字典序最小，我们应该怎么办呢？应该怎么办呢？小红同学你说一下！
小红：拿 $\text{\color{yellow}B}$ 开头，而且越多越好。
小红同学是一个错误示例。你们啊，真的是 too young, too simple! 我要给你传授一点人生的经验！要求字典序最小，
# 当然应该拿 A 开头啊！
### 你想想，如果拿 B 开头
# 他 tmd 能有比拿 A 开头的字典序小吗？？？？
# 开动你的小脑筋好好想一想？
那么，接下来看第二个条件。要求连续的相同字符个数最大值最小。我们可以先算出这个最大值 k。那么我们可以知道，$k$=$max${⌈ $(B+1)$/A⌉,⌈$(A+1)$/B⌉}。
如果我们要写成代码，应该要这么写：
$k=max(ceil(1.0*A/(B+1)),ceil(1.0*B/(A+1)));$。
这个非常显然，证明留作课后习题。
然后还有一条是长度的限制。不管了直接莽就是！反正长度再长我们也不用什么 $Splay$ 啊，$SAM$ 之类的高级数据结构结构去维护！
我们如果要一开始填充一堆 $\textbf{A}$ 的话，填充的 $A$ 的数量不能超过上面提到的 $\textrm{k}$，然后接下来就拿 $\mathrm{B}$ 阻断，然后再填充 $\texttt{A}$。
但是。
###### 注意，这里有个大坑点！
##### 注意，这里有个大坑点！
#### 注意，这里有个大坑点！
### 注意，这里有个大坑点！
## 注意，这里有个大坑点！
# 注意，这里有个大坑点！
同学们要认真听好！
（你还真的以为自己在讲课吗）？
# What we have explained before is only an ideal condition!
啥？英文你看不懂，换成日语！
# 前に説明したことは理想的な条件だけです！
算了换成中文！
# 我们之前所说的只是理想情况！
## 因为 A 不一定够那么多地让你能够这样构造下去。
我们考虑，到达一个位置时，从填充 $k$ 个 `A`，用 `B` 阻断，变成填充 $k$ 个 `B`，用 `A` 阻断。
这个东西在视频中有讲到，请看这个视频！
不对，放错了！
完了视频找不到了，就先这样吧！
很~~不~~明显的一点就是，我们随随便便二分两下就可以做了这个题。
代码嘛
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <cmath>
# include <cctype>
# include <queue>
# include <vector>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int A,B,C,D,k;
inline bool check(int mid)
{
int a=A-mid/(k+1)*k-mid%(k+1);
int b=B-mid/(k+1);
return b<=1LL*a*k;
}
int main()
{
int T=read();
while (T--)
{
A=read(),B=read(),C=read(),D=read();
k=max(ceil(1.0*A/(B+1)),ceil(1.0*B/(A+1)));
int left=0,right=A+B+1;
while (left<right)
{
int mid=(left+right)>>1;
if (check(mid))
left=mid+1;
else
right=mid;
}
int a=A-left/(k+1)*k-left%(k+1);
int b=B-left/(k+1);
right=left+b-a*k+1;
for (int i=C;i<=min(D,left);i++)
{
if (i%(k+1))
cout << 'A';
else
cout << 'B';
}
for (int i=max(C,left+1);i<=D;i++)
{
if ((i-right)%(k+1))
cout << 'B';
else
cout << 'A';
}
puts("");
}
return 0;
}
不对，希望使用更丰富的展现似乎需要使用 $Markdown$。我们重新附带一下代码！为了弥补一下大家看上面的代码的过错，我给大家附带了一些福利！
~~（小声 BB：其实也就是头文件和火车头）~~
```cpp
// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
using namespace std;
struct io{
char ibuf[1<<20];
char* s;
int a[24];
char obuf[1<<20];
char* t;
io():t(obuf){
fread(s=ibuf,1,
1<<20,stdin);
}
~io(){
fwrite(obuf,1,
t-obuf,stdout);
}
void scan(char* u){
while(*s<48)
++s;
while(*s>32)
*u++=*s++;
*u=0;
}
int scan(){
int u=0,v=1;
while(*s<48)
v=*s++^45?1:-1;
while(*s>32)
u=u*10+*s++-48;
return u*v;
}
void put(int u){
*t++=u;
}
template<class T>
void print(T u){
static int* v=a;
if(!u)put(48);
else{
if(u<0){put(45);
u*=-1;}
for(;u;u/=10)
*v++=u%10;
while(v!=a)
put(*--v+48);
}
}
template<class T>
void println(T u){
print(u),put(10);
}
}ip;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int A,B,C,D,k;
inline bool check(int mid)
{
int a=A-mid/(k+1)*k-mid%(k+1);
int b=B-mid/(k+1);
return b<=1LL*a*k;
}
int main()
{
int T=read();
while (T--)
{
A=read(),B=read(),C=read(),D=read();
k=max(ceil(1.0*A/(B+1)),ceil(1.0*B/(A+1)));
int left=0,right=A+B+1;
while (left<right)
{
int mid=(left+right)>>1;
if (check(mid))
left=mid+1;
else
right=mid;
}
int a=A-left/(k+1)*k-left%(k+1);
int b=B-left/(k+1);
right=left+b-a*k+1;
for (int i=C;i<=min(D,left);i++)
{
if (i%(k+1))
cout << 'A';
else
cout << 'B';
}
for (int i=max(C,left);i<=D;i++)
{
if ((i-right)%(k+1))
cout << 'B';
else
cout << 'A';
}
puts("");
}
return 0;
}
```
因为抄题解是不好的习惯，所以加上了反作弊哦！
洛谷管理都是大帅哥，我在这里向您最真挚地问好：
###### 求过！
##### 求过！
#### 求过！
### 求过！
## 求过！
# 求过！