It's a walking tour day in SIS.Winter, so tt groups of students are visiting Torzhok. Streets of Torzhok are so narrow that students have to go in a row one after another.
Initially, some students are angry. Let's describe a group of students by a string of capital letters "A" and "P":
- "A" corresponds to an angry student
- "P" corresponds to a patient student
Such string describes the row from the last to the first student.
Every minute every angry student throws a snowball at the next student. Formally, if an angry student corresponds to the character with index ii in the string describing a group then they will throw a snowball at the student that corresponds to the character with index i+1i+1 (students are given from the last to the first student). If the target student was not angry yet, they become angry. Even if the first (the rightmost in the string) student is angry, they don't throw a snowball since there is no one in front of them.
Let's look at the first example test. The row initially looks like this: PPAP. Then, after a minute the only single angry student will throw a snowball at the student in front of them, and they also become angry: PPAA. After that, no more students will become angry.
Your task is to help SIS.Winter teachers to determine the last moment a student becomes angry for every group.
InputThe first line contains a single integer tt — the number of groups of students (1≤t≤1001≤t≤100). The following 2t2t lines contain descriptions of groups of students.
The description of the group starts with an integer kiki (1≤ki≤1001≤ki≤100) — the number of students in the group, followed by a string sisi, consisting of kiki letters "A" and "P", which describes the ii-th group of students.
OutputFor every group output single integer — the last moment a student becomes angry.
Examples input Copy1 4 PPAPoutput Copy
1input Copy
3 12 APPAPPPAPPPP 3 AAP 3 PPAoutput Copy
4 1 0Note
In the first test, after 11 minute the state of students becomes PPAA. After that, no new angry students will appear.
In the second tets, state of students in the first group is:
- after 11 minute — AAPAAPPAAPPP
- after 22 minutes — AAAAAAPAAAPP
- after 33 minutes — AAAAAAAAAAAP
- after 44 minutes all 1212 students are angry
In the second group after 11 minute, all students are angry.
找一下最长的连续P序列即可。
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define LL long long
4 #define inf 0x3f3f3f3f
5 #define pii pair<int,int>
6 #define pb push_back
7 #define all(v) (v.begin(),v.end())
8 #define mp make_pair
9
10 int main()
11 {
12 int n,t;
13 string str;
14 int f[111];
15 cin>>t;
16 while(t--){
17 cin>>n>>str;
18 int tmp=0,ans=0;
19 for(int i=n-1;i>=0;--i){
20 if(str[i]=='A'){
21 ans=max(ans,tmp);
22 tmp=0;
23 }else{
24 tmp++;
25 }
26 }
27 cout<<ans<<endl;
28 }
29 return 0;
30 }
View Code
B. Hyperset time limit per test 3 seconds memory limit per test 256 megabytes input standard input output standard output
Bees Alice and Alesya gave beekeeper Polina famous card game "Set" as a Christmas present. The deck consists of cards that vary in four features across three options for each kind of feature: number of shapes, shape, shading, and color. In this game, some combinations of three cards are said to make up a set. For every feature — color, number, shape, and shading — the three cards must display that feature as either all the same, or pairwise different. The picture below shows how sets look.
Polina came up with a new game called "Hyperset". In her game, there are nn cards with kk features, each feature has three possible values: "S", "E", or "T". The original "Set" game can be viewed as "Hyperset" with k=4k=4.
Similarly to the original game, three cards form a set, if all features are the same for all cards or are pairwise different. The goal of the game is to compute the number of ways to choose three cards that form a set.
Unfortunately, winter holidays have come to an end, and it's time for Polina to go to school. Help Polina find the number of sets among the cards lying on the table.
InputThe first line of each test contains two integers nn and kk (1≤n≤15001≤n≤1500, 1≤k≤301≤k≤30) — number of cards and number of features.
Each of the following nn lines contains a card description: a string consisting of kk letters "S", "E", "T". The ii-th character of this string decribes the ii-th feature of that card. All cards are distinct.
OutputOutput a single integer — the number of ways to choose three cards that form a set.
Examples input Copy3 3 SET ETS TSEoutput Copy
1input Copy
3 4 SETE ETSE TSESoutput Copy
0input Copy
5 4 SETT TEST EEET ESTE STESoutput Copy
2Note
In the third example test, these two triples of cards are sets:
- "SETT", "TEST", "EEET"
- "TEST", "ESTE", "STES"
N^2遍历所有得(i,j)然后可以根据(i,j)字符串构造出来第三个T字符串，然后查找一下是否有这个T存在即可，注意最后答案要/3因为会重复出现。
查找时用了一个map，复杂度是O(N2log(N))这个样子，但是很慢，几乎跑满了。
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define LL long long
4 #define inf 0x3f3f3f3f
5 #define pii pair<int,int>
6 #define pb push_back
7 #define all(v) (v.begin(),v.end())
8 #define mp make_pair
9
10 string e[1505];
11 int n,K;
12 map<string,int>M;
13
14 int main()
15 {
16 ios::sync_with_stdio(false);
17 int S='S'+'E'+'T';
18 long long ans=0;
19 cin>>n>>K;
20 for(int i=1;i<=n;++i)cin>>e[i],M[e[i]]++;
21 for(int i=1;i<=n;++i){
22 for(int j=i+1;j<=n;++j){
23 if(i==j)continue;
24 string T;
25 for(int o=0;o<K;++o){
26 if(e[i][o]==e[j][o]) T+=e[i][o];
27 else{
28 T+=(char)(S-e[i][o]-e[j][o]);
29 }
30 }
31 ans+=M[T];
32 }
33 }cout<<ans/3<<endl;
34 return 0;
35 }
View Code
C. Garland time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output
Vadim loves decorating the Christmas tree, so he got a beautiful garland as a present. It consists of nn light bulbs in a single row. Each bulb has a number from 11 to nn (in arbitrary order), such that all the numbers are distinct. While Vadim was solving problems, his home Carp removed some light bulbs from the garland. Now Vadim wants to put them back on.
Vadim wants to put all bulb back on the garland. Vadim defines complexity of a garland to be the number of pairs of adjacent bulbs with numbers with different parity (remainder of the division by 22). For example, the complexity of 1 4 2 3 5 is 22 and the complexity of 1 3 5 7 6 4 2 is 11.
No one likes complexity, so Vadim wants to minimize the number of such pairs. Find the way to put all bulbs back on the garland, such that the complexity is as small as possible.
InputThe first line contains a single integer nn (1≤n≤1001≤n≤100) — the number of light bulbs on the garland.
The second line contains nn integers p1, p2, …, pnp1, p2, …, pn (0≤pi≤n0≤pi≤n) — the number on the ii-th bulb, or 00 if it was removed.
OutputOutput a single number — the minimum complexity of the garland.
Examples input Copy5 0 5 0 2 3output Copy
2input Copy
7 1 0 0 5 0 0 2output Copy
1Note
In the first example, one should place light bulbs as 1 5 4 2 3. In that case, the complexity would be equal to 2, because only (5,4)(5,4) and (2,3)(2,3) are the pairs of adjacent bulbs that have different parity.
In the second case, one of the correct answers is 1 7 3 5 6 4 2.
总算遇到了自己擅长得东西了，直接dp，f[i][j][k]表示当前处于下标i处，当前位置的数字奇偶性为j，且剩余未放置的数字中有k个是奇数，由于剩余未放置的数字中偶数得个数可以根据现有状态推得，所以没必要多开一维了。
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define LL long long
4 #define inf 0x3f3f3f3f
5 #define pii pair<int,int>
6 #define pb push_back
7 #define all(v) (v.begin(),v.end())
8 #define mp make_pair
9
10 int n,a[111],f[105][2][105],tot[105],pre[105];
11 int main()
12 {
13 memset(f,inf,sizeof(f));
14 cin>>n;
15 int ji=0,ou=0,sum=0;
16 for(int i=1;i<=n;++i) {
17 cin>>a[i];
18 tot[a[i]]++;
19 if(a[i]==0){
20 pre[i]=pre[i-1]+1;
21 a[i]=-1;
22 }else{
23 pre[i]=pre[i-1];
24 a[i]%=2;
25 }
26 }
27 for(int i=1;i<=n;++i){
28 if(!tot[i]){
29 if(i%2==0)ou++;
30 else ji++;
31 }
32 }//cout<<ji<<' '<<ou<<endl;
33 sum=ji+ou;
34 if(a[1]!=-1) f[1][a[1]][ji]=0;
35 else{
36 if(ji>0) f[1][1][ji-1]=0;
37 if(ou>0) f[1][0][ji]=0;
38 }
39 for(int i=1;i<=n;++i){
40 for(int j=0;j<=1;++j){
41 for(int k1=0;k1<=ji;++k1){
42 int k2=sum-k1-pre[i];
43 if(f[i][j][k1]!=inf){
44 if(a[i+1]==0){
45 if(j==0){
46 f[i+1][0][k1]=min(f[i+1][0][k1],f[i][j][k1]);
47 }else{
48 f[i+1][0][k1]=min(f[i+1][0][k1],f[i][j][k1]+1);
49 }
50 }else if(a[i+1]==1){
51 if(j==1){
52 f[i+1][1][k1]=min(f[i+1][1][k1],f[i][j][k1]);
53 }else{
54 f[i+1][1][k1]=min(f[i+1][1][k1],f[i][j][k1]+1);
55 }
56 }else{
57 //ji
58 if(k1>0){
59 if(j==1){
60 f[i+1][1][k1-1]=min(f[i+1][1][k1-1],f[i][j][k1]);
61 }else{
62 f[i+1][1][k1-1]=min(f[i+1][1][k1-1],f[i][j][k1]+1);
63 }
64 }
65 //ou
66 if(k2>0){
67 if(j==0){
68 f[i+1][0][k1]=min(f[i+1][0][k1],f[i][j][k1]);
69 }else{
70 f[i+1][0][k1]=min(f[i+1][0][k1],f[i][j][k1]+1);
71 }
72 }
73 }
74 }
75 }
76 }
77 }
78 //cout<<f[2][1][1]<<endl;
79 int ans=inf;
80 for(int k1=0;k1<=ji;++k1)ans=min(ans,min(f[n][0][k1],f[n][1][k1]));
81 cout<<ans<<endl;
82 return 0;
83 }
View Code