[Codeforces Round #841]

Codeforces Round #841 (Div. 2) and Divide by Zero 2022

Joey Takes Mone

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;
}

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;
}

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;
}

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;
}