牛客周赛round 43 A~E

A(简单博弈）

如果字符串长度大于1先手必赢。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using i64 = long long;
using i128 = __int128_t;
const ll inf = 1e18;
void solve()
{
    string s;
    cin>>s;  
    if(s.length()==1)
    cout<<"yukari"<<"\n";
        else
    cout<<"kou"<<"\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll t = 1;
    //cin >> t;
    while (t--)
        solve();
    return 0;
}

B(模拟）

解释#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using i64 = long long;
using i128 = __int128_t;
const ll inf = 1e18;
void solve()
{
    string s;
    cin>>s;  
    if(s.length()==1)
    cout<<"yukari"<<"\n";
        else
    cout<<"kou"<<"\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll t = 1;
    //cin >> t;
    while (t--)
        solve();
    return 0;
}

C(数学）

俩个素数乘积必为和数，要让极差最小，毫无疑问，就是让所有的数更加平均，只要用最大*最小，次大*次小...

注意n为奇数的时候留最后一位

解释#include<bits/stdc++.h>
#define int long long 
#define y second 
using namespace std;
typedef long long LL;
typedef double D;
const int N = 2e5 + 10;
typedef pair<int, int> Pii;
vector<int>s;
void solved()
{
    int n;
    cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a.begin(),a.end());
    int l=0,r=n-1;
    if(n%2==1)r--,s.push_back(a[n-1]);
    while(l<r){
      s.push_back(a[l]*a[r]);
      l++,r--;
    }
    sort(s.begin(),s.end());
    cout<<s[s.size()-1]-s[0]<<"\n";
}
signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t;
  t=1;
  while (t--)
  {
  solved();
  }
  return 0;
}

D(树）

如果n为奇数，肯定是-1

解释#include<bits/stdc++.h>
#define x first   
#define y second 
using namespace std;
typedef long long LL;
typedef double D;
const int N = 2e5 + 10;
typedef pair<int, int> Pii;
vector<int>e[N];
int ans=0;

int  dfs(int u,int fa){
    int res=1;
    for(auto son :e[u]){
        if(son==fa)continue;
        int k=dfs(son,u);
        if(k%2==0)ans+=1;
        else res+=k;
    }
    return res;
}
void solved()
{
     int n;cin>>n;
     for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        e[a].push_back(b);
        e[b].push_back(a);
     }  
     if(n&1)cout<<-1; 
     else{
        dfs(1,0);
        if(ans==0){
           cout<<-1;
        }
        else cout<<ans<<"\n";
    }
    
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t=1;
  while (t--)
  {
  solved();
  }
  return 0;
}

E(组合数）

对于第i位数字，它可以充当k位里面的第j位，如果判断其充当第k位的次数，其贡献就为s[i]*后面n-i个数里面先择k-j位，组合数学

解释#include<bits/stdc++.h>
#define int long long 
#define y second 
using namespace std;
typedef long long LL;
typedef double D;
const int N = 2e3 + 10;
typedef pair<int, int> Pii;
int c[N][N];
int mod=1e9+7;
int pre[N];
void init(){
    for(int i=0;i<=2000;i++){
        for(int j=0;j<=i;j++){
            if(j==0)c[i][j]=1;
            else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
        }
    }
}
int qmi(int  x,int  p){
    int  res=1;
    while(p){
        if(p&1)res=res*x%mod;
        x=x*x%mod;
        p>>=1;
    }
    return res;
}
void solved()
{
      int n,k;cin>>n>>k;
      string s;
      cin>>s;
      int ans=0;
    
      for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
          int x=n-i;
          int y=s[i-1]-'0'; 
          
          if(j==1){
            if(k-j>x)continue;
            ans+=c[x][k-j]*qmi(10,k-j)%mod*y%mod;
            ans%=mod;
            }
          else {
            x=i-1;
            int tp=j-1;
            if(n-i<k-j)continue;
            if(x<tp)continue;
            ans+=(c[x][tp]*c[n-i][k-j]%mod)*qmi(10,k-j)%mod*y%mod;
            ans%=mod;
          }
        }
      }
      cout<<ans<<"\n";
      
}
signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t;
  t=1;
  init();
  while (t--)
  {
  solved();
  }
  return 0;
}