鉴于自己太菜,只做了前4题,而且因为各种神奇的原因(没开LL、用B的模数给C题取模等等)wa了无数次,罚时爆炸QAQ
本次题解暂时只写前四题,更不更最后两题看自己的补题状态~

A

知识点:位运算、计数
题意:给一个数组。计算对所有数而言两两位与运算求和。
思路:由于数组长度为 ,显然不能 暴力求解。可以从位与运算的性质着手:两个数进行位于运算后,只有当某一位(二进制意义上)都是1的时候,位与之后才会变成1,否则就是0。
因此可以转化为这样的思路:有 个数在第 位二进制为1,那么最终的答案里就会累计 个第 位二进制的1,即 。最后所有的答案为
最终只需要统计每个数对每个二进制计数的贡献即可。
复杂度:
预估难度: 1500
代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    ll t,i,j,n,m=0;
    cin>>n;
    ll a[33]={0};
    for(i=0;i<n;i++){
        cin>>j;
        int k=0;
        while(j){
            a[k++]+=j%2;
            j/=2;
        }
    }
    for(i=0;i<32;i++){
        m+=(1<<i)*a[i]*a[i];
    }
    cout<<m;
}

B

知识点:计数
题意:给定n个点,求所有三角形的周长之和,三角形的边长取曼哈顿距离。
思路:这道题其实和A题有异曲同工之妙,都是统计后进行整体运算。这道题只需要统计每条边被计算多少次(答案显然是 次)即可。
复杂度:
预估难度:1300
代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=998244353;
int main(){
    ll t,i,j,n,m=0;
    cin>>n;
    ll a[3333][2]={0};
    for(i=0;i<n;i++){
        cin>>a[i][0]>>a[i][1];
    }
    for(i=0;i<n-1;i++){
        for(j=i+1;j<n;j++){
            m+=(abs(a[i][0]-a[j][0])+abs(a[i][1]-a[j][1]))*(n-2)%mod;
            m%=mod;
        }
    }
    cout<<m;
}

C

知识点:dp
题意:给定一个字符串,求有多少个长度为k的、不相同的子序列。
思路:看到子序列统计应该直接联想到dp。本题的难度在于“去重”。可以用这样的思路:
的含义是:前i个字符里,长度为j的、以字符'a'+k结尾的子序列数量。
那么可得转移方程:



复杂度:
预估难度:1900
代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
int dp[1010][1010][27];
int main(){
    ll t,i,j,n,k,m=0;
    cin>>n>>m;
    int a[3333][2]={0};
    string s;
    cin>>s;
    if(m==0){cout<<1;return 0;}
    for(i=1;i<=n;i++){
        dp[i][1][s[i-1]-'a']=1;
        for(j=1;j<=m;j++){
            for(k=0;k<26;k++){
                if(s[i-1]==k+'a'){
                    for(t=0;t<26;t++)dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-1][t])%mod;
                }
                else dp[i][j][k]+=dp[i-1][j][k],dp[i][j][k]%=mod;
            }
        }
    }
    ll res=0;
    for(i=0;i<26;i++)res=(res+dp[n][m][i])%mod;
    cout<<res;
}

D

知识点:数论
题意:求ax+by+cz=k的任意一组非负整数解。
思路:题目保证有解,因此可以用exgcd进行求解。从0开始遍历x,可以对 的情况进行剪枝,减少一些复杂度。
预估难度:1800
复杂度:
代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=998244353;
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll r=exgcd(b,a%b,x,y);
    ll temp=x;
    x=y;
    y=temp-(a/b)*y;
    return r;
}
ll gcd(ll a,ll b){
    if(a%b==0)return b;
    return gcd(b,a%b);
}

int main(){
    ll t,i,j,n,k,m=0,a,b,c;
    cin>>a>>b>>c>>k;
    ll g=gcd(b,c);
    for(i=0;i<k/a;i++){
        if((k-a*i)%g!=0)continue;
        ll x,y;
        ll cc=exgcd(b,c,x,y);
        t=(k-a*i)/cc;
        ll x1=x*t,y1=y*t,c1=c/g;
        x1=(x1%c1+c1)%c1;
        y1=(k-a*i-b*x1)/c;
        if(x1<0||y1<0)continue;
        cout<<i<<" "<<x1<<" "<<y1;
        break;
    }
}

E

知识点:树
题意:找出所有 这样的顶点对,满足 ①它们互不为祖先关系 ②它们之间的路径长度为k。对所有的这样顶点对的权值进行求和。
思路:(待补全)

F

(待补全)