15.5.5周练

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

密码：acmore

赛中出了3道，之后又写了俩。

AZOJ 3591 Nim（Nim博弈）

题目意思是说有n堆石子，Alice只能从中选出连续的几堆来玩Nim博弈,现在问Alice想要获胜有多少种方法（即有多少种选择方式）。

方法是这样的，由于Nim博弈必胜的条件是所有数的抑或值不为0，证明见点击，所以答案就转化为原序列有多少个区间的亦或值为0，用n*(n+1) / 2 减去这个值就可以了。

而求有多少个区间的亦或值为0，实际上就是求对于亦或值的前缀nim[i]，满足nim[i] == nim[j] 的对数，这时只要对nim数组排序就可以算了

详见代码：题解

 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 = 110000;
36 const int MAXM = 20010;
37 const double eps = 1e-4;
38 //LL MOD = 987654321;
39 
40 int n, a[MAXN], x, s, w, T;
41 
42 int main()
43 {
44     while(~scanf("%d", &T)) while(T--) {
45         cin >> n >> s >> w;
46         LL ans = (LL)n * (n + 1) / 2;
47         int g = s;
48         rep (i, 1, n) {
49             x = g;
50             if( x == 0 )    { x = g = w; }
51             if( g%2 == 0 )  { g = (g/2); }
52             else            { g = (g/2) ^ w; }
53             a[i] = a[i - 1] ^ x;
54             if(a[i] == 0) ans --;
55         }
56         sort(a + 1, a + n + 1);
57         int num = 1;
58         rep (i, 2, n) {
59             if(a[i] == a[i - 1]) {
60                 ans -= num;
61                 num++;
62             }
63             else num = 1;
64         }
65         cout << ans << endl;
66     }
67     return 0;
68 }

View Code

B： ZOJ 3593 One Person Game （扩展欧几里得）

正在搞。。。

C： ZOJ 3594 Sexagenary Cycle

乱搞。

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 #include <queue>
 5 #include <cmath>
 6 #include <cstring>
 7 #define mem0(a) memset(a, 0, sizeof(a))
 8 #define mem1(a) memset(a, -1, sizeof(a))
 9 using namespace std;
