Rday6

Rday6

小比赛

Connecting Vertices

There are n points marked on the plane. The points are situated in such a way that they form a regular polygon (marked points are its vertices, and they are numbered in counter-clockwise order). You can draw n - 1 segments, each connecting any two marked points, in such a way that all points have to be connected with each other (directly or indirectly).

But there are some restrictions. Firstly, some pairs of points cannot be connected directly and have to be connected undirectly. Secondly, the segments you draw must not intersect in any point apart from the marked points (that is, if any two segments intersect and their intersection is not a marked point, then the picture you have drawn is invalid).

How many ways are there to connect all vertices with n - 1 segments? Two ways are considered different iff there exist some pair of points such that a segment is drawn between them in the first way of connection, but it is not drawn between these points in the second one. Since the answer might be large, output it modulo 109 + 7.

Input
The first line contains one number n (3 ≤ n ≤ 500) — the number of marked points.

Then n lines follow, each containing n elements. ai, j (j-th element of line i) is equal to 1 iff you can connect points i and j directly (otherwise ai, j = 0). It is guaranteed that for any pair of points ai, j = aj, i, and for any point ai, i = 0.

Output
Print the number of ways to connect points modulo 109 + 7.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Examples
Input
3
0 0 1
0 0 1
1 1 0
Output
1
Input
4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
Output
12
Input
3
0 0 0
0 0 1
0 1 0
Output
0

题解:
题解:
区间dpdp
f[i][j]f[i][j]表示ii到jj有边且构成树的方案数
g[i][j]g[i][j]表示ii到jj无边且构成树的方案数
转移:枚举i,ji,j左右端点,kk是断点
f[i][j]+=∑j−1k=i(f[i][k]+g[i][k])∗(f[k+1][j]+g[k+1][j])f[i][j]+=∑k=ij−1(f[i][k]+g[i][k])∗(f[k+1][j]+g[k+1][j])
g[i][j]+=∑j−1k=i+1f[k][j]∗(f[i][k]+g[i][k])g[i][j]+=∑k=i+1j−1f[k][j]∗(f[i][k]+g[i][k])
初始化只要f[i][j]=1f[i][j]=1就可以了

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstdio>
#define ll long long
using namespace std;
const int N=1005,mod=1e9+7;
int n;
ll a[N][N],f[N][N],g[N][N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)f[i][i]=1;
for(int len=2;len<=n;len++)
for(int i=1;i+len-1<=n;i++)
{
int j=i+len-1;
for(int k=i;k<j;k++)
if(a[i][j])
f[i][j]=(f[i][j]+(f[i][k]+g[i][k])*(f[k+1][j]+g[k+1][j])%mod)%mod;
for(int k=i+1;k<j;k++)
if(a[k][j])
g[i][j]=(g[i][j]+f[k][j]*(f[i][k]+g[i][k])%mod)%mod;
}
printf("%lld\n",(f[1][n]+g[1][n])%mod);
return 0;
}

Local Extrema

You are given an array a. Some element of this array ai is a local minimum iff it is strictly less than both of its neighbours (that is, ai < ai - 1 and ai < ai + 1). Also the element can be called local maximum iff it is strictly greater than its neighbours (that is, ai > ai - 1 and ai > ai + 1). Since a1 and an have only one neighbour each, they are neither local minima nor local maxima.

An element is called a local extremum iff it is either local maximum or local minimum. Your task is to calculate the number of local extrema in the given array.

Input
The first line contains one integer n (1 ≤ n ≤ 1000) — the number of elements in array a.

The second line contains n integers a1, a2, …, an (1 ≤ ai ≤ 1000) — the elements of array a.

Output
Print the number of local extrema in the given array.

1
2
3
4
5
6
7
8
9
10
11
Examples
Input
3
1 2 3
Output
0
Input
4
1 5 2 5
Output
2

题解:
签到题,按照题意写就行了
code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
const int maxx = 1e5;
int a[maxx];
int main()
{
int t;
while(scanf("%d",&t)!=EOF)
{
memset(a, 0, sizeof a);
int ans = 0;
for(int i = 0; i < t; i ++) cin >> a[i];
for(int i = 1; i < t - 1; i ++)
{
if(((a[i] < a[i - 1]) && (a[i] < a[i + 1])) || ((a[i] > a[i - 1]) && (a[i] > a[i + 1])))
{
ans ++;
}
}
cout << ans << '\n';
}

return 0;
}

