A. 打怪

Solution

签到题,我是直接模拟,一开始我的做法是令cnt > 1e4 的输出直接输出 -1, 没想到超时了,出题人没给 t 的大小,上当了..
于是考虑下 -1 的情况,显然当我们的攻击大于等于小怪的血量时,我们每次都能先手的情况下,可以秒杀小怪不会掉血
所以, 当 h <= a 的时候输出 -1 其他情况模拟即可,时间复杂度
PS:其实也可以二分,当数据大的时候直接二分能打的怪数也是可以的,但对于这道签到题,就不画蛇添足了.

Code

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
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;
}();
const int N = 1e6 + 5;
int main(){
  int n;
  cin >> n;
  while(n--){
    int h, a, H, A;
    cin >> h >> a >> H >> A;
    int cnt = 0;
    int now = H;
    if(H <= a){
      cout << -1 << "\n";
      continue;
    }
    while(h > 0){
      now -= a;
      if(now <= 0){
        cnt++;
        now = H;
        continue;
      }
      h -= A;
    }
    //if(cnt > 1e4) cout << -1 << "\n";
    cout << cnt << "\n";
  }
  return 0;
}

B. 吃水果

Solution

这道题卡了好久,当时不知道怎么想的写了个bfs,妥妥的又一次超时了,冷静下来思考，对于 n, m 操作只有两种

  • n, m 都减 1
  • 其中一个 * 2

显然,我们要完成任务必须把 n, m 操作成 n == m 的情况才能把两者吃完
那么这么考虑, 设 n > m, 只对小的做第二种操作(不然大的 * 2, 小的 * 2 两者差值没有缩进 没有意义)
然后置顶一个结束点 n < 2 * m 时停止 * 2 的操作
此时有两个分支:

  1. 令 m *= 2, 然后两者重复操作1直到 n * 2 == m
  2. 重复操作1直到 n == m * 2

两者取min就是答案了

Code

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
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;
}();
const int N = 1e6 + 5;
int main(){
  int t;
  cin >> t;
  while(t--){
    ll n, m;
    cin >> n >> m;
    if(n == m) {
      cout << n << "\n";
      continue;
    }
    if(n < m) swap(n, m);
    int cnt = 0;
    while(n > 2 * m){
      m *= 2;
      cnt++;
    }
    int cur = cnt;
    ll pn = n, pm = m;
    while(n != 2 * m){
      n--, m--;
      cnt++;
    }
    pm *= 2;
    cur++;
    while(pm != 2 * pn){
      pm--, pn--;
      cur++;
    }
    cout << min(cnt + n + 1, cur + pm + 1) << "\n";
  }
}

C. 四个选项

Solution

做法1: 状压dp, 考虑枚举4^12, 按四进制的思想, 每一位会有0, 1, 2, 3, 分别可以代表 A, B, C, D, 直接for 0 to 4 ^ 12 转换成四进制检验即可
做法2: dfs, 构造可行方案然后逐一检验
这里只给出dfs的做法代码

Code

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
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;
}();
const int N = 1e4 + 5;
pair<int, int> query[N];
vector<string> v;
void dfs(int x1, int x2, int x3, int x4, string s){
  if(!x1 && !x2 && !x3 && !x4){
    v.push_back(s);
    return ;
  }
  if(x1){
    dfs(x1 - 1, x2, x3, x4, s + '0');
  }
  if(x2){
    dfs(x1, x2 - 1, x3, x4, s + '1');
  }
  if(x3){
    dfs(x1, x2, x3 - 1, x4, s + '2');
  }
  if(x4){
    dfs(x1, x2, x3, x4 - 1, s + '3');
  }
}
int main(){
  int na, nb, nc, nd, m;
  ll ans = 0;
  cin >> na >> nb >> nc >> nd >> m;
  for(int i = 1; i <= m; i++){
    int x, y;
    cin >> x >> y;
    query[i] = {x, y};
  }
  dfs(na, nb, nc, nd, "");
  for(int i = 0; i < v.size(); i++){
    int flag = 0;
    for(int j = 1; j <= m; j++){
      int x = query[j].first;
      int y = query[j].second;
      if(v[i][x - 1] != v[i][y - 1]){
        flag = 1;
        break;
      }
    }
    if(!flag) ans++;
  }
  cout << ans << "\n";
}

D. 最短路变短了

Solution

日常看错题,其实这道题可以加强的,我就是按着出题人的BONUS方向去做的，发现自己想复杂了
题目提到 若边反向后城市1不能到达城市n，我们视为最短路径长度没有变短
我当时的想法就是,什么边会是最短路的必经边,然后在加强版的路上越走越远
考虑建反向图,然后我们发现 如果对于一条边
假设起点为 u, 终点为 v, 反向之后

  • 如果能满足 G1.dist[v] + G2.dist[u] + w < G1.dist[n] 那么它就能令最短路变短 输出YES
  • 如果它是桥, 那么根据题意, 输出NO
  • 其余情况输出NO

PS:找桥的过程可以用tarjan, 但其实不用找桥....

