Codeforces Round #498 (Div. 3）ABCDE
B. Polycarp's Practice
C. Three Parts of the Array
D. Two Strings Swaps
E. Military Problem

A 签到

奇数不变，偶数减一

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 1e5+10;
 5 int n, a[N], b[N], tot;
 6 int M = 1e9;
 7 int main() {
 8     cin >> n;
 9     for(int i = 0; i < n; i ++) {
10         cin >> a[i];
11     }
12     for(int i = 0; i < n; i ++) {
13         if(a[i]&1) printf("%d ",a[i]);
14         else printf("%d ",a[i]-1);
15     }
16     return 0;
17 }

n个数，去k个区间，是的区间的最大值之和最大。

直接去最大的k个数就行。

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 1e5+10;
 5 int n, k, a[N], x;
 6 struct Nod{
 7     int id, num;
 8 }e[N];
 9 bool cmp(Nod a, Nod b) {
10     return a.num > b.num;
11 }
12 int main() {
13     cin >> n >> k;
14     for(int i = 1; i <= n; i ++) {
15         cin >> x;    
16         e[i].id = i;
17         e[i].num = x;
18     }
19     sort(e+1,e+1+n,cmp);
20     int ans = 0;
21     for(int i = 1; i <= k; i ++) {
22         a[i] = e[i].id;
23         ans += e[i].num;
24     }
25     printf("%d
",ans);
26     if(k==1) return 0*printf("%d
",n);
27     sort(a+1,a+1+k);
28     for(int i = 1; i < k; i ++) {
29         printf("%d ",a[i]-a[i-1]);
30     }
31     printf("%d
",n-a[k-1]);
32     return 0;
33 }

C. Three Parts of the Array

n个数，划分为三个区间，可以为空，求第一个区间之和与第三区间之和相同时，最大值是多少。

1至n，遍历下，求出前i个数之和，判断是否[j,n]之和等于前面的就行，二分查找。

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 2e5+10;
 5 ll n, a[N], sum[N], pre[N];
 6 bool ok(int l, int r, ll cnt) {
 7     while(l <= r) {
 8         int m = (l+r) >> 1;
 9         if(pre[m] == cnt) return true;
10         if(pre[m] > cnt) l = m+1;
11         else r = m-1;
12     }
13     return false;
14 }
15 int main() {
16     cin >> n;
17     for(int i = 1; i <= n; i ++) {
18         cin >> a[i];
19         sum[i] = sum[i-1] + a[i];
20     }
21     for(int i = n; i >= 0; i --) pre[i] = pre[i+1] + a[i];
22     ll MAX = 0;
23     for(int i = 1; i <= n; i ++) {
24         ll ans = sum[i];
25         if(ok(i+1,n, ans)) {
26             MAX = ans;
27         }
28     }
29     printf("%lld
",MAX);
30     return 0;
31 }

You are given two strings n, inclusive.

You are allowed to do the following changes:

Choose any index bi;
Choose any index an−i+1;
Choose any index bn−i+1.

Note that if b) but this move is useless. Also you can swap two equal characters but this operation is useless as well.

You have to make these strings equal by applying any number of changes described above, in any order. But it is obvious that it may be impossible to make two strings equal by these swaps.

In one preprocess move you can replace a character in ai:=c.

Your task is to find the minimum number of preprocess moves to apply in such a way that after them you can make strings changes described in the list above.

Note that the number of changes you make after the preprocess moves does not matter. Also note that you cannot apply preprocess movesto the string change is made.

Input

The first line of the input contains one integer b.

The second line contains the string n lowercase English letters.

The third line contains the string n lowercase English letters.

Output

Print a single integer — the minimum number of preprocess moves to apply before changes, so that it is possible to make the string changes from the list above.

Examples

input

Copy

7
abacaba
bacabaa

output

Copy

input

Copy

5
zcabd
dbacz

output

Copy

Note

In the first example preprocess moves are as follows: 4.

In the second example no preprocess moves are required. We can use the following sequence of changes to make swap(a2,a4).

$a$

有几种情况，

当为 a a 不需要改变 a c 改变一次 a a 改变两次

b b b a b c

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 2e5+10;
 5 int n;
 6 set<char> st;
 7 char str1[N], str2[N];
 8 int main() {
 9     cin >> n >> str1+1 >> str2+1;
10     int ans = 0;
11     for(int i = 1, j = n; i < j; i ++, j--) {
12         int now = min((str1[i]!=str2[i])+(str1[j]!=str2[j]), (str1[i]!=str2[j])+(str1[j]!=str2[i]));
13         if(str2[i]==str2[j]) now = min(now, int(str1[i]!=str1[j]));
14         ans += now;
15     }
16     ans += (n%2==1&&str1[(n+1)/2]!=str2[(n+1)/2]);
17     printf("%d
",ans);
18     return 0;
19 }

In this problem you will have to help Berland army with organizing their command delivery system.

There are a.

Officer y if one of the following conditions holds:

officer x;
the direct superior of officer y.

For example, on the picture below the subordinates of the officer 5,6,7,8,9.

The structure of Berland army is organized in such a way that every officer, except for the commander, is a subordinate of the commander of the army.

Formally, let's represent Berland army as a tree consisting of 1) corresponds to the commander of the army.

Berland War Ministry has ordered you to give answers on ki is a positive integer.

To process the ui. Typical DFS (depth first search) algorithm is used here.

Suppose the current officer is a finishes spreading the command.

Let's look at the following example:

$Codeforces Round #498 (Div. 3）ABCDE B. Polycarp's Practice C. Three Parts of the Array D. Two Strings Swaps E. Military Problem$

If officer [1,2,3,5,6,8,7,9,4].

If officer [3,5,6,8,7,9].

If officer [7,9].

If officer [9].

To answer the ki elements in it.

You should process queries independently. A query doesn't affect the following queries.

Input

The first line of the input contains two integers 2≤n≤2⋅105,1≤q≤2⋅105) — the number of officers in Berland army and the number of queries.

The second line of the input contains 1 and doesn't have any superiors.

The next ki is the index of the required officer in the command spreading sequence.

Output

Print ki.

You should process queries independently. They do not affect each other.

Example

input

Copy

9 6
1 1 1 3 5 3 5 7
3 1
1 5
3 4
7 3
1 8
1 9

output

Copy

3
6
8
-1
9
4


求从u考试按深度遍历第k个数是多少，没有则为-1
1为根，从根遍历求的顺序储存，其它的点遍历一定在根遍历的子序列中，所以只要求下从u开始遍历有多少个，并且开始的位置再根遍历的序列中的第几位就行了。

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 2e5+10;
 5 std::vector<int> v[N];
 6 int n, q, x, ans = 1, tot;
 7 int a[N], cnt[N];
 8 map<int,int> mp;
 9 void dfs(int u) {
10     int tmp = ans;
11     for(int i = 0; i < v[u].size(); i ++) {
12         ans++;
13         a[tot++] = v[u][i];
14         dfs(v[u][i]);
15     }
16 //    printf("%d %d %d
",u,ans,tmp );
17     cnt[u] = ans - tmp+1;
18 }
19 int main() {
20     cin >> n >> q;
21     for(int i = 2; i <= n; i ++) {
22         scanf("%d", &x);
23         v[x].push_back(i);
24     }
25     a[tot++] = 1;
26     cnt[1] = n;
27     dfs(1);
28     for(int i = 0; i < tot; i ++) {
29         mp[a[i]] = i;
30     }
31     // for(int i = 1; i <= tot; i ++) printf("%d ", cnt[i]);printf("
");
32     while(q--) {
33         int u, x;
34         scanf("%d%d",&u, &x);
35         if(cnt[u] < x) printf("-1
");
36         else {
37             printf("%d
",a[mp[u]+x-1]);
38         }
39     }
40     return 0;
41 }

Codeforces Round #498 (Div. 3）ABCDE B. Polycarp's Practice C. Three Parts of the Array D. Two Strings Swaps E. Military Problem

C. Three Parts of the Array

D. Two Strings Swaps

E. Military Problem

相关推荐