NOIP2012提高组解题报告

Day1T1

太长了不复制了, 看这里http://wikioi.com/problem/1197/

简单的字符串替换问题.

 1 #include <stdio.h>
 2 #include <string.h>
 3 char k[102], str[1002];
 4 int main()
 5 {
 6     scanf("%s%s", k, str);
 7     for (int i = 0, len = strlen(k); i < len; ++i)
 8         if (k[i] >= 'A' && k[i] <= 'Z')
 9             k[i] = 'a' + (k[i] - 'A');
10     for (int i = 0, p = 0, len = strlen(str), lenk = strlen(k); i < len; ++i, ++p, p = (p == lenk ? 0 : p))
11         if (str[i] >= 'A' && str[i] <= 'Z')
12         {
13             str[i] = str[i] - (k[p] - 'a');
14             if (str[i] - 'A' < 0)
15                 str[i] += 26;
16         }
17         else
18         {
19             str[i] = str[i] - (k[p] - 'a');
20             if (str[i] - 'a' < 0)
21                 str[i] += 26;
22         }
23     printf("%s\n", str);
24     return 0;
25 }

Day1T2

题目:http://wikioi.com/problem/1198/

给出一些二元组(Ai, Bi), 将他们按某种顺序排列. 对于每个二元组, 有一个值Fi, 计算方式是他之前所有二元组的Ai乘起来, 除以该二元组的Bi. 使得Max{F1, F2, F3 ... Fn}最小.

考虑交换相邻两个二元组的影响, 交换二元组i和二元组i+1，实际上只影响到Fi和Fi+1。

设T = A1 * A2 * ... * Ai-2 * Ai-1

方案A: Fi = T / Bi, Fi+1 =T * Ai / Bi+1

方案B: Fi = T / Bi+1, Fi+1 =T * Ai+1 / Bi

①假设1 / Bi < Ai / Bi+1, 1 / Bi+1 < Ai+1 / Bi

那么方案A优于方案B(Ai / Bi+1 < Ai+1 / Bi, Ai * Bi < Ai+1 * B i+1)

②假设1 / Bi ≥ Ai / Bi+1(Ai * Bi ≤ Bi+1)

那么1 / Bi ≤ Ai+1 / Bi, 方案A更优

③假设1 / Bi+1 ≥ Ai+1 / Bi(Ai+1 * Bi+1 ≤ Bi)

那么1 / Bi+1 ≤ Ai / Bi+1, 方案B更优

也就是说, 对于相邻两个二元组, 将A * B的较小的放在前面总能使答案更优.

