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

 

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

　　（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

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

 

 

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

a. points in segments

you are given a set of nn segments on the axis oxox, each segment has integer endpoints between 11 and mm inclusive. segments may intersect, overlap or even coincide with each other. each segment is characterized by two integers lili and riri (1≤li≤ri≤m1≤li≤ri≤m) — coordinates of the left and of the right endpoints.

consider all integer points between 11 and mm inclusive. your task is to print all such points that don't belong to any segment. the point xxbelongs to the segment [l;r][l;r] if and only if l≤x≤rl≤x≤r.

input

the first line of the input contains two integers nn and mm (1≤n,m≤1001≤n,m≤100) — the number of segments and the upper bound for coordinates.

the next nn lines contain two integers each lili and riri (1≤li≤ri≤m1≤li≤ri≤m) — the endpoints of the ii-th segment. segments may intersect, overlap or even coincide with each other. note, it is possible that li=rili=ri, i.e. a segment can degenerate to a point.

output

in the first line print one integer kk — the number of points that don't belong to any segment.

in the second line print exactly kk integers in any order — the points that don't belong to any segment. all points you print should be distinct.

if there are no such points at all, print a single integer 00 in the first line and either leave the second line empty or do not print it at all.

examples

input

3 5
2 2
1 2
5 5

output

2
3 4 

input

1 7
1 7

output

 0

note

in the first example the point 11 belongs to the second segment, the point 22 belongs to the first and the second segments and the point 55belongs to the third segment. the points 33 and 44 do not belong to any segment.

in the second example all the points from 11 to 77 belong to the first segment.

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

 

（一） 原题大意：

　　　　题目愿意是：输入四个量：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;
 } 

 

 

（四）ac截图：

 

 

注：我还是个渣渣辉，代码可能写得不够高效不够好，我也会努力优化，如果有更好的解法，真心希望您能够评论留言贴上您的代码呢~互相帮助互相鼓励才能成长鸭~~