10 
11 char T1[11][10] = {"Geng", "Xin", "Ren", "Gui", "Jia", "Yi", "Bing", "Ding", "Wu", "Ji"};
12 char T2[11][10] = {"Xin", "Geng", "Ji", "Wu", "Ding", "Bing", "Yi", "Jia", "Gui", "Ren"};
13 char D1[13][10] = {"shen", "you", "xu", "hai", "zi", "chou", "yin", "mao", "chen", "si", "wu", "wei"};
14 char D2[13][10] = {"you", "shen", "wei", "wu", "si", "chen", "mao", "yin", "chou", "zi", "hai", "xu"};
15 
16 int N, T;
17 
18 int main()
19 {
20     //freopen("in.txt", "r", stdin);
21     while(cin >> T) while(T--) {
22         cin >> N;
23         if(N > 0) printf("%s%s
", T1[N % 10], D1[N % 12]);
24         else printf("%s%s
", T2[(-N) % 10], D2[(-N) % 12]);
25     }
26     return 0;
27 }

View Code

D:没出

E:ZOJ 3596 Digit Number（DP+BFS）

见 http://www.cnblogs.com/gj-Acit/p/4492762.html

  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 = 110000;
 36 const int MAXM = 20010;
 37 const double eps = 1e-4;
 38 //LL MOD = 987654321;
 39 
 40 int t, n, m, x;
 41 struct Node {
 42     bool vis;
 43     char num;
 44     int pre, cnt;
 45 }s[(1<<10) * 1100];
 46 char ans[110000], d[110000];
 47 
 48 int bfs()
 49 {
 50     queue<int>q;
 51     q.push(0);
 52     while(!q.empty()) {
 53         int head = q.front();q.pop();
 54         rep (i, 0, 9) {
 55             if(head == 0 && i == 0) continue;
 56             int mod = (head % 1000 * 10 + i) % n;
 57             int tail = ((head / 1000) | (1 << i)) * 1000 + mod;
 58             if(s[tail].vis)
 59                 continue;
 60             s[tail].vis = true;
 61             s[tail].num = i + '0';
 62             s[tail].pre = head;
 63             s[tail].cnt = s[head].cnt + ((head / 1000) & (1 << i) ? 0 : 1);
 64             if(s[tail].cnt == m && mod == 0) {
 65                 return tail;
 66             }
 67             if(s[tail].cnt <= m) q.push(tail);
 68         }
 69     }
 70     return 0;
 71 }
 72 
 73 //calc a / b
 74 char* divide(char *a, int len, int b) {
 75     mem0(d);
 76     int i = 0, cur = 0, l = 0;
 77     while(cur < b && i < len) {
 78         cur = cur * 10 + a[i++] - '0';
 79     }
 80     d[l++] = cur / b + '0';
 81     while(i < len) {
 82         cur = cur % b * 10 + a[i++] - '0';
 83         d[l++] = cur / b + '0';
 84     }
 85     return d;
 86 }
 87 
 88 void print(int ed) {
 89     int len = 0;
 90     mem0(ans);
 91     while(ed) {
 92         ans[len++] = s[ed].num;
 93         ed = s[ed].pre;
 94     }
 95     reverse(ans, ans + len);
 96     printf("%s=%d*%s
", ans, n, divide(ans, len, n));
 97 }
 98 
 99 int main()
100 {
101     //FIN;
102     while(cin >> t) while(t--) {
103         cin >> n >> m;
104         mem0(s);
105         if( !(x = bfs()) ) {
106             puts("Impossible");
107         }
108         else {
109             print(x);
110         }
111     }
112     return 0;
113 }

View Code

F：ZOJ 3597 Hit the Target! （线段树扫描线 -- 求矩形所能覆盖的最多点数）

见博文http://www.cnblogs.com/gj-Acit/p/4493091.html

G:ZOJ 3598 Spherical Triangle

不多说，利用法向量计算平面夹角

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 #include <queue>
 5 #include <cmath>
 6 #include <cstring>
 7 #define mem0(a) memset(a, 0, sizeof(a))
 8 #define mem1(a) memset(a, -1, sizeof(a))
 9 using namespace std;
10 
11 const double PI = 4.0 * atan(1.0);
12 
13 struct Point {
14     double x, y, z;
15 }a[3];
16 
17 double dot(Point a, Point b) {
18     return a.x * b.x + a.y * b.y + a.z * b.z;
19 }
20 
21 Point cross(Point a, Point b) {
22     Point ret;
23     ret.x = a.y * b.z - a.z * b.y;
24     ret.y = a.z * b.x - a.x * b.z;
25     ret.z = a.x * b.y - a.y * b.x;
26     return ret;
27 }
28 
29 int T;
30 
31 int main()
32 {
33     //freopen("in.txt", "r", stdin);
34     while(cin >> T) while(T--) {
35         double A, B;
36         for(int i = 0; i < 3; i ++) {
37             cin >> A >> B;
38             B = B * PI / 180; A = A * PI / 180;
39             a[i].z = sin(B);
40             a[i].x = cos(B) * cos(A);
41             a[i].y = cos(B) * sin(A);
42         }
43         Point p1 = cross(a[0], a[1]), p2 = cross(a[1], a[2]), p3 = cross(a[2], a[0]);
44         double l1 = sqrt(dot(p1, p1)), l2 = sqrt(dot(p2, p2)), l3 = sqrt(dot(p3, p3));
45         double s1 = acos(dot(p1, p2) / l1 / l2), s2 = acos(dot(p2, p3) / l2 / l3), s3 = acos(dot(p3, p1) / l3 / l1);
46         double ans = PI * 3 - s1 - s2 - s3;
47         printf("%.2lf
", ans * 180 / PI);
48     }
49     return 0;
50 }

View Code