经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » 程序设计 » 编程经验 » 查看文章
Kickstart Round G 2018
来源：cnblogs　　作者：basasuya　　时间：2018/10/23 9:06:42　　对本文有异议

第一次打codejam....惨的一比,才A1.5题,感觉自己最近状态渣到姥姥家了,赶紧练练
A 模拟,注意0的问题

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <vector>
  8. #include <list>
  9. #include <queue>
  10. #include <stack>
  11. #include <map>
  12. #include <set>
  13. #include <bitset>
  14. #include <algorithm>
  15. #include <functional>
  16. #include <assert.h>
  17. #include <iomanip>
  18. using namespace std;
  19. const int N = 7005;
  20. const int M = 2e5 + 5;
  21. const int INF = 0x3f3f3f3f;
  22. const int MOD = 1000000007;
  23. typedef long long ll;
  26. int n;
  27. int A[N];
  28. vector<int> vc[M];
  29. int maxx;
  30. int solve(ll x, int pos) {
  31.     if(x > maxx) return 0;
  32.     int tt = (lower_bound(vc[x].begin(), vc[x].end(), pos) - vc[x].begin());
  33.     return vc[x].size() - tt;
  34. }
  35. int main() {
  36.     freopen("A-large.in", "r", stdin);
  37.     freopen("A-large.out", "w", stdout);
  38.     // vector<int> t1;
  39.     // t1.push_back(1); t1.push_back(2);
  40.     // int tt = (lower_bound(t1.begin(), t1.end(), -1) - t1.begin());
  41.     // printf("%d\n", tt);
  42.     int T;
  43.     scanf("%d", &T);
  44.     for(int _ = 1; _ <= T; ++_){
  45.         for(int i = 0; i < M; ++i) vc[i].clear();
  46.         scanf("%d", &n);
  47.         maxx = -1;
  48.         for(int i = 1; i <= n; ++i) {
  49.             scanf("%d",  &A[i]);
  50.             vc[A[i]].push_back(i);
  51.             maxx = max(maxx,  A[i]);
  52.         }
  53.         ll ans = 0;
  54.         for(int i = 1; i <= n; ++i) {
  55.             for(int j = i + 1; j <= n; ++j) {
  56.                 if(A[i] == 0 && A[j] == 0) ans += n - j;
  57.                 else if(A[i] == 0 || A[j] == 0) ans += solve(0, j + 1);
  58.                 else {
  59.                     int pre = -1;
  60.                     if(A[i] % A[j] == 0) ans += solve(A[i] / A[j], j+1), pre = A[i] / A[j];
  61.                     if(A[j] % A[i] == 0 && pre != A[j] / A[i]) ans += solve(A[j] / A[i], j+1), pre = A[j] / A[i];
  62.                     if(pre != 1ll * A[j] * A[i]) ans += solve(1ll * A[j] * A[i], j+1);
  63.                 }
  64.             }
  65.         }
  67.         printf("Case #%d: %lld\n", _, ans);
  68.     }
  69.     return 0;
  70. }