Xor-MST

You are given a complete undirected graph with n vertices. A number ai is assigned to each vertex, and the weight of an edge between vertices i and j is equal to ai xor aj.

Calculate the weight of the minimum spanning tree in this graph.

Input
The first line contains n (1 ≤ n ≤ 200000) — the number of vertices in the graph.

The second line contains n integers a1, a2, …, an (0 ≤ ai < 230) — the numbers assigned to the vertices.

Output
Print one number — the weight of the minimum spanning tree in the graph.

1
2
3
4
5
6
7
8
9
10
11
Examples
Input
5
1 2 3 4 5
Output
8
Input
4
1 2 3 4
Output
8

题意:
不妨从高到低贪心,我们把最高位按01分开两半分治,跨越两半的就在trie上贪心,这样做是O(nlog2n)O(n\log^2n)O(nlog 2n)的
dalao’s code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <math.h>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define drp(i,st,ed) for (int i=st;i>=ed;--i)
#define copy(x,t) memcpy(x,t,sizeof(x))

typedef long long LL;
const LL INF=2147483647;
const int N=200005;

int rec[N*35][2],size[N*35],tot;
int a[N],s[N];

std:: vector <int> v1,v2;

LL ans;

int read() {
int x=0,v=1; char ch=getchar();
for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
return x*v;
}

void ins(int v) {
int x=1;
drp(i,29,0) {
size[x]++;
int tar=(v>>i)&1;
if (!rec[x][tar]) {
rec[x][tar]=++tot;
rec[tot][0]=rec[tot][1]=0;
size[tot]=0;
}
x=rec[x][tar];
} size[x]++;
}

LL ask(int v) {
LL res=0; int x=1;
drp(i,29,0) {
int tar=(v>>i)&1;
if (size[rec[x][tar]]) {
x=rec[x][tar];
} else {
x=rec[x][!tar];
res+=(1LL<<i);
}
}
return res;
}

void solve(int l,int r,int p) {
if (l>=r||p<0) return ;
rep(i,l,r) if ((a[s[i]]>>p)&1) {
v1.push_back(s[i]);
} else v2.push_back(s[i]);
for (int i=0;i<v1.size();++i) s[l+i]=v1[i];
int mid=v1.size()+l;
for (int i=0;i<v2.size();++i) s[mid+i]=v2[i];
tot=1; rec[1][0]=rec[1][1]=0;
rep(i,l,mid-1) ins(a[s[i]]);
LL mn=INF;
rep(i,mid,r) mn=std:: min(mn,ask(a[s[i]]));
if (v1.size()&&v2.size()) ans+=mn;
v1.clear(); v2.clear();
solve(l,mid-1,p-1); solve(mid,r,p-1);
}

int main() {
int n=read(),mx=0;
rep(i,1,n) {
a[i]=read();
mx=std:: max(mx,(int)log2(a[i]));
s[i]=i;
}
solve(1,n,mx);
printf("%lld\n", ans);
return 0;
}

Buggy Robot

Ivan has a robot which is situated on an infinite grid. Initially the robot is standing in the starting cell (0, 0). The robot can process commands. There are four types of commands it can perform:

U — move from the cell (x, y) to (x, y + 1);
D — move from (x, y) to (x, y - 1);
L — move from (x, y) to (x - 1, y);
R — move from (x, y) to (x + 1, y).
Ivan entered a sequence of n commands, and the robot processed it. After this sequence the robot ended up in the starting cell (0, 0), but Ivan doubts that the sequence is such that after performing it correctly the robot ends up in the same cell. He thinks that some commands were ignored by robot. To acknowledge whether the robot is severely bugged, he needs to calculate the maximum possible number of commands that were performed correctly. Help Ivan to do the calculations!

Input
The first line contains one number n — the length of sequence of commands entered by Ivan (1 ≤ n ≤ 100).

The second line contains the sequence itself — a string consisting of n characters. Each character can be U, D, L or R.

Output
Print the maximum possible number of commands from the sequence the robot could perform to end up in the starting cell.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Examples
Input
4
LDUR
Output
4
Input
5
RRRUU
Output
0
Input
6
LLRRRR
Output
4

