Codeforces Round #612 (Div. 2)/A/B/C

A. Angry Students time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

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.

Codeforces Round #612 (Div. 2)/A/B/C

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.

Input

The 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.

Output

For every group output single integer — the last moment a student becomes angry.

Examples input Copy
1
4
PPAP
output Copy
1
input Copy
3
12
APPAPPPAPPPP
3
AAP
3
PPA
output Copy
4
1
0
Note

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序列即可。

Codeforces Round #612 (Div. 2)/A/B/C
 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.

Codeforces Round #612 (Div. 2)/A/B/C

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.

Input

The 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.

Output

Output a single integer — the number of ways to choose three cards that form a set.

Examples input Copy
3 3
SET
ETS
TSE
output Copy
1
input Copy
3 4
SETE
ETSE
TSES
output Copy
0
input Copy
5 4
SETT
TEST
EEET
ESTE
STES
output Copy
2
Note

In the third example test, these two triples of cards are sets:

  1. "SETT", "TEST", "EEET"
  2. "TEST", "ESTE", "STES"

 

N^2遍历所有得(i,j)然后可以根据(i,j)字符串构造出来第三个T字符串,然后查找一下是否有这个T存在即可,注意最后答案要/3因为会重复出现。

查找时用了一个map,复杂度是O(N2log(N))这个样子,但是很慢,几乎跑满了。

Codeforces Round #612 (Div. 2)/A/B/C
 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.

Codeforces Round #612 (Div. 2)/A/B/C

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.

Input

The 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.

Output

Output a single number — the minimum complexity of the garland.

Examples input Copy
5
0 5 0 2 3
output Copy
2
input Copy
7
1 0 0 5 0 0 2
output Copy
1
Note

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个是奇数,由于剩余未放置的数字中偶数得个数可以根据现有状态推得,所以没必要多开一维了。

Codeforces Round #612 (Div. 2)/A/B/C
 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

 

上一篇:墙裂谴责班级氪cp行为


下一篇:P1368 工艺 /【模板】最小表示法