挖土机周赛 Round 35（语法场）题解

三次方或三的幂

显然只有当 $n=3$ 时 $3^n=n^3$，其他时候都有 $3^n>n^3$

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    if (n == 3)
        cout << "No";
    else
        cout << "Yes";
    return 0;
}

几个子区间合法

首先区间的端点必然在 $1\sim n$，直接双重循环枚举所有起点终点，然后等差数列求和来计算的话，显然只能拿到 $90$ 分。

满分做法的话有很多，可以直接枚举所有起点，然后用二分或者数学方法找终点。

实际上直接暴力从前往后枚举终点，如果和超过 $n$ 就停也是能满分的，这个做法时间复杂度不太好算，可以简单估算一下上限。起点为 $i$ 时，不可能超过 $\frac{n}{i} 项，所以时间复杂度显然小于 $n+\frac{n}{2}+\frac{n}{3}+\cdots +\frac{n}{n}$。即小于 $n\log n$。数学好一点容易直到实际上项数少得多，这里就不展开推了。

二分做法

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    int n, cnt;
    cin >> n;
    cnt = 0;
    for (int i = 0; i <= n; i++)
    {
        int l = i;
        int r = n;
        int j = n;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if ((i + mid) * (mid - i + 1) >= 2 * n)
            {
                j = mid;
                r = mid - 1;
            }
            else
                l = mid + 1;
        }
        if ((i + j) * (j - i + 1) == 2 * n)
            cnt++;
    }
    cout << cnt;
    return 0;
}

枚举做法

// 代码来自 jonnyyuan
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int ans=0;
signed main(){
    cin>>n;
    for(int i=0;i<=n;i++){
        int now=i;
        int sum=0;
        while(true){
            sum+=now;
            now++;
            if(sum==n){
                ans++;
                break;
            }
            if(sum>n){
                break;
            }
        }
    }
    cout<<ans;
}

字符串有几个洞

其实唯一麻烦点是数清楚每个字符几个洞。

#include <bits/stdc++.h>
using namespace std;
int num[256];
string t1 = "ADOPQRabdeopq469";
string t2 = "Bg08";
int main()
{
    string s;
    cin >> s;
    for (int i = 0; i < 256; i++)
        num[i] = 0;
    for (int i = 0; i < t1.size(); i++)
        num[t1[i]] = 1;
    for (int i = 0; i < t2.size(); i++)
        num[t2[i]] = 2;
    int ans = 0;
    for (int i = 0; i < s.size(); i++)
        ans += num[s[i]];
    cout << ans;
    return 0;
}

切了又切的纸牌

本来想要求翻转后放到末尾的，但是似乎有点过难了，所以就改成直接放到末尾了，但现在就太简单了。

实际上不管做多少次，整个序列一定是环状意义上连续的，所以直接算出一共往后面放了 $a\ast b$ 个数，那就直到最终序列的起点了。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n, a, b;
    cin >> n >> a >> b;
    long long pos = a * b % n + 1;
    for (int i = pos; i <= n; i++)
        cout << i << " ";
    for (int i = 1; i <= pos - 1; i++)
        cout << i << " ";
    return 0;
}