题意:
最大能够执行的命令数量

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
const int maxx = 1e5;
int main()
{
ios::sync_with_stdio(false);
int t, maxnum = 0;
char c;
cin >> t;
int flag = 0;
int x = 0, y = 0, ans = 0;
int ans1 = 0, ans2 = 0, ans3 = 0, ans4 = 0;
for(int i = 0; i < t; i ++)
{
cin >> c;
if(c == 'L') ans1 ++;
else if(c == 'R') ans2 ++;
else if(c == 'U') ans3 ++;
else ans4 ++;
}
int min1 = min(ans1, ans2);
int min2 = min(ans3, ans4);
ans = (min1 + min2) * 2;
if(min1 != 0 || min2 != 0) cout << ans << '\n';
else puts("0");

return 0;
}

K-Dominant Character

You are given a string s consisting of lowercase Latin letters. Character c is called k-dominant iff each substring of s with length at least k contains this character c.

You have to find minimum k such that there exists at least one k-dominant character.

Input
The first line contains string s consisting of lowercase Latin letters (1 ≤ |s| ≤ 100000).

Output
Print one number — the minimum value of k such that there exists at least one k-dominant character.

1
2
3
4
5
6
7
8
9
10
11
12
13
Examples
Input
abacaba
Output
2
Input
zzzzz
Output
1
Input
abcde
Output
3

题意:
给你一个长度为n字符串,求最小的长度m,使得字符串中所有长度为m的子字符串中均包含某一种字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int maxn=1000000+10;
const int INF=0x3f3f3f3f;
char s[maxn];
int a[100],n;
int vis[100];
map<char,int>mp;
bool check(int x){
memset(a,0,sizeof(a));
memset(vis,0,sizeof(vis));
for(int i=0;i<x;i++){
a[s[i]-'a']++;
}
for(int i=0;i<26;i++) if(!a[i]) vis[i]=1;
for(int i=x;i<n;i++){
a[s[i]-'a']++;
a[s[i-x]-'a']--;
for(int j=0;j<26;j++) if(!a[j]) vis[j]=1;
}
for(int i=0;i<26;i++){
if(mp[i]){
if(!vis[i]) return true;
}
}
return false;
}
int main()
{
scanf("%s",s);
n=strlen(s);
int l=1,r=n;
for(int i=0;i<n;i++){
mp[s[i]-'a']++;
}
while(l<=r){
int m=(l+r)/2;
if(check(m)) r=m-1;
else l=m+1;
}
printf("%d\n",r+1);
return 0;
}

Maximum Subsequence

You are given an array a consisting of n integers, and additionally an integer m. You have to choose some sequence of indices b1, b2, …, bk (1 ≤ b1 < b2 < … < bk ≤ n) in such a way that the value of is maximized. Chosen sequence can be empty.

Print the maximum possible value of .

Input
The first line contains two integers n and m (1 ≤ n ≤ 35, 1 ≤ m ≤ 109).

The second line contains n integers a1, a2, …, an (1 ≤ ai ≤ 109).

Output
Print the maximum possible value of .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Examples
Input
4 4
5 2 4 1
Output
3
Input
3 20
199 41 299
Output
19
Note
In the first example you can choose a sequence b = {1, 2}, so the sum is equal to 7 (and that's 3 after taking it modulo 4).

In the second example you can choose a sequence b = {3}.

题意:
给你一个大小为n的数组和一个数m,求从数组中挑出任意多个数(可以为零,不可以重复),计算出
20190924202510.png
的最大值,其中k为选出的数的个数。

超大背包,将所有物品平均分成两部分,然后枚举所有状态。再枚举某一堆物品的所有值,二分从另一堆查找最优解即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int maxn=3000000+10;
const int INF=0x3f3f3f3f;
ll a[maxn];
ll q[maxn],p[maxn];
int main()
{
ll n,m;
scanf("%lld %lld",&n,&m);
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
a[i]%=m;
}
ll x=n/2;
ll N=1<<x;
for(int i=0;i<N;i++){
ll sum=0;
for(int j=0;j<x;j++){
if((i>>j)&1) sum=(sum+a[j])%m;
}
p[i]=sum;
}
N=1<<(n-x);
for(int i=0;i<N;i++){
ll sum=0;
for(int j=0;j<n-x;j++){
if((i>>j)&1) sum=(sum+a[j+x])%m;
}
q[i]=sum;
}
sort(q,q+N);
ll res=0;
for(int i=0;i<1<<x;i++){
ll pos=lower_bound(q,q+N,m-1-p[i])-q;
res=max(res,(p[i]+q[pos])%m);
if(pos) res=max(res,(p[i]+q[pos-1])%m);
}
printf("%lld\n",res);
return 0;
}

