A 咪咪游戏

Solution

$签到题,用一个指针指向当前需要匹配的字符$
$当匹配到末尾时把指针指向开头,并且中间不能出现其他字符$
$注意最后指针需要指向开头,即不能最后只有m没有q$

Code

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 4e5 + 5;
const ll mod = 19961993;
const int DEG = 20;
const double PI = acos(-1.0);
const double eps = 1e-10;
const ll inf = 1e18;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
string tmp = "mq";
int main(){
  int t;
  cin >> t;
  while(t--){
    string s;
    cin >> s;
    int now = 0;
    int flag = 0;
    for(int i = 0; i < s.size(); i++){
      if(s[i] != tmp[now]){
        flag = 1;
        break;
      }
      else {
        now = (now + 1) % tmp.size();
      }
    }
    //cout << flag << ' ' << now << "\n";
    cout << ((!flag && !now) ? "Yes\n" : "No\n");
  }
  return 0;
}

B 三角形

Solution

$考虑到每一个箱子只取一个宝盒$
$我们维护一个大小为k的堆即可$
$每次更新,最后得到前k小的和$
$具体看注释$

Code

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e6 + 5;
const ll mod = 19961993;
const int DEG = 20;
const double PI = acos(-1.0);
const double eps = 1e-10;
const ll inf = 1e18;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
ll a[105], b[N];
int main(){
  int n, k;
  cin >> n >> k;
  int cnt = 0;
  int cur = 0;
  priority_queue<int> q;
  q.push(0);
  while(n--){
    int m;
    cin >> m;
    for(int j = 1; j <= m; j++) cin >> a[j];
    sort(a + 1, a + 1 + m);
    cnt = 0, cur = 0;
    while(!q.empty())  b[++cnt] = q.top(), q.pop();
    for(int i = 1; i <= m; i++){
      for(int j = cnt; j >= 1; j--){
        if(cur < k) q.push(a[i] + b[j]), ++cur; // 堆小于k 放入
        else if(q.top() <= a[i] + b[j]) // 堆大小为k, 因为a[i] and b[j] 已经排序 后面不用看了
          break;
        else {
          q.pop(), q.push(a[i] + b[j]); // 更新
        }
      }
    }
  }
  cnt = 0;
  while(!q.empty()){
    b[++cnt] = q.top(), q.pop();
  }
  ll ans = 0;
  for(int i = 1; i <= cnt; i++){
    ans += b[i];
  }
  cout << ans << "\n";
  return 0;
}

C 区间加

Solution

$我20分的做法(逃:$
$对于第二档数据推得公式 2^{n - 1}$
$对于第三档数据直接输出-1$

$update:$
$再贴一个从群友那里偷来的dp思路$
$dp[i]表示到第i个有多少种情况$
$由题目的限定要求$
$只会出现$
$1.\ \ a[i] == a[i - 1]$
$2.\ \ a[i] - a[i - 1] == 1$
$3.\ \ a[i - 1] - a[i] == 1$
$三种情况,我们分情况讨论$
$情况1. \ \ dp[i] = dp[i - 1] + dp[i - 1] * (m - a[i - 1])$
$其中,dp[i - 1]表示不选(i,i)$
$再从(m - a[i - 1])个以a[i - 1]的序列中选出其中(m - a[i - 1] - 1)$
$情况2.\ \ dp[i] = dp[i - 1] * (m - a[i - 1])，表示只能由a[i - 1]结尾中选择延长$
$情况3.\ \ dp[i] = dp[i - 1],以a[i - 1]结尾的都延长到a[i]$

Code

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e6  + 5;
const ll mod = 998244355;
const int DEG = 20;
const double PI = acos(-1.0);
const double eps = 1e-10;
const ll inf = 1e18;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
ll dp[N];
ll a[N];
int main(){
  int n, m;
  cin >> n >> m;
  for(int i = 1; i <= n; i++) cin >> a[i];
  if(a[1] > m || a[1] < m - 1){
    cout << 0 << "\n";
    return 0;
  }
  dp[1] = 1;
  for(int i = 2; i <= n; i++){
    if(m - a[i] > i || a[i] > m || m - a[i] > n - i + 1){
      cout << 0 << "\n";
      return 0;
    }
    if(a[i - 1] - a[i] == 1){
      dp[i] = dp[i - 1];
    }
    else if(a[i] - a[i - 1] == 1){
      dp[i] = dp[i - 1] * (m - a[i - 1]) % mod;
    }
    else if(a[i] == a[i - 1]){
      dp[i] = dp[i - 1] + dp[i - 1] * (m - a[i - 1]) % mod;
      dp[i] %= mod;
    }
  }
  cout << dp[n] << "\n";
  return 0;
}

D 多元组

Solution

$注意到100\%数据的M只有50$
$考虑用50个树状数组维护前缀和$
$因为我们有递推式子ans[j][i] = \sum _{k = 1}^{i - 1} ans[j - 1][i] (a[i] > a[k])$
$这个式子的意思是第i个数所组成j元组$
$只要满足a[i] > a[k] 可以由第k个数所组成的j - 1元组转移$
$剩下的就是一边插入一边查询的操作了注意1e9的数据要离散化一下$

Code

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e5  + 5;
const ll mod = 1e9 + 7;
const int DEG = 20;
const double PI = acos(-1.0);
const double eps = 1e-10;
const ll inf = 1e18;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
ll t[55][N];
ll ans[55][N];
int a[N];
int b[N];
int lowbit(int x){
  return x & (-x);
}
void update(int id, int x, int add){
  while(x < N){
    t[id][x] += add;
    t[id][x] %= mod;
    x += lowbit(x);
  }
}
ll query(int id, int x){
  ll res = 0;
  while(x){
    res +=  t[id][x];
    res %= mod;
    x -= lowbit(x);
  }
  return res;
}
int main(){
  int n, m;
  cin >> n >> m;
  for(int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
  sort(b + 1, b + 1 + n);
  int len = unique(b + 1, b + 1 + n) - b - 1;
  for(int i = 1; i <= n; i++){
    a[i] = lower_bound(b + 1, b + 1 + len, a[i]) - b; // 离散化
  }
  for(int i = 1; i <= n; i++){
    ans[1][i] = 1; // 自己本身肯定可以组成一元组啦
  }
  for(int i = 1; i <= n; i++){
    update(1, a[i], 1); // 把自己本身构成的一元组插入树状数组
    for(int j = 2; j <= m; j++){
      ans[j][i] = ans[j][i] + query(j - 1, a[i] - 1); // j - 1元组里 小于等于a[i - 1]的都统计
      update(j, a[i], ans[j][i]); // 更新一下 a[i]所能构成的j元组
      ans[j][i] %= mod;
    }
  }
  ll cal = 0;
  for(int i = 1; i <= n; i++){
    //cout << cal << "\n";
    cal += ans[m][i];
    cal %= mod;
  }
  cout << cal << "\n";
  return 0;
}

牛客OI周赛15-普及组 题解

A 咪咪游戏

Solution

Code

B 三角形

Solution

Code

C 区间加

Solution

Code

D 多元组

Solution

Code

牛客OI周赛15-普及组题解