A:

  • 涉及知识点： 位运算

  • 解法： &运算对应的二进制运算，如果第i个数的二进制第k位为1，那么它可以和其余所有二进制第k位为1的每一个数产生(1<<i)的贡献(当然也包括它本身)，所以统计二进制第k位为1的个数，最后加一下

  • 时间复杂度： O(nlogn)

  • 代码： 

    #include <bits/stdc++.h>
using namespace std;
#define ll long long
ll a[35];
int main()
{
  int n,x;
  ll ans = 0;
  cin>>n;
  for(int i=1;i<=n;i++){
      cin>>x;
      int cnt = 0;
      while(x){
          int z = x%2;
          x /= 2;
          a[cnt++] += z;
      }
  }
  for(int i=0;i<=30;i++)
      ans += (1ll*(1<<i)*a[i]*a[i]);
  cout<<ans<<endl;
  return 0;
}

B:

  • 涉及知识点： 计数

  • 解法： n个点，任意两点之间都可以形成唯一一条直线，那么取任意一条直线，这条直线可以和剩余的n-2个点，形成n-2个不相同的三角形，所以一条边可以对所有三角形的周长产生(n-2)次的贡献

  • 时间复杂度：O(n^2)

  • 代码： 

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

C:

  • 涉及知识点： dp

  • 解法： 只会写O(26)的dp，如果n再大一点的话，就t了，然后又补一个O()的代码

    我们设dp[ i ][ j ]表示前i个字母组成长度为j的子序列的个数 那么dp[ i ][ j ]就等于dp[ i-1 ][ j-1 ] + dp[ i-1 ][ j ],那么重复的其实就等于上一个s[i]的位置记为pos，即dp[ pos-1 ][ j-1 ]的个数，减去即可，为了防止等于负数，记得先加上mod

  • 时间复杂度： O()

  • 代码： 

//这是O(26n^2)的代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 +7;
ll dp[1005][1005][30];
char s[1005];
int main()
{
    int n,m;
    cin>>n>>m;
    scanf("%s",s+1);
    if(m == 0){
        cout<<"1"<<endl;
        return 0;
    }
    for(int i=1;i<=n;i++){
        dp[i][1][s[i]-'a'] = 1;
        for(int j=1;j<=m;j++){
            for(int k=0;k<26;k++){
                if(s[i] == 'a' + k){
                     for(int z=0;z<26;z++)
                        dp[i][j][k] += (dp[i-1][j-1][z]),dp[i][j][k]%=mod;
                }
                else
                    dp[i][j][k] += dp[i-1][j][k],dp[i][j][k]%=mod;
            }
        }
    }
    ll ans = 0;
    for(int i=0;i<26;i++)
        ans += dp[n][m][i],ans%=mod;
    cout<<ans<<endl;
    return 0;
}
//这是O(n^2)的代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
const int maxn = 1005;
char s[maxn];
int pre[maxn];
ll dp[maxn][maxn];
int main()
{
    int n,k;
    scanf("%d %d",&n,&k);
    scanf("%s",s+1);
    dp[0][0] = 1;
    for(int i=1;i<=n;i++){
        dp[i][0] = 1;
        for(int j=1;j<=i;j++){
            dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
            if(pre[s[i]-'a'])
                dp[i][j] = (dp[i][j] - dp[pre[s[i]-'a'] - 1][j-1] + mod)%mod;
            dp[i][j] %= mod;
        }
        pre[s[i]-'a'] = i;
    }
    printf("%lld\n",dp[n][k]%mod);
    return 0;
}

D:

  • 涉及知识点： 同余/扩展欧几里得

  • 解法： 可以将方程移项得到 ax + by = k - cz ,由于方程组一定有解，我们枚举z，这就变成了典型的扩展欧几里得，显然 (k - cz)%gcd(a , b) 等于 0 才有解，然后根据exgcd求出最小的y，最后求得x，如果 x 或者 y 小于 0 ，继续遍历...

  • 时间复杂度： 不会算呀QAQ

  • 代码： 

    #include <bits/stdc++.h>
using namespace std;
#define ll long long
//扩展欧几里得,求ax+by=d,d是a和b的最大公约数
ll exgcd(ll a,ll b,ll &x,ll &y)
{
  if(!b){
      x = 1,y = 0;
      return a;
  }
  ll d = exgcd(b , a%b , y , x);
  y -= (a/b)*x;
  return d;
}
int main()
{
  ll a,b,c,k;
  cin>>a>>b>>c>>k;
  ll gc = __gcd(a , b);
  for(int i=0;i<=k/c;i++)
  {
      if((k - c*i)%gc != 0)continue ;
      ll x,y;
      ll d = exgcd(a ,b , x, y);
      x = (k-c*i)*x/gc;
      x = (x%(b/d) + (b/d))%(b/d);
      y = (k - a*x - c*i)/b;
      if(x < 0 || y < 0)
          continue ;
      cout<<x<<" "<<y<<" "<<i<<endl;
      break ;
  }
  return 0;
}

  • 顺便放一下给出方程组：ax + by = k ,a , b, k都已知的情况下，求最小的x的模板：

    #include <bits/stdc++.h>
using namespace std;
#define ll long long
//扩展欧几里得,求ax+by=d,d是a和b的最大公约数
ll exgcd(ll a,ll b,ll &x,ll &y)
{
  if(!b){
      x = 1,y = 0;
      return a;
  }
  ll d = exgcd(b , a%b , y , x);
  y -= (a/b)*x;
  return d;
}
int main()
{
  ll a,b,k;
  cin>>a>>b>>k;
  if(k%__gcd(a,b))
      cout<<"Impossible"<<endl;
  else{
      ll c,d;
      ll gc = exgcd(a,b,c,d);
      c = k*c/gc;
      ll ans = (c%(b/gc) + (b/gc))%(b/gc);
      cout<<ans<<endl;
  }
  return 0;
}