15.3.24周练

地址http://acm.hust.edu.cn/vjudge/contest/view.action?cid=72728#overview

A：简单贪心

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <vector>
 8 #include <cstdio>
 9 #include <cctype>
10 #include <cstring>
11 #include <cstdlib>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 #define INF 0x3f3f3f3f
16 #define inf (-((LL)1<<40))
17 #define lson k<<1, L, mid
18 #define rson k<<1|1, mid+1, R
19 #define mem0(a) memset(a,0,sizeof(a))
20 #define mem1(a) memset(a,-1,sizeof(a))
21 #define mem(a, b) memset(a, b, sizeof(a))
22 #define FIN freopen("in.txt", "r", stdin)
23 #define FOUT freopen("out.txt", "w", stdout)
24 #define rep(i, a, b) for(int i = a; i <= b; i ++)
25 
26 template<class T> T CMP_MIN(T a, T b) { return a < b; }
27 template<class T> T CMP_MAX(T a, T b) { return a > b; }
28 template<class T> T MAX(T a, T b) { return a > b ? a : b; }
29 template<class T> T MIN(T a, T b) { return a < b ? a : b; }
30 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
31 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }
32 
33 //typedef __int64 LL;
34 typedef long long LL;
35 const int MAXN = 1010;
36 const int MAXM = 2000010;
37 const double eps = 1e-4;
38 
39 int n, a[110000];
40 
41 int main()
42 {
43     while(~scanf("%d", &n)) {
44         rep (i, 0, n - 1) scanf("%d", &a[i]);
45         sort(a, a + n);
46         int ans = 0;
47         rep (i, 0, n - 1) ans = max(ans, a[i] + n + 1 - i);
48         cout << ans << endl;
49     }
50     return 0;
51 }

View Code

B:不会= =

C:YY一下，将需要计算的值写成a * 10 ^ p + b（这里可以看到b < 10^p 且 1<=a<=9）,那么可以写出等式：

（a * 10 ^ p + b） * X = b * 10 + a 移项后可以得到：

（X * 10^p - 1） * a = (10 - X) * b

由于X * 10^p - 1一定是整数，所以若X>=10一定是No solution，然后便是枚举a=[1, 9], p=[0,7]算出所有的b，若算出来b是整数，便记录答案即可

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <vector>
 8 #include <cstdio>
 9 #include <cctype>
10 #include <cstring>
11 #include <cstdlib>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 #define INF 0x3f3f3f3f
16 #define inf (-((LL)1<<40))
17 #define lson k<<1, L, mid
18 #define rson k<<1|1, mid+1, R
19 #define mem0(a) memset(a,0,sizeof(a))
20 #define mem1(a) memset(a,-1,sizeof(a))
21 #define mem(a, b) memset(a, b, sizeof(a))
22 #define FIN freopen("in.txt", "r", stdin)
23 #define FOUT freopen("out.txt", "w", stdout)
24 #define rep(i, a, b) for(int i = a; i <= b; i ++)
25 
26 template<class T> T CMP_MIN(T a, T b) { return a < b; }
27 template<class T> T CMP_MAX(T a, T b) { return a > b; }
28 template<class T> T MAX(T a, T b) { return a > b ? a : b; }
29 template<class T> T MIN(T a, T b) { return a < b ? a : b; }
30 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
31 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }
32 
33 //typedef __int64 LL;
34 typedef long long LL;
35 const int MAXN = 1010;
36 const int MAXM = 2000010;
37 const double eps = 1e-6;
38 
39 double x;
40 LL a, p;
41 LL ans[10000];
42 
43 int main()
44 {
45     while(~scanf("%lf", &x)) {
46         if(x >= 10) {puts("No solution");continue;}
47         int cnt = 0;
48         for(a = 1; a <=9; a ++) {
49             for(p = 0; p <= 7; p ++) {
50                 double b = a * (x * pow(10, p) - 1) / (10.0 - x);
51                 if(fabs(b - (LL)(b + eps)) < eps && b < pow(10, p)) ans[cnt++] = (LL)(a * pow(10, p) + b);
52             }
53         }
54         sort(ans, ans + cnt);
55         rep (i, 0, cnt - 1) cout << ans[i] << endl;
56         if(cnt == 0) puts("No solution");
57     }
58     return 0;
59 }

View Code

D:给n个点，求最远点距

我的方法后来被我自己证明是错的了，，，，算了还是把代码贴上来，毕竟A了

