/*
_ __ __ _ _
| | \ \ / / | | (_)
| |__ _ _ \ V /__ _ _ __ | | ___ _
| '_ \| | | | \ // _` | '_ \| | / _ \ |
| |_) | |_| | | | (_| | | | | |___| __/ |
|_.__/ \__, | \_/\__,_|_| |_\_____/\___|_|
__/ |
|___/
*/
const int MAX = 2e5+50;
int main()
{
int T;scanf("%d",&T);
while(T--){
ll p,a,b,c;scanf("%lld%lld%lld%lld",&p,&a,&b,&c);
a = (a - p % a) % a;
b = (b - p % b) % b;
c = (c - p % c) % c;
printf("%lld\n",min(min(a,b),c));
}
return 0;
}
B：Card Deck | 贪心
【题意】 有
n
n
n 张牌，
p
i
p_i
pi 表示从牌底到牌顶第
i
i
i 张牌的编号。编号是个
n
n
n 的全排列。 你可以第一堆卡，选择牌顶的
k
k
k 张牌，按照这个顺序把在这几张牌放在终点堆。 最后第一堆卡被拿空了，得分为终点堆按这个式子计算：
∑
i
n
n
−
i
×
p
i
\sum_i n^{n-i}\times p_i
∑inn−i×pi
【范围】
1
≤
n
≤
1
0
5
1\le n\le 10^5
1≤n≤105
【思路】赛内 首先随便看看，式子按照
i
i
i 增加，左边的大系数会递减。我们就希望越靠近前面的
i
i
i，
p
i
p_i
pi 越大。 然后看一下样例，就随便得到了结论： 假设拿牌的范围为
[
s
t
,
e
d
]
[st,ed]
[st,ed]，我们的要求是
∀
i
∈
[
s
t
,
e
d
]
\forall i\in[st,ed]
∀i∈[st,ed] 满足
p
s
t
≥
p
i
p_{st}\ge p_i
pst≥pi 并且
p
s
t
<
p
e
d
+
1
p_{st}<p_{ed+1}
pst<ped+1 具体原因的话，因为此时拿
p
e
d
+
1
p_{ed+1}
ped+1 放到前面更优啥的。 用队列模拟一下就行了。
【代码】 时间复杂度：
O
(
n
)
O(n)
O(n)
/*
_ __ __ _ _
| | \ \ / / | | (_)
| |__ _ _ \ V /__ _ _ __ | | ___ _
| '_ \| | | | \ // _` | '_ \| | / _ \ |
| |_) | |_| | | | (_| | | | | |___| __/ |
|_.__/ \__, | \_/\__,_|_| |_\_____/\___|_|
__/ |
|___/
*/
const int MAX = 2e5+50;
const int INF = 0x3f3f3f3f;
int aa[MAX];
deque<int>Q;
int main()
{
int T;scanf("%d",&T);
while(T--){
int n;scanf("%d",&n);
for(int i = 1;i <= n;++i)scanf("%d",&aa[i]);
for(int i = 1;i <= n;++i){
int st = i;int ed = i;
while(ed + 1 <= n && aa[ed+1] < aa[st])ed++;
for(int j = ed;j >= st;--j)Q.push_front(aa[j]);
i = ed;
}
while(!Q.empty()){
printf("%d ",Q.front());
Q.pop_front();
}
puts("");
}
return 0;
}
C：Maximum width | 贪心 + 思维
【题意】 给你两个字符串
s
、
t
s、t
s、t，然后
n
=
∣
s
∣
，
m
=
∣
t
∣
n=|s|，m=|t|
n=∣s∣，m=∣t∣ 你需要得到一个序列
p
[
1
,
2
,
⋯
,
m
]
p[1,2,\cdots,m]
p[1,2,⋯,m]，满足
1
≤
p
1
<
p
2
<
⋯
<
p
m
≤
n
1\le p_1<p_2<\cdots<p_m\le n
1≤p1<p2<⋯<pm≤n， 然后
∀
i
∈
[
1
,
m
]
\forall i\in[1,m]
∀i∈[1,m]，满足
s
p
i
=
t
i
s_{p_i}=t_i
spi=ti 定义该序列的宽度为
max
i
{
p
i
+
1
−
p
i
}
\max_i\{p_{i+1}-p_i\}
maxi{pi+1−pi} 保证该序列至少存在一个。 你需要给出宽度的最大值。
【范围】
2
≤
m
≤
n
≤
2
×
1
0
5
2\le m\le n\le 2\times 10^5
2≤m≤n≤2×105
【思路】赛内 挺有意思的题目。首先那个序列相当于是
L
C
S
LCS
LCS 最长公共子序列的感觉。 但是要求宽度最大，一时不知道哪个字母该对应哪个字母。 然后我们想到了，对于某一个位置
i
i
i ，该位置之前的字母都优先左匹配，该位置之后的字母都优先右匹配 这样时间复杂度不够。 那我们就想到了：位置
i
i
i 一步一步挪过来，貌似只影响一个字母的匹配位置。 假设一开始所有的字母都是优先左匹配，然后倒着去处理，把最右边的优先左匹配的点改成优先右匹配。然后去求间隔的最大值。 优先右匹配，就是去记录每一个字母出现的最右合法位置，可以用一个队列
q
u
e
u
e
queue
queue 去处理。 那么什么位置是不合法的呢？比如目前该位置的字母的最右合法位置为
y
o
u
you
you ，那么接下来的所有字母的右匹配位置都不能在
y
o
u
you
you 位置的右边。
【代码】 时间复杂度：
O
(
∣
n
∣
+
∣
m
∣
)
O(|n| + |m|)
O(∣n∣+∣m∣)
【题意】 给你数字
a
,
b
,
k
a,b,k
a,b,k 你需要构造两个二进制串
x
,
y
x,y
x,y，满足他们没有前导零，且
x
≥
y
x\ge y
x≥y 首先，这两个串的
0
0
0 的个数都等于
a
a
a 其次，这两个串的
1
1
1 的个数都等于
b
b
b 其次，
(
x
−
y
)
2
(x-y)_2
(x−y)2 的
1
1
1 的个数等于
k
k
k，就是两个数字相减后的二进制表示的
1
1
1 的个数为
k
k
k。 问你怎么构造，或者无法构造。
【范围】
0
≤
a
0\le a
0≤a
1
≤
b
1\le b
1≤b
0
≤
k
≤
a
+
b
≤
2
×
1
0
5
0\le k\le a+b\le 2\times 10^5
0≤k≤a+b≤2×105
【思路】赛内 + 赛后
(
%
%
%
s
o
l
e
m
n
t
e
e
%
%
%
)
\color{red}(\%\%\%solemntee\%\%\%)
(%%%solemntee%%%) 默认以下竖式都是减法 首先有这么几种简单的消耗操作：
1111
1111
−
−
−
−
−
−
0000
\begin{matrix} 1111\\ 1111\\ ------\\ 0000 \end{matrix}
11111111−−−−−−0000 可以把两个串的多余的
1
1
1 消耗掉。
0000
0000
−
−
−
−
−
−
0000
\begin{matrix} 0000\\ 0000\\ ------\\ 0000 \end{matrix}
00000000−−−−−−0000 可以把两个串的多余的
0
0
0 消耗掉。 也就是说，
a
，
b
a，b
a，b 明显是少了不顶用，多了没关系的。接下来看怎么产生
1
1
1。
1000
0001
−
−
−
−
−
−
0111
\begin{matrix} 1000\\ 0001\\ ------\\ 0111 \end{matrix}
10000001−−−−−−0111 这是一个产生
1
1
1 的关键式子。消耗了
a
a
a 个
0
0
0 和一个
1
1
1 ，就可以产生
a
a
a 个
1
1
1。 然后我们按照这个思路去做，
k
k
k 的上限为
a
a
a ，在做一些特判，结果
W
a
Wa
Wa 了。 为啥呢？我们还有更神奇的式子
1011100
0011101
−
−
−
−
−
−
0111111
\begin{matrix} 1011100\\ 0011101\\ ------\\ 0111111 \end{matrix}
10111000011101−−−−−−0111111 消耗了
a
a
a 个
0
0
0 和
b
b
b 个
1
1
1 ，就可以产生
a
+
b
−
1
a+b-1
a+b−1 个
1
1
1。这是具有决定意义的式子。 然后由于
y
y
y 串不能有前导零，必须每个式子花掉一个
1
1
1 于是
k
k
k 的最大上限为：
a
+
b
−
2
a+b-2
a+b−2，前提是
b
≥
2
b\ge 2
b≥2 【总结一下】
k
=
0
k=0
k=0 的时候有些特殊，只要前面全放
1
1
1 后面全放
0
0
0 就行了。
k
>
0
k>0
k>0 的时候，
1
1
1 必须要用两个(一个开头一个产生
1
1
1)，
0
0
0 必须要用一个(为了产生
1
1
1)，上限为
a
+
b
−
2
a+b-2
a+b−2 首先我们需要拿一个
1
1
1 作为开头。接下来产生剩余的
1
1
1。 然后我们构造
1
x
x
x
x
x
0
0
x
x
x
x
x
1
−
−
−
−
−
−
0111111
\begin{matrix} 1xxxxx0\\ 0xxxxx1\\ ------\\ 0111111 \end{matrix}
1xxxxx00xxxxx1−−−−−−0111111 ，其中
x
x
x 的要求：上下都为
1
1
1 或上下都为
0
0
0 都可。 最后一些多余的
1
、
0
1、0
1、0，我们直接消耗掉即可。 即最终的解长得样子为：
11
x
x
x
x
x
01
⋯
10
⋯
0
10
x
x
x
x
x
11
⋯
10
⋯
0
−
−
−
−
−
−
−
−
−
−
−
0011111110
⋯
00
⋯
0
\begin{matrix} 11xxxxx01\cdots10\cdots0\\ 10xxxxx11\cdots10\cdots0\\ -----------\\ 0011111110\cdots00\cdots0 \end{matrix}
11xxxxx01⋯10⋯010xxxxx11⋯10⋯0−−−−−−−−−−−0011111110⋯00⋯0