CodeChef--SEPT14小结

这套题目只做了几个相对简单的。其他的做起来比较吃力。

A 找下规律

 1 /*************************************************************************
 2     > File Name: A.cpp
 3     > Author: Stomach_ache
 4     > Mail: sudaweitong@gmail.com
 5     > Created Time: 2014年09月06日 星期六 16时32分54秒
 6     > Propose: 
 7  ************************************************************************/
 8 
 9 #include <cmath>
10 #include <string>
11 #include <cstdio>
12 #include <fstream>
13 #include <cstring>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 /*Let's fight!!!*/
18 
19 const int MOD = 1e9 + 7;
20 typedef long long LL;
21 int t, n;
22 char s[100005];
23 
24 int main(void) {
25       ios::sync_with_stdio(false);
26     cin >> t;
27     while (t--) {
28           cin >> s;
29           n = strlen(s);
30         LL res = 1;
31         for (int i = 0; i < n; i++) {
32               if ((i + 1) % 2 == 1) res = (res * 2) % MOD;
33             else res = (res * 2 - 1) % MOD;
34             if (s[i] == 'r') res = (res + 2) % MOD;
35         }
36         cout << res << endl;
37     }
38     return 0;
39 }

B　模拟

 1 n, m = map(int, raw_input().split());
 2 a = map(int, raw_input().split());
 3 now = 1;
 4 while m:
 5     m -= 1;
 6     Q = raw_input().split();
 7     if Q[0] == 'R':
 8           print a[(now + int(Q[1]) - 1) % n - 1]
 9     elif Q[0] == 'C':
10         now = (now + int(Q[1])) % n;
11     else :
12         now = (now - int(Q[1]) + n) % n;

C

这题被我写烦了。。。是想烦了。

我是枚举中间一堆的个数。然后就是组合数学了。。。。。。。

 1 /*************************************************************************
 2     > File Name: C.cpp
 3     > Author: Stomach_ache
 4     > Mail: sudaweitong@gmail.com
 5     > Created Time: 2014年09月06日 星期六 11时08分09秒
 6     > Propose: 
 7  ************************************************************************/
 8 
 9 #include <cmath>
10 #include <string>
11 #include <cstdio>
12 #include <fstream>
13 #include <cstring>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 /*Let's fight!!!*/
18 
19 const int MOD = 1e9 + 7;
20 typedef long long LL;
21 LL fact[1000005], n;
22 
23 LL pow_mod(LL a, LL b) {
24     LL res = 1;
25     while (b) {
26         if (b & 1) res = (res * a) % MOD;
27         a = (a * a) % MOD;
28         b >>= 1;
29     }
30     return res;
31 }
32 
33 void init() {
34     fact[5] = 1; fact[6] = 6;
35     int now = 2;
36     for (int i = 7; i <= 1000000; i++, now++) fact[i] = (fact[i - 1] * pow_mod(now, MOD - 2) % MOD * i) % MOD;
37 }
38 
39 int main(void) {
40     ios::sync_with_stdio(false);
41     init();
42     while (cin >> n) {
43         if (n < 13) {
44             cout << "0" << endl;
45             continue;
46         }
47         LL res = 0;
48         if (n % 2 == 0){
49             for (int i = 2; i <= n - 12; i += 2) {
50               　res = (res + fact[(n - i)/2 - 1]) % MOD;
51             }
52         } else {
53             for (int i = 1; i <= n - 12; i += 2) {
54                 res = (res + fact[(n - i)/2 - 1]) % MOD;
55             }
56         }
57         cout << res << endl;
58     }
59 
60     return 0;
61 }

D
E

题解上这题也是个Easy..可是当时愣是没有看出来，知道突破点是ｋ比较小。

正解是枚举数列中第一个和最后一个没有改变的位置,　这个不超过k^2，然后。。。

这里getchar_unlocked是getchar()的线程不安全版本。。好像已经被windows弃用。

还有，n*10可以表达为(n<<3) + (n<<1)

 1 /*************************************************************************
 2     > File Name: E.cpp
 3     > Author: Stomach_ache
 4     > Mail: sudaweitong@gmail.com
 5     > Created Time: 2014年09月15日 星期一 21时04分57秒
 6     > Propose: 
 7  ************************************************************************/
 8 
 9 #include <cmath>
