T1

题目描述

给定一个含有 \(n\) 个字符串的序列 \(s\)，其中每个字符串长度不超过 \(3\)，且仅由小写字母组成，判断是否有一个它的子序列，满足子序列中的字符串首尾相接后形成的字符串是一个回文串。若存在，请求出最小的整数 \(X\)，满足存在一个这样的子序列，它的最后一个字符串的下标为 \(X\)；若不存在，输出 \(−1\)。

输入格式

从文件 \(pali.in\) 中读入数据。

第一行一个整数 \(T\) 代表数据组数。

对每组数据，第一行一个整数 \(n\)。

接下来 \(n\) 行每行一个长度不超过 \(3\)，且仅由小写字母组成的字符串 \(s_i\)。

输出格式

输出到文件 \(pali.out\) 中。

对每组数据输出一个整数，若存在满足条件的子序列，则输出 \(X\)；若不存在，则输出 \(−1\)。

输入样例

6
5
zx
ab
cc
zx
ba
2
ab
bad
4
co
def
orc
es
3
a
b
c
3
ab
cd
cba
2
ab
ab

输出样例

3
-1
-1
1
3
-1

数据规模

对于 \(100\%\) 数据，\(1 \leq T \leq 10, 1 \leq n \leq 10^5\)。

完整代码

#include <bits/stdc++.h>
using namespace std;
int T, n;
map <string, bool> mp;
string s;
int main(){
	freopen("pali.in", "r", stdin);
	freopen("pali.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin >> T;
	while(T--){
		mp.clear();
		cin >> n;
		bool flag = false;
		int ans;
		for(int i = 1; i <= n; i++){
			cin >> s;
			if(flag)
				continue;
			mp[s] = true;
			int len = s.length();
			string tmp = s;
			reverse(tmp.begin(), tmp.end());
			if(tmp == s){
				ans = i;
				flag = true;
			} else if(len == 3){
				if(mp[tmp]){
					ans = i;
					flag = true;
				}
				string t = "";
				for(int j = 0; j <= 1; j++)
					t += s[2 - j];
				if(mp[t]){
					ans = i;
					flag = true;
				}
			} else {
				if(mp[tmp]){
					ans = i;
					flag = true;
				}
				string t = "";
				for(int j = 0; j <= 1; j++)
					t += s[1 - j];
				if(mp[t]){
					ans = i;
					flag = true;
				}
				for(int j = 0; j < 26; j++){
					string tt = t + char('a' + j);
					if(mp[tt]){
						ans = i;
						flag = true;
						break;
					}
				}	
			}
		}
		if(!flag)
			cout << -1 << endl;
		else
			cout << ans << endl;
	}
	return 0;
}

T2

题目描述

给定一个 \(n \times n\) 的矩阵，定义一次操作为选择一个整数 \(i\)，对于所有整数 \(j \in [1, n]\) 且
\(j \neq i\)，交换 \(A_{j, i}\) 与 \(A_{i, j}\)。

求出在进行若干次操作后可达成的矩阵中，以 \(A_{1, 1}, A_{1, 2}, \dots, A_{1, n}, A_{2, 1}, A_{2, 2}, \dots, A_{n, n}\) 的形式排列后，字典序最小的矩阵。

输入格式

从文件 \(swap.in\) 中读入数据。

第一行一个整数 \(n\) 代表矩阵大小。

接下来 \(n\) 行每行 \(n\) 个整数，代表 \(A_{i, j}\)。

输出格式

输出到文件 \(swap.out\) 中。

输出 \(n\) 行，每行 \(n\) 个整数，可达成的字典序最小的矩阵。

输入样例

3
2 8 6
7 5 1
4 9 3

输出样例

2 7 4
8 5 1
6 9 3

数据规模

对于 \(100\%\) 数据，\(n \leq 1000, 1 \leq A_{i, j} \leq 10^9\)。

T3

题目描述

给定一张由 \(n\) 个点和 \(m\) 条边组成的无向联通图，点的编号从 \(1\) 到 \(n\)，点有点权，第 \(i\) 个点点权为 \(C_i\)，对于任意 \(C_i\) 满足 \(Ci \in [−n, n]\)，且 \(C_i\) 的奇偶性与 \(i\) 的度数的奇偶性相同。一个点的度数为与其相邻的边的个数。

现在你要为每一条边都赋一个边权，要求每个点所有相邻的边的边权和等于该点的点权，且边权的大小 \(w_i \in [−2n^2, 2n^2]\)。

输入格式

从文件 \(graph.in\) 中读入数据。

第一行两个整数 \(n\) 和 \(m\)。

接下来一行 \(n\) 个整数 \(C_1, C_2, \dots, C_n\) 为点的点权。

接下来 \(m\) 行每行两个整数 \(u_i, v_i\) 表示第 \(i\) 条边链接 \(u_i\) 与 \(v_i\)。

保证原图中无重边无自环。

输出格式

输出到文件 \(graph.out\) 中。

一行输出 \(m\) 个整数 \(w_1, w_2, \dots, w_m\)，为第 \(i\) 条边的边权。

输入样例

3 2
2 −1 3
3 1
2 1

输出样例

3 -1

数据规模

对于 \(100\%\) 数据，\(1 \leq n, m \leq 10^5\)。

提示

除样例 \(1\) 外，其他样例的答案文件为空，选手可以通过下发的 \(checker.cpp\) 来检验自己输出结果的正确性。

T4

题目描述

给定一个大小为 \(3 \times n\) 的矩阵，你要从矩阵的左上角走到右下角，即要从 \((1, 1)\) 走到 \((3, n)\), 每步只能从 \((x, y)\) 走到 \((x + 1, y)\) 或 \((x, y + 1)\)。

矩阵的每个位置上都有一个数 \(A_{i, j}\)，代表经过这个位置时所需要的收益。与此同时，矩阵第二行的格子初始是不可通行的，有 \(m\) 个开关，第 \(i\) 个开关有三个参数 \(l_i, r_i, v_i\) 打开后可以使第二行的 \([li, ri]\) 区间内的位置全部可以通行，但是要额外花费 \(v\) 的代价。一条路径的收益即为路上经过的所有位置的收益和，减去需要打开开关所需要的代价和。

现在要你求出从 \((1, 1)\) 走到 \((3, n)\) 所能获得的最大收益。

输入格式

从文件 \(seg.in\) 中读入数据。

第一行两个整数 \(n, m\)。

接下来三行每行 \(n\) 个数 \(A_{i, j}\)。

接下来 \(m\) 行每行 \(3\) 个数 \(li, ri, vi\)，为第 \(i\) 个开关的信息。

输出格式

输出到文件 \(seg.out\) 中。

一行一个整数，代表能获得的最大收益。

输入样例

5 5
−6 4 −7 −6 10
−3 −6 3 −5 −8
−9 10 5 6 −1
2 4 10
4 4 4
1 1 7
1 3 9
2 3 7

输出样例

5

数据规模

对于 \(100\%\) 数据，\(1 \leq n, m \leq 5 \times 10^5，1 \leq li \leq ri \leq n，1 \leq vi \leq 10^9，|Ai,j | \leq 10^9\)。