[Codeforces Round #841]
Codeforces Round #841 (Div. 2) and Divide by Zero 2022
A. Joey Takes Money
Problem：
给一个正整数序列 \(a_1,a_2,…,a_n (n≥2)\) ，能进行任意次操作，操作是：找到 \(x\) 和 \(y\) 使得 \(x⋅y=a_i⋅a_j\) ，分别用 \(x\) 和 \(y\) 替换 \(a_i\) 和 \(a_j\) ，求操作过后最大的序列和
Solution：
贪心，对于两个正整数：
\(a*b + 1-(a+b) = (a-1)(b-1) \ge 0\) 恒成立
所以将两数相乘并取 \(a*b\) 和 \(1\) 一定会使贡献增加
而两个乘的数越大，越能使贡献增加
所以贪心策略是把最大的数和其他所有的数乘，最后别忘了加上\(n-1\) 个 \(1\)
Code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
int x = 0,f = 1;char ch = getchar();
while(ch < '0'||ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0'&&ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x*f;
}
int a[60];
signed main()
{
int t = read();
while(t--)
{
int n = read();
for(int i = 1;i <= n;i++) a[i] = read();
sort(a+1,a+n+1);
int ans = a[n];
for(int i = n - 1;i >= 1;i--)
{
ans*=a[i];
}
ans+=n-1;
cout<<ans*2022<<endl;
}
return 0;
}
B. Kill Demodogs
Problem：
给一个 \(n \times n\) 的方格 ，第 \(i\) 行第 \(j\) 列的数值是 \(x⋅y\)
从 \((1,1)\) 走到 \((n,n)\) ，只能向下或向右走，求操作过后最大的序列和
Solution：
首先，可以看出这个方格是一个对称矩阵
其次，通过目测可以看出一直贴着主对角线走贡献最大
答案就是$ ∑i^2 + ∑i(i-1)$
$ ∑i^2 = n(n+1)(2n+1)/6$
\(∑i(i-1) = ∑i^2 -∑i = n(n+1)(2n+1)/6 -n(n+1)/2\)
把二者加起来，\(O(1)\) 输出
Code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9+7;
int read()
{
int x = 0,f = 1;char ch = getchar();
while(ch < '0'||ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0'&&ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x*f;
}
signed main()
{
int t = read();
while(t--)
{
int n = read();
int ans = ((337*n%mod)*(n+1)%mod)*(4*n%mod-1+mod)%mod;
cout<<ans%mod<<endl;
}
return 0;
}
C. Even Subarrays
Problem：
给一个正整数序列 \(a_1,a_2,…,a_n (1≤a_i≤n)\) 找到 \((i,j)\) 使得 $ a_i⊕a_{i+1}+⋯⊕a_j$ 有偶数个因数
完全平方数有奇数个因数，特别的，0被认为有奇数个因数
多组数据，\(1≤t≤10^4\) , \(2≤n≤2⋅10^5\)
Solution：
首先要熟悉异或前缀和的概念，求出前缀和后
$ a_i⊕a_{i+1}+⋯⊕a_j$ 即为 $ sum_{i-1} ⊕sum_j$
枚举序列，对于当前数 \(i\) ，考虑从前面的前缀和中找到位置\(x (x < i)\) 使得 $ sum_{x} ⊕sum_i = k$ ，k不为完全平方数
那么其实就是找前面有没有异或前缀和为 \(sum_{y}⊕k\) ，考虑开一个桶记录数量
考虑时间复杂度，枚举 $ k$ 为 \(O(n^2)\) ，可以枚举完全平方数，最后用总子序列数减去，时间复杂度 \(O(n\sqrt{n})\)
注意细节：前缀和为0的数量初始值为1，序列中两个数异或后理论最大值是\(2n\)，枚举 \(k\) 时要考虑到
Code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9+7;
int read()
{
int x = 0,f = 1;char ch = getchar();
while(ch < '0'||ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0'&&ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x*f;
}
int a[200010];
int sum[200010];
int cnt[1000010];
signed main()
{
int t = read();
while(t--)
{
int n = read();
for(int i = 1;i <= n;i++) a[i] = read();
int ans = 0;
cnt[0] = 1;//注意
for(int j = 1;j <= n;j++)
{
sum[j] = sum[j-1]^a[j];
for(int i = 0;i*i<=2*n;i++)//2*n注意
{
ans += cnt[sum[j]^(i*i)];
}
cnt[sum[j]]++;
}
cout<<(n+1)*n/2-ans<<endl;
for(int i = 1;i <= n;i++) cnt[sum[i]] = 0,sum[i] = 0,a[i] = 0;
}
return 0;
}
D. Valiant's New Map
Problem：
给一个 \(n \times m\) 的方格，每个方格上有数\(a_{i,j}\)
找到一个数 \(l\) 使得 方格中存在一个 \(l \times l\) 的正方形，其中所有的数都大于等于\(l\)，求\(l\)最大值
多组数据，\(1≤t≤1000\) , \(1≤n⋅m≤10^6\)
Solution：
比较裸的二分题：
主要有两个细节
一是给的范围是 \(1≤n⋅m≤10^6\) 存数要二维转一维
二是怎么较好的判断，这里的方法是运用二维前缀和，把\(a_{i,j} \ge l\)的赋值为1，否则为0，直接判断正方形中数据和是否为 \(l \times l\)
Code:
#include <bits/stdc++.h>
using namespace std;
int read()
{
int x = 0,f = 1;char ch = getchar();
while(ch < '0'||ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0'&&ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x*f;
}
int dp[1000010],a[1000010];
int n,m;
int tr(int x,int y)
{
return (x-1)*m+y;
}
bool check(int k)
{
for(int i = 1;i <= n*m;i++) dp[i] = a[i] >= k?1:0;
for(int i = 1;i <= n*m;i++)
{
int x = (i-1)/m + 1,y = (i-1)%m + 1;
dp[i] = dp[i] + dp[tr(x-1,y)] + dp[tr(x,y-1)] - dp[tr(x-1,y-1)];
}
for(int i = tr(k,k);i <= n*m;i++)
{
int x = (i-1)/m + 1,y = (i-1)%m + 1;
if(x < k||y < k) continue;
int ans = dp[i] - dp[tr(x-k,y)] - dp[tr(x,y-k)] + dp[tr(x-k,y-k)];
if(ans == k*k) return true;
else continue;
}
return false;
}
int main()
{
int T = read();
while(T--)
{
n = read(),m = read();
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
a[tr(i,j)] = read();
}
}
int l = 1,r = min(n,m);
int ans = l;
while(l <= r)
{
int mid = l + r>>1;
if(check(mid))
{
ans = mid;
l = mid+1;
}
else r = mid-1;
}
cout<<ans<<endl;
}
return 0;
}