B 前缀和,二分

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <vector>
  8. #include <list>
  9. #include <queue>
  10. #include <stack>
  11. #include <map>
  12. #include <set>
  13. #include <bitset>
  14. #include <algorithm>
  15. #include <functional>
  16. #include <assert.h>
  17. #include <iomanip>
  18. using namespace std;
  19. const int N = 4e5 + 5;
  20. const int MM = 1e5 + 5;
  21. // const int M = 2e5 + 5;
  22. const int INF = 0x3f3f3f3f;
  23. const int MOD = 1000000007;
  24. typedef long long ll;
  25. struct Node{
  26.     int num, offset;
  27.     Node(int a=0, int b=0):num(a), offset(b) {}
  28.     bool operator < (const Node &T) const {
  29.         if(num != T.num) return num < T.num;
  30.         else return offset < T.offset;
  31.         ///
  32.     }
  33. };
  34. struct Tode{
  35.     ll sum; int val; int len; int now;
  36.     Tode(ll a=0, int b=0, int c=0, int d=0):sum(a), val(b), len(c), now(d){}
  37.     bool operator < (const Tode &T) const {
  38.         if(sum != T.sum) return sum < T.sum;
  39.         else return 1;
  40.         ///
  41.     }
  42. };
  44. int n, q;
  45. ll X[N], Y[N], A[5], B[5], C[5], M[5];
  46. ll Z[MM];
  47. Node seq[N * 2];
  48. Tode prefix[N * 2];
  49. ll hhh[N * 2];
  51. int main() {
  52.     freopen("B-small-attempt4.in", "r", stdin);
  53.     freopen("B-small-attempt4.out", "w", stdout);
  54.     
  55.     int T;
  56.     scanf("%d", &T);
  57.     for(int _ = 1; _ <= T; ++_){
  58.         scanf("%d %d", &n, &q);
  59.         scanf("%lld %lld %lld %lld %lld %lld", &X[1], &X[2], &A[1], &B[1], &C[1], &M[1]);
  60.         scanf("%lld %lld %lld %lld %lld %lld", &Y[1], &Y[2], &A[2], &B[2], &C[2], &M[2]);
  61.         scanf("%lld %lld %lld %lld %lld %lld", &Z[1], &Z[2], &A[3], &B[3], &C[3], &M[3]);
  63.         for(int i = 3; i <= n; ++i) {
  64.             X[i] = (A[1] * X[i - 1] + B[1] * X[i - 2] + C[1]) % M[1];
  65.             Y[i] = (A[2] * Y[i - 1] + B[2] * Y[i - 2] + C[2]) % M[2];
  66.         }
  67.         for(int i = 3; i <= q; ++i) {
  68.             Z[i] = (A[3] * Z[i - 1] + B[3] * Z[i - 2] + C[3]) % M[3];
  69.         }
  70.         for(int i = 1; i <= n; ++i) {
  71.             X[i] ++; Y[i] ++;
  72.         }
  73.         for(int i = 1; i <= q; ++i) Z[i] ++;
  75.         int tot = 0;
  76.         ll tt = 0;
  77.         for(int i = 1; i <= n; ++i) {
  78.             if(X[i] > Y[i]) swap(X[i], Y[i]);
  79.             // printf("%lld %lld\n", X[i], Y[i]);
  80.             tt += Y[i] - X[i] + 1;
  81.             seq[tot ++ ] = Node(X[i], 1);
  82.             seq[tot ++ ] = Node(Y[i] + 1, -1);
  83.         }
  84.         // printf("%lld\n", tt);
  86.         sort(seq, seq + tot);
  88.         // for(int i = 0; i < tot; ++i) printf("%d %d : ", seq[i].num, seq[i].offset); printf("\n");
  89.         // seq[tot] = Node(seq[tot - 1].num + 1, 0); 
  90.         int tmp = 0;
  91.         int tot2 = 0;
  92.         ll all = 0;
  93.         for(int i = 1; i < tot; ++i) {
  94.             tmp += seq[i-1].offset;
  95.             if(seq[i].num != seq[i-1].num) {
  96.                 int tt = seq[i].num - seq[i - 1].num;
  97.                 prefix[tot2] = Tode(all, tmp, tt, seq[i-1].num);
  98.                 // if(seq[i-1].num < 0) printf("hhh");
  99.                 hhh[tot2 ++] = all;
  100.                 // printf("%lld %d %d from %d to %d\n", all, tmp, tt, seq[i-1].num, seq[i].num);
  101.                 all += 1ll * tt * tmp;
  102.             }
  103.         }
  104.         // printf("%lld\n", all);
  106.         ll ans = 0;
  107.         for(int i = 1; i <= q; ++i) {
  108.             // printf("hhh: %lld\n", Z[i]);
  109.             Z[i] = tt - Z[i] + 1;
  110.             if(Z[i] <= 0) continue;
  111.             // Z[i] = 1;
  112.             // printf("hhh: %lld\n", Z[i]);
  113.             int pos = lower_bound(hhh, hhh + tot2, Z[i]) - hhh;
  114.             pos --;
  115.             ll lef = Z[i] - prefix[pos].sum;
  116.             // printf("%d %d %lld\n", pos, prefix[pos].now, lef);
  117.             ll tt = prefix[pos].now + lef / prefix[pos].val ;
  118.             if(lef && (lef % prefix[pos].val == 0) ) tt --;
  119.             // printf("%lld\n", tt);
  120.             ans += 1ll * tt * i;
  121.         }
  123.         printf("Case #%d: %lld\n", _, ans);
  124.     }
  126.     return 0;
  127. }
  129. /*
  131. 3
  132. 5 5
  133. 3 1 4 1 5 9
  134. 2 7 1 8 2 9
  135. 4 8 15 16 23 42
  138. 3
  139. 5 1
  140. 3 1 4 1 5 9
  141. 2 7 1 8 2 9
  142. 4 8 15 16 23 42
  143. 5 5
  144. 3 1 4 1 5 9
  145. 2 7 1 8 2 9
  146. 4 8 15 16 23 42
  147. 1 2
  148. 0 0 0 0 0 1
  149. 0 0 0 0 0 1
  150. 0 1 0 0 0 2
  152. 100
  153. 1 2
  154. 0 0 0 0 0 1
  155. 0 0 0 0 0 1
  156. 0 1 0 0 0 2
  158. 100
  159. 55769 1
  160. 0 0 0 0 0 1000000000
  161. 999999999 999999999 0 0 999999999 1000000000
  162. 2512670 116262940 14464944 27962747 49835299 118572793
  165. 400000 1
  166. 97295458 97277314 13871606 251023440 11331260 274678035
  167. 97295458 97277314 13871606 251023440 11331260 274678035
  168. 244442 258459 136705 290087 276595 400000
  169. */