Alomost Identity Permutations

A permutation p of size n is an array such that every integer from 1 to n occurs exactly once in this array.

Let’s call a permutation an almost identity permutation iff there exist at least n - k indices i (1 ≤ i ≤ n) such that pi = i.

Your task is to count the number of almost identity permutations for given numbers n and k.

Input
The first line contains two integers n and k (4 ≤ n ≤ 1000, 1 ≤ k ≤ 4).

Output
Print the number of almost identity permutations for given n and k.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Examples
input
4 1
output
1
input
4 2
output
7
input
5 3
output
31
input
5 4
output
76

题意:
问n个数的全排列中,有多少排列满足∑pi=i的值大于等于n−k。
k≤4,枚举即可。

对于k=1 , res=1;
对于k=2 , res=C2n
对于k=3 , res=C3n∗2
对于k=4 , res=C4n∗9
上面每一行的意义在于:从n个数中挑出k个数,每种选法又分别多少种方案使得∑ki=1pi=1 的值为0。
code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int maxn=3000000+10;
const int INF=0x3f3f3f3f;

int main()
{
ll n,k;
scanf("%lld %lld",&n,&k);
ll cur=n;
ll res=1;
ll fac=1;
for(ll i=2;i<=k;i++){
fac=fac*i;
cur=cur*(n-i+1)/i;
if(i==2) res+=cur;
if(i==3) res+=cur*2;
if(i==4) res+=cur*9;
}
printf("%lld\n",res);
return 0;
}

Alyona and Spreadsheet

During the lesson small girl Alyona works with one famous spreadsheet computer program and learns how to edit tables.

Now she has a table filled with integers. The table consists of n rows and m columns. By ai, j we will denote the integer located at the i-th row and the j-th column. We say that the table is sorted in non-decreasing order in the column j if ai, j ≤ ai + 1, j for all i from 1 to n - 1.

Teacher gave Alyona k tasks. For each of the tasks two integers l and r are given and Alyona has to answer the following question: if one keeps the rows from l to r inclusive and deletes all others, will the table be sorted in non-decreasing order in at least one column? Formally, does there exist such j that ai, j ≤ ai + 1, j for all i from l to r - 1 inclusive.

Alyona is too small to deal with this task and asks you to help!

Input
The first line of the input contains two positive integers n and m (1 ≤ n·m ≤ 100 000) — the number of rows and the number of columns in the table respectively. Note that your are given a constraint that bound the product of these two integers, i.e. the number of elements in the table.

Each of the following n lines contains m integers. The j-th integers in the i of these lines stands for ai, j (1 ≤ ai, j ≤ 109).

The next line of the input contains an integer k (1 ≤ k ≤ 100 000) — the number of task that teacher gave to Alyona.

The i-th of the next k lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n).

Output
Print “Yes” to the i-th line of the output if the table consisting of rows from li to ri inclusive is sorted in non-decreasing order in at least one column. Otherwise, print “No”.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Example
input
5 4
1 2 3 5
3 1 3 2
4 5 2 3
5 5 3 2
4 4 3 4
6
1 1
2 5
4 5
3 5
1 3
1 5
output
Yes
No
Yes
Yes
Yes
No
Note
In the sample, the whole table is not sorted in any column. However, rows 13 are sorted in column 1, while rows 45 are sorted in column 3.

题意:
从n∗m的矩阵中挑出从第l行到第r行,问在这(r−l+1)∗m的矩阵中是否存在某一列,使得这一列的元素按序号从小到大非递减。

前缀和即可。计算每一行某个元素前面的所有的元素能够非递增的最小的起点,由于n,m的值未定,所以必须用一维数组来保存。