我是用的凸包+三分求极值（实际不可以求极值来算= =）

  1 #include <map>
  2 #include <set>
  3 #include <stack>
  4 #include <queue>
  5 #include <cmath>
  6 #include <ctime>
  7 #include <vector>
  8 #include <cstdio>
  9 #include <cctype>
 10 #include <cstring>
 11 #include <cstdlib>
 12 #include <iostream>
 13 #include <algorithm>
 14 using namespace std;
 15 #define eps 1e-12
 16 #define MAXN 55
 17 #define INF 1e30
 18 #define mem0(a) memset(a,0, sizeof(a))
 19 #define mem1(a) memset(a,-1,sizeof(a))
 20 #define rep(i, a, b) for(int i = a; i <= b; i ++)
 21 double MAX(double a, double b) {return a > b ? a : b;}
 22 double MIn(double a, double b) {return a < b ? a : b;}
 23 typedef long long LL;
 24 /****************************************计算几何头文件**************************************************/
 25 struct Point{
 26     int x,y;
 27     Point(int x=0, int y=0):x(x),y(y){}
 28     bool operator < (const Point &A) const {
 29         return x != A.x ? x < A.x : y < A.y;
 30     }
 31 };
 32 
 33 Point operator + (Point A, Point B) {return Point(A.x+B.x, A.y+B.y);}
 34 
 35 Point operator - (Point A, Point B) {return Point(A.x-B.x, A.y-B.y);}
 36 
 37 double Dot(Point A, Point B) { return A.x*B.x + A.y*B.y;}    //点积
 38 
 39 double Length(Point A) { return sqrt(Dot(A,A));}             //向量长度
 40 
 41 double Angle(Point A, Point B) {return acos(Dot(A,B) / Length(A) / Length(B));}//向量夹角
 42 
 43 double cross(Point A, Point B) {return A.x*B.y - A.y*B.x;}
 44 
 45 bool crossed(Point a, Point b, Point c, Point d)//线段ab和cd是否相交
 46 {
 47     if(cross(a-c, d-c)*cross(b-c, d-c)<=0
 48        && cross(c-a, b-a)*cross(d-a, b-a)<=0)
 49     {
 50         return true;
 51     }
 52     return false;
 53 }
 54 
 55 int convexHull(Point* p, int n, Point* ch)
 56 {
 57     sort(p, p + n);
 58     int m = 0;
 59     for(int i = 0; i < n; i ++) {
 60         while(m > 1 && cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;
 61         ch[m++] =p[i];
 62     }
 63     int k = m;
 64     for(int i = n - 2; i >= 0; i --) {
 65         while(m > k && cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;
 66         ch[m++] = p[i];
 67     }
 68     if(n > 1) m --;
 69     return m;
 70 }
 71 
 72 /****************************************************************************************************/
 73 Point p[110000], q[210000];
 74 int n, m;
 75 
 76 double dis(Point a, Point b)
 77 {
 78     double x = (double)a.x - b.x, y = (double)a.y - b.y;
 79     return sqrt(x * x + y * y);
 80 }
 81 
 82 double tsearch(int id, int low, int high)
 83 {
 84     while(low  + 2 < high) {
 85         int ml = low + (high - low) / 3;
 86         int mr = (high + ml) >> 1;
 87         if(dis(q[ml], q[id]) > dis(q[mr], q[id])) {
 88             high = mr;
 89         }
 90         else low = ml;
 91     }
 92     return max(dis(q[low], q[id]), max(dis(q[low + 1], q[id]), dis(q[high], q[id])));
 93 }
 94 
 95 int main()
 96 {
 97     while(~scanf("%d", &n)) {
 98         rep (i, 0, n - 1) {
 99             scanf("%d %d", &p[i].x, &p[i].y);
100         }
101         m = convexHull(p, n, q);
102         double ans = 0;
103         rep (i, 0, m- 1) q[i + m] = q[i];
104         rep (i, 0, m - 1) {
105             ans = max(ans, tsearch(i, i + 1, i + m));
106         }
107         printf("%.8lf
", ans);
108     }
109     return 0;
110 }

View Code

E:一道细节题

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <vector>
 8 #include <cstdio>
 9 #include <cctype>
10 #include <cstring>
11 #include <cstdlib>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 #define INF 0x3f3f3f3f
16 #define inf (-((LL)1<<40))
17 #define lson k<<1, L, mid
18 #define rson k<<1|1, mid+1, R
19 #define mem0(a) memset(a,0,sizeof(a))
20 #define mem1(a) memset(a,-1,sizeof(a))
21 #define mem(a, b) memset(a, b, sizeof(a))
22 #define FIN freopen("in.txt", "r", stdin)
23 #define FOUT freopen("out.txt", "w", stdout)
24 #define rep(i, a, b) for(int i = a; i <= b; i ++)
25 
26 template<class T> T CMP_MIN(T a, T b) { return a < b; }
27 template<class T> T CMP_MAX(T a, T b) { return a > b; }
28 template<class T> T MAX(T a, T b) { return a > b ? a : b; }
29 template<class T> T MIN(T a, T b) { return a < b ? a : b; }
30 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
31 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }
32 
33 //typedef __int64 LL;
34 typedef long long LL;
35 const int MAXN = 1010;
36 const int MAXM = 2000010;
37 const double eps = 1e-4;
38 
39 char s[110000], t[110000];
40 
41 int main()
42 {
43     //FIN;
44     while(gets(s)) {
45         gets(t);
46         int f = 0, r = strlen(t) - 1;
47         int l1 = strlen(s), l2 = strlen(t);
48         for (f = 0; s[f] && t[f] && s[f] == t[f];f ++);
49         for (;l1 - (l2 - r) >= 0 && r >= 0 && s[l1 - (l2 - r)] == t[r]; r--);
50         if(r >= f) {
51             if(f == l1 || l1 + r - l2 < 0) cout << l2 - l1 << endl;
52             else cout << r - f + 1 << endl;
53         }
54         else {
55             if(l2 <= l1) cout << 0 << endl;
56             else cout << min(r + 1, l2 - f) << endl;
57         }
58     }
59     return 0;
60 }

View Code

F:模拟暴力

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <vector>
 8 #include <cstdio>
 9 #include <cctype>
10 #include <cstring>
11 #include <cstdlib>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 #define INF 0x3f3f3f3f
16 #define inf (-((LL)1<<40))
17 #define lson k<<1, L, mid
18 #define rson k<<1|1, mid+1, R
19 #define mem0(a) memset(a,0,sizeof(a))
20 #define mem1(a) memset(a,-1,sizeof(a))
21 #define mem(a, b) memset(a, b, sizeof(a))
22 #define FIN freopen("in.txt", "r", stdin)
23 #define FOUT freopen("out.txt", "w", stdout)
24 #define rep(i, a, b) for(int i = a; i <= b; i ++)
25 
26 template<class T> T CMP_MIN(T a, T b) { return a < b; }
27 template<class T> T CMP_MAX(T a, T b) { return a > b; }
28 template<class T> T MAX(T a, T b) { return a > b ? a : b; }
29 template<class T> T MIN(T a, T b) { return a < b ? a : b; }
30 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
31 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }
32 
33 //typedef __int64 LL;
34 typedef long long LL;
35 const int MAXN = 1010;
36 const int MAXM = 2000010;
37 const double eps = 1e-6;
38 
39 char num[10][20] = {
40     "**** ** ** ****",
41     "  *  *  *  *  *",
42     "***  *****  ***",
43     "***  ****  ****",
44     "* ** ****  *  *",
45     "****  ***  ****",
46     "****  **** ****",
47     "***  *  *  *  *",
48     "**** ***** ****",
49     "**** ****  ****"
50 };
51 
52 char ma[100][110];
53 
54 int trans(int y)
55 {
56     char s[20] = {0};
57     for(int i = 0; i < 5; i ++) {
58         for(int j = 0; j < 3; j ++) {
59             s[i*3+j] = ma[i][y + j];
60             if(s[i*3+j]==0) s[i*3+j]=' ';
61         }
62     }
63     for(int i = 0; i < 10; i ++) if(strcmp(num[i], s) == 0)
64         return i;
65     return -1;
66 }
67 
68 int main()
69 {
70     while(gets(ma[0])) {
71         for(int i = 1; i < 5;i ++) {
72            gets(ma[i]);
73         }
74         int num = 0, l = strlen(ma[0]);
75         for(int y = 0; y < l- 2; y += 4) {
76             num = num * 10 + trans(y);
77         }
78         if(num % 6 == 0) puts("BEER!!");
79         else puts("BOOM!!");
80     }
81     return 0;
82 }

View Code

G：关键是看懂提：

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <vector>
 8 #include <cstdio>
 9 #include <cctype>
10 #include <cstring>
11 #include <cstdlib>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 #define INF 0x3f3f3f3f
16 #define inf (-((LL)1<<40))
17 #define lson k<<1, L, mid
18 #define rson k<<1|1, mid+1, R
19 #define mem0(a) memset(a,0,sizeof(a))
20 #define mem1(a) memset(a,-1,sizeof(a))
21 #define mem(a, b) memset(a, b, sizeof(a))
22 #define FIN freopen("in.txt", "r", stdin)
23 #define FOUT freopen("out.txt", "w", stdout)
24 #define rep(i, a, b) for(int i = a; i <= b; i ++)
25 
26 template<class T> T CMP_MIN(T a, T b) { return a < b; }
27 template<class T> T CMP_MAX(T a, T b) { return a > b; }
28 template<class T> T MAX(T a, T b) { return a > b ? a : b; }
29 template<class T> T MIN(T a, T b) { return a < b ? a : b; }
30 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
31 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }
32 
33 //typedef __int64 LL;
34 typedef long long LL;
35 const int MAXN = 1010;
36 const int MAXM = 2000010;
37 const double eps = 1e-4;
38 
39 char s[110000], t[110000];
40 int n;
41 
42 int main()
43 {
44     while(~scanf("%d%*c", &n)) {
45         gets(s); gets(t);
46         int l1 = strlen(s), l2 = strlen(t), num = 0;
47         if(strcmp(s, t) == 0 && n % 2 == 0) {
48             puts("Deletion succeeded");
49             continue;
50         }
51         for(int i = 0; i < l1 ; i ++) if(s[i] != t[i]) num++;
52         printf("%s
", (num==l1&&(n&1)) ? "Deletion succeeded" : "Deletion failed");
53     }
54     return 0;
55 }

View Code

H:不敢看( ⊙ o ⊙ )啊！