- G - Famous game
- B - BAN & PICK
- A - As easy as one and two
- D - Dima & Timofey
- E - Enigmatic Treasure
- F - Game of Stone
- H - Hard Parallelogram
G - Famous game
Problem Statement
There are N N N stones arranged in a row. The i-th stone from the left is painted in the color C i C_i Ci.
Snuke will perform the following operation zero or more times:
- Choose two stones painted in the same color. Repaint all the stones between them, with the color of the chosen stones.
Find the number of possible final sequences of colors of the stones, modulo 1 0 9 + 7 10^9+7 109+7.
Constraints
- 1 ≤ N ≤ 2 × 1 0 5 1≤N≤2×10^5 1≤N≤2×105
- 1 ≤ C i ≤ 2 × 1 0 5 ( 1 ≤ i ≤ N ) 1≤C_i≤2×10^5(1≤i≤N) 1≤Ci≤2×105(1≤i≤N)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
N
N
C
1
C_1
C1
:
C
N
C_N
CN
Output
Print the number of possible final sequences of colors of the stones, modulo 1 0 9 + 7 10^9+7 109+7.
Sample Input 1
5
1
2
1
2
2
Sample Output 1
3
We can make three sequences of colors of stones, as follows:
- (1,2,1,2,2), by doing nothing.
- (1,1,1,2,2), by choosing the first and third stones to perform the operation.
- (1,2,2,2,2), by choosing the second and fourth stones to perform the operation.
Sample Input 2
6
4
2
5
4
2
4
Sample Output 2
5
Sample Input 3
7
1
3
1
2
3
3
2
Sample Output 3
5
思路
可以理解为：各次操作之间不能有交集。
状态转移方程： f [ i ] = f [ i − 1 ] + ∑ j < i , a [ i ] = a [ j ] f [ j − 1 ] f[i]=f[i-1]+\sum_{j<i,a[i]=a[j]} f[j-1] f[i]=f[i−1]+j<i,a[i]=a[j]∑f[j−1]
其中 ∑ j < i , a [ i ] = a [ j ] f [ j − 1 ] \sum_{j<i,a[i]=a[j]} f[j-1] ∑j<i,a[i]=a[j]f[j−1]可以用前缀和来记录。
#include<cstdio>
#define int long long
using namespace std;
const int maxn=2e5+10,mod=1e9+7;
int n,a[maxn],pre[maxn],f[maxn]={1};
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=n;i++){
if(a[i]==a[i-1]){f[i]=f[i-1];continue;}
f[i]=(f[i-1]+pre[a[i]])%mod;
pre[a[i]]=(pre[a[i]]+f[i-1])%mod;
}
printf("%lld\n",f[n]);
}
B - BAN & PICK
5 friends play LOL together . Every one should BAN one character and PICK one character . The enemy should BAN 5 characters and PICK 5 characters . All these 20 heroes must be different .
Every one can BAN any heroes by his personal washes . But he can only PICK heroes which he has bought .
Suppose the enemy can PICK or BAN any heroes. How many different ways are there satisfying the conditions?
For example , a valid way is :
Player 1 : picks hero 1, bans hero 2
Player 2 : picks hero 3, bans hero 4
Player 3 : picks hero 5, bans hero 6
Player 4 : picks hero 7, bans hero 8
Player 5 : picks hero 9, bans hero 10
Enemies pick heroes 11,12,13,14,15 , ban heroes 16,17,18,19,20 .
Input
The input contains multiple test cases.(No more than 20)
In each test case . there’s 5 strings S[1]∼S[5] ,respectively whose lengths are 100 , For the i-th person if he has bought the j-th hero, the j-th character of S[i] is ‘1’, or ‘0’ if not. The total number of heroes is exactly 100 .
Output
For each test case , print the answer mod 1000000007 in a single line .
Sample Input
0110011100011001001100011110001110001110001010010111111110101010010011010000110100011001001111101011
1000111101111110110100001101001101010001111001001011110001111110101000011101000001011100001001011010
0100101100011110011100110110011100111100010010011001111110101111111000000110001110000110001100001110
1110010101010001000110100011101010001010000110001111111110101010000000001111001110110101110000010011
1000010011111110001101100000101001110100011000111010011111110110111010011111010110101111011111011011
Sample Output
515649254
思路
双方PICK英雄顺序不同，代表不同的选择，但是BAN只考虑组合数。
状态压缩dp， f [ i ] [ j ] f[i][j] f[i][j]代表前i个英雄，我方PICK状态为 j j j的选择数量， ( 0 < = j < 32 , 1 < = i < = 100 ) (0<=j<32,1<=i<=100) (0<=j<32,1<=i<=100)。
状态转移方程（
⊕
\oplus
⊕代表异或）：
f
[
i
]
[
j
]
=
∑
j
&
(
1
<
<
k
)
且
a
[
k
]
[
i
]
=
=
′
1
′
f
[
i
−
1
]
[
j
⊕
(
1
<
<
k
)
]
f[i][j]=\sum_{j\&(1<<k)且a[k][i]=='1'} f[i-1][j \oplus (1<<k)]
f[i][j]=j&(1<<k)且a[k][i]==′1′∑f[i−1][j⊕(1<<k)]
初态 f [ 0 ] [ 0 ] = 1 f[0][0]=1 f[0][0]=1，终态 f [ 100 ] [ ( 1 < < 5 ) − 1 ] f[100][(1<<5)-1] f[100][(1<<5)−1]。
计算结果 f [ 100 ] [ ( 1 < < 5 ) − 1 ] f[100][(1<<5)-1] f[100][(1<<5)−1]仅代表我方PICK的选择数量，还需乘 A 95 5 A^5_{95} A955（敌方PICK选择数）、 C 90 5 C^5_{90} C905（我方BAN选择数）、 C 85 5 C^5_{85} C855 (敌方BAN选择数)。
可以先预处理出 [ 1 , 100 ] [1,100] [1,100]的阶乘，以及阶乘的逆元，计算排列组合时直接调用。或者先算出 A 95 5 × C 90 5 × C 85 5 = 531192758 A^5_{95} \times C^5_{90} \times C^5_{85} = 531192758 A955×C905×C855=531192758 (mod 1000000007)，每次直接乘这个常数。
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
const int maxn=110,mod=1000000007;
char a[6][maxn];
int f[maxn][40],jc[maxn],inv[maxn];
int qpow(int a,int b){
int ret=1;
while(b){
if(b&1) ret=ret*a%mod;
a=a*a%mod,b>>=1;
}
return ret;
}
int A(int up,int down){return jc[down]*inv[down-up]%mod;}
int C(int up,int down){return jc[down]*inv[down-up]%mod*inv[up]%mod;}
signed main(){
jc[0]=1;
for(int i=1;i<=100;i++){
jc[i]=jc[i-1]*i%mod;
inv[i]=qpow(jc[i],mod-2);
}
while(~scanf("%s",a[1]+1)){
memset(f,0,sizeof(f));
for(int i=2;i<=5;i++) scanf("%s",a[i]+1);
f[0][0]=1;
for(int i=1;i<=100;i++)
for(int j=0;j<1<<5;j++){
f[i][j]=f[i-1][j];
for(int k=1;k<=5;k++)
if(a[k][i]=='1'&&j&(1<<(k-1)))
f[i][j]=(f[i][j]+f[i-1][j^(1<<(k-1))])%mod;
}
printf("%lld\n",f[100][(1<<5)-1]*A(5,95)%mod*C(5,90)%mod*C(5,85)%mod);
}
}
A - As easy as one and two
You are given a non-empty string s = s 1 s 2 … s n s=s_1s_2…s_n s=s1s2…sn, which consists only of lowercase Latin letters. Polycarp does not like a string if it contains at least one string “one” or at least one string “two” (or both at the same time) as a substring. In other words, Polycarp does not like the string s if there is an integer j ( 1 ≤ j ≤ n − 2 ) j (1≤j≤n−2) j(1≤j≤n−2), that s j s j + 1 s j + 2 s_js_{j+1}s_{j+2} sjsj+1sj+2=“one” or s j s j + 1 s j + 2 s_js_{j+1}s_{j+2} sjsj+1sj+2=“two”.
For example:
- Polycarp does not like strings “oneee”, “ontwow”, “twone” and “oneonetwo” (they all have at least one substring “one” or “two”),
- Polycarp likes strings “oonnee”, “twwwo” and “twnoe” (they have no substrings “one” and “two”).
Polycarp wants to select a certain set of indices (positions) and remove all letters on these positions. All removals are made at the same time.
For example, if the string looks like s=“onetwone”, then if Polycarp selects two indices 3 and 6, then “onetwone” will be selected and the result is “ontwne”.
What is the minimum number of indices (positions) that Polycarp needs to select to make the string liked? What should these positions be?
Input
The first line of the input contains an integer t ( 1 ≤ t ≤ 1 0 4 ) t (1≤t≤10^4) t(1≤t≤104) — the number of test cases in the input. Next, the test cases are given.
Each test case consists of one non-empty string s. Its length does not exceed 1.5 ⋅ 1 0 5 1.5⋅10^5 1.5⋅105. The string s consists only of lowercase Latin letters.
It is guaranteed that the sum of lengths of all lines for all input data in the test does not exceed 1.5 ⋅ 1 0 6 1.5⋅10^6 1.5⋅106.
Output
Print an answer for each test case in the input in order of their appearance.
The first line of each answer should contain r ( 0 ≤ r ≤ ∣ s ∣ ) r (0≤r≤|s|) r(0≤r≤∣s∣) — the required minimum number of positions to be removed, where |s| is the length of the given line. The second line of each answer should contain r different integers — the indices themselves for removal in any order. Indices are numbered from left to right from 1 to the length of the string. If r=0, then the second line can be skipped (or you can print empty). If there are several answers, print any of them.
Examples
input
4
onetwone
testme
oneoneone
twotwo
output
2
6 3
0
3
4 1 7
2
1 4
input
10
onetwonetwooneooonetwooo
two
one
twooooo
ttttwo
ttwwoo
ooone
onnne
oneeeee
oneeeeeeetwooooo
output
6
18 11 12 1 6 21
1
1
1
3
1
2
1
6
0
1
4
0
1
1
2
1 11
Note
In the first example, answers are:
-
“onetwone”,
-
“testme” — Polycarp likes it, there is nothing to remove,
-
“oneoneone”,
-
“twotwo”.
In the second example, answers are: -
“onetwonetwooneooonetwooo”,
-
“two”,
-
“one”,
-
“twooooo”,
-
“ttttwo”,
-
“ttwwoo” — Polycarp likes it, there is nothing to -remove,
-
“ooone”,
-
“onnne” — Polycarp likes it, there is nothing to remove,
-
“oneeeee”,
-
“oneeeeeeetwooooo”.
思路
其实只有三种情况：
- “twone”，删除*的"o"。
- “one”，删除*的"n"。
- “two”，删除*的“w”。
为什么总要删除*的元素呢？首先对于第一种情况是显然的，只有删除"o"才能一次删掉两个字串；对于第二三种情况，若原字符串为"oooneeee"和"ttwoo"，那么删除两边的元素都无法一次操作删掉这个字串，只能删除*的元素。
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5;
int n,a[maxn],st[maxn],tot;
char s[maxn];
void solve(){
scanf("%s",s+1);
n=strlen(s+1);
tot=0;
memset(a,0,sizeof(a));
for(int i=2;i+1<=n;i++){
if(s[i-1]=='o'&&s[i]=='n'&&s[i+1]=='e'||s[i-1]=='t'&&s[i]=='w'&&s[i+1]=='o'){
a[i]=1;
}
}
for(int i=n;i>=0;i--){
if(a[i]==1){
if(i-2>=1&&a[i-2]==1){
a[i-2]=0;
st[tot++]=i-1;
}else{
st[tot++]=i;
}
}
}
printf("%d\n",tot);
for(int i=0;i<tot;i++){
printf("%d%c",st[i],i==tot-1?'\n':' ');
}
}
int main(){
int te;
scanf("%d",&te);
while(te--) solve();
}
下面代码是参考cf上的答案：
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int te;
cin>>te;
while(te--){
string s;
vector<int> vec;
cin>>s;
for(string sub : {"twone","one","two"}){
for(int p=0;(p=s.find(sub,p))!=string::npos;){
s[p+sub.size()/2]='?';
vec.push_back(p+sub.size()/2);
}
}
cout<<vec.size()<<endl;
for(int i=0;i<vec.size();i++)
cout<<vec[i]+1<<(i==vec.size()-1?'\n':' ');
}
}
D - Dima & Timofey
Young Timofey has a birthday today! He got kit of n cubes as a birthday present from his parents. Every cube has a number ai, which is written on it. Timofey put all the cubes in a row and went to unpack other presents.
In this time, Timofey’s elder brother, Dima reordered the cubes using the following rule. Suppose the cubes are numbered from 1 to n in their order. Dima performs several steps, on step i he reverses the segment of cubes from i-th to (n - i + 1)-th. He does this while i ≤ n - i + 1.
After performing the operations Dima went away, being very proud of himself. When Timofey returned to his cubes, he understood that their order was changed. Help Timofey as fast as you can and save the holiday — restore the initial order of the cubes using information of their current location.
Input
The first line contains single integer n (1 ≤ n ≤ 2·105) — the number of cubes.
The second line contains n integers a1, a2, …, an ( - 109 ≤ ai ≤ 109), where ai is the number written on the i-th cube after Dima has changed their order.
Output
Print n integers, separated by spaces — the numbers written on the cubes in their initial order.
It can be shown that the answer is unique.
Input
7
4 3 7 6 9 1 2
Output
2 3 9 6 7 1 4
Input
8
6 1 4 2 5 6 9 2
Output
2 1 6 2 5 4 9 6
Note
Consider the first sample.
- At the begining row was [2, 3, 9, 6, 7, 1, 4].
- After first operation row was [4, 1, 7, 6, 9, 3, 2].
- After second operation row was [4, 3, 9, 6, 7, 1, 2].
- After third operation row was [4, 3, 7, 6, 9, 1, 2].
- At fourth operation we reverse just middle element, so nothing has changed. The final row is [4, 3, 7, 6, 9, 1, 2]. So the answer for this case is row [2, 3, 9, 6, 7, 1, 4].
思路
离边缘距离为奇数的数字交换顺序，距离偶数的不变。
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int a[maxn],n;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=0;i<n;i++){
if(1+i>=n-i) break;
if(i%2==0) swap(a[1+i],a[n-i]);
}
for(int i=1;i<=n;i++)
printf("%d%c",a[i],i==n?'\n':' ');
}
E - Enigmatic Treasure
Malek has recently found a treasure map. While he was looking for a treasure he found a locked door. There was a string s written on the door consisting of characters ‘(’, ‘)’ and ‘#’. Below there was a manual on how to open the door. After spending a long time Malek managed to decode the manual and found out that the goal is to replace each ‘#’ with one or more ‘)’ characters so that the final string becomes beautiful.
Below there was also written that a string is called beautiful if for each i (1 ≤ i ≤ |s|) there are no more ‘)’ characters than ‘(’ characters among the first i characters of s and also the total number of ‘(’ characters is equal to the total number of ‘)’ characters.
Help Malek open the door by telling him for each ‘#’ character how many ‘)’ characters he must replace it with.
Input
The first line of the input contains a string
s
(
1
≤
∣
s
∣
≤
1
0
5
)
s(1 ≤ |s| ≤ 10^5)
s(1 ≤ ∣s∣ ≤ 105). Each character of this string is one of the characters ‘(’, ‘)’ or ‘#’. It is guaranteed that s contains at least one ‘#’ character.
Output
If there is no way of replacing ‘#’ characters which leads to a beautiful string print - 1. Otherwise for each character ‘#’ print a separate line containing a positive integer, the number of ‘)’ characters this character must be replaced with.
If there are several possible answers, you may output any of them.
Input
(((#)((#)
Output
1
2
Input
()((#((#(#()
Output
2
2
1
Input
#
Output
-1
Input
(#)
Output
-1
Note
|s| denotes the length of the string s.
思路一
先扫描一次原字符串，将所有的")“与前方最近的”(“配对，删掉它们。得到一个新的字符串s，s中应不存在”)"，并且第一个字符不为“#”，最后一个字符不为"("，若不满足任意一条，则无解。
从前到后扫描s，记录"#“的数量numfill和”("的数量numleft，在扫描每一个字母后，都应满足numleft>=numfill，否则无解。
在输出答案时，前面的所有"#“都只匹配一个”("，最后一个"#“匹配所有的多余的”("。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
char s[maxn],news[maxn];
int st[maxn],tot,n,newlen;
int main(){
scanf("%s",s+1);
n=strlen(s+1);
for(int i=1;i<=n;i++){
if(s[i]=='(') st[tot++]=i;
else if(s[i]==')'&&tot>0) s[st[--tot]]='.',s[i]='.';
}
for(int i=1;i<=n;i++){
if(s[i]==')'){puts("-1");return 0;}
else if(s[i]=='.') continue;
else news[++newlen]=s[i];
}
int lnum=0,fillnum=0;
for(int i=1;i<=newlen;i++){
if(news[i]=='(') lnum++;
else if(news[i]=='#') fillnum++;
if(fillnum>lnum){puts("-1");return 0;}
}
if(news[newlen]!='#'||news[1]=='#'){puts("-1");return 0;}
for(int i=1;i<fillnum;i++) printf("1\n");
printf("%d",lnum-fillnum+1);
}
思路二(cf题解)
开一个数组a，a[i]代表当前位置多余的’('数量。
- 若s[i]==’(’，a[i]=a[i-1]+1。
- 否则，a[i]=a[i-1]-1。
每一位a[i]都应非负，否则无解。
若a[n]>0，应倒着往回找最后一个’#’，在查找过程中应满足a[i]>=a[n]（包括s[i]==’#'这个位置），若不满足，无解。
最后一步是自己设计的，cf上只是简单提了一下，没有具体操作。a[i]>=a[n]是为了确保在最后一个s[i]==’#‘的位置添加’)'时，依然不会出现a[i]为负的情况。
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1e5+10;
char s[maxn];
int a[maxn];
int main(){
scanf("%s",s+1);
int n=strlen(s+1);
int Left=0,Fill=0;
for(int i=1;i<=n;i++)
if(s[i]=='(') Left++;
else if(s[i]==')') Left--;
else if(s[i]=='#') Fill++;
for(int i=1;i<=n;i++){
if(s[i]=='(') a[i]=a[i-1]+1;
else a[i]=a[i-1]-1;
if(a[i]<0){printf("-1\n");return 0;}
}
for(int i=n;i>=0;i--){
if(a[i]<a[n]){printf("-1\n");return 0;}
if(s[i]=='#') break;
}
for(int i=1;i<Fill;i++) printf("1\n");
printf("%d\n",Left-Fill+1);
}
F - Game of Stone
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 ⋅ 1 0 9 ) n (1 ≤ n ≤ 2·10^9) n(1 ≤ n ≤ 2⋅109)— the number of movements made by the operator.
The second line contains a single integer x ( 0 ≤ x ≤ 2 ) x (0 ≤ x ≤ 2) 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.
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.
思路
显然，答案是有一个周期的。
#include<bits/stdc++.h>
using namespace std;
const int a[6][3]={{0,1,2},{1,0,2},{1,2,0},{2,1,0},{2,0,1},{0,2,1}};
int n,m;
int main(){
scanf("%d%d",&n,&m);
printf("%d\n",a[n%6][m]);
}
H - Hard Parallelogram
Long time ago Alex created an interesting problem about parallelogram. The input data for this problem contained four integer points on the Cartesian plane, that defined the set of vertices of some non-degenerate (positive area) parallelogram. Points not necessary were given in the order of clockwise or counterclockwise traversal.
Alex had very nice test for this problem, but is somehow happened that the last line of the input was lost and now he has only three out of four points of the original parallelogram. He remembers that test was so good that he asks you to restore it given only these three points.
Input
The input consists of three lines, each containing a pair of integer coordinates x i x_i xi and y i ( − 1000 ≤ x i , y i ≤ 1000 ) y_i ( - 1000 ≤ x_i, y_i ≤ 1000) yi( − 1000 ≤ xi, yi ≤ 1000). It’s guaranteed that these three points do not lie on the same line and no two of them coincide.
Output
First print integer k — the number of ways to add one new integer point such that the obtained set defines some parallelogram of positive area. There is no requirement for the points to be arranged in any special order (like traversal), they just define the set of vertices.
Then print k lines, each containing a pair of integer — possible coordinates of the fourth point.
Input
0 0
1 0
0 1
Output
3
1 -1
-1 1
1 1
Note
If you need clarification of what parallelogram is, please check Wikipedia page:
https://en.wikipedia.org/wiki/Parallelogram
思路
恒有三个点满足条件。
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int px1,px2,px3,py1,py2,py3;
int main(){
scanf("%d%d%d%d%d%d",&px1,&py1,&px2,&py2,&px3,&py3);
printf("3\n");
int dx=px3-px1,dy=py3-py1;
printf("%d %d\n",px2+dx,py2+dy);
dx=px3-px2,dy=py3-py2;
printf("%d %d\n",px1+dx,py1+dy);
dx=px2-px3,dy=py2-py3;
printf("%d %d\n",px1+dx,py1+dy);
}