全球彩票平台_全球彩票注册平台|官网下载地址

热门关键词: 全球彩票平台,全球彩票注册平台,全球彩官网下载地址

全球彩票注册平台指南针模拟

HDU_5510_Bazinga,

Bazinga

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 5056    Accepted Submission(s): 1596

Problem Description

Ladies and gentlemen, please sit up straight.
Don't tilt your head. I'm serious.

全球彩票注册平台 1

For n given strings S1,S2,⋯,Sn, labelled from 1 to n, you should find the largest i (1≤i≤n) such that there exists an integer j (1≤j<i) and Sj is not a substring of Si.

A substring of a string Si is another string that occurs in Si. For example, ``ruiz" is a substring of ``ruizhang", and ``rzhang" is not a substring of ``ruizhang".

 

 

Input

The first line contains an integer t (1≤t≤50) which is the number of test cases.
For each test case, the first line is the positive integer n (1≤n≤500) and in the following n lines list are the strings S1,S2,⋯,Sn.
All strings are given in lower-case letters and strings are no longer than 2000 letters.

 

 

Output

For each test case, output the largest label you get. If it does not exist, output −1.

 

 

Sample Input

4 5 ab abc zabc abcd zabcd 4 you lovinyou aboutlovinyou allaboutlovinyou 5 de def abcd abcde abcdef 3 a ba ccc

 

 

Sample Output

Case #1: 4 Case #2: -1 Case #3: 4 Case #4: 3

 

 

Source

2015ACM/ICPC亚洲区沈阳站-重现赛(感谢东北大学)

 

  • 找到最大ID字符串i使得存在j<i的字符串不是i的子串
  • 首先考虑如果从l到r串都满足都是r的子串,那么k>r串只需要检测r串即可
  • 如果自l串开始到l k串都是存在小于l的串不是当前串子串,那么对于l k 1串就要检测l-1串和l到l k串
  • 算法出来了,就是记录当前最大id使得此id之前全是id串的子串,然后检测串的范围就是这个id到当前ID的前一位
  • 如果用这样的算法,用c的strstr即可,用kmp可以减少一半时间

 

 

 1 #include <iostream>
 2 #include <string>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <cmath>
 8 #include <vector>
 9 #include <queue>
10 #include <stack>
11 #include <set>
12 #include <map>
13 using namespace std;
14 typedef long long           LL ;
15 typedef unsigned long long ULL ;
16 const int    maxn = 1e5   10   ;
17 const int    inf  = 0x3f3f3f3f ;
18 const int    npos = -1         ;
19 const int    mod  = 1e9   7    ;
20 const int    mxx  = 100   5    ;
21 const double eps  = 1e-6       ;
22 const double PI   = acos(-1.0) ;
23 
24 int T, n, use[maxn], mx, ans;
25 char s[505][2005];
26 std::vector<int> v;
27 int main(){
28     // freopen("in.txt","r",stdin);
29     // freopen("out.txt","w",stdout);
30     while(~scanf("%d",&T)){
31         for(int kase=1;kase<=T;kase  ){
32             ans=-1;
33             scanf("%d",&n);
34             mx=1;
35             use[1]=0;
36             v.clear();
37             scanf("%s",s[1]);
38             for(int i=2;i<=n;i  ){
39                 scanf("%s",s[i]);
40                 int flag=1;
41                 if(strstr(s[i],s[mx])==NULL)
42                     flag=0;
43                 if(flag&&use[i-1]){
44                     for(int j=v.size()-1;j>=0 && flag;j--){
45                         if(strstr(s[i],s[v[j]])==NULL)
46                             flag=0;
47                     }
48                 }
49                 if(flag){
50                     mx=i;    use[i]=0;    v.clear();
51                 }else{
52                     ans=i;    use[i]=1;    v.push_back(i);
53                 }
54             }
55 
56             printf("Case #%d: %dn",kase,ans);
57         }
58     }
59     return 0;
60 }

 

 

 

Bazinga

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 5056    Accepted Submission(s): 1596

Problem Description

Ladies and gentlemen, please sit up straight.
Don't tilt your head. I'm serious.

全球彩票注册平台 2

For n given strings S1,S2,⋯,Sn, labelled from 1 to n, you should find the largest i (1≤i≤n) such that there exists an integer j (1≤j<i) and Sj is not a substring of Si.

A substring of a string Si is another string that occurs in Si. For example, ``ruiz" is a substring of ``ruizhang", and ``rzhang" is not a substring of ``ruizhang".

 

 

