A - Exponential or Quadratic Editorial

解题思路

由数学归纳法可以证明当n >= 5时一定有$2n > n2$
而n小于5时,只有当n = 3时才有$2n > n2$

代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n; cin >> n;
	if(2 <= n && n <= 4) cout << "No" << endl;
	else cout << "Yes" << endl;
}

B - Pizza

题目大意

一个披萨,在上面切上n刀,每切一次将披萨顺时针旋转$A_i$度
切完后找出最大的那块披萨(即圆心角最大),输出最大的圆心角

解题思路

本题采用逆向思维,题目中是将pizza顺时针旋转,其实就相当于将刀逆时针旋转

对于第1刀,刀沿逆时针旋转过的角度为0,  
对于第2刀,刀沿逆时针旋转过的总角度为a[1];  
对于第3刀,刀沿逆时针旋转过的总角度为(a[1] + a[2]) % 360;  
对于第4刀,刀沿逆时针旋转过的总角度为(a[1] + a[2] + a[3]) % 360;  

我们假设第1,2,3刀总角度分别为0,120,180..
则第1个圆心角为120-0=120,第1个圆心角为180-120=60..

TIPS:360在圆中等同于0, 而本题第一刀永远为0,所以对于输入处理后从0开始%360循环找出最大圆心角

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 360;

int n, p, x;
bool st[N];  // 表示此处是否被切过

int main()
{
    cin >> n;

    st[0] = true;  // 第1刀永远为0,标记为切过
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        p += x, p %= 360;  // 在之前的位置x的基础上接着逆时针旋转;
        st[p] = true;
    }
    
    int res = 0, cur = 0;
    for (int i = 0; i <= 360; i++)  // 从0遍历到360即可,因为圆只有360
    {
        if (st[i % 360]) res = max(res, cur), cur = 0;  // 如果找到被切过的位置,比较大小
        cur++;  // 可以理解为每次走过1度
    }

    cout << res << endl;
    return 0;
}

C - digitnum

题目描述

avatar
$f(x)$的意思是跟x的位数相同且不大于x的数字个数(不含0)

解题思路

打表发现规律

f(1) = 1, f(2) = 2, f(3) = 3 ······ f(9) = 9,
f(10) = 1, f(11) = 2, f(12) = 3 ······ f(99) = 90,
f(100) = 1, f(101) = 2, f(102) = 3 ······ f(999) = 900,

我们可以发现,位数相同的数是1,2,3···9这样连续的排序下去
于是我们可以对N进行不同位数的分别求和,然后相加
假设N是四位数,x是三位数时,可以直接用900*(900+1)/2求出所有三位数的f(x)值
而当x是四位数时,就得用n-1000+1得出项数,n-1000+1+1得出首末之和

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;

ll n, ans;

int main()
{
    cin >> n;
    ll x = n, t = 0, len = 0;  // t用来表示跟N相同位数的最小数,比如N是2022的话,t就是1000
    while (n) {len++,n /= 10,t = t == 0 ? t = 1 : t *= 10;}  // 求出数字位数

    if (len == 1) 
        for (int i = 1; i <= x; i++)    ans += i;
    else 
    {
        ll num = 9;  // 表示项数
        for (int i = 1; i < len; i++)  // 枚举最后一位之前
        {
            ans = (ans + (num * (num + 1)) / 2 % mod) % mod;  // num + 1是首项+末项
            num = num * 10 % mod;
        }

        // 最后一位需要特殊处理
        num = (x - t + 1) % mod;  // 通过这一步可以得到长度为N.size()时的项数(最后)
        ans = (ans + (num * (num + 1)) / 2 % mod) % mod;
    }
    cout << ans;
    return 0;
}

D - AND and SUM

题目描述

avatar

解题思路

$\because x & y= a$
$\therefore x \geq a且y \geq 等价于x + y \geq 2a$
又$\because x + y = s$
$\therefore 符合条件之一是s \geq2a$
假设$A$集合中存放$x,y$上都是1的位置,则有$x_a = a$
假设$B$集合中存放$x,y$上其中一个是1的位置(即不全为1),则$B = s - 2a$
TIPS:显然$A \cap B = \varnothing$
因此$(s - 2a) & a = 0$是符合条件之二

举例证明
CASE:$59 = (111011)_2$, $53 = (110101)_2$
则$59 & 53 = (110001)_2 = 49 = a$
而$59 + 53 = 112 = s$
$s - 2a = 14 = (001110)_2$
$s - 2a & a = (001110)_2 & (110001)_2 = 0$
得证!

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll T, a, s;

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> a >> s;
        if (s - 2 * a >= 0)
        {
            ll t = s - 2 * a;
            if ((t & a) == 0)
            {
                puts("Yes");
                continue;
            }
        }
        puts("No");
    }
    return 0;
}

E - Range Sums

题目描述

avatar
翻译:给定$N$个区间的区间和,最后是否能够得出$a_1+a_1+···a_n$的值?

解题思路

对于给出的一组区间[l,r]表示为$a_l+a_{l+1}+ ··· +a_r$,可以转换为前缀和$b_r-b_$
举例:第一次给出[3,6]即$a_1+a_2+a_3$的值,我们可以将它转换为前缀和$b_6-b_2$

本题我们可以采用并查集来做,首先将所有的端点放入各自的集合
而对于每一个给出的区间,我们只需要将它的(右端点)和(左端点-1)合并,
如果最后查找$n$和$0$在一个集合内,说明可以求出$a_1+a_1+···a_n$

问:为什么最后是判断$n$和$0$?

因为[1,n]的前缀和为b[n]-b[1-1]= b[n]-b[0],并查集中存的是前缀和区间

问:为什么可以用并查集做?

因为对于每个给出的区间,其实是给出了某段区间的左右端点,而一开始每个点都是零散的集合
用并查集的目的就是把某些端点连接起来,使得最后0和n两个端点能够连接,即在一个集合内

问:如果给出n = 4, m = 2, c = {[1,3], [2,4]} 这一组数据,能否输出“Yes”?

不能,因为给出这两个区间只能算出[1,3],[2,4]两个区间和,不管两个区间和如何加减乘除都算不出[1,4];
要算出[1,4]需要额外的区间信息如[3,4]或[1,2]或{[1,1],[2,2]}或{[3,3],[4,4]等};

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;

int n, m, l, r;
int fa[N];

int find(int x)
{
    if (x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}

int main() 
{
    cin >> n >> m;
    for (int i = 0; i < N; i++) fa[i] = i;  // 初始化

    while (m--)
    {
        cin >> l >> r;
        fa[find(l - 1)] = find(r); 
    }

    if (find(0) == find(n)) puts("Yes");
    else puts("No");
    return 0;
}

上一篇 下一篇