牛客练习赛138

牛客练习赛138

A.小s的签到题

思路：过题人数最多的就是签到题

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, char> PII;

bool cmp(PII a, PII b)
{
  return a.first > b.first;
}

void solve()
{
  int n;
  cin >> n;
  vector<PII> vec(n + 10);
  for (int i = 1; i <= n; i++)
    cin >> vec[i].second;

  for (int i = 1; i <= n; i++)
  {
    int a, b;
    scanf("%d/%d", &a, &b);
    vec[i].first = a;
  }

  sort(vec.begin() + 1, vec.begin() + 1 + n, cmp);
  cout << vec[1].second << endl;
}

int main()
{
  // ios::sync_with_stdio(0);
  // cin.tie(0), cout.tie(0);
  // int t;
  // cin >> t;
  // while(t--)
  solve();
}

B.行列改写

思路：第i行第j列会被第i行的值影响到，要么会被第j列所影响到，所以每个位置为当前所在行列的最大值，当我们固定行，看列的时候可以发现，先对列所对应的值从小到大排序，当当前行所对应的值>列时，值全为行，剩下的为列的后缀和 ，所以我们可以维护一个列的后缀和，然后对于每一行二分找到第一个大于行所对应值的位置

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
 
int main(){
     int n,m;
    cin>>n>>m;
    vector<ll>a(n+10,0),b(m+10,0),s(m+10,0);
     
      for(int i=1;i<=n;i++)  cin>>a[i];
     for(int i=1;i<=m;i++)   cin>>b[i];
     
    sort(b.begin()+1,b.begin()+1+m);
            
    for(int i=1;i<=m;i++)   s[i]=s[i-1]+b[i];
        
   ll sum=0;
     
     for(int i=1;i<=n;i++){
         int id=upper_bound(b.begin()+1,b.begin()+1+m,a[i])-b.begin();
            id--;
        sum+=a[i]*id;
        sum+=s[m]-s[id];      
     }
     
     cout<<sum<<endl;
}

C 树上替身追赶游戏

思路：尝试几次后能发现无论如何走，那个人一直会在你后面一个，所以最大能坚持的回合数为树的最大深度

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<int>> vec;
int ans = 0;

int  dfs(int u,int fa){
    if(!vec[u].size())  return 1;
  int cnt = 1;
  int mx = 0;
  for (auto it : vec[u]){
    if (it == fa)   continue;
    mx = max(mx, dfs(it, u));
  }
  cnt += mx;
  return cnt;
}


void solve(){
  int n, k;
  cin >> n >> k;
  vec.resize(n+10);

  for (int i = 1; i < n;i++){
    int a, b;
    cin >> a >> b;
    vec[a].push_back(b), vec[b].push_back(a);
  }

  cout << dfs(k, -1) << endl;
}

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  // int t;
  // cin >> t;
  // while(t--)
    solve();
}

D. 全对！

题意：有n组字符串由0或者1组成，长度最大为16，求一个时刻使得n组字符串都为1

思路：

​ 我们可以发现当t时刻时遍历到了字符串的第(t-1）%字符串的长度，首先我们可以想到当所有字符串的最小公倍数里都没有一个时刻使得所有字符串都为1的话即为-1。

​ 其次因为字符串长度为1e5所有不能一个一个枚举，但是当看到字符串的长度小于等于16时我们可以往长度方向思考，当有多个字符串长度相同时他们若想再某一时刻相等的话只能是他们所对应的位置都是1，所以可以预处理字符串相同的位置，然后枚举不同时刻所对应的不同长度是不是为1

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



ll gcd(ll a,ll b){
  return b ? gcd(b, a % b) : a;
}

void solve(){
  int n;
  cin >> n;

  vector<string> a(20);
  ll num = 0;

  for (int i = 1; i <= n;i++){
    string s;
    cin >> s;
       if(!num)  num = s.size();
          else      num = num * s.size() / gcd(num, s.size());
    if(!a[s.size()].size())  a[s.size()] = s;
    else{
      for (int j = 0; j < s.size();j++)
             if(a[s.size()][j]=='1'&&s[j]=='1')     a[s.size()][j] = '1';
              else      a[s.size()][j] = '0';
    }
  }

  for (int i = 0; i <= num-1;i++){
    int ok = 1;
    for (int j = 0; j < 20;j++) 
          if(!a[j].size())     continue;
          else   if(a[j][i%j]=='0')    ok = 0;

            if(ok){
              cout << i + 1 << endl;
              return;
            }
  }
  cout << -1 << endl;
}

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  // int t;
  // cin >> t;
  // while(t--)
    solve();
}