首页 > > 程序设计 > C/C++ >

『ACM C++』 Codeforces | 1066A - Points in Se…

2019-03-01 10:11:54来源：博客园阅读 ()

　　大一生活真特么 ”丰富多彩“ ，多彩到我要忙到哭泣，身为班长，很多班级的事情需要管理，也是，什么东西都得体验学一学，从学生会主席、团委团总支、社团社长都体验过一番了，现在差个班长也没试过，就来体验了一番哈哈哈，其实这种精心服务一个班级的人还是很棒的一种感觉呢。思考思考最近的任务啊：

　　（1）英语剧

　　（2）三下乡公益策划

　　（3）兼职 - 影视剧组后期特效

　　（3）三月底程序设计大赛天梯赛

　　（4）班会以及班级细节事件处理

　　（5）多模态视频处理

　　（6）兼职 - 校方艺考航拍记录

　　（7）六月四级考试和三下乡

　　（8）七月暑假学车

　　（9）兼职 - Eddy工作

　　哇大致想了想我真的可以忙死加学到死鸭，嘛，能者多劳，扛住就是胜利！！！好啦~不扯多，今天ACM集训队训练有道坑题得六个心眼，妈耶交了九次WA九次，最后一次交终于AC，哭迈

今日兴趣新闻：

MWC折叠屏刷屏背后的一场大戏：5家厂商恩怨情仇史

链接：https://mbd.baidu.com/newspage/data/landingsuper?context=%7B"nid"%3A"news_9543883370009568888"%7D&n_type=0&p_from=1

　　最近华为的新手机在朋友圈刷了不少圈，这种合并平板和手机的方式说不定真的会在未来畅销，因为这两者的用户需求量本来就是挺大的~，这篇新闻还是蛮有趣的讲了这几年的势头，可以看看。

------------------------------------------------题目----------------------------------------------------------

You are given a set of

Consider all integer points between

Input

The first line of the input contains two integers

The next

Output

In the first line print one integer

In the second line print exactly

If there are no such points at all, print a single integer

Examples

input

output

2
3 4

input

1 7
1 7

output

Note

In the first example the point

In the second example all the points from

（一）原题大意：

　　　　题目愿意是：输入四个量：L、V、left、right，其中从1到L为范围界，即1<=x<=L，当满足x可以整除V时，说明该处有灯笼，但left和right这个范围内没有灯笼，请统计有几个灯笼。

　　　　题目感觉是不难的，但就是在一些端点特值处理上会有些问题。

（二）题目分析：

　　　　这里记录一下我原本的错误思想：

　　　　第一次我的错误想法是直接就for暴力搜索了，结果就会超时Time limit exceeded on test 2

　　　　错误代码：

#include<stdio.h>
int times,L,V,left,right;
int ans_light;
int main()
{
    scanf("%d",&times);
    while(times--)
    {
        ans_light = 0;
        scanf("%d %d %d %d",&L,&V,&left,&right);
        for(int i = 1;i<left;i++) if(i%V == 0) ans_light++;
        for(int i = right+1;i<=L;i++) if(i%V == 0) ans_light++;
        printf("%d\n",ans_light);
    }
    return 0;
 }

　　　　谨记千万没事就不要暴搜，看看有没有快捷的方式可以快速得到答案，这是ACM要训练我们的。

　　　　第二个错误的想法：

　　　　原本的想法是用了ceil函数，即向上取整，让V输入的数是个浮点数，代码大概如下：

             ans_light_1 = ceil((left - 1)/V);
             ans_light_2 = ceil((L - right)/V);
             printf("%d\n",ans_light_1+ans_light_2);

　　　　然而这个做法，在V小于left的时候，答案是正确的，交了半天发现当V大于等于left的时候就会出现问题了

　　　　所以第三个错误想法，我就把V和left的两种情况区分开来讨论了：

#include<stdio.h>
#include<math.h>
int times,L,left,right;
float V;
int ans_light_1,ans_light_2;
int main()
{
    scanf("%d",&times);
    while(times--)
    {
        ans_light_1 = ans_light_2 = 0;
        scanf("%d %f %d %d",&L,&V,&left,&right); 
        if(V<left)
        {
             ans_light_1 = ceil((left - 1)/V);
             ans_light_2 = ceil((L - right)/V);
             printf("%d\n",ans_light_1+ans_light_2);
        }
        else
        {
            ans_light_1 = L/int(V);
            ans_light_2 = right/int(V) - left/int(V);
            if(left % int(V) == 0)
            {
                printf("%d\n",ans_light_1 - ans_light_2 - 1);
                continue;
            }
            printf("%d\n",ans_light_1 - ans_light_2);
        }
    }
    return 0;
 }

　　　　结果写到这里的时候，突然发现可以直接用一个公式直接求解：

　　　　这里的灯笼数，实际上等于 L / V 减去（ r / V - ( l - 1 ) / V ) 这样就能得到结果了。

（三） AC代码：

　　　　因为代码比较简单，就不分块了，直接献上，给自己留个提醒。

#include<stdio.h>
#include<math.h>
int times,L,left,right;
int V;
int ans_light_1,ans_light_2;
int main()
{
    scanf("%d",&times);
    while(times--)
    {
        ans_light_1 = ans_light_2 = 0;
        scanf("%d %d %d %d",&L,&V,&left,&right); 
        ans_light_1 = L/V;
        ans_light_2 = right/V - (left-1)/V;
        printf("%d\n",ans_light_1 - ans_light_2);
    }
    return 0;
 }