Codeforces Round #329（Div2）

CodeForces 593A

题意：n个字符串，选一些字符串，在这些字符串中使得不同字母最多有两个，求满足这个条件可选得的最多字母个数。

思路：用c[i][j]统计文章中只有i,j对应两个字母出现的字符串的长度和。

c[i][i]表示只有一个字母字符串的累计长度。

c[i][j] i!=j时：i>j i<-->j i与j交换。

统计完以后，i,j 0->26. i==j ans=max(max,c[i][i]) i!=j ans=max(max,c[i][j]+c[i][i]+c[j][j])

注意：不能直接暴力，存下每个字符串出现不超过两个不同的字母，再进行两重循环判断，这样比较复杂，并且answer不对。

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 using namespace std;
 6 
 7 int n,c[30][30],len;
 8 char s[1005];
 9 
10 void deal()
11 {
12     len=strlen(s);
13     int f=0,x,y,z;
14     for(int j=0;j<len;j++)
15     {
16         z=s[j]-'a';
17         if(f==0)
18         {
19             x=z;
20             f++;
21         }
22         else if(f==1&&x!=z)
23         {
24             y=z;
25             f++;
26         }
27         else if(f==2&&x!=z&&y!=z)
28         {
29             f++;
30             break;
31         }
32     }
33     if(f==1)
34         c[x][x]+=len;
35     else if(f==2)
36     {
37         if(y<x)
38         {
39             int t=x;x=y;y=t;
40         }
41         c[x][y]+=len;
42     }
43 }
44 
45 int countt()
46 {
47     int maxx=0;
48     for(int i=0;i<26;i++)
49         for(int j=i;j<26;j++)
50         {
51             if(i!=j)
52             maxx=max(maxx,c[i][j]+c[i][i]+c[j][j]);    
53             else
54                 maxx=max(maxx,c[i][j]);
55         }    
56     return maxx;
57 }
58 
59 int main()
60 {
61     while(~scanf("%d",&n))
62     {
63         memset(c,0,sizeof(c));
64         for(int i=0;i<n;i++)
65         {
66             scanf("%s",s);
67             deal();
68         }    
69         printf("%d
",countt());
70     }
71     return 0;
72 }

View Code

CodeForces 593B

题意：在一个坐标中，给定x1,x2.为一个区间范围，给出n条线的Ki,Bi. Yi=Xi*Ki+Bi x1<Xi<x2.求这些线在x1,x2中间是否有交点。

思路：可以求出每条线与x1,x2的交点，即Y的取值范围。

例：r1,r2与x1分别交点L1,L2,与x2分别交点R1,R2。两条线相交，必须满足：L1<L2&&R1>R2 || L1>L2&&R1<R2

数据n范围为1e5,直接暴力比较n^2会超时。可利用sort()排序，nlogn. 在排序中对两条线的端点进行判断标记即可

注意：数据范围！！！！

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxn=1e5+5;
 7 
 8 int n,x1,x2,flag;
 9 struct node
10 {
11     int l,r;
12 }p[maxn];
13 
14 bool cmp(node a,node b)
15 {
16     if((a.l<b.l&&a.r>b.r)||(a.r<b.r&&a.l>b.l))
17         flag=1;
18     if(a.l==b.l)
19         return a.r<b.r;
20     return a.l<b.l;
21 }
22 
23 int main()
24 {
25     int x,y;
26     while(~scanf("%d",&n))
27     {
28         flag=0;
29         scanf("%d%d",&x1,&x2);
30         for(int i=0;i<n;i++)
31         {
32             scanf("%d%d",&x,&y);
33             p[i].l=x*x1+y;
34             p[i].r=x*x2+y;
35         }
36         sort(p,p+n,cmp);
37         printf("%s
",flag==1?"YES":"NO");
38     }
39     return 0;
40 }

View Code