做题笔记 III

sunkuangzheng / 2024-02-20 / 原文

$1 \sim 100$ 的题目在做题笔记 II。

$\texttt{Le0**an}$：我写了四篇做题笔记、一篇生成函数详解和一篇模拟赛复盘了！

$\texttt{xl****13}$：我写了零篇做题笔记了！！！111

$101 \sim 125$

$\color{blue}(101)$ ARC172E Last 9 Digits

难度 $^*2400$。数论

抽象题。

有一个结论，对于 $k \ge 2$，若 $x \bmod 2 \ne0 $ 且 $x \bmod 5 \ne 0$ 则 $n^n \equiv x \pmod {10^k}$ 一定有唯一解。可以考虑打表验证。

考虑如果 $n^n \equiv x \pmod {10^k}$，则一定 $n^n \equiv x \pmod {10^{k-1}}$。那么我们从 $k=2$ 开始，先暴力枚举找到 $n^n \equiv x \pmod {10^{2}}$ 的 $n$，然后考虑 $n,n+10^k,n+2\cdot 10^k,\ldots,n+9\cdot10^k$ 一定是 $n^n \equiv x \pmod {10^{k+1}}$ 的所有可能解，暴力检验即可。时间复杂度 $\mathcal O(\log^2 x)$，带 $10$ 倍常数。

代码