在查找[l,r]行时,只需要看第r行的m个元素是否存在某个元素,他所在的非递减序列的起点小于等于l即可,由于不能用for循环查询,所以需要前缀和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int maxn=3000000+10;
const int INF=0x3f3f3f3f;
ll a[maxn];
ll b[maxn];
ll res[maxn];
ll dp[maxn];
int main()
{
ll n,m,q,l,r;
scanf("%lld %lld",&n,&m);
for(int i=1;i<=n*m;i++){
scanf("%lld",&a[i]);
}
res[0]=1;
for(int j=1;j<=m;j++){
ll pos=1;
res[j]=1;
for(int i=2;i<=n;i++){
if(a[m*(i-1)+j]>=a[(i-2)*m+j]) res[(i-1)*m+j]=pos;//非递减
else{//递减的话就是一个新的起点
res[m*(i-1)+j]=i;
pos=i;
}
if(j>1) res[m*(i-1)+j]=min(res[m*(i-1)+j],res[m*(i-1)+j-1]);\\计算前缀最小值
}
}
scanf("%lld",&q);
while(q--){
scanf("%lld %lld",&l,&r);
if(res[r*m]<=l) printf("Yes\n");
else printf("No\n");
}
return 0;
}

Shell Game

Bomboslav likes to look out of the window in his room and watch lads outside playing famous shell game. The game is played by two persons: operator and player. Operator takes three similar opaque shells and places a ball beneath one of them. Then he shuffles the shells by swapping some pairs and the player has to guess the current position of the ball.

Bomboslav noticed that guys are not very inventive, so the operator always swaps the left shell with the middle one during odd moves (first, third, fifth, etc.) and always swaps the middle shell with the right one during even moves (second, fourth, etc.).

Let’s number shells from 0 to 2 from left to right. Thus the left shell is assigned number 0, the middle shell is 1 and the right shell is 2. Bomboslav has missed the moment when the ball was placed beneath the shell, but he knows that exactly n movements were made by the operator and the ball was under shell x at the end. Now he wonders, what was the initial position of the ball?

Input
The first line of the input contains an integer n (1 ≤ n ≤ 2·109) — the number of movements made by the operator.

The second line contains a single integer x (0 ≤ x ≤ 2) — the index of the shell where the ball was found after n movements.

Output
Print one integer from 0 to 2 — the index of the shell where the ball was initially placed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Examples
input
4
2
output
1
input
1
1
output
0
Note
In the first sample, the ball was initially placed beneath the middle shell and the operator completed four movements.

During the first move operator swapped the left shell and the middle shell. The ball is now under the left shell.
During the second move operator swapped the middle shell and the right one. The ball is still under the left shell.
During the third move operator swapped the left shell and the middle shell again. The ball is again in the middle.
Finally, the operators swapped the middle shell and the right shell. The ball is now beneath the right shell.

题意:
三个杯子,初始某个杯子中有一个小球,经过n次下列操作后,小球在第x号杯子(0,1,2号):

此次操作次数的序号为第奇数次,交换0号和1号杯子。
此次操作次数的序号为第偶数次,交换1号和2号杯子。
问初始小球在那个杯子。

模拟后发现,每6次操作一个循环,因此n mod 6后模拟计算即可。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int maxn=3000000+10;
const int INF=0x3f3f3f3f;
int a[maxn];
int res[maxn];
int dp[maxn];
int main()
{
int n,m;
scanf("%d %d",&n,&m);
n%=6;
int a[10];
a[0]=0;a[1]=1;a[2]=2;
for(int i=1;i<=n;i++){
if(i&1) swap(a[0],a[1]);
else swap(a[1],a[2]);
}
printf("%d\n",a[m]);
return 0;
}

Hanoi Factory

Of course you have heard the famous task about Hanoi Towers, but did you know that there is a special factory producing the rings for this wonderful game? Once upon a time, the ruler of the ancient Egypt ordered the workers of Hanoi Factory to create as high tower as possible. They were not ready to serve such a strange order so they had to create this new tower using already produced rings.

There are n rings in factory’s stock. The i-th ring has inner radius ai, outer radius bi and height hi. The goal is to select some subset of rings and arrange them such that the following conditions are satisfied:

Outer radiuses form a non-increasing sequence, i.e. one can put the j-th ring on the i-th ring only if bj ≤ bi.
Rings should not fall one into the the other. That means one can place ring j on the ring i only if bj > ai.
The total height of all rings used should be maximum possible.
Input
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of rings in factory’s stock.

