cf 940 div.2 5/7

比赛链接：Dashboard - Codeforces Round 940 (Div. 2) and CodeCraft-23 - Codeforces

A

题意：给出 $n$ 个整数，求最多能构造出的等边多边形数量。

构造三角形即可。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int check[500]={0};
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            check[x]++;
        }
        int ans=0;
        for(int i=1;i<500;i++)ans+=check[i]/3;
        cout<<ans<<endl;
    }
    return 0;
}

B

给定 $n,k$ ，需要构造一个长为 $n$ 的数组 $a$ 使得：

$\sum a_i=k$，$a_i\geq0$

$a_1|a_2|…|a_n$ 中的1的个数最大化。

使 $a_1$ 包含最多的1，其他的数再凑够 $k$ 。找 $a_1$ 即找最大的 $i$ 使得 $2^i-1\leq k$ 。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int t;
    cin>>t;
    set<int>q;
    for(int i=0;i<=32;i++)
    {
        q.insert(pow(2,i)-1);
    }
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        if(n==1)
        {
            cout<<k<<endl;
            continue;
        }
        int x=*(--q.upper_bound(k));
        cout<<x<<" ";
        for(int i=1;i<=n-2;i++)cout<<"0 ";
        if(x!=k)cout<<k-x;
        else cout<<0;
        cout<<endl;
    }
}

C

给出一个 $n*n(n\leq 3\times 10^5)$ 的棋盘，玩家与电脑下棋。玩家下在 $(r,c)$ 时，若 $r!=c$ ，则电脑下在 $(c,r)$ ；若 $r=c$ ，电脑跳过，继续由玩家下棋。要求是玩家下的每一步棋都需满足第 $r$ 行第 $c$ 列没有其他棋子。给出玩家下了 $k$ 步棋之后的局面，求下到不能下时可能的局面会有多少种情况。

首先简化目标：下了 $k$ 步棋后，设有 $x$ 步 $r=c$ ，那么相当于棋盘变成了一个 $(n-k\times2+x,n-k\times2+x)$ 的空白棋盘。

对于一个 $n’\times n’$ 的棋盘，设 $dp[i]$ 表示边长为 $i$ 的棋盘的下棋方案数，有：
$$
dp[i]=dp[i-1]+dp[i-2]\times (i-1)\times 2
$$

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int maxn=3e5+5;
int dp[maxn];

signed main()
{
    dp[0]=1;
    dp[1]=1;
    dp[2]=3;
    for(int i=3;i<=maxn;i++)
    {
        dp[i]=(dp[i-1]+2*dp[i-2]*(i-1)%mod)%mod;
    }

    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        int ans=n;
        for(int i=1;i<=k;i++)
        {
            int r,c;
            cin>>r>>c;
            if(r==c)ans--;
            else ans-=2;
        }
        cout<<dp[ans]<<endl;
    }
    return 0;
}

D

题意：给定一个长为 $n$ 的数组 $a$ ，求 $(x,y,z)$ 的组数，其中：

$1\leq x\leq y\leq z\leq n $

$f(x,y)\bigoplus f(y,z)>f(x,z)$

其中$f(l,r)=a_l\bigoplus a_{l+1}\bigoplus…\bigoplus a_r$

简化题意：找 $(x,y,z)$ 使得 $f(x,z)\bigoplus a_y>f(x,z)$ 。

