お前はどこまで見えている

1. 题目 题目链接：P1352「没有上司的舞会」 。 题目描述 某大学有 nnn 个职员，编号为 1…n1 \ldots n1…n 。 他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。 现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 rir_iri​，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。 所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。 输入格式 输入的第一行是一个整数 nnn。 第 2 到第 (n+1)(n + 1)(n+1) 行，每行一个整数，第 (i+1)(i+1)(i+1) 行的整数表示 iii 号职员的快乐指数 rir_iri​ 。 第 (n+2)(n + 2)(n+2) 到第 2n2n2n 行，每行输入一对整数 l,kl, kl,k，代表 kkk 是 lll 的直接上司。 输出格式 输出一行一个整数代表最大的快乐指数。 输入输出样例 输入 #1 1234567891011121314711111111 32 36 47 44 53 5 输出 # ...

1. 题目 题目链接：P5357「【模板】AC自动机（二次加强版）」 。 题目描述 给你一个文本串 SSS 和 nnn 个模式串 T1..nT_{1..n}T1..n​，请你分别求出每个模式串 TiT_iTi​ 在 SS 中出现的次数。 输入格式 第一行包含一个正整数 nnn 表示模式串的个数。 接下来 nnn 行，第 iii 行包含一个由小写英文字母构成的字符串 TiT_iTi​ 。 最后一行包含一个由小写英文字母构成的字符串 SSS 。 数据不保证任意两个模式串不相同。 输出格式 输出包含 nnn 行，其中第 iii 行包含一个非负整数表示 TiT_iTi​ 在 SSS 中出现的次数。 输入输出样例 输入 #1 12345675abbaaabaaabaaaabaaabaa 输出 #1 1234560321 说明/提示 1≤n≤2×1051 \leq n \leq 2 \times 10^51≤n≤2×105，T1..nT_{1..n}T1..n​ 的长度总和不超过 2×1052 \times 10^52×105，SSS 的长度不超过 2×1062 \times 10^62×106 ...

1. 题目 题目链接：CF1409F「Subsequences of Length Two」 。 Description You are given two strings sss and ttt consisting of lowercase Latin letters. The length of ttt is 222 (i.e.i.e.i.e. this string consists only of two characters). In one move, you can choose any character of s and replace it with any lowercase Latin letter. More formally, you choose some iii and replace sis_isi​ (the character at the position iii) with some character from 'a' to 'z'. You want to do no more than kkk replacements in such ...

1. 简介 AC 自动机可以看作是字典树 + KMP，其主要构建步骤为： 将所有模式串插入字典树中，构建出字典树 BFS 字典树上所有的结点构造失配指针（同时考虑路径压缩） AC 自动机主要应用于多模式串匹配问题，即一个主串多个匹配的模式串问题。 2. 思想 AC 自动机基于字典树结构，将所有模式串插入字典树中，然后对字典树中的每个结点构造失配指针。AC 自动机中的失配指针与 KMP 中不同的是，AC 自动机中的失配指针是相对于整棵字典树的，即失配指针不再是局限于当前模式串，而是对于整棵字典树中所有的模式串而言的。 AC 自动机中的失配指针匹配的是当前模式串能匹配到的最长后缀对应的字典树中的结点，即从根结点出发能够匹配到的当前字符串最长后缀的结点。 假设字典树中当前结点为 uuu，uuu 的父结点为 ppp，ppp 通过边字符 ccc 指向 uuu，即 trie[p][c]=u trie[p][c] = u trie[p][c]=u，结点失配数组为 failfailfail。若深度小于 uuu 的所有结点的 failfailfail 指针都已经求得，则： 如果结点 ...

1. 题目 题目链接：UVA12604「Caesar Cipher」 。 Description In cryptography, a Caesar cipher, also known as Caesar’s cipher, the shift cipher, Caesar’s code or Caesar shift, is one of the simplest and most widely known encryption techniques. It is a type of substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet (wrapping around in the end). For example, given an alphabet of capital letters in usual order, with a shift of 333, AAA w ...

1. 题目 题目链接：UVA11452「Dancing the Cheeky-Cheeky」 。 Description The Cheeky-Cheeky is a new song. They dance it in Mula, and also in Hong Kong. All the freekies dance it, and the geek all love it. And the Cheeky-Cheeky is danced like this: The breikin-brokin. The meneito. The roboqueitor. The maiquel-guolkin. In this problem you have to learn to dance the Cheeky-Cheeky. This dancing consists of 444 basic steps (as listed above) that are arranged into a particular sequence. Then this sequence can b ...

