NOI2023春季测试

P9118 幂次

题目传送门

10pts代码

题解：

(摘自洛谷大佬永远的幻想乡)

我们令 $f(i)$ 表示 $x=a^i(x\le N,x_i\not=x_j)$ 的个数。

令 $g(i)$ 表示 $x=a^i(x\le N)$ 的个数。 很容易得到 $g(i)=f(i)+f(2i)+\cdots+f(ki),(ki\le 100)$。

易知 $g(i)=\sqrt[i]n$。

所以 $f(i)=g(i)-f(2i)-f(3i)-\cdots-f(ki)$。

从前往后推，容斥即可，时间复杂度 $O(k\log k)$。

code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll Maxn=110;
ll f[Maxn],n,k,ans=1;
int main(){
    scanf("%lld%lld",&n,&k);
    for(ll i=100;i>=k;i--){
        f[i]=pow<long double>(n,1.0/i)-1;
        for(ll j=i<<1;j<=100;j+=i) f[i]-=f[j];
        ans+=f[i];
    }
    printf("%lld",ans);
    return 0;
} 

补充知识：组合数学 —— 容斥定理

P9117 涂色游戏

题目传送门

10pts代码

题解：

(摘自洛谷大佬andyli)

对于每行和每列，分别记录这一整行/列上一次被修改为的值以及修改的时间。最终对于每个数，它对应行和对应列中修改时间靠后的那一行/列的值便是他的值。

int main() {
    multipleTests([&]() {
        dR(int, n, m, q);
        std::vector<int> a(n), b(m), t0(n), t1(m);
        for (int i = 1; i <= q; i++) {
            dR(int, op, x, c), x--;
            if (op == 0)
                a[x] = c, t0[x] = i; // 修改这行的值及时间戳
            else
                b[x] = c, t1[x] = i; // 修改这列的值及时间戳
        }
        for (int i = 0; i < n; i++, writeln())
            for (int j = 0; j < m; j++)
                if (t0[i] > t1[j]) // 比较修改时间
                    io.write(a[i], ' ');
                else
                    io.write(b[j], ' ');
    });
    return 0;
}

你也可以只用两个 unsigned long long 数组，前半部分存时间，后半部分存值，输出时强制转换成 unsigned 可以取值，比较大小可以直接比较。

加上一些快读和快写优化跑到了最优解（官方数据 207ms）。

int main() {
    dR(unsigned, t);
    while (t--) {
        dR(unsigned, n, m, q);
        std::vector<u64> a(n), b(m);
        for (unsigned i = 1; i <= q; i++) {
            dR(unsigned, op, x, c), x--;
            if (op == 0)
                a[x] = (u64(i) << 32) + c;
            else
                b[x] = (u64(i) << 32) + c;
        }
        for (unsigned i = 0; i < n; i++, writeln())
            for (unsigned j = 0; j < m; j++)
                if (a[i] > b[j])
                    io.write(unsigned(a[i]), ' ');
                else
                    io.write(unsigned(b[j]), ' ');
    }
    return 0;
}