CF 387C 贪心

Advertisement

题目链接:这里
题意:就是给处一个长度不超过10^5的十进制正整数, 是按照题目所给的方法从一个数组中拼出来的,为初始的那个数组最多有多少个元素。
解法:从末尾向开头贪心加更大字符串的字符串即可。

//CF 387C

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
char s[maxn], tmp[maxn];
int cnt, i;
bool check(){
    if(i > cnt) return true;
    if(i < cnt) return false;
    for(int i = 0; i < cnt; i++){
        if(s[i] < tmp[cnt-1-i]) return false;
    }
    return true;
}
int main()
{
    scanf("%s", s);
    int len = strlen(s), ans = 1;
    cnt = 0;
    for(i = len - 1; i >= 0; i--){
        if(s[i] == '0') tmp[cnt++] = s[i];
        else{
            tmp[cnt++] = s[i];
            if(check()){
                ans++;
                cnt = 0;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

Similar Posts:

  • CF 490E 贪心,回溯法

    题目链接:这里 题意:一个严格递增序列 某些数字的某些位被盖住了 求 恢复后的序列. 解法:贪心,让每个数在大于前一个的基础上尽量小,先考虑数字长度.if(len[i] < len[i+1])输出NO,当len[i] > len[i-1],如果第一位是?就改成1,其他的问号改成0,接下来是长度相等的时候DFS(回溯法)即可. //CF 490E #include <bits/stdc++.h> using namespace std; const int maxn = 1e5+10

  • CF 782C 贪心,DFS染色,水题

    题目链接:见这里 题意:给了一颗树,要让每个连起来的(u, v, w)三个点的颜色不同,默认1点被染成颜色1,问最少多少种颜色可以完成,并输出每个点的颜色编号. 解法:贪心+DFS,直接记录一下,这个点的父亲的颜色,和这个点的父亲的父亲的颜色,只要颜色颜色和它们不同就可以用这个颜色更新当前这个点的颜色,染完这个点之后让颜色编号nowc++,使得每个点的其他儿子节点和它的颜色不同. #include <bits/stdc++.h> using namespace std; const int m

  • [置顶] 只会做水题-

    都是水题 15.11.09 数字为POJ题号 ------------------------11.9 1003 1004 1005 1007 1006 中国剩余定理 1001 浮点数高精度计算 1002 map映射 ---------------------11.10 1088 dfs 1163 dfs 1008 模拟 1050 dp 1012 约瑟夫问题 暴力模拟+打表 1011 DFS+剪枝 2027 ---------------------------11.11 2388 1046 1

  • CF Anya and Ghosts (贪心)

    Anya and Ghosts time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Anya loves to watch horror movies. In the best traditions of horror, she will be visited by m ghosts tonight. Anya has lots

  • CF 557C Arthur and Table(贪心)

    刚读题想到用dp,思考一下发现dp并不是那么容易.然后脑补出来了贪心做法:枚举每一个长度 l 使得最终的稳定态是以 l 为最长腿,那么所有比 l 大的桌腿我们都要砍掉,然后所有 l 的都不砍,最后把比 l 小的若干个 d 比较小的砍掉之后使得 l 的个数大于其他桌腿的个数. 具体实现的时候,我们先把桌腿按照 l 升序排列,然后预处理出来cnt[i],first[i],两个个数组.其中cnt[i]表示桌腿长度为i的个数,first[i]表示长度为 i 的桌腿第一次出现在数列中的位置.然后枚举桌腿的

  • CF#323-DIV2-D. Once Again-暴力贪心LIS

    给出n长度的字符串 重复t个周期 求LIS(最长非递减子序列) 由于n最大才100..考虑最极端情况n=100,t=1e7 显然,我们只需要把前100段拼接起来,求一遍LIS 此后的t-100周期, 我们只需要 取 重复个数最多的那个元素. 一直重复t-100次得到的答案必然是最优的 (不可能有其他情况了) 例如 n=4; 6 2 2 3 前100次 我们取得的lis是100对 (2 2) 以及一个3 那么显然 重复最多次的元素是2,次数为2 剩下t-100次,我们只需要先把最后一个3 去掉,然

  • CF 500 C. New Year Book Reading 贪心 简单题

    New Year is coming, and Jaehyun decided to read many books during 2015, unlike this year. He has n books numbered by integers from 1 to n. The weight of the i-th (1 ≤ i ≤ n) book is wi. As Jaehyun's house is not large enough to have a bookshelf, he k

  • CF 556D Case of Fugitive 根据岛屿选择桥(贪心)

    http://codeforces.com/contest/556/problem/D 题意:给你n个岛屿 m个桥,岛屿在一条线上 给岛屿的左坐标与又坐标(L,R).从左到右按顺序给每个岛的L,R 再给你每个桥的长度,每个桥只能用一次 让你用桥把岛屿连接起来,能连则输出yes,并且输出每两个岛屿之间的桥的编号 连接的要求是,每个桥要能连接两个相邻岛屿,又不能越出两个岛屿的最大距离,即x>=L[i+1]-R[i] && x<=R[i+1]-L[i] 思路:贪心,存下两两相邻岛屿之

  • 贪心 CF 333B Chips

    题目链接: http://codeforces.com/problemset/problem/333/B 题目意思: 给一个n*n的矩阵,里面有m个障碍点,问最多可以在不是角落的边框上放多少个点,使得所有点的同时向对面移动,不遇到障碍点且不相互冲突. 解题思路: 贪心思想. 首先障碍点所在行和列不能放,然后当n为奇数时,n/2+1行和列只能放一个,其他行或列只要能放就放,因为不冲突,对于任意一行和一列,四种情况中必有一种满足他们两之间不冲突. 代码: #include<iostream> #i

  • CF 779 C Dishonest Sellers 贪心,排序

    题目链接:见这里 题意:给了一些物品,每个物品有俩个价格,一个是打折前的,一个是打折后的(打折发生在一周后),现在一个人必须先买k个物品,然后剩下的物品既可以选择现在买,也可以选择一周后买,其中打折后的价格不一定比现有价格低,无良商人,大家都懂. 解法:我们先考虑一下必须买的k个物品,肯定要优先选择那些打折后变贵的物品,并且在变得同等贵的时候,我们要优先买现在价格大的.买完k个之后,剩下的就是俩个价格取个小,这题就做完了. //CF 779C #include <bits/stdc++.h>

Tags: