CodeForces_R919 + 牛客练习赛120混合题解
这是1月12~1月13日期间的两场比赛，题目考察数学方向和思维方向的知识会多一点，这篇文章混合选取了部分题目并给出了题解，题目顺序由个人认为的难度由低到高给出。
【题目1】（牛客练习赛120_B生成函数，数学）
【题意】有三种数量无限的砝码和一个天平，天平的一端有一个质量为 m 的物品，问能否通过放置砝码使得天平平衡？
【思路】本题属于裴蜀定理的扩展，类似于：LG4549、CF510D
裴蜀定理：（摘自OI-Wiki）
有了这些前置知识以后，我们只需要关注m是否能被a,b,c的最大公因数整除即可，值得留意， 头文件<algorithm>里面是自带__gcd的。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b,c,m;
signed main(){
int ttt; cin >> ttt;
while(ttt--){
cin >> a >> b >> c >> m;
int gcd = a;
gcd = __gcd(gcd, b), gcd = __gcd(gcd, c);
if(m % gcd) puts("NO");
else puts("YES");
}
return 0;
}
【题目2】（Codeforces Round 919(Div. 2) Partitioning the Array，数学）
【英文题面】
【题意】给定长为 n 的序列 a ，对于 n 的所有因数，我们可以把序列a分成如下的 n/k 个子序列：
如果能找到一个大于等于2的正整数 m 使得这 n/k 个子序列对m取模后完全相同，则答案+1。
【思路】依题，
#include <bits/stdc++.h>
using namespace std;
const int N(2e5+5);
int a[N];
inline void sol(){
int n, ans = 0; cin >> n;
for(int i=0;i<n;i++) cin >> a[i];
for(int k=1;k<=n;k++)
if (n % k == 0){
int gcd = 0;
for (int i=0;i+k<n;i++) gcd = __gcd(gcd, abs(a[i+k]-a[i]));
ans += (gcd!=1);
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int ttt; cin >> ttt;
while(ttt--) sol();
return 0;
}
【题目3】（牛客练习赛120_C选择交换，思维）
【题意】给定一个数列a，问经过数次交换以后能否让数列满足下式要求：
能的话输出YES并输出这数次交换的操作元素下标，不能的话输出NO。
【思路】显然，上式最终等于
#include <bits/stdc++.h>
#define pii pair<int,int>
#define endl '\n'
using namespace std;
template <class T>
inline void read(T &x){ x=0; char c = getchar(); bool f=0; for(;!isdigit(c);c=getchar()) f^= (c=='-'); for(;isdigit(c);c=getchar()) x=(x<<3) + (x<<1) + (c^48); x=f?-x:x;}
const int N(2e5+5);
struct node{
int v,idx;
bool operator<(const node& kkk) const {return v < kkk.v;}
}a[N],b[N];
int n;
void sol(){
vector<pii> res; read(n);
for(int i=1;i<=n;i++) read(a[i].v), a[i].idx=i, b[i]=a[i];
sort(b+1,b+1+n);
int sum=b[1].v+b[n].v;
for (int i=1;i<=(n+1)/2;i++)
if (b[i].v+b[n-i+1].v!=sum){ cout << "NO" << endl; return; }
for(int i=1;i<=n;i++) a[b[i].idx].idx = i;
for(int i=1;i<=n;i++)
while(a[i].idx!=i)
res.push_back({i,a[i].idx}), swap(a[i], a[a[i].idx]);
cout << "YES" << endl;
cout << (int)res.size() << endl;
for(auto &x:res)
cout << x.first << " " << x.second << endl;
}
int main(){
int ttt; read(ttt);
while(ttt--) sol();
return 0;
}
【题目4】（牛客练习赛120_D数数大师，数学）
【题意】给定长为 n 的序列 a，可以多次对序列中的某元素进行 +1 操作，问至多操作 k 次后，序列中至多有多少个区间和为奇数的区间。
【思路】我们其实只关心序列的奇偶性，故我们可以讨论在模 2 意义下的前缀和序列sum，区间 (l , r) 的奇偶性为 sum[ l-1 ] ⊗ sum[ r ]，问题可以转化为尽可能让0和1的数量接近，而原题定义的操作相当于反转i以后的01串。而且可以发现至多操作1次就可以达到最优解，证明如下：
证明：假设sum序列的第 i 位以后 0 的个数为 (len-i)-m ， 1 的个数为 m ，第 i 位以前（含第 i 位）的 0 个数为 i-n ，1 的个数为 n 。
所以操作前sum序列 0 的总数 (Σ0) 为 len-m-n ，1 的总数 (Σ1) 为 m+n ，(delta) = | len-2m-2n |。
操作一次后，第 i 位以后 0 的个数为 m ， 1 的个数为 (len-i)-m ，此时 (Σ'0) = i-n+m ，(Σ'1) = len-i-m+n，(delta)' = | 2i-2n+2m-len |，显然 (delta)' 是关于i线性的，故至多操作1次就可以达到最优解。
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
template <class T>
inline void read(T &x){ x=0; char c = getchar(); bool f=0; for(;!isdigit(c);c=getchar()) f^= (c=='-'); for(;isdigit(c);c=getchar()) x=(x<<3) + (x<<1) + (c^48); x=f?-x:x;}
using namespace std;
const int N(2e5+5);
int a[N],sum[N];
void sol(){
int cnt=0,n,k;
read(n), read(k);
memset(sum,0,sizeof sum);
for(int i=1;i<=n;i++){
read(a[i]), a[i]&=1;
sum[i]=sum[i-1]^a[i];
cnt+=sum[i];
}
if(k) cnt=(n+1)/2;
cout << cnt*(n-cnt+1) << endl;
}
signed main(){
int ttt; read(ttt);
while(ttt--) sol();
return 0;
}
【题目5】（Codeforces Round 919(Div. 2) Array Repetition，数学）
【英文题面】
【题意】初始有一个空序列，有m次操作,每次给出一种操作：
1.在序列末尾添加一个数x；
2.将原序列复制c次插入到序列末尾。
每次询问为操作完的序列的第k个元素。
【思路】（来源于官方题解）首先，我们预计算lst和dp，其中lst数组是执行前i次操作后的最后一个元素，dp数组是执行前i次操作后的元素总数。显然，如果dp=k，则答案是lst。否则，我们就要求第一个i使得dpi>k。这将成为一个重复计算，而最后的答案就在其中一个重复计算中。此时，序列可以划分为这样：
设第k个元素为上图中的 l_2 ，该元素等价于(k % dp[i-1]) 个元素。
还有一道与此题极其类似的题可以拿来训练：CF380A
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
int n, q; cin >> n >> q;
ll dp[n + 1] = {};
int lstAdd[n + 1] = {};
vector<int> pos;
for (int i = 1, doAdd = true; i <= n; i++){
int a, v;
cin >> a >> v;
if (a == 1){
lstAdd[i] = v;
dp[i] = dp[i - 1] + 1;
}
else{
lstAdd[i] = lstAdd[i - 1];
dp[i] = ((v + 1) > 2e18 / dp[i - 1]) ? (ll)2e18 : dp[i - 1] * (v + 1);
if (doAdd)
pos.push_back(i);
}
// No need to consider any more repetitions after this point
if (dp[i] == 2e18) doAdd = false;
}
while (q--){
ll k; cin >> k;
for (int i = pos.size() - 1; ~i; i--){
int idx = pos[i];
if (dp[idx] > k and dp[idx - 1] < k){
if (k % dp[idx - 1] == 0){
k = dp[idx - 1];
break;
}
k %= dp[idx - 1];
}
}
cout<<lstAdd[lower_bound(dp + 1, dp + n + 1, k) - dp]<<" \n"[q == 0];
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int tc; cin >> tc;
while (tc--) solve();
}