C 状压dp+dfs

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <vector>
  8. #include <list>
  9. #include <queue>
  10. #include <stack>
  11. #include <map>
  12. #include <set>
  13. #include <tuple>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <assert.h>
  18. #include <iomanip>
  19. using namespace std;
  20. const int N = 32768;
  21. const int M = 2e5 + 5;
  22. const int INF = 0x3f3f3f3f;
  23. const int MOD = 1000000007;
  24. typedef long long ll;
  26. int n, m, e, sx, sy, tx, ty;
  27. int mp[105][105];
  28. int has[105][105];
  29. int dir[][2] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };
  30. ll energy[N];
  31. int exiting[N];
  32. int remain[N];
  33. int tag[105][105];
  34. vector<tuple<int, int, int> > trap;
  35. int trapNum;
  36. ll dp[N];
  37. void solve(ll all, int id) {
  38.     memset(has, 0, sizeof(has));
  39.     queue<tuple<int, int> > Q;
  40.     Q.push(make_tuple(sx, sy));
  41.     has[sx][sy] = 1;
  42.     int flag = 0;
  43.     int remainNum = 0;
  44.     while(!Q.empty()) {
  45.         int x = get<0>(Q.front()); int y = get<1>(Q.front()); Q.pop();
  46.         if(x == tx && y == ty) {
  47.             flag = 1;
  48.         }
  49.         for(int i = 0; i < 4; ++i) {
  50.             int dx = x + dir[i][0];  int dy = y + dir[i][1];
  51.             if(dx < 1 || dx > n || dy < 1 || dy > m  || has[dx][dy] || mp[dx][dy] == -100000) continue;
  52.             if(mp[dx][dy] < 0 ) {
  53.                 remainNum |= 1 << tag[dx][dy]; continue;
  54.             }
  55.             all += mp[dx][dy];
  56.             has[dx][dy] = 1;
  57.             Q.push(make_tuple(dx, dy));
  58.         }
  59.     }
  60.     energy[id] = all;
  61.     exiting[id] = flag;
  62.     remain[id] = remainNum;
  63. }
  65. ll dfs(int mask) {
  66.     if(~dp[mask]) return dp[mask];
  68.     ll ans = -1;
  69.     if(exiting[mask] == 1) ans = energy[mask];
  71.     for(int i = 0; i < trapNum; ++i) {
  72.         if( (remain[mask] >> i) & 1) {
  73.             if(-mp[get<0>(trap[i])][get<1>(trap[i])] <= energy[mask])
  74.                 ans = max(ans, dfs(mask | (1<<i)));
  75.         }
  76.     }
  78.     dp[mask] = ans;
  79.     return ans;
  80. }
  81. int main() {
  82.     freopen("./C-large-practice2.in", "r", stdin);
  83.     // freopen("./C-large-practice2.out", "w", stdout);
  84.     int T;
  85.     scanf("%d", &T);
  86.     for(int _ = 1; _ <= T; ++_){
  87.         trap.clear();
  88.         memset(dp, -1, sizeof(dp));
  89.         scanf("%d %d %d %d %d %d %d", &n, &m, &e, &sx, &sy, &tx, &ty);
  91.         for(int i = 1; i <= n; ++i) {
  92.             for(int j = 1; j <= m; ++j) {
  93.                 scanf("%d", &mp[i][j]);
  94.             }
  95.         }
  97.         for(int i = 1; i <= n; ++i) {
  98.             for(int j = 1; j <= m; ++j) {
  99.                 if(mp[i][j] < 0 && mp[i][j] != -100000) {
  100.                     trap.emplace_back(i, j, mp[i][j]);
  101.                     tag[i][j] = trap.size() - 1;
  102.                 }
  103.             }
  104.         }
  106.         trapNum = trap.size();
  108.         for(int i = 0; i < 1 << trapNum; ++i) {
  109.             ll all = e;
  110.             for(int j = 0; j < trapNum; ++j) {
  111.                 if( (i >> j) & 1 ) {
  112.                     mp[get<0>(trap[j])][get<1>(trap[j])] = 0;
  113.                     all += get<2>(trap[j]);
  114.                 }
  115.             }
  117.             solve(all, i);
  119.             for(int j = 0; j < trapNum; ++j) {
  120.                 if( (i >> j) & 1 ) {
  121.                     mp[get<0>(trap[j])][get<1>(trap[j])] = get<2>(trap[j]);
  122.                 }
  123.             }
  124.         }
  126.         // for(int i = 0; i < 1<<trapNum; ++i) printf("%lld %d %d\n", energy[i], remain[i], exiting[i]);
  128.         printf("Case #%d: %lld\n", _, dfs(0));
  129.         
  130.         
  131.         
  132.     }
  133.     return 0;
  134. }
  136. /*
  139. 2
  140. 4 4 100 1 1 4 4
  141. 0 0 0 0
  142. 0 0 0 0
  143. 0 0 0 -100000
  144. 0 0 -100000 0
  145. 8 8 250 7 1 1 7
  146. -100000 -100000 -100000 -100000 -100000 -100000 0 -100000
  147. -100000 0 -100000 0 -400 0 0 -100000
  148. -100000 100 -300 0 -100000 -300 -100000 -100000
  149. -100000 0 -100000 500 -100000 250 0 -100000
  150. -100000 -200 -100000 -100000 -100000 -100000 -100 -100000
  151. -100000 0 -100000 0 0 50 50 -100000
  152. 0 0 -100 0 -100000 50 -100000 -100000
  153. -100000 -100000 -100000 -100000 -100000 -100000 -100000 -100000
  156. */
 友情链接：直通硅谷 　点职佳 　北美留学生论坛

