题目链接

最后一题是Splay...还没有学会。。蒟蒻！！！

A

 /*************************************************************************

     > File Name: A.cpp

     > Author: Stomach_ache

     > Mail: sudaweitong@gmail.com

     > Created Time: 2014年09月28日 星期日 13时33分32秒

     > Propose:

  ************************************************************************/

 #include <cmath>

 #include <string>

 #include <cstdio>

 #include <fstream>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 /*Let's fight!!!*/

 int n, A[];

 int main(void) {

     ios::sync_with_stdio(false);

     int t;

     cin >> t;

     while (t--) {

         cin >> n;

         for (int i = ; i < n; i++) cin >> A[i];

         sort(A, A + n);

         long long res = ;

         for (int i = n - ; i >= ; i -= ) res += A[i];

         cout << res << endl;

     }

     return ;

 }

B

处理出每个素数在所有数中出现的次数最多的个数。

 /*************************************************************************

     > File Name: B.cpp

     > Author: Stomach_ache

     > Mail: sudaweitong@gmail.com

     > Created Time: 2014年09月28日 星期日 13时36分46秒

     > Propose:

  ************************************************************************/

 #include <map>

 #include <cmath>

 #include <string>

 #include <cstdio>

 #include <vector>

 #include <fstream>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 /*Let's fight!!!*/

 typedef pair<int, int> pii;

 const int MAX_N = ;

 const int MAX_M = ;

 bool vis[MAX_M];

 int prime[MAX_N], A[MAX_N], cnt;

 void init() {

       cnt = ;

       memset(vis, false, sizeof(vis));

     for (int i = ; i < MAX_M; i++) {

           if (!vis[i]) {

               prime[++cnt] = i;

             for (int j = *i; j < MAX_M; j += i) vis[j] = true;

         }

     }

 }

 #define rep(i, n) for (int i = (1); i <= (n); i++)

 vector<pii> factor(MAX_M);

 vector<pii>::iterator it;

 void work(int x, int y) {

     if (factor[x].second == ) {

         factor[x].second = y; }

     else {

         factor[x].second = max(y, factor[x].second);

     }

 }

 int main(void) {

     init();

     ios::sync_with_stdio(false);

     int t, n;

     cin >> t;

     while (t--) {

         rep (i, MAX_M) factor[i-].second = ;

         cin >> n;

         rep (i, n) cin >> A[i];

         rep (i, n) {

               int x = A[i];

             if (x == ) continue;

               rep (j, cnt) {

                   if (prime[j]*prime[j] > A[i]) break;

                   if (x % prime[j] == ) {

                       int tmp = ;

                     while (x % prime[j] == ) tmp++, x /= prime[j];

                     work(prime[j], tmp);

                 }

             }

           　　if (x > ) work(x, );

         }

         int res = ;

         for (it = factor.begin(); it != factor.end(); ++it) {

             res += it->second;

         }

         cout << res << endl;

     } 

     return ;

 }

C

线段树。

对于第一种修改，就是区间减１

对于第二种修改，就是单点更新