实现要使用高精度, 结束.

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 #define MAXN 1001
  5 struct Person
  6 {
  7     int a, b;
  8 } p[MAXN];
  9 struct High
 10 {
 11     int len;
 12     int num[4001];
 13 };
 14 int n;
 15 bool operator < (Person n1, Person n2)
 16 {
 17     return n1.a * n1.b < n2.a * n2.b;
 18 }
 19 bool operator > (High n1, High n2)
 20 {
 21     if (n1.len > n2.len)
 22         return true;
 23     if (n1.len < n2.len)
 24         return false;
 25     for (int i = n1.len - 1; i > -1; --i)
 26     {
 27         if (n1.num[i] > n2.num[i])
 28             return true;
 29         if (n1.num[i] < n2.num[i])
 30             return false;
 31     }
 32     return true;
 33 }
 34 High operator * (High n1, int number)
 35 {
 36     int k = 0;
 37     n1.len += 5;
 38     for (int i = 0; i < n1.len; ++i)
 39         n1.num[i] *= number;
 40     for (int i = 0; i < n1.len; ++i)
 41     {
 42         n1.num[i] += k;
 43         k = n1.num[i]/10;
 44         n1.num[i] %= 10;
 45     }
 46     while (n1.num[n1.len - 1] == 0)
 47         --n1.len;
 48     return n1;
 49 }
 50 High operator / (High n1, int number)
 51 {
 52     High ans;
 53     memset(ans.num, 0, sizeof ans.num);
 54     ans.len = 0;
 55     int now = 0;
 56     for (int i = n1.len - 1; i > -1; --i)
 57     {
 58         now = now * 10 + n1.num[i];
 59         if (now < number && ans.len == 0)
 60             continue;
 61         ans.num[ans.len++] = now / number;
 62         now %= number;
 63     }
 64     for (int i = 0; i < ans.len / 2; ++i)
 65         std::swap (ans.num[i], ans.num[ans.len - i - 1]);
 66     return ans;
 67 }
 68 void Give(High *n1, int number)
 69 {
 70     memset (n1 -> num, 0, sizeof n1->num);
 71     n1 -> len = 0;
 72     do
 73     {
 74         n1 -> num[(n1 -> len)++] = number % 10;
 75         number /= 10;
 76     }
 77     while (number != 0);
 78 }
 79 void Print(High n1)
 80 {
 81     for (int i = n1.len - 1; i > -1; --i)
 82         printf("%d", n1.num[i]);
 83     printf("\n");
 84 }
 85 void Init()
 86 {
 87     scanf("%d", &n);
 88     for (int i = 0; i <= n; ++i)
 89         scanf("%d %d", &p[i].a, &p[i].b);
 90     for (int i = 1, j; i < n; ++i)
 91         for (j = i + 1; j <= n; ++j)
 92             if (!(p[i] < p[j]))
 93                 std::swap (p[i], p[j]);
 94 }
 95 int main()
 96 {
 97     Init();
 98     High s, maxx;
 99     Give(&s,p[0].a);
100     Give(&maxx,0);
101     for (int i = 1; i <= n; ++i)
102     {
103         if (s / p[i].b > maxx)
104             maxx = s / p[i].b;
105         s = s * p[i].a;
106     }
107     Print(maxx);
108     return 0;
109 }

Day1T3开车旅行

题目:http://wikioi.com/problem/1199/

对每个i点维护nextA[i], nextB[i]表示i往后A的话去哪里, B的话去哪里. 这个可以用链表来计算, 我们把所有数从小到大排序, 然后串成一个链表. 从1到n每次找Hi在链表里的前后4个判断一下, 然后把Hi从链表里删掉. 然后这样我们再用nextAB[i]表示i往后A走一次B走一次到哪里. 那么可以发现i->nextAB[i]形成了一颗树. 之后可以用树的算法做. 不过最简单的还是预处理next[i][j]表示i往后A和B都走了2^j次到哪里. 然后从大到小判2的每个次幂.

