“蔚来杯“2022牛客暑期多校训练营8，签到题F

题号 标题 已通过代码 通过率 团队的状态
A Puzzle: X-Sums Sudoku 点击查看 19/55
B Puzzle: Patrick’s Parabox 点击查看 1/70
C Puzzle: Hearthstone 点击查看 2/105
D Poker Game: Decision 点击查看 311/3285
E Poker Game: Construction 点击查看 1/64
F Longest Common Subsequence 点击查看 1332/9989
G Lexicographic Comparison 点击查看 12/159
H Expression Evaluation 点击查看 2/26
I Equivalence in Connectivity 点击查看 39/252
J Symmetry: Tree 点击查看 17/336
K Symmetry: Convex 点击查看 2/12
L Symmetry: Closure 点击查看 1/21

文章目录

• F.Longest Common Subsequence

F.Longest Common Subsequence

链接：https://ac.nowcoder.com/acm/contest/33193/F
来源：牛客网

题目描述
Given sequence ss of length nn and sequence tt of length mm, find the length of the longest common subsequence of ss and tt.
输入描述:

There are multiple test cases. The first line of input contains an integer TT(1le Tle 10^31≤T≤10
 3
 ), the number of test cases.For each test case:
The only line contains 77 integers, nn, mm, pp, xx, aa, bb, cc (1le n1≤n, mle 10^6m≤10
 6
 , 0le x0≤x, aa, bb, c

+bx+c)modp, and then set s_is
i

to xx. And then, for each i=1i=1, 22, cdots⋯, mm in order, update xx to (ax^2+bx+c)bmod p(ax
2
+bx+c)modp, and then set t_it
i

to xx.

It is guaranteed that the sum of nn and the sum of mm over all test cases does not exceed 10^610
6
.
输出描述:
For each test case:

Output an integer – the length of the longest common subsequence of ss and tt, in one line.
示例1
输入
复制
2
4 3 1024 1 1 1 1
3 4 1024 0 0 0 0
输出
复制
0
3
说明
In the first sample, s=[3,13,183,905]s=[3,13,183,905] and t=[731,565,303]t=[731,565,303].

In the second sample, s=[0,0,0]s=[0,0,0] and t=[0,0,0,0]t=[0,0,0,0].

题意：

• 给出n, m, p, x, a, b, c。 令。
  让长为n的序列s，s[1]=f(x), s[2]=f(s[1]), s[3]=f(s[2])，依次递推。
  让长为m的序列t，t[1]=f(s[n]), t[2] = f(t[1]), t[3] = f(t[2])，依次类推。
• 最后求序列s和序列t的LCS（最长公共子序列）。

思路：

• 因为要%p，所以可以发现，到后面这两个序列都是循环的。换句话说，如果两个序列中有相同数字，那么后面的数字一定全一样。
• 开个map记录下序列s中每个数第一次出现的位置。对于t进行遍历的时候，找到这个数的位置，将序列t[j]与s[i]对上后，不难发现 [ t[j], m ] 与 [ s[i], n ] 这两个区间一定是一样的，因为都是往后无限循环，取个min就是LCS的大小。遍历一遍维护最大值即可。

#include
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
typedef long long LL;

int main(){
    LL T;  cin>>T;
    while(T--){
        LL n, m, p, x, a, b, c;  cin>>n>>m>>p>>x>>a>>b>>c;
        unordered_mapmp;        //每个数最早出现的位置
        for(LL i = 1; i 

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net