Problem_A(593A):
题意：
给n个单词， 每个单词由小写字母组成， 且长度<=1000.
组成一篇文章的要求是：
所有单词所用字母 <= 2
即最多只能有两个不同的字母。
求一篇文章的最长长度。
思路：
首先注意到单词都是由小写字母组成，小写字母只有26个， 所以可以转换一下：
如果一个单词所用字母超过2个， 那么我们舍弃它。因为它怎么都不可能会是一篇文章的组成部分。
如果没有超过两个， 那么找出这两个单词， 记录它的长度即可。
设f[i][j] = 只有字母为i + 'a' 和 j + 'a'的单词的长度，如果i == j则只有一个字母。
答案则为 max(f[i][j] + f[i][i] + f[j][j] (f[i][j] > 0), f[i][i] + f[j][j])
代码：
1 #include <cmath> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <ctime> 6 #include <set> 7 #include <map> 8 #include <list> 9 #include <stack> 10 #include <queue> 11 #include <string> 12 #include <vector> 13 #include <fstream> 14 #include <iterator> 15 #include <iostream> 16 #include <algorithm> 17 using namespace std; 18 #define LL long long 19 #define INF 0x3f3f3f3f 20 #define MOD 1000000007 21 #define eps 1e-6 22 #define MAXN 100010 23 #define MAXM 100 24 #define dd {cout<<"debug"<<endl;} 25 #define pa {system("pause");} 26 #define p(x) {printf("%d\n", x);} 27 #define pd(x) {printf("%.7lf\n", x);} 28 #define k(x) {printf("Case %d: ", ++x);} 29 #define s(x) {scanf("%d", &x);} 30 #define sd(x) {scanf("%lf", &x);} 31 #define mes(x, d) {memset(x, d, sizeof(x));} 32 #define do(i, x) for(i = 0; i < x; i ++) 33 #define dod(i, x, l) for(i = x; i >= l; i --) 34 #define doe(i, x) for(i = 1; i <= x; i ++) 35 struct node 36 { 37 LL l; 38 LL r; 39 }; 40 int n; 41 LL x[2]; 42 bool flag; 43 struct node f[MAXN]; 44 bool cmp(struct node x, struct node y) 45 { 46 if(((x.l - y.l < 0) && (x.r - y.r > 0)) || ((x.l - y.l > 0) && (x.r - y.r < 0))) 47 flag = true; 48 if(x.l == y.l) return x.r < y.r; 49 return x.l < y.l; 50 } 51 52 int main() 53 { 54 flag = false; 55 scanf("%d", &n); 56 scanf("%I64d %I64d", &x[0], &x[1]); 57 LL k, b; 58 for(int i = 0; i < n; i ++) 59 { 60 scanf("%I64d %I64d", &k, &b); 61 f[i].l = x[0] * k + b; 62 f[i].r = x[1] * k + b; 63 } 64 sort(f, f + n, cmp); 65 printf("%s\n", flag? "YES" : "NO"); 66 return 0; 67 }
Problem_B(593B):
题意：
给n条直线， 然后一个区间[x1, x2].
问， 这n条直线之中， 是否会有直线在[x1, x2]这个区间上有交点。
思路：
嗯....利用了奇淫技巧。
正常的思路是这样的：
先把每条直线在这个区间的值域[y1, y2]求出来。
然后会发现， 如果两条直线在这里有交点的话， 必然是对应两端点之差的符号相反。
即[y1, y2] [y3, y4]:
y1 - y3 < 0 && y2 - y4 > 0 或者
y1 - y3 > 0 && y2 - y4 < 0
贪心即可， 然而个人比较懒， 利用sort偷了个懒。
代码：
1 #include <cmath> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <ctime> 6 #include <set> 7 #include <map> 8 #include <list> 9 #include <stack> 10 #include <queue> 11 #include <string> 12 #include <vector> 13 #include <fstream> 14 #include <iterator> 15 #include <iostream> 16 #include <algorithm> 17 using namespace std; 18 #define LL long long 19 #define INF 0x3f3f3f3f 20 #define MOD 1000000007 21 #define eps 1e-6 22 #define MAXN 100010 23 #define MAXM 100 24 #define dd {cout<<"debug"<<endl;} 25 #define pa {system("pause");} 26 #define p(x) {printf("%d\n", x);} 27 #define pd(x) {printf("%.7lf\n", x);} 28 #define k(x) {printf("Case %d: ", ++x);} 29 #define s(x) {scanf("%d", &x);} 30 #define sd(x) {scanf("%lf", &x);} 31 #define mes(x, d) {memset(x, d, sizeof(x));} 32 #define do(i, x) for(i = 0; i < x; i ++) 33 #define dod(i, x, l) for(i = x; i >= l; i --) 34 #define doe(i, x) for(i = 1; i <= x; i ++) 35 struct node 36 { 37 LL l; 38 LL r; 39 }; 40 int n; 41 LL x[2]; 42 bool flag; 43 struct node f[MAXN]; 44 bool cmp(struct node x, struct node y) 45 { 46 if(((x.l - y.l < 0) && (x.r - y.r > 0)) || ((x.l - y.l > 0) && (x.r - y.r < 0))) 47 flag = true; 48 if(x.l == y.l) return x.r < y.r; 49 return x.l < y.l; 50 } 51 52 int main() 53 { 54 flag = false; 55 scanf("%d", &n); 56 scanf("%I64d %I64d", &x[0], &x[1]); 57 LL k, b; 58 for(int i = 0; i < n; i ++) 59 { 60 scanf("%I64d %I64d", &k, &b); 61 f[i].l = x[0] * k + b; 62 f[i].r = x[1] * k + b; 63 } 64 sort(f, f + n, cmp); 65 printf("%s\n", flag? "YES" : "NO"); 66 return 0; 67 }