最后，查询每个点２，３，５因子的个数。

 /*************************************************************************

     > File Name: C.cpp

     > Author: Stomach_ache

     > Mail: sudaweitong@gmail.com

     > Created Time: 2014年09月28日 星期日 14时06分24秒

     > Propose:

  ************************************************************************/

 #include <cmath>

 #include <string>

 #include <cstdio>

 #include <fstream>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 /*Let's fight!!!*/

 const int MAX_N = ;

 int factor[][MAX_N], A[MAX_N], id[MAX_N];

 #define rep(i, n) for (int i = (1); i <= (n); i++)

 #define lson(x) ((x<<1))

 #define rson(x) ((x<<1) | 1)

 struct node {

     int l, r, Min[];

 }Tr[MAX_N<<];

 void build(int rt, int l, int r) {

     Tr[rt].l = l, Tr[rt].r = r;

     rep(i, ) Tr[rt].Min[i-] = ;

     if (l == r) {

         rep (i, ) Tr[rt].Min[i-] = factor[i-][l];

         id[l] = rt;

         return ;

     }

     int mid = (l + r) / ;

     build(lson(rt), l, mid);

     build(rson(rt), mid + , r);

 }

 void pushdown(int rt, int p) {

     if (Tr[rt].Min[p] != ) {

         Tr[lson(rt)].Min[p] += Tr[rt].Min[p];

         Tr[rson(rt)].Min[p] += Tr[rt].Min[p];

         Tr[rt].Min[p] = ;

     }

 }

 void update1(int rt, int l, int r, int p) {

     if (Tr[rt].l >= l && Tr[rt].r <= r) {

         Tr[rt].Min[p]--;

         return ;

     }

     pushdown(rt, p);

     int mid = Tr[lson(rt)].r;

     if (l <= mid) update1(lson(rt), l, r, p);

     if (r > mid) update1(rson(rt), l, r, p);

 }

 void update2(int rt, int l, int p, int d) {

     if (Tr[rt].l == Tr[rt].r && Tr[rt].l == l) {

         Tr[rt].Min[p] = d;

         return ;

     }

     pushdown(rt, p);

     int mid = Tr[lson(rt)].r;

     if (l <= mid) update2(lson(rt), l, p, d);

     else update2(rson(rt), l, p, d);

 }

 int query(int rt, int l, int p) {

     if (Tr[rt].l == Tr[rt].r && Tr[rt].l == l) {

         return max(Tr[rt].Min[p], );

     }

     pushdown(rt, p);

     int mid = Tr[lson(rt)].r;

     if (l <= mid) query(lson(rt), l, p);

     else query(rson(rt), l, p);

 }

 void read(int &res) {

     res = ;

     char c = ' ';

     while (c < '' || c > '') c = getchar();

     while (c >= '' && c <= '') res = res*+c-'', c = getchar();

 }

 int POW(int a, int b) {

     int res = ;

     while (b) {

         if (b & ) res *= a;

         a *= a;

         b >>= ;

     }

     return res;

 }

 int main(void) {

     int N, M, a[] = {, , , };

     read(N);

     rep (i, N) {

         read(A[i]);

         int x = A[i];

         factor[][i] = factor[][i] = factor[][i] = ;

         rep (j, ) {

             int tmp = , p = a[j];

             while (x % p == ) tmp++, x /= p;

             factor[j-][i] = tmp;

         }

         A[i] = x;

     }

     build(, , N);

     read(M);

     int t, l, r, p, d, tmp;

     while (M--) {

         read(t);

         if (t == ) {

             read(l), read(r), read(p);

             update1(, l, r, (p+)/-);

         } else {

             read(l), read(d);

             rep (i, ) {

                 tmp = , p = a[i];

                 while (d % p == ) tmp++, d /= p;

                 update2(, l, i-, tmp);

             }

             A[l] = d;

         }

     }

     rep (i, N) {

          rep (j, ) {

            tmp = query(, i, j-);

            A[i] *= POW(a[j], tmp);

      　　}

     　　 printf("%d%c", A[i], i == N ? '\n' : ' ');

     }

     return ;

 }

D

最新文章

  1. Map工具系列-08-map控件查看器
  2. the computer spends over 96% of its time waiting for I/O devices to finish transferring data
  3. XML文件解析DOM解析和SAX解析
  4. Spring security3入门（转）
  5. 通用权限管理系统接口文档V4.2 版本之消息接口介绍
  6. C 实现的算法篇
  7. jquery中eq和get的区别与使用方法
  8. label 和 legend标签的用法
  9. [Codecademy] HTML&amp;CSS第八课：Design a Button for Your Webwite
  10. Shell split character line by line
  11. parseSdkContent failed 解决方案
  12. MVC不用302跳转Action,内部跳转
  13. Halcon一日一练：创建三通道图像
  14. Java核心技术卷一基础知识-第3章-Java的基本程序设计结构-读书笔记
  15. C. Polycarp Restores Permutation
  16. open jdk
  17. Git -- 使用GitHub
  18. abap 从屏幕输入数据
  19. css sticker footer
  20. 保存chrome主题背景的图片

热门文章

  1. windows 内核下获取进程路径
  2. Python全栈开发：基本数据类型
  3. Android开发 ViewPager删除Item后,不会更新数据和View
  4. mysql 表查询结果 总行数计算
  5. WPF 免费控件库（2）
  6. Django常用组件之分页器
  7. 洛谷P3694 邦邦的大合唱
  8. 反编译之jd-gui的安装
  9. Django 异步任务、定时任务Celery
  10. hibernate查询timestamp条件