写的我太难受了, 连平时喜欢纠结的格式都没纠结成.

  1 #include <cmath>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <iostream>
  5 #include <algorithm>
  6 #include <cstring>
  7 #include <set>
  8 using namespace std;
  9 #define N 101000
 10 #define L 14
 11 #define INF 0x3f3f3f3f
 12 const double EPS = 1e-8;
 13 struct City
 14 {
 15  int h, id;
 16  inline City(): h(0), id(0) {
 17  }
 18  inline City(int h, int id): h(h), id(id) {
 19  }
 20  inline bool operator ==(const City &p) const {
 21   return (p.id == id);
 22  }
 23 }nexB[N], nexA[N];
 24 struct Dist
 25 {
 26  int a, b, dis, id;
 27  inline Dist(): a(0), b(0), dis(INF), id(0) {
 28  }
 29  inline Dist(int a, int b, int dis, int id): a(a), b(b), dis(dis), id(id) {
 30  }
 31  inline Dist operator +(const Dist &p) const {
 32   return Dist(a + p.a, b + p.b, dis + p.dis, p.id);
 33  }
 34 }f[N][L], c;
 35 inline bool cmp1(const City &a, const City &b) {return a.h < b.h;}
 36 inline bool cmp2(const City &a, const City &b) {return a.h > b.h;}
 37 bool (*cp1)(const City &, const City &) = cmp1, (*cp2)(const City &, const City &) = cmp2;
 38 set <City, bool(*)(const City &, const City &)> lr(cp1), hr(cp2);
 39 int n, m, h[N];
 40 inline void Update(int &dis, int dis1, City &CC, set <City>::iterator iter)
 41 {
 42  if ((dis > dis1) || (dis == dis1 && CC.h > (iter -> h))) dis = dis1, CC = *(iter);
 43 }
 44 inline City nex_B(const City &now, set<City>::iterator liter, set<City>::iterator hiter)
 45 {
 46  City CC; int dis = INF;
 47  int co = 1;
 48  for (set<City>::iterator iter = liter; co <= 1 && iter != lr.end(); iter ++, co ++) Update(dis, abs(now.h - (iter -> h)), CC, iter);
 49  co = 1;
 50  for (set<City>::iterator iter = hiter; co <= 1 && iter != hr.end(); iter ++, co ++) Update(dis, abs(now.h - (iter -> h)), CC, iter);
 51  if (dis == INF) return City();
 52  return CC;
 53 }
 54 inline City nex_A(const City &now, set<City>::iterator liter, set<City>::iterator hiter)
 55 {
 56  City fir = nex_B(now, liter, hiter);
 57  City CC; int dis = INF;
 58  int co = 1;
 59  for (set<City>::iterator iter = liter; co <= 2 && iter != lr.end(); iter ++, co ++) if (!((*iter) == fir)) Update(dis, abs(now.h - (iter -> h)), CC, iter);
 60  co = 1;
 61  for (set<City>::iterator iter = hiter; co <= 2 && iter != hr.end(); iter ++, co ++) if (!((*iter) == fir)) Update(dis, abs(now.h - (iter -> h)), CC, iter);
 62  if (dis == INF) return City();
 63  return CC;
 64 }
 65 void init()
 66 {
 67  scanf("%d", &n);
 68  for (int i = 1; i <= n; i ++) scanf("%d", &h[i]);
 69  for (int i = n; i >= 1; i --) {
 70   lr.insert(City(h[i], i)), hr.insert(City(h[i], i));
 71   set<City>::iterator liter = ++ lr.lower_bound(City(h[i], i)), hiter = ++ hr.lower_bound(City(h[i], i));
 72   City j = nex_A(City(h[i], i), liter, hiter); nexA[i] = j; nexB[i] = nex_B(City(h[i], i), liter, hiter);
 73   if (j == City()) continue ;
 74   int a = abs(h[i] - j.h), hj = j.h, b; j = nexB[j.id];
 75   if (j == City()) continue ; b = abs(hj - j.h);
 76   f[i][0] = Dist(a, b, a + b, j.id);
 77   for (int j = 1; j < L; j ++)
 78    if (f[f[i][j - 1].id][j - 1].dis != INF) f[i][j] = f[i][j - 1] + f[f[i][j - 1].id][j - 1];
 79  }
 80 }
 81 inline Dist go(int s, int x)
 82 {
 83  Dist CC = Dist(0, 0, 0, s);
 84  for (int i = L - 1; i >= 0; i --)
 85   if ((CC + f[CC.id][i]).dis <= x) CC = CC + f[CC.id][i];
 86  City nex = nexA[CC.id];
 87  if ((!(nex == City())) && (CC.dis + abs(h[CC.id] - nex.h) <= x)) CC = CC + Dist(abs(h[CC.id] - nex.h), 0, abs(h[CC.id] - nex.h), nex.id);
 88  return CC;
 89 }
 90 void solve()
 91 {
 92  double CC = (double) INF;
 93  int id = 0, x0, s, x;
 94  bool flag = false;
 95  scanf("%d", &x0);
 96  for (int i = 1; i <= n; i ++) {
 97   c = go(i, x0);
 98   if (c.b != 0 && ((double) c.a / (double)c.b < CC || (fabs((double) c.a / (double) c.b == CC)) && h[i] > h[id])) CC = (double) c.a / (double) c.b, id = i, flag = true;
 99  }
100  if (!flag) cout << hr.begin() -> id << endl; else cout << id << endl;
101  scanf("%d", &m);
102  for (int i = 1; i <= m; i ++)
103   scanf("%d%d", &s, &x), c = go(s, x), printf("%d %d\n", c.a, c.b);
104 }
105 int main()
106 {
107  init();
108  solve();
109  return 0;
110 }

