A - Palindromic Twist
You are given a string s consisting of n lowercase Latin letters. n is even.
For each position i (1≤i≤n) in string s you are required to change the letter on this position either to the previous letter in alphabetic order or to the next one (letters ‘a’ and ‘z’ have only one of these options). Letter in every position must be changed exactly once.
For example, letter ‘p’ should be changed either to ‘o’ or to ‘q’, letter ‘a’ should be changed to ‘b’ and letter ‘z’ should be changed to ‘y’.
That way string “codeforces”, for example, can be changed to “dpedepqbft” (‘c’ → ‘d’, ‘o’ → ‘p’, ‘d’ → ‘e’, ‘e’ → ‘d’, ‘f’ → ‘e’, ‘o’ → ‘p’, ‘r’ → ‘q’, ‘c’ → ‘b’, ‘e’ → ‘f’, ‘s’ → ‘t’).
String s is called a palindrome if it reads the same from left to right and from right to left. For example, strings “abba” and “zz” are palindromes and strings “abca” and “zy” are not.
Your goal is to check if it’s possible to make string s a palindrome by applying the aforementioned changes to every position. Print “YES” if string s can be transformed to a palindrome and “NO” otherwise.
Each testcase contains several strings, for each of them you are required to solve the problem separately.
Input
The first line contains a single integer T (1≤T≤50) — the number of strings in a testcase.
Then 2T lines follow — lines (2i−1) and 2i of them describe the i-th string. The first line of the pair contains a single integer n (2≤n≤100, n is even) — the length of the corresponding string. The second line of the pair contains a string s, consisting of n lowercase Latin letters.
Output
Print T lines. The i-th line should contain the answer to the i-th string of the input. Print “YES” if it’s possible to make the i-th string a palindrome by applying the aforementioned changes to every position. Print “NO” otherwise.
Example
Input
5
6
abccba
2
cf
4
adfa
8
abaazaba
2
ml
Output
YES
NO
YES
NO
NO
Note
The first string of the example can be changed to “bcbbcb”, two leftmost letters and two rightmost letters got changed to the next letters, two middle letters got changed to the previous letters.
The second string can be changed to “be”, “bg”, “de”, “dg”, but none of these resulting strings are palindromes.
The third string can be changed to “beeb” which is a palindrome.
The fifth string can be changed to “lk”, “lm”, “nk”, “nm”, but none of these resulting strings are palindromes. Also note that no letter can remain the same, so you can’t obtain strings “ll” or “mm”.
要么两个字母都加要么都减，要么一个加一个减
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <map>
#include <unordered_map>
#include <vector>
#include <cmath>
//#include <ext/rope>
#include <bits/stdc++.h>
using namespace std;
#define gt(x) x = read()
#define int long long
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
//#define x first
//#define y second
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
//typedef __int128 INT;
typedef pair<double, int> PDI;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
inline int read(int out = 0)
{
char c;
while((c=getchar()) < 48 || c > 57);
while(c >= 48 && c <= 57) out=out*10+c-48,c=getchar();
return out;
}
const int N = 1e3 + 10;
const int M = 2e7 + 10;
const int mod = 1e9 + 7;
const int PP = 13331;
const int inf = 0x3f3f3f3f;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-10;
const double PI = acos(-1);
signed main(){
int T;
scanf("%lld", &T);
while(T --){
int n;
scanf("%lld", &n);
string str;
cin >> str;
bool flag = false;
for (int i = 0; i < (n / 2); i ++){
if (str[i] == str[n - i - 1] || str[i] + 1 == str[n - i - 1] - 1 || str[i] - 1 == str[n - i - 1] + 1) continue;
flag = true;
}
if (flag) cout << "NO" << endl;
else cout << "YES" << endl;
}
return 0;
}
B - Numbers on the Chessboard
You are given a chessboard of size n×n. It is filled with numbers from 1 to n2 in the following way: the first ⌈n22⌉ numbers from 1 to ⌈n22⌉ are written in the cells with even sum of coordinates from left to right from top to bottom. The rest n2−⌈n22⌉ numbers from ⌈n22⌉+1 to n2 are written in the cells with odd sum of coordinates from left to right from top to bottom. The operation ⌈xy⌉ means division x by y rounded up.
For example, the left board on the following picture is the chessboard which is given for n=4 and the right board is the chessboard which is given for n=5.
You are given q queries. The i-th query is described as a pair xi,yi. The answer to the i-th query is the number written in the cell xi,yi (xi is the row, yi is the column). Rows and columns are numbered from 1 to n.
Input
The first line contains two integers n and q (1≤n≤109, 1≤q≤105) — the size of the board and the number of queries.
The next q lines contain two integers each. The i-th line contains two integers xi,yi (1≤xi,yi≤n) — description of the i-th query.
Output
For each query from 1 to q print the answer to this query. The answer to the i-th query is the number written in the cell xi,yi (xi is the row, yi is the column). Rows and columns are numbered from 1 to n. Queries are numbered from 1 to q in order of the input.
Examples
Input
4 5
1 1
4 4
4 3
3 2
2 4
Output
1
8
16
13
4
Input
5 4
2 1
4 2
3 3
3 4
Output
16
9
7
20
Note
Answers to the queries from examples are on the board in the picture from the problem statement.
找到是第几个字母，和是奇数还是偶数
-#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <map>
#include <unordered_map>
#include <vector>
#include <cmath>
//#include <ext/rope>
#include <bits/stdc++.h>
using namespace std;
#define gt(x) x = read()
#define int long long
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
//#define x first
//#define y second
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
//typedef __int128 INT;
typedef pair<double, int> PDI;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
inline int read(int out = 0)
{
char c;
while((c=getchar()) < 48 || c > 57);
while(c >= 48 && c <= 57) out=out*10+c-48,c=getchar();
return out;
}
const int N = 1e3 + 10;
const int M = 2e7 + 10;
const int mod = 1e9 + 7;
const int PP = 13331;
const int inf = 0x3f3f3f3f;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-10;
const double PI = acos(-1);
signed main(){
int n, q;
scanf("%lld%lld", &n, &q);
int cnt = (n * n + 2 - 1) / 2;
while(q --){
int x, y;
scanf("%lld%lld", &x, &y);
if ((x + y) % 2 == 0){
int ans = ((x * n - n + y + 1) / 2);
cout << ans << endl;
}
else{
int ans = ((x * n - n+ y + 1) / 2);
cout << ans + cnt << endl;
}
}
return 0;
}
C - Minimum Value Rectangle
You have n sticks of the given lengths.
Your task is to choose exactly four of them in such a way that they can form a rectangle. No sticks can be cut to pieces, each side of the rectangle must be formed by a single stick. No stick can be chosen multiple times. It is guaranteed that it is always possible to choose such sticks.
Let S be the area of the rectangle and P be the perimeter of the rectangle.
The chosen rectangle should have the value P2S minimal possible. The value is taken without any rounding.
If there are multiple answers, print any of them.
Each testcase contains several lists of sticks, for each of them you are required to solve the problem separately.
Input
The first line contains a single integer T (T≥1) — the number of lists of sticks in the testcase.
Then 2T lines follow — lines (2i−1) and 2i of them describe the i-th list. The first line of the pair contains a single integer n (4≤n≤106) — the number of sticks in the i-th list. The second line of the pair contains n integers a1,a2,…,an (1≤aj≤104) — lengths of the sticks in the i-th list.
It is guaranteed that for each list there exists a way to choose four sticks so that they form a rectangle.
The total number of sticks in all T lists doesn’t exceed 106 in each testcase.
Output
Print T lines. The i-th line should contain the answer to the i-th list of the input. That is the lengths of the four sticks you choose from the i-th list, so that they form a rectangle and the value P2S of this rectangle is minimal possible. You can print these four lengths in arbitrary order.
If there are multiple answers, print any of them.
Example
Input
3
4
7 2 2 7
8
2 8 1 4 8 2 1 5
5
5 5 5 5 5
Output
2 7 7 2
2 2 1 1
5 5 5 5
Note
There is only one way to choose four sticks in the first list, they form a rectangle with sides 2 and 7, its area is 2⋅7=14, perimeter is 2(2+7)=18. 18214≈23.143.
The second list contains subsets of four sticks that can form rectangles with sides (1,2), (2,8) and (1,8). Their values are 622=18, 20216=25 and 1828=40.5, respectively. The minimal one of them is the rectangle (1,2).
You can choose any four of the 5 given sticks from the third list, they will form a square with side 5, which is still a rectangle with sides (5,5).
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <map>
#include <unordered_map>
#include <vector>
#include <cmath>
//#include <ext/rope>
#include <bits/stdc++.h>
using namespace std;
#define gt(x) x = read()
#define int long long
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
//#define x first
//#define y second
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
//typedef __int128 INT;
typedef pair<double, int> PDI;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
inline int read(int out = 0)
{
char c;
while((c=getchar()) < 48 || c > 57);
while(c >= 48 && c <= 57) out=out*10+c-48,c=getchar();
return out;
}
const int N = 1e4 + 10;
const int M = 2e7 + 10;
const int mod = 1e9 + 7;
const int PP = 13331;
const int inf = 0x3f3f3f3f;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-10;
const double PI = acos(-1);
int cnt[N];
signed main(){
// ios;
int T;
scanf("%lld", &T);
while(T --){
vector<int> v;
memset(cnt, 0, sizeof cnt);
int n;
scanf("%lld", &n);
for (int i = 1; i <= n; i ++){
int x;
scanf("%lld", &x);
cnt[x] ++;
if (cnt[x] == 4) v.push_back(x);
if (cnt[x] == 2) v.push_back(x);
;;
}
sort(v.begin(), v.end());
double mind = 0x3f3f3f3f;
int ans1, ans2;
for (int i = 1; i < v.size(); i ++){
// cout << v[i] << "---" << endl;
double res = ((double)v[i] / (double)v[i - 1]);
if (v[i] == v[i - 1]){
ans1 = (int)v[i];
ans2 = (int)v[i - 1];
break;
}
//cout << res << endl;
if (res < mind){
ans1 = v[i], ans2 = v[i - 1];
mind = res;
// if (mind - 1.0 < 1e-6) break;
}
}
printf("%lld %lld %lld %lld\n", ans1, ans1, ans2, ans2);
}
return 0;
}
D - Mouse Hunt
Medicine faculty of Berland State University has just finished their admission campaign. As usual, about 80% of applicants are girls and majority of them are going to live in the university dormitory for the next 4 (hopefully) years.
The dormitory consists of n rooms and a single mouse! Girls decided to set mouse traps in some rooms to get rid of the horrible monster. Setting a trap in room number i costs ci burles. Rooms are numbered from 1 to n.
Mouse doesn’t sit in place all the time, it constantly runs. If it is in room i in second t then it will run to room ai in second t+1 without visiting any other rooms inbetween (i=ai means that mouse won’t leave room i). It’s second 0 in the start. If the mouse is in some room with a mouse trap in it, then the mouse get caught into this trap.
That would have been so easy if the girls actually knew where the mouse at. Unfortunately, that’s not the case, mouse can be in any room from 1 to n at second 0.
What it the minimal total amount of burles girls can spend to set the traps in order to guarantee that the mouse will eventually be caught no matter the room it started from?
Input
The first line contains as single integers n (1≤n≤2⋅105) — the number of rooms in the dormitory.
The second line contains n integers c1,c2,…,cn (1≤ci≤104) — ci is the cost of setting the trap in room number i.
The third line contains n integers a1,a2,…,an (1≤ai≤n) — ai is the room the mouse will run to the next second after being in room i.
Output
Print a single integer — the minimal total amount of burles girls can spend to set the traps in order to guarantee that the mouse will eventually be caught no matter the room it started from.
Examples
Input
5
1 2 3 2 10
1 3 4 3 3
Output
3
Input
4
1 10 2 10
2 4 2 2
Output
10
Input
7
1 1 1 1 1 1 1
2 2 2 3 6 7 6
Output
2
Note
In the first example it is enough to set mouse trap in rooms 1 and 4. If mouse starts in room 1 then it gets caught immideately. If mouse starts in any other room then it eventually comes to room 4.
In the second example it is enough to set mouse trap in room 2. If mouse starts in room 2 then it gets caught immideately. If mouse starts in any other room then it runs to room 2 in second 1.
Here are the paths of the mouse from different starts from the third example:
1→2→2→…;
2→2→…;
3→2→2→…;
4→3→2→2→…;
5→6→7→6→…;
6→7→6→…;
7→6→7→…;
So it’s enough to set traps in rooms 2 and 6.
有n个房间，保证每一个房间只会通向另一个房间(可能会通向自己，可能有多个房间通向一个房间)
有一只老鼠，初始房间不一定，它会在相通的房间内乱窜
你有无数个老鼠夹，可以放到任意房间内，保证老鼠已进入该房间就会被抓住，在不同的房间内放老鼠夹都会有一个对应的代价
请你计算：最少花费多少的代价，才能保证老鼠不管初始在哪个房间内都会被抓住
做法：
首先建图：让第i个房间指向它所能到的房间的编号to[i]，然后使用tarjan缩点，将图变为DAG后，统计每一个强连通分量的出度数（一定要是该点所在的强连通分量的出度数！！！！）
然后只需要统计出度数为0的强连通分量内的最小代价即可
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <map>
#include <unordered_map>
#include <vector>
#include <cmath>
//#include <ext/rope>
#include <bits/stdc++.h>
using namespace std;
#define gt(x) x = read()
#define int long long
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
//#define x first
//#define y second
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
//typedef __int128 INT;
typedef pair<double, int> PDI;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
inline int read(int out = 0)
{
char c;
while((c=getchar()) < 48 || c > 57);
while(c >= 48 && c <= 57) out=out*10+c-48,c=getchar();
return out;
}
const int N = 2e5 + 10;
const int M = 2e5 + 10;
const int mod = 1e9 + 7;
const int PP = 13331;
const int inf = 0x3f3f3f3f;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-10;
const double PI = acos(-1);
int c[N];
int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, Size[N];
int dout[N];
int to[N];
int mind[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++ timestamp;
stk[ ++ top] = u, in_stk[u] = true;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
}
if (dfn[u] == low[u])
{
++ scc_cnt;
int y;
do {
y = stk[top -- ];
in_stk[y] = false;
id[y] = scc_cnt;
mind[scc_cnt] = min(mind[scc_cnt], c[y]);
Size[scc_cnt] ++ ;
} while (y != u);
}
}
signed main(){
memset(mind, 0x3f, sizeof mind);
int n;
scanf("%lld", &n);
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++) scanf("%lld", &c[i]);
for (int i = 1; i <= n; i ++){
scanf("%lld", &to[i]);
add(i, to[i]);
}
for (int i = 1; i <= n; i ++){
if (!dfn[i])
tarjan(i);
}
for (int i = 1; i <= n; i ++){
if (id[i] != id[to[i]])
dout[id[i]] ++;
}
int ans = 0;
for (int i = 1; i <= n; i ++){
if (!dout[id[i]]){
ans += mind[id[i]];
mind[id[i]] = 0;
}
}
cout << ans << endl;
return 0;
}