注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Saffah's Blog

 
 
 

日志

 
 

BestCoder Round #11  

2014-09-29 10:32:18|  分类: BestCoder |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
上一场打挂了掉到div2了……所以这场就能参加了233
题目都很水,所以本文不适合神牛观看……
按Ctrl-A出题解。

1001 Alice and Bod(HDU 5054)
题意略……
题解略……
int main(){
    int n, m, x, y;
    while(scanf("%d%d%d%d", &n, &m, &x, &y) != EOF){
        if(n == 2 * x && m == 2 * y) printf("YES\n"); else printf("NO\n");
    }
    return 0;
}

1002 Bob and math problem(HDU 5055)
给n个数字,让你重排成一个不含前导零的最大的奇数,或输出无解。
选一个最小的奇数放到最后,如果找不到就无解。
然后如果剩下的全是0就无解,否则从大往小放。
int cnt[10];
char buf[256], *cb;

int main(){
    int n;
    while(scanf("%d", &n) != EOF){
        memset(cnt, 0, sizeof(cnt));
        memset(buf, 0, sizeof(buf));
        f(i, 1, n){
            int a; scanf("%d", &a); ++cnt[a];
        }
        int lst = -1;
        for(int i = 1; i < 10; i += 2) if(cnt[i]){
            lst = i; --cnt[i]; break;
        }
        if(lst == -1){
            printf("-1\n"); continue;
        }
        cb = buf;
        int ok = false;
        h(i, 9, 1) while(cnt[i]--){
            cb += sprintf(cb, "%d", i); ok = true;
        }
        if(cnt[0] && !ok){
            printf("-1\n"); continue;
        }
        while(cnt[0]--) cb += sprintf(cb, "0");
        printf("%s%d\n", buf, lst);
    }
    return 0;
}

1003 Boring count(HDU 5056)
给一个字符串,问有多少子串使得每个字母的出现次数都不超过k。
如果算出了每个字母出现次数的前缀和,那么可以枚举右端点,二分查找最远的左端点。
然后发现左端点是单调的,所以two pointers搞一搞。
int cnt[26];
char s[100086]; int k;

int main(){
    int T; scanf("%d", &T);
    while(T--){
        scanf("%s%d", s + 1, &k);
        int n = strlen(s + 1);
        f(i, 1, n) s[i] -= 'a';
        memset(cnt, 0, sizeof(cnt));
        LL ans = 0;
        int l = 1;
        f(r, 1, n){
            int &tar = cnt[s[r]];
            if((++tar) > k) while(tar > k){
                --cnt[s[l]]; ++l;
            }
            ans += (LL) (r - l + 1);
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

1004 Argestes and Sequence(HDU 5057)
给一个序列,每次可以改一个数,或询问[L,R]中第d位是p的数有多少个。
直接开100个线段树是修改要改10个线段树,查询查1个线段树。好像空间有压力。
那就分块好了,修改改10个块,查询查O(sqrtn)个块。
(我居然是最快的23333)
inline void read(int &x){
    char c = getchar();
    while(c < '0') c = getchar();
    x = c - '0'; c = getchar();
    while(c >= '0'){
        x = x * 10 + (c - '0'); c = getchar();
    }
}
char buf[256], *cb = buf;
inline void writeln(int x){
    if(x){
        while(x){
            *(cb++) = x % 10 + '0'; x /= 10;
        }
        while(cb != buf) putchar(*(--cb));
    }else putchar('0');
    putchar('\n');
}

int block[520][11][10];
int digit[100086][11];
//400 blocks, each 256
int n, m;

int main(){
    int T; read(T);
    while(T--){
        read(n); read(m);
        memset(block, 0, sizeof(block));
        f(i, 1, n){
            int a; read(a);
            f(j, 1, 10){
                int b = i >> 8;
                ++block[b][j][digit[i][j] = a % 10];
                a /= 10;
            }
        }
        while(m--){
            char c = getchar();
            while(c != 'S' && c != 'Q') c = getchar();
            if(c == 'S'){
                int x, y; read(x); read(y);
                int b = x >> 8;
                f(j, 1, 10){
                    --block[b][j][digit[x][j]];
                    ++block[b][j][digit[x][j] = y % 10];
                    y /= 10;
                }
            }else{
                int l, r, d, p; read(l); read(r); read(d); read(p);
                int bl = ((l - 1) >> 8) + 1, br = (r + 1) >> 8;
                if(bl <= br){
                    int bls = bl << 8, brs = br << 8;
                    int ans = 0;
                    g(i, l, bls) ans += (digit[i][d] == p);
                    f(i, brs, r) ans += (digit[i][d] == p);
                    g(i, bl, br) ans += block[i][d][p];
                    writeln(ans);
                }else{
                    int ans = 0;
                    f(i, l, r) ans += (digit[i][d] == p);
                    writeln(ans);
                }
            }
        }
    }
    return 0;
}

  评论这张
 
阅读(153)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018