Input

The first line contains an integer t (1≤t≤50) which is the number of test cases.
For each test case, the first line is the positive integer n (1≤n≤500) and in the following n lines list are the strings S1,S2,⋯,Sn.
All strings are given in lower-case letters and strings are no longer than 2000 letters.

 

 

Output

For each test case, output the largest label you get. If it does not exist, output −1.

 

 

Sample Input

4 5 ab abc zabc abcd zabcd 4 you lovinyou aboutlovinyou allaboutlovinyou 5 de def abcd abcde abcdef 3 a ba ccc

 

 

Sample Output

Case #1: 4 Case #2: -1 Case #3: 4 Case #4: 3

 

 

Source

2015ACM/ICPC亚洲区沈阳站-重现赛(感谢东北大学)

 

  • 找到最大ID字符串i使得存在j<i的字符串不是i的子串
  • 首先考虑如果从l到r串都满足都是r的子串,那么k>r串只需要检测r串即可
  • 如果自l串开始到l k串都是存在小于l的串不是当前串子串,那么对于l k 1串就要检测l-1串和l到l k串
  • 算法出来了,就是记录当前最大id使得此id之前全是id串的子串,然后检测串的范围就是这个id到当前ID的前一位
  • 如果用这样的算法,用c的strstr即可,用kmp可以减少一半时间

 

 

 1 #include <iostream>
 2 #include <string>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <cmath>
 8 #include <vector>
 9 #include <queue>
10 #include <stack>
11 #include <set>
12 #include <map>
13 using namespace std;
14 typedef long long           LL ;
15 typedef unsigned long long ULL ;
16 const int    maxn = 1e5   10   ;
17 const int    inf  = 0x3f3f3f3f ;
18 const int    npos = -1         ;
19 const int    mod  = 1e9   7    ;
20 const int    mxx  = 100   5    ;
21 const double eps  = 1e-6       ;
22 const double PI   = acos(-1.0) ;
23 
24 int T, n, use[maxn], mx, ans;
25 char s[505][2005];
26 std::vector<int> v;
27 int main(){
28     // freopen("in.txt","r",stdin);
29     // freopen("out.txt","w",stdout);
30     while(~scanf("%d",&T)){
31         for(int kase=1;kase<=T;kase  ){
32             ans=-1;
33             scanf("%d",&n);
34             mx=1;
35             use[1]=0;
36             v.clear();
37             scanf("%s",s[1]);
38             for(int i=2;i<=n;i  ){
39                 scanf("%s",s[i]);
40                 int flag=1;
41                 if(strstr(s[i],s[mx])==NULL)
42                     flag=0;
43                 if(flag&&use[i-1]){
44                     for(int j=v.size()-1;j>=0 && flag;j--){
45                         if(strstr(s[i],s[v[j]])==NULL)
46                             flag=0;
47                     }
48                 }
49                 if(flag){
50                     mx=i;    use[i]=0;    v.clear();
51                 }else{
52                     ans=i;    use[i]=1;    v.push_back(i);
53                 }
54             }
55 
56             printf("Case #%d: %dn",kase,ans);
57         }
58     }
59     return 0;
60 }

 

 

 

题目链接

题目链接

Bazinga

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 5056    Accepted Submission(s): 1596

Problem Description Ladies and gentlemen, please sit up straight.
Don't tilt your head. I'm serious.

全球彩票注册平台 3

For n given strings S1,S2,⋯,Sn, labelled from 1 to n, you should find the largest i (1≤i≤n) such that there exists an integer j (1≤j<i) and Sj is not a substring of Si.

A substring of a string Si is another string that occurs in Si. For example, ``ruiz" is a substring of ``ruizhang", and ``rzhang" is not a substring of ``ruizhang".  

 

Input The first line contains an integer t (1≤t≤50) which is the number of test cases.
For each test case, the first line is the positive integer n (1≤n≤500) and in the following n lines list are the strings S1,S2,⋯,Sn.
All strings are given in lower-case letters and strings are no longer than 2000 letters.  

 

Output For each test case, output the largest label you get. If it does not exist, output −1.  

 

Sample Input 4 5 ab abc zabc abcd zabcd 4 you lovinyou aboutlovinyou allaboutlovinyou 5 de def abcd abcde abcdef 3 a ba ccc  

 

