Codeforces Round #223 (Div. 2)-白红宇

Codeforces Round #223 (Div. 2)

阅读量：5902 次

发布时间：2019-06-19

本文共 3687 字，大约阅读时间需要 12 分钟。

题意：两个人从序列两端取大的一个值，轮流取，问最后各自的和。

分析：直接模拟。

/***************************************** File Name: 223a.cpp* Author: sky0917* Created Time: 2014年01月12日 22:59:43****************************************/#include #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;const int maxn = 100005;int n, m;int a[1002];int b[2];int main(){ while (scanf("%d",&n)!=EOF){ int l = 0, r = n-1; for (int i=0; i
            
              a[r]){ b[tot&1] += a[l]; l++; } else { b[tot&1] += a[r]; r--; } } printf("%d %d\n",b[1],b[0]); } return 0;}

题意：一个人有m个数字，现在他要选出尽可能多的数字摆成一个序列，满足以下条件：

a1 < a2 < ... < ai - 1 < ai > ai + 1 > ... > a|a| - 1 > a|a|.

分析：由于数字的值最大是5000，所以可以用标记数组记录每个数出现的次数，然后先从小到大遍历一遍输出，再从大到小遍历输出。

/***************************************** File Name: 223b.cpp* Author: sky0917* Created Time: 2014年01月12日 23:29:26****************************************/#include #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;const int maxn = 100005;int n;int a[maxn];int b[5005];int res[maxn];int main(){ while (scanf("%d",&n)!=EOF){ memset(b, 0, sizeof(b)); int va; for (int i=0; i
            
             =1; i--){ if (b[i]){ res[tp++] = i; } } printf("%d\n",tp); for (int i=0; i

题意：给出m < 100000 次操作,每次操作两种：

1 xi ：表示在序列结尾加上一个值为 xi 的数

2 li ci: 表示把序列的前li个数重复ci次放在序列结尾

给出 n 个数 ai

输出序列中第 ai 个数的值

由于 li <= 100000 所以可以仅保留序列的前 100000 个数即可，

对于 1 情况看看 len + 1 是否等于 ai，等于就输出，否则不管，

对于情况 2 第 ai　个数的值为 (ai-len) % li 个位置的数，直接输出即可，每次 len += ci * li

/***************************************** File Name: 223c.cpp* Author: sky0917* Created Time: 2014年01月13日  9:33:31****************************************/#include #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;const int maxn = 100005;int m, n;long long va[maxn];struct node{ int ty; long long li, ci; long long ai;}q[maxn];long long a[maxn];void solve(){ int tt = 0; int tp = 0; long long len = 0; for (int i=0; i
            
             = va[tt]){ long long xu = (va[tt]-len) % q[i].li; xu = (xu-1 + q[i].li) % q[i].li; printf("%I64d ", a[xu]); tt++; } len += q[i].ci * q[i].li; for (long long j=0; j

题意：给出一个类似 ())(())(())( 的括号序列，长度 m < 1000000,给出 n 个询问 l, r，输出[l, r]区间内最多有多少个匹配的括号，n<100000。

分析：树状数组+离线。

先把询问保存，然后按照（位置从大到小排序，

从括号序列的尾部向前遍历，维护一个）位置的栈

如果遇到 i　位置为）则把 i 入栈，

如果遇到 i 位置为（，如果栈不为空，则 add（pos = st[top])，即把区间[1, st[top]] 都+1

对于当前位置 i, 计算所有询问左区间 = i 的值为 getsum（r).

/***************************************** File Name: 223e.cpp* Author: sky0917* Created Time: 2014年01月13日 10:15:04****************************************/#include #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;const int maxn = 1000005;const int maxm = 100005;char s[maxn];struct node{ int l, r; int xu;}q[maxm];int n, m;bool cmp(node a, node b){ return a.l > b.l;}int res[maxm];inline int lowbit(int x){ return (x) & (-x);}int tr[maxn];void add(int pos){ while (pos < m){ tr[pos] += 1; pos += lowbit(pos); }}int getsum(int pos){ int su = 0; while (pos > 0){ su += tr[pos]; pos -= lowbit(pos); } return su;}int st[maxn];int tp;void solve(){ sort(q, q+n, cmp); tp = 0; int j = 0; for (int i=m-1; i >= 0; i--){ if (s[i] == ')'){ st[++tp] = i; } else if (tp > 0){ add(st[tp--]); } while (j < n && q[j].l == i){ res[q[j].xu] = getsum(q[j].r); j++; } } for (int i=0; i

转载于:https://www.cnblogs.com/sky0917/p/3517029.html

你可能感兴趣的文章