/**
*    author: sunkuangzheng
*    created: 20.02.2024 09:42:18
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5e5+5;
using namespace std;
int T,n,x,pw[11],d;
int qp(int a,int b,int mod){
    int r = 1;
    for(;b;b >>= 1,a = 1ll * a * a % mod) if(b & 1) r = 1ll * r * a % mod;
    return r;
}void los(){
    cin >> x; int ans = -1;
    for(int i = 0;i <= 99;i ++) if(qp(i,i,100) == x % 100) ans = i;
    for(int i = 3;i <= 9;i ++)
        for(int j = 0;j < 10;j ++)
            if(d = ans + j * pw[i - 1],qp(d,d,pw[i]) == x % pw[i]) ans = d;
    cout << ans << "\n";
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    pw[0] = 1;
    for(int i = 1;i <= 9;i ++) pw[i] = pw[i - 1] * 10;
    for(cin >> T;T --;) los();
}

$\color{blue}(102)$ ABC313G Redistribution of Piles

难度 $^*2800$。数学

首先先进行一次 $2$ 操作再进行 $1$ 操作没有意义，我们的操作序列形如 $11\ldots 122\ldots 2$。

考虑对 $a$ 升序排序，如果当前所有数字都大于 $0$，那你先进行一次 $1$ 再进行一次 $2$ 也没有意义。设当前 $a_{i-1}$ 已经等于 $0$，则背包里有 $s = a_{i-1}(n-i+1)+\sum \limits_{j=1}^{i-1} a_j$ 个数字。设对 $a_i$ 操作 $k$ 次，则和会增加 $k(n-i+1)$，容易发现这些操作后序列互不相同。也就是说，我们会得到 $\sum \limits_{k=1}^{a_i-a_{i-1}} \lfloor\dfrac{s+k(n-i+1)}{n} \rfloor$，可以用 atcoder::floor_sum 求解。时间复杂度 $\mathcal O(n \log m)$。有一些实现细节。

代码

/**
*    author: sunkuangzheng
*    created: 20.02.2024 10:54:20
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5e5+5,mod = 998244353;
using namespace std;
#include <atcoder/all>
using Z = atcoder::modint998244353;
int T,n,a[N];
void los(){
    cin >> n; Z ans = 0; ll sum = 0;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    sort(a+1,a+n+1); ans = a[1] + 1;
    for(int i = 1;i < n;i ++)
        sum += a[i],
        ans += atcoder::floor_sum(a[i + 1] - a[i] + 1,n,n - i,sum + 1ll * a[i] * (n - i)),
        ans -= atcoder::floor_sum(1,n,n - i,sum + 1ll * a[i] * (n - i)),
        ans += a[i + 1] - a[i];
    cout << ans.val();
}signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(T = 1;T --;) los();
}

$\color{blue}(103)$ AT_toyota2023spring_final_c Count Dividing XOR

难度 $^*2100$。暴力；数学

容易发现 $a \oplus b \ge b - a,a \oplus b | b - a$，也即 $a \oplus b = b - a$。又因为 $a \oplus b | a,a \oplus b | b$，那么枚举 $b - a$，$a,b$ 都是 $b -a$ 的倍数，由调和级数，$a$ 的数量是 $\mathcal O(n \log n)$ 级别的，可以通过。

代码

/**
*    author: sunkuangzheng
*    created: 20.02.2024 14:39:34
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5e5+5;
using namespace std;
ll l,r,T;
void los(){
    cin >> l >> r; ll ans = 0;
    for(int i = 1;i <= r - l + 1;i ++)
        for(ll j = 1ll * (l + i - 1) / i * i + i;j <= r;j += i)
            ans += (j ^ (j - i)) == i;
    cout << ans;
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(T = 1;T --;) los();
}

$\color{blue}(104)$ CF1007C Guess two numbers

难度 $^*2900$。构造；交互；倍增

很厉害的倍增。容易发现若答案是 $(a,b)$，你询问了 $(x,y)$，如果得到 $1$ 说明 $a > x$，得到 $2$ 说明 $b > y$，将点放在平面上，可以看作得到 $1,2$ 可以排除一个矩形。

问题是得到 $3$ 我们只能排除右上角，会得到 L 形。我们考虑倍增。设当前位置为 $(p,q)$，偏移量为 $(x,y)(x,y \ge 1)$，每次如果得到 $1,2$ 则对应维度加倍，否则两维减半。这样的倍增在遇到 $3$ 时很容易回退。显然这样的询问次数是 $\mathcal O(\log n)$ 级别，虽然常数较大但是不会超过 $8$ 倍。

代码

/**
*    author: sunkuangzheng
*    created: 20.02.2024 15:46:12
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5e5+5;
using namespace std;
ll T,n,x = 1,y = 1,p,q,fk;
void los(){
    for(cin >> n;;){
        cout << p + x << " " << q + y << endl,cin >> fk;
        if(!fk) return ;
        if(fk == 1) p += x,x = min(x * 2,n - p);
        if(fk == 2) q += y,y = min(y * 2,n - q);
        if(fk == 3) x /= 2,y /= 2,x = max(x,1ll),y = max(y,1ll);
    }
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(T = 1;T --;) los();
}

$\color{blue}(105)$ CF949E Binary Cards

难度 $^*2600$。搜索

观察一些基本性质。

性质一：我们不会同时选 $k,k$ 或者 $k,-k$。
对于第一种情况，选择 $k,2k$ 更优；对于第二种情况，选择 $2k,-k$ 更优。

从小到大枚举 $k$，那么我们考虑到 $2^k$ 时所有数字都是 $2^{k}$ 的倍数。如果它不是 $2^{k+1}$ 的倍数，我们就要进行操作。注意到操作完后所有数字都是 $2^{k+1}$ 的倍数，那么全都除 $2$ 后去重，数组规模减半，递归处理。由于只会递归 $\log$ 层，去重后每一层的所有元素数量和是 $\mathcal O(a_i)$ 级别，总复杂度 $\mathcal O(a_i \log a_i)$。

代码

/**
*    author: sunkuangzheng
*    created: 20.02.2024 16:24:08
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5e5+5;
using namespace std;
int T,n; vector<int> a,ans,res;
void dfs(vector<int> a,int d){
    sort(a.begin(),a.end()),a.erase(unique(a.begin(),a.end()),a.end());
    if(a.size() == 1 && !a[0]){
        if(res.size() > ans.size()) res = ans;
        return;
    }int fg = 0;
    if(d > 20) return ;
    for(int i : a) if(i % 2) fg = 1;
    if(!fg){for(int &i : a) i /= 2; dfs(a,d + 1);}
    else{
        vector<int> b = a;
        for(int &i : a) i = (i + abs(i % 2)) >> 1; 
        ans.push_back(-(1 << d)),dfs(a,d + 1);
        ans.pop_back(),ans.push_back((1 << d));
        for(int &i : b) i = (i - abs(i % 2)) >> 1; dfs(b,d + 1);
        ans.pop_back();
    } 
}
void los(){
    for(int i = 1;i <= 30;i ++) res.push_back(i);
    cin >> n; a.resize(n);for(int &i : a) cin >> i; dfs(a,0);
    cout << res.size() << "\n";
    for(int i : res) cout << i << " ";
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(T = 1;T --;) los();
}