Code

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
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;
}();
const int N = 2e5 + 5;
struct node{
  int nxt, u, v;
  ll w;
};
bool bridge[N];
struct Graph{
  struct Node{
    int v;
    ll dis;
    Node(ll a, int b): dis(a), v(b){};
    bool operator < (const Node &a)const{
      return dis > a.dis;
    }
  };
  node edge[N];
  int tot = 0;
  int head[N], id[N];
  bool vis[N];
  ll d[N];
  Graph(){
    memset(head, -1, sizeof(head));
  }
  void add(int u, int v, ll w){
    edge[tot] = {head[u], u, v, w};
    head[u] = tot++;
  }
  void add(int u, int v, ll w, int _id){
    edge[tot] = {head[u], u, v, w};
    id[tot] = _id; head[u] = tot++;
  }
  void dijkstra(int S){
    priority_queue<Node> Q;
    memset(d, 0x3f, sizeof(d));
    memset(vis, 0, sizeof(vis));
    d[S] = 0;
    Q.push(Node(d[S], S));
    while(!Q.empty()){
      Node t = Q.top();
      Q.pop();
      int v = t.v;
      if(vis[v]) continue;
      vis[v] = 1;
      for(int i = head[v]; ~i; i = edge[i].nxt){
        if(d[edge[i].v] > d[v] + edge[i].w){
          d[edge[i].v] = d[v] + edge[i].w;
          Q.push(Node(d[edge[i].v], edge[i].v));
        }
      }
    }
  }
  int vistime = 0;
  int dfn[N], low[N];
  void tarjan(int v, int u){
    dfn[v] = low[v] = ++vistime;
    for(int i = head[v]; ~i; i = edge[i].nxt){
      if(!dfn[edge[i].v]){
        tarjan(edge[i].v, v);
        low[v] = min(low[v], low[edge[i].v]);
        if(low[edge[i].v] > dfn[v])
          bridge[id[i]] = 1;
      }
      else if(edge[i].v != u){
        low[v] = min(low[v], dfn[edge[i].v]);
      }
    }
  }
}G1, G2, G3;
int n, m, u, v;
ll w;
int ans[N];
int main(){
  cin >> n >> m;
  for(int i = 1; i <= m; i++){
    cin >> u >> v >> w;
    G1.add(u, v, w);
    G2.add(v, u, w);
  }
  G1.dijkstra(1);
  G2.dijkstra(n);
  ll s = G1.d[n];
  for(int i = 0; i < G1.tot; i++){
    u = G1.edge[i].u;
    v = G1.edge[i].v;
    w = G1.edge[i].w;
    if(G1.d[u] + G2.d[v] + w == s){ // 构成最短路的边
      G3.add(u, v, w, i);
      G3.add(v, u, w, i);
    }
  }
  G3.tarjan(1, 0); // 找桥
  for(int i = 0; i < G1.tot; i++){
    u = G1.edge[i].u;
    v = G1.edge[i].v;
    w = G1.edge[i].w;
    if(G1.d[v] + G2.d[u] + w < s){ // 可以令最短路变短
      ans[i] = 1;
    }
    else if(bridge[i]){ // 是桥
      ans[i] = 2;
    }
    else ans[i] = 3;
  }
  int q;
  cin >> q;
  while(q--){
    int x;
    cin >> x;
    if(ans[x - 1] == 1){
      cout << "YES\n";
    }
    else if(ans[x - 1] == 2){
      cout << "NO\n";
    } // 桥
    else if(ans[x - 1] == 3){
      cout << "NO\n";
    }
  }
  return 0;
}

E. 相似的子串

Solution

显然满足单调性, 我们考虑二分答案, 用一个map记录前端点， 用字符串哈希的方法找到下一个相同的串

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 2e5 + 5;
const ll mod = 998244353;
const int DEG = 30;
const double PI = acos(-1.0);
const double eps = 1e-12;
const ll inf = 1e18;
static auto fast_iostream = [](){
  ios::sync_with_stdio(false);
  cout.tie(nullptr);
  return 0;
}();
const int seed = 127;
int n, k;
string a;
unsigned long long Hash[N];
map<unsigned long long, pair<int, int> > mp;
bool check(int x){
  mp.clear();
  unsigned long long now = 0;
  for(int i = 1; i <= x; i++){
    now = now * seed + (a[i - 1] - 'a' + 1);
  }
  mp[now] = make_pair(x, 1);
  for(int i = x + 1; i <= n; i++){
    now = now - (Hash[x - 1] * (a[i - x - 1] - 'a' + 1));
    now = now * seed + (a[i - 1] - 'a' + 1);
    if(mp.find(now) != mp.end()){
      if(mp[now].first < i - x + 1){
        int pos = mp[now].second;
        if(pos + 1 == k){
          return true;
        }
        mp[now] = make_pair(i, pos + 1);
      }

    }
    else {
      mp[now] = make_pair(i, 1);
    }
  }
  return false;
}
void init(){
  Hash[0] = 1;
  for(int i = 1; i <= n; i++) Hash[i] = Hash[i - 1] * seed; 
}
int main(){
  cin >> n >> k;
  cin >> a;
  init();
  if(k == 1){
    cout << n << "\n";
    return 0;
  }
  int ans = 0;
  int left = 1, right = n / k; 
  while(left <= right){
    int mid = left + right >> 1;
    if(check(mid)){
      left = mid + 1;
      ans = mid;
    }
    else {
      right = mid - 1;
    }
  }
  cout << ans << "\n";
  return 0;
}

F. 苹果树

Solution

还没看