The i-th of the next n lines contains three integers ai, bi and hi (1 ≤ ai, bi, hi ≤ 109, bi > ai) — inner radius, outer radius and the height of the i-th ring respectively.

Output
Print one integer — the maximum height of the tower that can be obtained.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Examples
input
3
1 5 1
2 6 2
3 7 3
output
6
input
4
1 2 1
1 3 3
4 6 2
5 7 1
output
4
Note
In the first sample, the optimal solution is to take all the rings and put them on each other in order 3, 2, 1.

In the second sample, one can put the ring 3 on the ring 4 and get the tower of height 3, or put the ring 1 on the ring 2 and get the tower of height 4.

题意:
给你n个圆环,每个圆环有一个外径和内径,现在将这些圆环堆起来,满足上面的圆环外径bi≤bj且bi>aj 其中aj,bj分别为下面一个圆环的内径和外径。问最高能将这些圆环堆多高。

一个简单的模拟题。。。(我居然写了一下午的区间更新查询线段树)

按照圆环外径从大到小排序,如果外径相同按照内径从大到小排序,然后按照顺序模拟即可,如果当前这个圆环放不到前面这个圆环,就继续往前面找,直到找到为止(这里可以用一个数组保存每个圆环找到的位置。
code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int maxn=2000000+10;
const int INF=0x3f3f3f3f;
struct node{
ll l,r,h;
bool friend operator<(node i,node j){
if(i.r==j.r) return i.l>j.l;
return i.r>j.r;
}
}a[maxn];
ll res[maxn];
ll pre[maxn];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld %lld %lld",&a[i].l,&a[i].r,&a[i].h);
}
sort(a+1,a+n+1);
res[1]=a[1].h;
int cur=1;
for(int i=2;i<=n;i++){
while(!(a[cur].l<a[i].r && a[i].r<=a[cur].r) && cur) cur=pre[cur];
res[i]=res[cur]+a[i].h;
pre[i]=cur;
cur=i;
}
ll ans=0;
for(int i=1;i<=n;i++) ans=max(ans,res[i]);
printf("%lld\n",ans);
return 0;
}

Cloud of Hashtags

Vasya is an administrator of a public page of organization “Mouse and keyboard” and his everyday duty is to publish news from the world of competitive programming. For each news he also creates a list of hashtags to make searching for a particular topic more comfortable. For the purpose of this problem we define hashtag as a string consisting of lowercase English letters and exactly one symbol ‘#’ located at the beginning of the string. The length of the hashtag is defined as the number of symbols in it without the symbol ‘#’.

The head administrator of the page told Vasya that hashtags should go in lexicographical order (take a look at the notes section for the definition).

Vasya is lazy so he doesn’t want to actually change the order of hashtags in already published news. Instead, he decided to delete some suffixes (consecutive characters at the end of the string) of some of the hashtags. He is allowed to delete any number of characters, even the whole string except for the symbol ‘#’. Vasya wants to pick such a way to delete suffixes that the total number of deleted symbols is minimum possible. If there are several optimal solutions, he is fine with any of them.

Input
The first line of the input contains a single integer n (1 ≤ n ≤ 500 000) — the number of hashtags being edited now.

Each of the next n lines contains exactly one hashtag of positive length.

