[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 0;
}

B:Harshad Number

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;cin >> n;
    int temp=n,sum=0;
    while(temp) sum+=(temp%10),temp/=10;
    if(n%sum==0) cout << "Yes";
    else cout << "No";
    return 0;
}

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[105][15];
long long p[105][15];

long long cal(int x)
{
    long long ret=0;
    for(int i=1;i<=n;i++)
    {
        int sum=0;
        for(int j=0;j<=9;j++)
            if(open[i][j] && (x&(1<<j))) sum++;
        ret+=p[i][sum];
    }
    return ret;
}

int main()
{    
    cin >> n;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=9;j++)
            cin >> open[i][j];
    for(int i=1;i<=n;i++)
        for(int j=0;j<=10;j++)
            cin >> p[i][j];
    
    long long res=-(1<<30);
    for(int i=1;i<=1023;i++)
    {
        long long temp=cal(i);
        res=max(res,temp);
    }
    cout << res;
    return 0;
}

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=100001;
int n,m,st[MAXN],et[MAXN],c[MAXN],pre[MAXN],res[MAXN];

int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >>st[i] >>et[i] >>c[i];
    for(int i=1;i<=m;i++)
    {
        memset(pre,0,sizeof(pre));
        for(int j=1;j<=n;j++) if(c[j]==i) pre[st[j]]++,pre[et[j]+1]--;
        for(int j=1;j<MAXN;j++) pre[j]+=pre[j-1]; //差分约束和操作
        for(int j=1;j<MAXN;j++) if(pre[j]>0) res[j]++; //因为i,j属于一个频道，所以只能算一次 
    }
    
    int ans=0;
    for(int i=1;i<MAXN;i++) ans=max(ans,res[i]);
    cout << ans;
    return 0;
}

Review:

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

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

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

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

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