可以观察到若 $f(x,z)$ 第 $p$ 位是0，且 $a_y$ 最高位为第 $p$ 位，那么这一组 $(x,y,z)$ 一定可行。因此用 $dp[i][p][0/1] $ 表示从前往后包含第 $i$ 个数中第 $p$ 位1的个数为奇数或偶数的区间数；同理处理出从后往前的 $dp$ 数组，最后枚举 $a_y$ 统计答案。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
void solve()
{
    int n;
    cin>>n;
    int a[n+5];
    for(int i=1;i<=n;i++)cin>>a[i];
    int dp1[n+5][33][2];
    int dp2[n+5][33][2];
    memset(dp1,0,sizeof(dp1));
    memset(dp2,0,sizeof(dp2));

    for(int i=1;i<=n;i++)
    {
        for(int p=31;p>=0;p--)
        {
            if((a[i]>>p)&1)
            {
                dp1[i][p][1]=dp1[i-1][p][0]+1;
                dp1[i][p][0]=dp1[i-1][p][1];
            }
            else
            {
                dp1[i][p][1]=dp1[i-1][p][1];
                dp1[i][p][0]=dp1[i-1][p][0]+1;
            }
            // cout<<i<<" "<<p<<" "<<dp1[i][p][0]<<" "<<dp1[i][p][1]<<endl;
        }
    }
    
    for(int i=n;i>=1;i--)
    {
        for(int p=31;p>=0;p--)
        {
            if((a[i]>>p)&1)
            {
                dp2[i][p][1]=dp2[i+1][p][0]+1;
                dp2[i][p][0]=dp2[i+1][p][1];
            }
            else
            {
                dp2[i][p][1]=dp2[i+1][p][1];
                dp2[i][p][0]=dp2[i+1][p][0]+1;
            }
        }
    }

    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int p=log2(a[i]);
        ans+=dp1[i-1][p][1]*dp2[i+1][p][0];
        ans+=dp1[i-1][p][0]*dp2[i+1][p][1];
        ans+=dp1[i-1][p][1];
        ans+=dp2[i+1][p][1];
    }
    cout<<ans<<endl;
}

signed main()
{
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

位运算

E

题意：求 $\sum_{i=1}^{n}\sum_{j=1}^{i}(C(i,j)mod\ j)$ ，其中 $C(i,j)$ 表示从 $1,2,…,i$ 个数中挑 $j$ 个数排列的方案数，但循环同构视为同一种排列。

易知：
$$
C(i,j)\equiv\frac{A_i^j}{j}\equiv\frac{i(i-1)…(i-j+1)}{j}\equiv\lfloor\frac{i}{j}\rfloor\times (j-1)!\ mod\ j
$$

由威尔逊定理知：
$$
(n-1)!\ mod\ n=-1\ (p\ is \ a\ prime)
$$

$$
(n-1)!\ mod\ n=2\ (p=4)
$$

$$
(n-1)!\ mod\ n=0\ (otherwise)
$$

因此只有当 $j$ 是质数或2时才对答案有贡献，即：
$$
C(i,j)=-\lfloor \frac{i}{j}\rfloor\ mod\ j\ (j\ is \ a\ prime)
$$

$$
C(i,j)=2\times\lfloor \frac{i}{j}\rfloor\ mod\ j\ (j=4)
$$

统计答案时，注意到当 $i=1,2,…,j-1$ 时无贡献，当 $i=j,j+1,…2j-1$ 时贡献为-2，当 $i=2j,2j+1,…,3j-1$ 时贡献为-3……

因此对每个质数 $j,2j,3j,…$ 统计 $i$ ，采用差分数组统计 $i$，然后前缀和还原出每个值对应的答案。

注意单独统计 $j=4$ 的情况。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int maxn=1e6+3;
bitset<maxn> isprime;
vector<int>pr;
int de[maxn];
 
void pp() 
{
    isprime.set();
    isprime[0] = isprime[1] = false;
    for (int i = 4; i < maxn; i += 2) isprime[i] = false;
    for (int i = 3; i * i < maxn; i += 2)
        if (isprime[i])
            for (int j = i * i; j < maxn; j += i * 2) isprime[j] = false;
    for (int i = 2; i < maxn; i++)
        if (isprime[i]) pr.push_back(i);

}
 
int ans[maxn];
 
signed main() 
{
    pp();
    for(auto p:pr)
    {
        for(int now=p;now<=maxn;now+=p)
        {
            int inc=(p-now/p%p)%p;
            de[now]=(de[now]+inc)%mod;
            if(now+p<=maxn)de[now+p]=(de[now+p]-inc+mod)%mod;
        }
    }

    for(int now=4;now<=maxn;now+=4)
    {
        int inc=(2*now/4)%4;
        de[now]=(de[now]+inc)%mod;
        if(now+4<=maxn)de[now+4]=(de[now+4]-inc+mod)%mod;
    }
    
    int pre=0;
    for(int i=1;i<=maxn;i++)
    {
        pre=(pre+de[i])%mod;
        ans[i]=(ans[i-1]+pre)%mod;
    }

    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        cout<<ans[n]<<endl;
    }
    // system("pause");
    return 0;
}

math