2025乔斯复赛集训十连测-(第十场)

参考标程

A

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

int a[11];

int main() {
  freopen("money.in", "r", stdin);
  freopen("money.out", "w", stdout);
  for (int i = 1; i <= 9; i++) cin >> a[i];
  a[0] = 1, a[10] = 10000;
  double mx = 0;
  int year = 0;
  for (int i = 1; i <= 10; i++) {
    if (a[i] / a[i - 1] > mx) {
      mx = a[i] / a[i - 1];
      year = i;
    }
  }
  cout << year;
  return 0;
}

B

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

map<char, int> mp;

struct Node {
  char c;
  int num;
};
bool cmp(Node x, Node y) {
  if (x.num != y.num) return x.num > y.num;
  return x.c < y.c;
} 
int main() {
  freopen("title.in", "r", stdin);
  freopen("title.out", "w", stdout);
  string s;
  getline(cin, s);
  for (int i = 0; i < s.size(); i++) {    //统计每个字符的出现次数
    if(s[i] != ' ') mp[s[i]]++;
  }
  vector<Node> a;
  for (auto x : mp) {   //遍历 map 中的每个元素
    a.push_back((Node){x.first, x.second});
  }
  sort (a.begin(), a.end(), cmp);
  for (auto x : a) cout << x.c;
  return 0;
}

C

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

int T, M, a, b, c, fenzi, fenmu; 

void yuefen() {   //分子,分母约分
  bool f = (fenzi < 0 ? 1 : 0);
  if (f) fenzi *= -1;       //先变成正数，然后进行约分
  int k = __gcd(fenzi, fenmu);
  fenzi /= k, fenmu /= k;
  if (f) fenzi *= -1;
}
int k, t;
void calcu(int n) {   //算出 k*sqrt(w)
  for (int i = sqrt(n); i >= 1; i--) {
    int w = n / i / i;
    if (w * i * i == n) {
      k = i, t = w;
      return;
    }
  }
}
int main() {
  freopen("uqe.in", "r", stdin);
  freopen("uqe.out", "w", stdout);
  cin >> T >> M;
  while (T--) {
    cin >> a >> b >> c;
    int delta = b * b - 4 * a * c;
    if (delta < 0) { cout << "NO\n"; continue; }    //不存在
    if (a < 0) a = -a, b = -b, c = -c;
    int sq = sqrt(delta);
    if (sq * sq == delta) {   //如果 delta 能够开平方根
      fenzi = -b + sq, fenmu = 2 * a;
      yuefen();
      if (fenmu == 1) printf("%d\n", fenzi);
      else printf("%d/%d\n", fenzi, fenmu);
    }
    else {      //如果 delta 不能开平方根
      fenzi = -b, fenmu = a * 2;
      yuefen();
      if (b != 0) {    //输出前半部分
        if (fenmu == 1) printf("%d", fenzi);
        else printf("%d/%d", fenzi, fenmu);
        printf("+");
      }
      calcu(delta);       //计算后半部分
      fenzi = k, fenmu = a * 2;
      yuefen();
      if (fenzi == 1 && fenmu == 1) printf("sqrt(%d)", t);
      else if (fenzi == 1) printf("sqrt(%d)/%d", t, fenmu);
      else if (fenmu == 1) printf("%d*sqrt(%d)", fenzi, t);
      else printf("%d*sqrt(%d)/%d", fenzi, t, fenmu);
      printf("\n");
    }
  }
  return 0;
}

D

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

#define int long long
#define inf 0x3f3f3f3f
const int N = 1e4 + 5;
int n, m, k, vis[N][105];
struct Edge { int v, w; };
vector<Edge> G[N];
struct Node {
  int x, t;     
  bool operator < (const Node &b) const {
    return t > b.t;
  }
}d[N][105];   //d[i][j]表示 起点到 i 点的时间 %k 的值为 j 的最短消耗时间

void Dij(int st) {
  for (int i = 1; i <= n; i++)      //初始化，将所有点到起点的距离初始化成无穷大
    for (int j = 0; j < k; j++) 
      d[i][j].x = i, d[i][j].t = inf;

  priority_queue<Node> q;
  d[st][0].t = 0;
  q.push(d[st][0]);     //放入起点
  while (q.size()) {
    int u = q.top().x, t = q.top().t; 
    q.pop();
    if (vis[u][t % k]) continue;
    vis[u][t % k] = 1;
    for (auto e : G[u]) {       //枚举 u 的所有出边
      int v = e.v, w = e.w, nt;
      if (t >= w) nt = t;     //如果当前的时刻能够直接通过这条路
      else nt = ceil((w - t) * 1.0 / k) * k + t;  //如果不能通过，我们需要通过推迟起点的出发时间达到通过这条路
      if (d[v][(nt + 1) % k].t > nt + 1) {
        d[v][(nt + 1) % k].t = nt + 1;
        q.push((Node){v, nt + 1});
      } 
    }
  }
}
signed main() {
  freopen("bus.in", "r", stdin);
  freopen("bus.out", "w", stdout);
  cin >> n >> m >> k;
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    G[u].push_back((Edge){v, w});
  }
  Dij(1);
  cout << (vis[n][0] ? d[n][0].t : -1);
  return 0;
}