It is guaranteed that the total length of all hashtags (i.e. the total length of the string except for characters ‘#’) won’t exceed 500 000.

Output
Print the resulting hashtags in any of the optimal solutions.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
Examples
input
3
#book
#bigtown
#big
output
#b
#big
#big
input
3
#book
#cool
#cold
output
#book
#co
#cold
input
4
#car
#cart
#art
#at
output
#
#
#art
#at
input
3
#apple
#apple
#fruit
output
#apple
#apple
#fruit
Note
Word a1, a2, ..., am of length m is lexicographically not greater than word b1, b2, ..., bk of length k, if one of two conditions hold:

at first position i, such that ai ≠ bi, the character ai goes earlier in the alphabet than character bi, i.e. a has smaller character than b in the first position where they differ;
if there is no such position i and m ≤ k, i.e. the first word is a prefix of the second or two words are equal.
The sequence of words is said to be sorted in lexicographical order if each word (except the last one) is lexicographically not greater than the next word.

For the words consisting of lowercase English letters the lexicographical order coincides with the alphabet word order in the dictionary.

According to the above definition, if a hashtag consisting of one character '#' it is lexicographically not greater than any other valid hashtag. That's why in the third sample we can't keep first two hashtags unchanged and shorten the other two.

题意:
有n个新闻标题,你要删除最少的字符,使得最后所有的标题按照输入顺序字典序升序排列。并输出删除后的新闻标题。

首先知道如果两个标题的字典序比较为降序,那么一定是要删除前面的那个标题,使得那个标题字典序变小。所以我们从后往前删除,能够保证每个标题删除的字符数量最少。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int maxn=3000000+10;
const int INF=0x3f3f3f3f;
string a[maxn];
int len[maxn];
int main()
{
int n;
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i];
len[i]=a[i].length();
}
for(int i=n-1;i>0;i--){
bool flag=0;
for(int j=1;j<=min(len[i],len[i+1]);j++){
if(a[i][j]<a[i+1][j]) break;
if(a[i][j]>a[i+1][j]){
a[i][j]='\0';
break;
}
}
}
for(int i=1;i<=n;i++){
for(int j=0;a[i][j]!='\0';j++){
cout << a[i][j];
}
cout << endl;
}
return 0;
}

Game of Credit Cards

After the fourth season Sherlock and Moriary have realized the whole foolishness of the battle between them and decided to continue their competitions in peaceful game of Credit Cards.

Rules of this game are simple: each player bring his favourite n-digit credit card. Then both players name the digits written on their cards one by one. If two digits are not equal, then the player, whose digit is smaller gets a flick (knock in the forehead usually made with a forefinger) from the other player. For example, if n = 3, Sherlock’s card is 123 and Moriarty’s card has number 321, first Sherlock names 1 and Moriarty names 3 so Sherlock gets a flick. Then they both digit 2 so no one gets a flick. Finally, Sherlock names 3, while Moriarty names 1 and gets a flick.

Of course, Sherlock will play honestly naming digits one by one in the order they are given, while Moriary, as a true villain, plans to cheat. He is going to name his digits in some other order (however, he is not going to change the overall number of occurences of each digit). For example, in case above Moriarty could name 1, 2, 3 and get no flicks at all, or he can name 2, 3 and 1 to give Sherlock two flicks.

Your goal is to find out the minimum possible number of flicks Moriarty will get (no one likes flicks) and the maximum possible number of flicks Sherlock can get from Moriarty. Note, that these two goals are different and the optimal result may be obtained by using different strategies.

Input
The first line of the input contains a single integer n (1 ≤ n ≤ 1000) — the number of digits in the cards Sherlock and Moriarty are going to use.

The second line contains n digits — Sherlock’s credit card number.

The third line contains n digits — Moriarty’s credit card number.

Output
First print the minimum possible number of flicks Moriarty will get. Then print the maximum possible number of flicks that Sherlock can get from Moriarty.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Examples
input
3
123
321
output
0
2
input
2
88
00
output
2
0
Note
First sample is elaborated in the problem statement. In the second sample, there is no way Moriarty can avoid getting two flicks.

题意:
S 某,M某分别有一张序号长度为n的信用卡,他们定了一个规则:比赛分为n局,每局S某,M某从n个数字中分别不重复的取出一个数字,谁的数字小谁得一分,平局不算分。
问如果随机排列这些数字,S某可能的最高得分和M某可能的最低得分分别为多少。

模拟题,算最高分时只要从小到大让S某牌去压M某小于自己当前牌大小的牌即可。算最低分时,只要从大到小让M某去压S某大于等于自己当前牌大小的牌即可。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int maxn=1000000+10;
const int INF=0x3f3f3f3f;
char s[maxn],t[maxn];
int a[100],b[100];
int main()
{
int n;
scanf("%d",&n);
scanf("%s %s",s,t);
for(int i=0;i<n;i++){
a[s[i]-'0']++;
b[t[i]-'0']++;
}
int res1=0,res2=0;
int sum=0;
for(int i=0;i<10;i++){
sum+=a[i];
res1+=min(b[i],sum);
sum-=min(b[i],sum);
}
sum=0;
for(int i=9;i>=0;i--){
res2+=min(a[i],sum);
sum-=min(a[i],sum);
sum+=b[i];
}
printf("%d\n%d\n",n-res1,res2);
return 0;
}

---------------- The End ----------------
0%