编程经验热门文章

  • Prometheus监控之SNMP Exporter介绍和数据展现
  • Intel 82599网卡异常挂死原因
  • 腾讯防水墙的分析识别与破解
  • 桌面应用自动化WinAppDriver入门
  • 文档在线预览（三）使用js前端实现word、excel、pdf、ppt 在线预览
  • 「教程」如何下载AcFun网站上的视频、A站视频下载工具
  • 基于Hi3559AV100的SVP(NNIE)开发整体流程
  • GBDT(梯度提升树)scikit-klearn中的参数说明及简汇
  • antd之RangePicker设置默认值方式
  • 决胜经典算法之插入排序

    • 编程经验推荐文章

  • wifi基础(一)：无线电波与WIFI信号干扰、衰减
  • 甲方扔给两个存在包名与类名均相同的Jar包，要在工程中同时使用怎么办？
  • 《花100块做个摸鱼小网站! 》第三篇—热搜表结构设计和热搜数据存储
  • Fluent Editor：一个基于 Quill 2.0 的富文本编辑器，功能强大、开箱即用！
  • 方法的三种调用形式
  • 《花100块做个摸鱼小网站! 》第二篇—后端应用搭建和完成第一个爬虫
  • 《熬夜整理》保姆级系列教程-玩转Wireshark抓包神器教程(4)-再识Wireshark - 北京-宏哥
  • 《软件性能测试分析与调优实践之路》(第2版) 读书笔记（二）总体介绍（下）-真正从性能分析与调优来看性能测试
  • 架构知识点（三）
  • 《花100块做个摸鱼小网站! 》第一篇—买云服务器和初始化环境

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号