AtCoder Beginner Contest 258比赛总结

总结

虽然前几次也在打，但是这次重新开始做总结，这场赛中只做出两个题，有点不舒服加上开摆E就没做了，最后补出E和G（F有点难），G有一个bitset优化技巧
比赛链接：Tasks - AtCoder Beginner Contest 258

A.When?

简单不表
这里有一个输出时间的技巧：（例如输出22:03)

h = 22, m = 3;
cout<<hh<<":"<<m/10<<m%10<<endl;

这样就不用if判断或者fill什么操作了

B.Number Box

不表
这里也有技巧，就是表示上下左右以及四个对角线的方向如何表示？
我是写了8个for循环，然后用两个if判断x,y是否越界，很蠢...看jly代码——

for (int dx = -1; dx <= 1; dx++) {
    for (int dy = -1; dy <= 1; dy++) {
        if (dx == 0 && dy == 0) 
            continue;
        ...
    }
}

这样就能模拟出8个方向...也就是

C.Rotation

每次O(1)输出，只需要累加x即可，然后取模
代码:

inline void Case_Test()
{
    cin>>n>>m>>s;
    s = " "+s;
    while (m--)
    {
        cin>>op>>x;
        if (op==1)
            tag = (tag + x)%n;
        else
        {
            if (x>tag)
                cout<<s[x-tag]<<endl;     
            else
                cout<<s[n-tag+x]<<endl;
        }
    }
}

D.Trophy（思维）

题意

给你$n$关游戏，你需要通过关卡$x$次（不论第几关，一共$x$关即可）。每关第一次需要花费$a_i$时间看视频，然后花$b_i$时间通过，后面就不用看视频了，每次只需要花费$b_i$即可通过。问通关$x$需要最少花费多少时间？

思路

每次扫一遍，扫到第$i$关维护需要都通关一次需要$res$时间，不难看出$res = \sum_{k=1}^i(a_k+b_k)$。然后一路上维护最小$b_i$值，也就是说我通关$i$个关卡，还需要$x-i$关，都用这个最小$b_i$通过，每次对答案$ans$取最小值即可

代码

inline void Case_Test()
{
    cin>>n>>x;
    ans = 9223372036854775807;
    int pre = INF;
    int res = 0;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
        pre = Min(b[i],pre);
        res += a[i]+b[i];
        ans = Min(ans,res+(x-i)*pre);
    }
    cout<<ans;
}

E.Packing Potatoes（二分+思维+循环节）

题意

我有无限个土豆，有一个长度为$n$的重量为$w_i$序列无限循环着（在一个传送带上）,还有一个值$x$。每次在传送带上将当前土豆放入当前盒子中，如果重量大于等于$x$，那么就封装起来，重新拿出一个新盒子继续装。将有若干次询问，每次询问第$k$个盒子里面有多少个土豆。

思路

不难想到这个肯定会有循环节，那么我们需要去找循环节，找循环节的时候需要注意一个问题，开头的可能不是循环节：

例如：盒子是8,3,4,4,2,5,6,7,4,4,2,5,6,7,4...
那么前面8,3就不是循环节，（8,3,[4,4,2,5,6,7],[4,4,2,5,6,7,4]...）

然后怎么思考呢，我有$a_1,a_2,...,a_n$序列代表土豆重量，因为是循环的，会取完最后一个然后再回头取第一个，所以我需要扩展成两倍变成：$a_1,a_2,...,a_n,a_1,a_2,...,a_n$这样我可以越界去取。

再用前缀和优化，这样可以在$O(1)$的时间复杂度求出$[l,r]$内的土豆总重量。

    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=n+1;i<=2*n;i++) a[i] = a[i-n];
    for (int i=1;i<=2*n;i++)
        pre[i] = pre[i-1] + a[i];
    int sum = pre[n];

然后就去寻找循环节，不难想到，当空盒子第一个面临$x$号土豆再次出现的时候，就是循环节出现的时候，因为会跟第一次出现的情况一模一样。

一开始设置一个指针t=1指向当前进来的那个土豆，然后进入循环。每次对于$x$进行整除取模处理，因为$x$可能很大，我上面扩展的$2sum都不够

int t = 1;
    while (1)
    {
        int res = x % sum, g = x / sum;
        ...
}

这里判断一下，如果这时候res==0，就说明整除了，说明不用继续下去了，每次都是这个土豆开始，到它上一个土豆结束，然后又从这个土豆开始。

然后就是在整个a数组中判断大于$x$的时候是什么时候，这个时候因为是前缀和处理，所以lower_bound的时候需要判断的是res+pre[t-1]，而不是res（可以想一下为什么）。

那么个数就是num = pos-t+1 + g*n，包括当前余数需要的和整除需要的。

并且设置当前的t标志数组vis[t]=1，如果下次还是t开始的话可以break退出了。

我这里设置了一下下标，当前第cnt个盒子对应哪个土豆开始的（t），这样到时候找不在循环节内的就好找了，t也赋值为下一次位置t = pos % n + 1

最后循环出来之后可以用b数组找到哪个开始结束不在循环节内，最后每次读入的时候判断一下，如果不用取模直接输出就好。

代码

写的很乱，不过思考都写在上面了。

inline void Case_Test()
{
    cin>>n>>q>>x;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=n+1;i<=2*n;i++) a[i] = a[i-n];
    for (int i=1;i<=2*n;i++)
        pre[i] = pre[i-1] + a[i];
    int sum = pre[n];
    int t = 1;
    while (1)
    {
        int res = x % sum, g = x / sum;
        if (res == 0) 
        {
            pack[++cnt] = g*n;
            b[cnt] = t;
            break;
        }
        int pos = lower_bound(pre+1,pre+1+2*n,res+pre[t-1])-pre;
        int num = pos - t + 1;
        vis[t] = 1;
        pack[++cnt] = num + g*n;
        b[cnt] = t;
        t = pos % n + 1;
        if (vis[t]) break;
    }
    for (int i=1;i<=cnt;i++)
        if (b[i]==t) {t = i;break;}
    t--;
    int p = cnt - t;
    while (q--)
    {
        cin>>k;
        if (k<=cnt) cout<<pack[k]<<endl;
        else cout<<pack[(k-t-1)%p+t+1]<<endl;
    }
}

G-Triangle（bitset）

题意

给你一个$n\times n$的01矩阵，$a[i][j]=1$则表示在顶点$i$和顶点$j$之间有一条边。问你能否找到一个三元组$(i,j,k)$满足$1\leq i < j < k\leq n$满足$i$到$j$有一条边，$j$到$k$有一条边，$k$到$i$有一条边。

思路

先从暴力考虑，枚举$i,j$，且$a[i][j]=1$然后枚举$k$看有多少个$k$满足$a[i][k]=a[j][k]=1$。
发现这个东西就是集合$S_i$与$S_j$取交集之后的$1$的个数，也就是$|S_i \cap S_j|$，其中为了不重复，$S_i$表示满足$j>i,a[i][j]=1$的$j$集合，于是可以用bitset来优化。

代码

bitset<N> S[N];
inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        {
            cin>>c;
            a[i][j] = c-'0';
            if (j>i) S[i].set(j,c-'0');
        }
    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=n;j++)
            if (a[i][j])
                ans += (S[i]&S[j]).count();
    cout<<ans;
}