10 #include <string>
11 #include <cstdio>
12 #include <fstream>
13 #include <cstring>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 /*Let's fight!!!*/
18  
19 const int MAX_N = 100050;
20 typedef long long LL;
21 #define rep(i, a, b) for (int i = (a); i <= (b); i++)
22 int n, k, a[MAX_N];
23 
24 void read(int &res) {
25     char c = ' ';
26     res = 0;
27     int sign = 1;
28     while (c < '0' || c > '9') {if (c == '-') sign = -1; c = getchar_unlocked();}
29     while (c >= '0' && c <= '9') res = (res<<3) + (res<<1) + c - '0', c= getchar_unlocked();
30     res *= sign;
31 }
32 
33 int main(void) {
34     read(n), read(k);
35     rep (i, 1, n) read(a[i]);
36 
37     int a1 = 0x3f3f3f3f, d = 0x3f3f3f3f;
38     rep (i, 1, k+1) rep (j, n-k+i-1, n) {
39         int cnt = 0, tmp_d = (a[j] - a[i]) / (j - i), tmp_a1 = a[i] - (i - 1) * tmp_d;
40         rep (t, 1, n) if (a[t] != tmp_a1 + (t - 1) * tmp_d) cnt++;
41         if (cnt <= k) {
42             if (a1 > tmp_a1) a1 = tmp_a1, d = tmp_d;
43             else if (a1 == tmp_a1 && d > tmp_d) d = tmp_d;
44         }
45     }
46 
47     rep (i, 1, n) printf("%d%c", a1 + (i - 1) * d, i == n ? '
' : ' ');
48 
49     return 0;
50 }

F

 1 /*************************************************************************
 2     > File Name: F.cpp
 3     > Author: Stomach_ache
 4     > Mail: sudaweitong@gmail.com
 5     > Created Time: 2014年09月08日 星期一 13时07分43秒
 6     > Propose: 
 7  ************************************************************************/
 8 #include <cmath>
 9 #include <string>
10 #include <cstdio>
11 #include <vector>
12 #include <fstream>
13 #include <cstring>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 /*Let's fight!!!*/
18 
19 typedef long long LL;
20 LL N, M;
21 
22 /*
23  *　(a / b) % c 等价于 (a % (b * c)) / b;
24  * 　适用于ｂｃ不大而且ｂ在ｃ的剩余系中逆元不存在的情况
25  */
26 LL sum(LL n) {
27       LL m = M * 30;
28       n %= m;
29       return (n * (6 * n % m * n % m * n % m * n % m + 15 * n % m * n % m * n % m + 10 * n % m * n % m - 1 + m) % m) % m / 30;
30 }
31 
32 int main(void) {
33     ios::sync_with_stdio(false);
34     int T;
35     cin >> T;
36     while (T--) {
37         cin >> N >> M;
38         if (N == 1) {
39             cout << N % M << endl;
40             continue;
41         } else if (N == 2) {
42             cout << (N + 16) % M << endl;
43             continue;
44         } else if (N == 3) {
45             cout << (N + 16 + 81) % M << endl;
46             continue;
47         }
48 
49         LL res = 0, i = 1, fst = 0, last = N, j;
50         while (true) {
51             LL r = N / (i + 1), l = i;
52             j = N / i;
53             res = (res + (sum(last) - sum(r) + M) % M * (i % M) % M) % M;
54             if (r != fst || last != l)
55                 res = (res + (sum(l) - sum(fst) + M) % M * (j % M) % M) % M;
56             if (l >= r) break;
57             i++;
58             last = r;
59             fst = l;
60         }
61 
62         cout << res << endl;
63     }
64 
65     return 0;
66 }

G

需要维护每个区间内比右短点小的个数和比左端点小的个数，BIT系列。。是个不错的题。

  1 /*************************************************************************
  2     > File Name: E.cpp
  3     > Author: Stomach_ache
  4     > Mail: sudaweitong@gmail.com
  5     > Created Time: 2014年09月08日 星期一 17时18分23秒
  6     > Propose: 
  7  ************************************************************************/
  8 
  9 #include <cmath>
 10 #include <string>
 11 #include <cstdio>
 12 #include <fstream>
 13 #include <vector>
 14 #include <cstring>
 15 #include <iostream>
 16 #include <algorithm>
 17 using namespace std;
 18 /*Let's fight!!!*/
 19 
 20 #define rep(i, n) for (int i = (1); i <= (n); i++)
 21 #define per(i, n) for (int i = (n); i >= (1); i--)
 22 const int MAX_N = 200050;
 23 typedef long long LL;
 24 int N, M, w, A[MAX_N], c[MAX_N];
 25 struct node {
 26     int id, l, r, ltr, ltl, eql, eqr;
 27     node () {}
 28     node (int id, int l, int r):id(id), l(l), r(r),ltr(0), ltl(0) {}
 29     friend bool operator < (const node &x, const node &y) {
 30           return x.id < y.id;
 31     }
 32 }Q[MAX_N];
 33 
 34 int lowbit(int x) {
 35       return x & -x;
 36 }
 37 
 38 void add(int x) {
 39       while (x <= w) {
 40         c[x]++;
 41         x += lowbit(x);
 42     }
 43 }
 44 
 45 int sum(int x) {
 46       int res = 0;
 47       while (x > 0) {
 48         res += c[x];
 49         x -= lowbit(x);
 50     }
 51     return res;
 52 }
 53 
 54 int main(void) {
 55     ios::sync_with_stdio(false);
 56     while (cin >> N >> M) {
 57         vector<int> var;
 58         rep (i, N) {
 59             cin >> A[i];
 60             var.push_back(A[i]);
 61         }
 62         sort(var.begin(), var.end());
 63         var.resize(unique(var.begin(), var.end()) - var.begin());
 64         w = var.size();
 65 
 66         memset(c, 0, sizeof(c));
 67         LL res = 0;
 68         rep (i, N) {
 69             int pos = lower_bound(var.begin(), var.end(), A[i]) - var.begin() + 1;
 70             res += i - 1 - sum(pos - 1) - (sum(pos) - sum(pos - 1));    
 71             add(pos);
 72         }
 73         
 74 //        cerr << res << endl;
 75 
 76         vector<int> lft[MAX_N], rgt[MAX_N];
 77         int x, y;    
 78         rep (i, M) {
 79             cin >> x >> y;
 80             if (x > y) swap(x, y);
 81             Q[i] = node(i, x, y);
 82             lft[x].push_back(i);
 83             rgt[y].push_back(i);
 84         }
 85 
 86         memset(c, 0, sizeof(c));
 87         rep (i, N) {
 88               int szl = lft[i].size(), szr = rgt[i].size();    
 89             for (int j = 0; j < szl; j++) {
 90                 int id = lft[i][j];
 91                 int pos = lower_bound(var.begin(), var.end(), A[Q[id].r]) - var.begin() + 1;
 92                 Q[id].eqr = sum(pos) - sum(pos - 1);
 93                 Q[id].ltr = sum(pos - 1);
 94             }
 95 
 96             int pos = lower_bound(var.begin(), var.end(), A[i]) - var.begin() + 1;
 97             for (int j = 0; j < szr; j++) {
 98                 int id = rgt[i][j];
 99                 Q[id].ltr = sum(pos - 1) - Q[id].ltr;
100                 Q[id].eqr = sum(pos) - sum(pos - 1) - Q[id].eqr;
101             }
102             add(pos);
103         }
104 
105         memset(c, 0, sizeof(c));
106         per (i, N) {
107             int szl = lft[i].size(), szr = rgt[i].size();    
108             for (int j = 0; j < szr; j++) {
109                 int id = rgt[i][j];
110                 int pos = lower_bound(var.begin(), var.end(), A[Q[id].l]) - var.begin() + 1;
111                 Q[id].ltl = sum(pos - 1);
112                 Q[id].eql = sum(pos) - sum(pos - 1);
113             }
114             int pos = lower_bound(var.begin(), var.end(), A[i]) - var.begin() + 1;
115             for (int j = 0; j < szl; j++) {
116                 int id = lft[i][j];
117                 Q[id].ltl = sum(pos - 1) - Q[id].ltl;
118                 Q[id].eql = sum(pos) - sum(pos - 1) - Q[id].eql;
119             }
120             add(pos);
121         }
122     //    cerr << "say hello
";
123 
124         sort (Q + 1, Q + M + 1);
125         rep (i, M) {
126             int l = Q[i].l, r = Q[i].r;
127             LL tmp = Q[i].ltr - Q[i].ltl - (r - l + 1 - Q[i].ltr - Q[i].eqr) + (r - l + 1 - Q[i].ltl - Q[i].eql); 
128             if (A[r] > A[l]) tmp--;
129             else if (A[r] < A[l]) tmp++;
130             cout << res + tmp << endl;
131         }
132     }
133 
134     return 0;
135 }

H

I

J

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Stomach-ache/p/3977206.html