[Atcoder 080] A~D Tutorial

很好奇这周为什么只有Beginner Contest而没有Regular Contest，本来想着去30minAK的，结果1个小时了还有一道题调不出来o(╯□╰)o

A：Parking

让我体验了下开场30sAC的快感......

#include <bits/stdc++.h>

using namespace std;

int main()

{

    long long n,a,b;cin >> n >> a >> b;

    if(n*a<b) cout << n*a;

    else cout << b;

    return ;

}

B:Harshad Number

#include <bits/stdc++.h>

using namespace std;

int main()

{

    int n;cin >> n;

    int temp=n,sum=;

    while(temp) sum+=(temp%),temp/=;

    if(n%sum==) cout << "Yes";

    else cout << "No";

    return ;

}

C:Shopping Street

很简单的暴力+位运算，然而直到最后也没调出来......

出来一看题解，发现只有一个地方不同：标程初始化-1<<30,我的初始化-1<<27

猛然发现1<<27到不了1e9，平时为了保险防溢出用1<<27没事，但最值为1e9时初始值要为1<<30或1e9+7

#include <bits/stdc++.h>

using namespace std;

int n;

bool open[][];

long long p[][];

long long cal(int x)

{

    long long ret=;

    for(int i=;i<=n;i++)

    {

        int sum=;

        for(int j=;j<=;j++)

            if(open[i][j] && (x&(<<j))) sum++;

        ret+=p[i][sum];

    }

    return ret;

}

int main()

{

    cin >> n;

    for(int i=;i<=n;i++)

        for(int j=;j<=;j++)

            cin >> open[i][j];

    for(int i=;i<=n;i++)

        for(int j=;j<=;j++)

            cin >> p[i][j];

    long long res=-(<<);

    for(int i=;i<=;i++)

    {

        long long temp=cal(i);

        res=max(res,temp);

    }

    cout << res;

    return ;

}

D:Recording

题意：在m个频道中有n个节目需要录制，如第i个节目在start time i~end time i(not included)播放，则在start time i-0.5~end time i(not included)这个时间段中同一台录制机不能在其他频道中进行录制，问至少要多少个录制机？

思路很明显，判断哪个时间点上同时出现的节目最多即可

当时连频道这个数据都没管，直接树状数组对所有时间维护一下，最后选择和最大的时间点即可，结果WA了5发

这道题中有一个题意理解很重要，题中说 [s-0.5,e) 是不能在其他频道中录制。我当时把所有节目都按[s,e]处理了，但事实上题目中暗示如果两个节目属于同一频道，可以连续录制，就没有-0.5这个制约了......（比赛中其实发了clarification,但日文怎么看╮(╯▽╰)╭）

此题除了读题不够细致之外，一开始我有一个很大的问题就是没把频道m这个条件放在心上

在很多时候数据本身及其范围就可以带来很多提示，并从而想到更简便的做法

如果这题使用树状数组，为了对在同一频道中首尾相连的节目特殊处理还需要进行排序，原本的效率优势就没有了

而如果很好的使用了m<30这个条件，可以一个频道一个频道地处理，用差分前缀和优化即可，思路明显清晰

PS：这题中有一个-0.5的操作，本题可以直接在整数上处理，但在其他情况中遇到-0.5时，可将整个数组放大2倍，由s-0.5 ---> 2*s-1

#include <bits/stdc++.h>

using namespace std;

const int MAXN=;

int n,m,st[MAXN],et[MAXN],c[MAXN],pre[MAXN],res[MAXN];

int main()

{

    cin >> n >> m;

    for(int i=;i<=n;i++) cin >>st[i] >>et[i] >>c[i];

    for(int i=;i<=m;i++)

    {

        memset(pre,,sizeof(pre));

        for(int j=;j<=n;j++) if(c[j]==i) pre[st[j]]++,pre[et[j]+]--;

        for(int j=;j<MAXN;j++) pre[j]+=pre[j-]; //差分约束和操作

        for(int j=;j<MAXN;j++) if(pre[j]>) res[j]++; //因为i,j属于一个频道，所以只能算一次

    }

    int ans=;

    for(int i=;i<MAXN;i++) ans=max(ans,res[i]);

    cout << ans;

    return ;

}

Review:

这次面对4道水题处理的不够好，注意点：

1.在最值很大时一定要特殊考虑，不能盲目使用平时的初始化值

2.读题时要对目标对象的限制语好好揣膜摩

3.要利用好每一个数据和范围，尽量不忽略

4.在复杂度允许O（n）操作时，在处理区间和问题时可不用树状数组，而直接使用差分前缀和

巴特西

[Atcoder 080] A~D Tutorial

最新文章

热门文章