1. 题目 题目链接：UVA12467「Secret Word」 。 Description Alicia and Roberto like to play games. Today, Roberto is trying to guess a secret word that Alicia chose. Alicia wrote a long string SSS in a piece of paper and gave Roberto the following clues: The secret word is a non-empty substring (A substring of SSS is defined as any consecutive sequence of characters belonging to SSS. For example, if SSS = abcd then a, abcd, ab, bc and bcd are some of the substrings of SSS but ac, aa, aabbccdd and dcba are ...

1. 题目 题目链接：UVA455「Periodic Strings」 。 Description A character string is said to have period kkk if it can be formed by concatenating one or more repetitions of another string of length kkk. For example, the string abcabcabcabc has period 333, since it is formed by 444 repetitions of the string abc. It also has periods 666 (two repetitions of abcabc) and 121212 (one repetition of abcabcabcabc). Write a program to read a character string and determine its smallest period. Input The first line of t ...

1. 定义 1.1 前缀 & 真前缀 前缀是指从串首开始到某个位置 iii 结束的一个特殊子串。字符串 SSS 的以 iii 结尾的前缀表示为 prefix(S,i)=S[0..i]\begin{array}{c} prefix(S,i) = S[0..i] \end{array} prefix(S,i)=S[0..i]​ 真前缀指除了 SSS 本身的 SSS 的前缀。 1.2 后缀 & 真后缀 后缀是指从某个位置 iii 开始到整个串末尾结束的一个特殊子串。字符串 SSS 的从 iii 开头的后缀表示为 suffix(S,i)=S[i..∣S∣−1]\begin{array}{c} suffix(S,i) = S[i..|S|-1] \end{array} suffix(S,i)=S[i..∣S∣−1]​ 真后缀指除了 SSS 本身的 SSS 的后缀。 1.3 前缀函数 给定一个长度为 nnn 的字符串 sss，其前缀函数定义为一个长度为 nnn 的数组 π\piπ。其中 π[i]\pi[i]π[i] 含义为： 如果子串 s[0..i]s[0..i]s[0..i] ...

1. 简介 KMP 算法是一种优秀的字符串模式匹配算法，相对于暴力匹配方法来说，其改进在于：每当一趟匹配过程出现字符比较不相等时，不需回溯主串的 iii 指针，而是利用已经得到的「部分匹配」的结果将模式串向右「滑动」尽可能远的一段距离后（即回溯模式串的 jjj 指针），继续进行比较。 2. 实现 设模式串为 p1p2⋯pmp_1 p_2 \cdots p_mp1​p2​⋯pm​，主串为 s1s2⋯sns_1 s_2 \cdots s_ns1​s2​⋯sn​。 定义失配数组 next[j]next[j]next[j] 表示当模式串中第 jjj 个字符与主串中相应字符失配时，在模式串中需要重新和主串中该字符进行比较的模式串字符的位置。 假设从主串第 pospospos 个字符开始和模式串匹配，此时主串中第 i(pos≤i)i(pos \leq i)i(pos≤i) 个字符和模式串的第 jjj 个字符比较，且 si≠pjs_i \ne p_jsi​=pj​，说明从主串第 pospospos 个字符开始匹配无法找到模式串子串，因此需要将 pospospos 向右「滑动」（即增 ...

1. 简介 字典树（Trie）用边来代表字母，从根结点到树上某一结点的路径就代表了一个字符串。 2. 实现 由于字典树中的字符串都是从根结点开始，于是我们可以通过标记字符串的终止结点来记录已经插入字典树中的字符串。 我们用 δ(u,c)\delta(u,c)δ(u,c) 表示结点 uuu 的 ccc 字符指向的下一结点，即在结点 uuu 代表的字符串后面添加一个字符 ccc 形成的字符串的结点。 由于字典树的分支取决于字符串中最大可能出现的不同字符数 mmm，因此字典树是一棵 mmm 叉树，我们可以采用动态开点的方式构建字典树。 3. 模板 1234567891011121314151617181920212223242526272829303132333435363738394041#include <bits/stdc++.h>using namespace std;#ifndef _TRIE_#define _TRIE_#define ll int#define MAXN 100005#define MAXCHAR 128//字典树struct Trie
...

1. 题目 题目链接：P2580「于是他错误的点名开始了」 。 题目背景 XS中学化学竞赛组教练是一个酷爱炉石的人。 他会一边搓炉石一边点名以至于有一天他连续点到了某个同学两次，然后正好被路过的校长发现了然后就是一顿欧拉欧拉欧拉（详情请见已结束比赛 CON900）。 题目描述 这之后校长任命你为特派探员，每天记录他的点名。校长会提供化学竞赛学生的人数和名单，而你需要告诉校长他有没有点错名。（为什么不直接不让他玩炉石。） 输入格式 第一行一个整数 nnn，表示班上人数。 接下来 nnn 行，每行一个字符串表示其名字（互不相同，且只含小写字母，长度不超过 505050）。 第 n+2n+2n+2 行一个整数 mmm，表示教练报的名字个数。 接下来 mmm 行，每行一个字符串表示教练报的名字（只含小写字母，且长度不超过 505050）。 输出格式 对于每个教练报的名字，输出一行。 如果该名字正确且是第一次出现，输出 OK，如果该名字错误，输出 WRONG，如果该名字正确但不是第一次出现，输出 REPEAT。 输入输出样例 输入 #1 123456789105 abcadacd3aae 输出 ...