Day2T1同余方程

求关于 x 同余方程 ax ≡ 1 (mod b)的最小正整数解.

一句话: 用exgcd或则利用结论a^(phi(b)-1)%b.

 1 #include <stdio.h>
 2 typedef long long int64;
 3 int64 stack_k[8193];
 4 int top = -1;
 5 int64 extended_euclidian_algo(int64 x, int64 y)
 6 {
 7     int64 a = x, b = y, p, q;
 8     while (b != 0ll)
 9     {
10         stack_k[++top] = (a / b) % y;
11         int64 t = a % b;
12         a = b;
13         b = t;
14     }
15     p = 1ll;
16     q = 0ll;
17     while (top != -1)
18     {
19         int64 t = (p - q * stack_k[top--] % y) % y;
20         if (t < 0)
21             t += y;
22         p = q;
23         q = t;
24     }
25     return p;
26 }
27 int main()
28 {
29     int64 a, b;
30     scanf("%I64d %I64d", &a, &b);
31     scanf("%I64d\n", extended_euclidian_algo(a, b));
32     return 0;
33 }

Day2T2借教室

题目:http://wikioi.com/problem/1217/

标准解法是:让我们考虑现在有m个操作，我们先把这些操作的端点离散化一下，之后可以注意到，相邻的两个关键点之间，只有最少的哪天是有用的，那么我们可以把天数压到2m级别。然后有m个操作，我们先加入前m/2个，然后用部分和判断一下前m/2个会不会跪，会的话就在前m/2个中递归，不然就在后m/2个中递归。由于我们每次可以压天数。复杂度函数就是F(n)=n+F(n/2)=O(n).

然后我很纠结的写了个二分...

 1 #include <math.h>
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 #include <string.h>
 5 #define N 1004000
 6 int a[N], sum[N], n, m, d[N];
 7 struct query
 8 {
 9  int x, y, d;
10 }q[N];
11 inline int Read()
12 {
13  char ch = getchar();
14  while (!(ch >= '0' && ch <= '9')) ch = getchar();
15  int x = 0;
16  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
17  return x;
18 }
19 void init()
20 {
21  scanf("%d%d", &n, &m);
22  for (int i = 1; i <= n; i ++) a[i] = Read();
23  for (int i = 1; i <= m; i ++) q[i].d = Read(), q[i].x = Read(), q[i].y = Read();//scanf("%d%d%d", &q[i].d, &q[i].x, &q[i].y);
24 }
25 bool check(int m)
26 {
27  memset(d, 0, sizeof(d));
28  for (int i = 1; i <= m; i ++) d[q[i].x] += q[i].d, d[q[i].y + 1] -= q[i].d;
29  for (int i = 1; i <= n; i ++) {
30   sum[i] = sum[i - 1] + d[i];
31   if (sum[i] > a[i]) return false;
32  }
33  return true;
34 }
35 int find(int l, int r)
36 {
37  int mid = (l + r) >> 1;
38  while (l <= r) {
39   if (check(mid)) l = mid + 1;
40   else r = mid - 1;
41   mid = (l + r) >> 1;
42  }
43  return r;
44 }
45 int main()
46 {
47  init();
48  int CC = find(0, m);
49  if (CC == m) {puts("0\n");return 0;}
50  printf("%d\n%d\n", -1, CC + 1);
51  return 0;
52 }

Day2T3没时间写, 改天写.