题号 标题 已通过代码 通过率 团队的状态
A Car Show 点击查看 1347/3168
B Two Frogs 点击查看 777/2832
C Global Positioning System 点击查看 41/136
D Half Turns 点击查看 9/28
E Longest Increasing Subsequence 点击查看 183/1423
F Matrix and GCD 点击查看 79/369
G Magic Spells 点击查看 461/3045
H Radar Scanner 点击查看 0/79
I The Great Wall II 点击查看 173/929
J Colourful Journey 点击查看 2/25
K NIO’s OAuth2 Server 点击查看 70/282
链接：https://ac.nowcoder.com/acm/contest/33194/A
来源：牛客网
题目描述
There are nn cities and mm car styles in NIO Kingdom. According to the investigations, for the ii-th city, cars of style T_iT
i
are the most popular.
Now there will be a car show in NIO Kingdom, and the person in charge wants to choose an integer interval [l,r][l,r] (1\le l \le r \le n)(1≤l≤r≤n) and let the cities whose indices are in this interval hold the show jointly. And to manifest the variety of the cars, every style should occur at least once among the most popular styles in the host cities. Determine the number of integer intervals satisfying the constraint mentioned before.
输入描述:
The first line contains two integers nn and mm (1 \le m \le n \le 100,000)(1≤m≤n≤100000), denoting the number of cities and the number of car styles respectively.
The second line contains nn integers T_1, T_2, \cdots, T_nT
1
,T
2
,⋯,T
n
(1 \le T_i \le m)(1≤T
i
≤m), denoting the most popular styles.
输出描述:
Output one line containing one integer, denoting the answer.
示例1
输入
复制
5 3
1 2 3 2 1
输出
复制
5
说明
For the sample case, the 55 intervals are [1, 3], [1, 4], [1, 5], [2, 5], [3, 5][1,3],[1,4],[1,5],[2,5],[3,5] respectively.
题意：
思路：
#include链接：https://ac.nowcoder.com/acm/contest/33194/B
来源：牛客网
题目描述
In the Lonely Mountain, there are a lot of treasure well protected by dwarfs. Later, one day, the last dragon Smaug came and sensed the treasure being. As known to all, dragons are always much too greedy for treasure. So definitely, the war between dwarfs and Smaug begins.
During the war, two goblins Alice and Bob are turned into frogs by Gandalf, The Grey. In front of them, there are nn lotus leaves in a line. In order to break the spell, they must jump from the 11-st lotus leaf to the nn-th lotus leaf. If the frog is now on the ii-th lotus leaf instead of the nn-th lotus leaf, it can jump to a lotus leaf in range (i, i + a_i](i,i+a
i
].
Goblins are lack of intelligence and it’s also true even after turned into frogs. So Alice and Bob will jump randomly, which means, they will separately pick an available lotus leaf in every jump uniformly at random.
Since Alice and Bob have already being playing games for decades, so they want to know the probability that they jump to the nn-th lotus leaf with the same count of jumps.
输入描述:
The first line contains an integer nn (2 \leq n \leq 8,000)(2≤n≤8000), denoting the number of lotus leaf.
The second line contains n-1n−1 integers a_1, a_2, \ldots, a_{n-1}a
1
,a
2
,…,a
n−1
, where the ii-th integer a_ia
i
(1 \leq a_i \leq n-i)(1≤a
i
≤n−i) indicates the range of lotus leaves that can be reached from the ii-th lotus leaf.
输出描述:
Output a line containing a single integer, indicating the probability that Alive and Bob jump to nn-th lotus leaf with the same count of jumps, taken modulo 998,244,353998244353.
Formally speaking, let the result, which is a rational number, be \frac{x}{y}
y
x
as an irreducible fraction, you need to output x \cdot y^{-1} \bmod{998,244,353}x⋅y
−1
mod998244353, where y^{-1}y
−1
is a number such that y \cdot y^{-1} \equiv 1 \pmod{998,244,353}y⋅y
−1
≡1(mod998244353). You may safely assume that such y^{-1}y
−1
always exists.
示例1
输入
复制
5
1 1 1 1
输出
复制
1
示例2
输入
复制
5
4 3 2 1
输出
复制
440198031
题意：
思路：
//时间优化
#include//空间优化
#include链接：https://ac.nowcoder.com/acm/contest/33194/G
来源：牛客网
题目描述
One day in the magic world, the young wizard RoundDog was learning the compatibility of spells. After experimenting for a long time, he reached the conclusion that the compatibility of a spell collection can be measured by the number of distinct palindromes that are substrings of all the spells in the collection. He was so excited and planned to write a program to calculate the compatibility of any input spell collection.
However, RoundDog was busy participating the NowWizard Multi-Universe Training this week. He was too struggling during the competition and feels tired now.
Since RoundDog is not in the mood to finish the program now, could you help him?
输入描述:
The first line contains a single integer kk (1 \leq k \leq 5)(1≤k≤5), indicating the number of spells in a spell collection.
In the following kk lines, each line contains a spell SS (1 \le |S| \le 300,000)(1≤∣S∣≤300000), which is a string containing only lowercase English letters.
It is guaranteed that the total length of the spells does not exceed 300,000300000.
输出描述:
Output the compatibility of the input spell collection, which is the number of distinct palindromes that are substrings of all the spells in the collection.
示例1
输入
复制
3
abaca
abccaca
acabb
输出
复制
4
说明
In the example, “a”, “b”, “c”, “aca” are the four distinct palindromes that are substrings of all the input spells.
题意：
思路：
//manacher+hash
#include//回文自动机
#include链接：https://ac.nowcoder.com/acm/contest/33194/E
来源：牛客网
题目描述
Given an integer mm, you need to construct a permutation pp whose length does not exceed 100100 such that there are exactly mm longest increasing subsequences in pp.
If multiple solutions exist, print any of them. If no solution exists, report it.
输入描述:
The first line contains an integer TT (1\le T \le 1,000)(1≤T≤1000), denoting the number of test cases.
Each test case contains an integer mm (1\le m \le 10^9)(1≤m≤10
9
) in one line.
输出描述:
For each test case:
If no solution exists, print “-1” (without quotes) in one line.
Otherwise, print one integer nn (1\le n\le 100)(1≤n≤100) in the first line denoting the length of the permutation you construct. Then print nn integers p_1, p_2, \cdots, p_np
1
,p
2
,⋯,p
n
, (1 \le p_i \le n, \forall , 1 \le i < j \le n, p_i \neq p_j)(1≤p
i
≤n,∀1≤i
=p
j
) in the second line denoting the permutation you construct.
示例1
输入
复制
2
3
5
输出
复制
4
2 4 1 3
5
3 2 5 1 4
说明
In the first test case, the length of the LIS (longest increasing subsequence) is 22, and the 33 LISs are {2, 4}, {2, 3}, {1, 3}{2,4},{2,3},{1,3}.
In the second test case, the length of the LIS is 22, and the 55 LISs are {3, 5}, {3, 4}, {2, 5}, {2, 4}, {1, 4}{3,5},{3,4},{2,5},{2,4},{1,4}.
题意：
思路：
#include链接：https://ac.nowcoder.com/acm/contest/33194/I
来源：牛客网
题目描述
Beacon towers are built throughout and alongside the Great Wall. There was once a time when there were nn beacon towers built from west to east for defending against the invaders. The altitude of the ii-th beacon tower, based on historical records, is a_ia
i
.
The defenders divide strategically all beacon towers into kk parts where each part contains several, but at least one, consecutive beacon towers. To fully defend against the invaders, to each part a team of defenders should be assigned, the cost of which is given by the highest altitudes of beacon towers in that part.
As a historian, you are dying to know the minimum costs of assignments for every k = 1, 2, \ldots, nk=1,2,…,n.
输入描述:
The first line contains an integer nn (1 \leq n \leq 8,000)(1≤n≤8000), denoting the number of beacon towers alongside the Great Wall.
The second line contains nn integers a_1, a_2, \ldots, a_na
1
,a
2
,…,a
n
, where the ii-th integer a_ia
i
(1 \leq a_i \leq 100,000)(1≤a
i
≤100000) is the altitude of the ii-th beacon tower.
输出描述:
Output nn lines, the ii-th of which contains an integer indicating the minimum cost for k = ik=i.
示例1
输入
复制
5
1 2 3 4 5
输出
复制
5
6
8
11
15
示例2
输入
复制
5
1 2 1 2 1
输出
复制
2
3
4
6
7
题意：
思路：
𝑑𝑝(𝑖,𝑗)表示将𝑎1,𝑎2,…,𝑎𝑗分为𝑖段的最小代价。
转移时已经知道分为i-1段的最小代价，枚举k
对于固定的𝑗，当𝑘从𝑗开始遍历到1时，max{𝑎𝑘,𝑎(𝑘+1),…,𝑎j}是不减的，每一个取值对应一段𝑘。
新增一个𝑎(𝑗+1)时末尾一些段会被合并成一个max值是𝑎(𝑗+1)的段，可以使用单调栈维护所有段。
每个数最多入栈和出栈一次，因此遍历一次整个数组时维护单调栈的复杂度是𝑂(𝑛)。
假设当前的段是[𝑙1,𝑟1],[𝑙2,𝑟2],…,[𝑙𝑠,𝑟𝑠]，对应的max值是𝑣1,𝑣2,…,𝑣𝑠。
转移式改写为𝑑p(𝑖,𝑗)=min(1≤𝑡≤𝑠){min{𝑑𝑝(𝑖−1,𝑙𝑡 ),𝑑𝑝(𝑖−1,𝑙𝑡+1),…,𝑑𝑝(𝑖−1,𝑟_𝑡 )}+𝑣𝑡}。
#include
stk.pop_back();
}
//a[i]可以放到最大值>当前的段里，不需要代价。 或者单独成段，代价+a[i]。
dp[i][j] = min(dp[stk.back().first][j], mi+a[i]);
stk.push_back({i,min(mi, dp[i][j-1])});
}
}
for(int i = 1; i <= n; i++)cout<<dp[n][i]<<"\n";
return 0;
}