Sample Output Case #1: 4 Case #2: -1 Case #3: 4 Case #4: 3  

 

Source 2015ACM/ICPC亚洲区沈阳站-重现赛(感谢东北大学)  

  • 找到最大ID字符串i使得存在j<i的字符串不是i的子串
  • 首先考虑如果从l到r串都满足都是r的子串,那么k>r串只需要检测r串即可
  • 如果自l串开始到l k串都是存在小于l的串不是当前串子串,那么对于l k 1串就要检测l-1串和l到l k串
  • 算法出来了,就是记录当前最大id使得此id之前全是id串的子串,然后检测串的范围就是这个id到当前ID的前一位
  • 如果用这样的算法,用c的strstr即可,用kmp可以减少一半时间

 

 

 1 #include <iostream>
 2 #include <string>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <cmath>
 8 #include <vector>
 9 #include <queue>
10 #include <stack>
11 #include <set>
12 #include <map>
13 using namespace std;
14 typedef long long           LL ;
15 typedef unsigned long long ULL ;
16 const int    maxn = 1e5   10   ;
17 const int    inf  = 0x3f3f3f3f ;
18 const int    npos = -1         ;
19 const int    mod  = 1e9   7    ;
20 const int    mxx  = 100   5    ;
21 const double eps  = 1e-6       ;
22 const double PI   = acos(-1.0) ;
23 
24 int T, n, use[maxn], mx, ans;
25 char s[505][2005];
26 std::vector<int> v;
27 int main(){
28     // freopen("in.txt","r",stdin);
29     // freopen("out.txt","w",stdout);
30     while(~scanf("%d",&T)){
31         for(int kase=1;kase<=T;kase  ){
32             ans=-1;
33             scanf("%d",&n);
34             mx=1;
35             use[1]=0;
36             v.clear();
37             scanf("%s",s[1]);
38             for(int i=2;i<=n;i  ){
39                 scanf("%s",s[i]);
40                 int flag=1;
41                 if(strstr(s[i],s[mx])==NULL)
42                     flag=0;
43                 if(flag&&use[i-1]){
44                     for(int j=v.size()-1;j>=0 && flag;j--){
45                         if(strstr(s[i],s[v[j]])==NULL)
46                             flag=0;
47                     }
48                 }
49                 if(flag){
50                     mx=i;    use[i]=0;    v.clear();
51                 }else{
52                     ans=i;    use[i]=1;    v.push_back(i);
53                 }
54             }
55 
56             printf("Case #%d: %dn",kase,ans);
57         }
58     }
59     return 0;
60 }

 

 

 

Bazinga Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 5056Accepted Submission(s): 1596 Problem Descriptio...

 

 

Problem Description

Problem Description

Ladies and gentlemen, please sit up straight.
Don't tilt your head. I'm serious.

Ladies and gentlemen, please sit up straight.
Don't tilt your head. I'm serious.

全球彩票注册平台 4

全球彩票注册平台 5

For n given strings S1,S2,⋯,Sn, labelled from 1 to n, you should find the largest i (1≤i≤n) such that there exists an integer j (1≤j<i) and Sj is not a substring of Si.

For n given strings S1,S2,⋯,Sn, labelled from 1 to n, you should find the largest i (1≤i≤n) such that there exists an integer j (1≤j<i) and Sj is not a substring of Si.

A substring of a string Si is another string that occurs in Si. For example, ``ruiz" is a substring of ``ruizhang", and ``rzhang" is not a substring of ``ruizhang".

A substring of a string Si is another string that occurs in Si. For example, ``ruiz" is a substring of ``ruizhang", and ``rzhang" is not a substring of ``ruizhang".

 

 

Input

Input

The first line contains an integer t (1≤t≤50) which is the number of test cases.
For each test case, the first line is the positive integer n (1≤n≤500) and in the following n lines list are the strings S1,S2,⋯,Sn.
All strings are given in lower-case letters and strings are no longer than 2000 letters.

The first line contains an integer t (1≤t≤50) which is the number of test cases.
For each test case, the first line is the positive integer n (1≤n≤500) and in the following n lines list are the strings S1,S2,⋯,Sn.
All strings are given in lower-case letters and strings are no longer than 2000 letters.

 

 

本文由全球彩票平台发布于全球彩票注册平台编程,转载请注明出处:全球彩票注册平台指南针模拟

TAG标签: 全球彩票平台
Ctrl+D 将本页面保存为书签,全面了解最新资讯,方便快捷。