2024年冬第八届河北工业大学程序设计校赛

Posted on In Word count in article: 2.7k Reading time ≈ 9 mins.
  • 第一次线下赛，但是校内
  • 游戏本没插座，没电...
  • 老登之下众生平等，全凭手速
  • 如何田忌赛马...
  • 丢了伞

https://ac.nowcoder.com/acm/contest/93226#question

ranking

E Color Inversion

题目描述

给定一个颜色在 RGB24 模式下的 RGB 值（数值以十六进制表示），请输出该颜色的反色的 RGB 值。 如果你并不了解 RGB 颜色模型与反色的意义，请参考 Note 部分的简单介绍。

输入描述

本题的单个测试点内含有多个测试数据。记 为测试点内测试数据组数，输入数据共 行：
输入第一行仅包含一个正整数 ，代表该测试点内测试数据组数。
随后 行，为 组测试数据。每组测试数据仅有一行，每行仅包含一个字符串 ，代表题目给出颜色的 RGB 值，保证该字符串的长度必定为 ，以 # 开头，字母均为大写，且必然为合法的 RGB 值。

输出描述

输出 行。
对每组测试数据输出一行，该行应包含且仅包含一个字符串，代表你的答案。
注意：你的答案需要严格按照题目给定的 RGB 值格式输出，即字符串的长度必须为 7，必须以 "#" 开头，字母必须为大写，且必须为合法的 RGB 值，见样例。

示例

示例 1

输入
1
2
3
4
5
6
5
#1F1E33
#114514
#000000
#FFFFFF
#ABCDEF
输出
1
2
3
4
5
#E0E1CC
#EEBAEB
#FFFFFF
#000000
#543210

备注：

【数据规模与限制】

为仅由字符 #1234567890ABCDEF 组成的必然代表一个合法 RGB 值的字符串。

【名词解释】
以下内容摘自维基百科，有修改。
三原色光模式（RGB color model），又称 RGB 颜色模型，是一种加色模型，将红、绿、蓝三原色的色光以不同的比例相加混色，以合成产生各种色彩光。
RGB24，即 比特模式，每像素 位（bits per pixel, bpp）编码的 RGB 值。它使用三个 位无符号整数（ 到 ，本题中使用十六进制表示，即 到 ）表示红色、绿色和蓝色的强度。当三个数值位为最大时，显示为白色，当三个数值最小时，显示为黑色。
反色是等量混合后能够产生白色的两种颜色。在 RGB 系统中，当两个颜色的 RGB 各项值加起来都等于 的时候，该两种颜色互为反色。

Solution

16 进制转 10 进制，再把 10 进制转 16 进制
需要注意的是需要 padding 前导 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
typedef long long ll;
using namespace std;
string m = "0123456789ABCDEF0";
int hextodec(string &s, ll i, ll j) {
  int res = 0;
  char c = s[i];
  for (ll t = i; t <= j; t++, c = s[t]) {
    if ('0' <= c && c <= '9') {
      res = res * 16 + c - '0';
    } else {
      res = res * 16 + c - 'A' + 10;
    }
  }
  return res;
}
string dectohex(int d) {
  string res = "";
  while (d != 0) {
    res = m[d % 16] + res;
    d /= 16;
  }
  while (res.size() != 2) {
    res = "0" + res;
  }
  return res;
}
void solve() {
  string rgb1;
  string rgb2 = "#";
  cin >> rgb1;
  int r = hextodec(rgb1, 1, 2);
  int g = hextodec(rgb1, 3, 4);
  int b = hextodec(rgb1, 5, 6);
  r = 255 - r;
  g = 255 - g;
  b = 255 - b;
  rgb2 += dectohex(r) + dectohex(g) + dectohex(b);
  cout << rgb2 << endl;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  cin >> t;
  while (t--) solve();
  return 0;
}

J Basic Geometry Problem

题目描述

现有一长为 宽为 的矩形与一圆心为该矩形两对角线交点，半径为 的圆。记矩形与圆重叠区域的面积为 。现已知 的值，你需要求出对应的 的值。

输入描述

本题的单个测试点内含有多个测试数据。记 为测试点内测试数据组数，输入数据共 行：
输入第一行仅包含一个正整数 ，代表该测试点内测试数据组数。
随后 行，为 组测试数据。每组测试数据仅有一行，每行包含三个整数 ，意义见题目描述。

输出描述

输出 行。
对每组测试数据输出一行，代表你的答案。若该组数据有解，你需要输出一个实数，代表你求得的 的值；若无解，你的程序应当输出一个整数 。
裁判程序会首先判定你的程序是否对有解性做出了正确判断。若程序正确判断了解的存在情况且结果为有解，裁判程序会计算你的答案对应的 的值，当该值与输入数据给出的 的相对误差小于 时，你的答案即被视作正确。

示例

示例 1

输入
1
2
3
4
5
4
9 1 1
5 2 7
514 114 1000000
1000 1000 987
输出
1
2
3
4
0.582822162446
1.844815035395
-1
-1

备注:

【数据规模与限制】



【提示】
请注意题目描述中对 范围的限制。

Solution

怎么说呢，公式推了半天，卡了 1h，最后发现是弧长当面积用了。（是小糖人

先画个图
pic.png

如图所示，所求面积即为 所围成的面积，将其切成两个等腰三角形()和两个扇形()
接着我们需要求 ，以及用于求扇形夹角的
由
我们有
由题意
因而
所以
因此：

那接下来的问题就是如何求解这个问题了，根据题目给的提示，是想要你去二分的，但是我做的时候首先想到的是 牛顿迭代法 后面发现其实更麻烦了，因为这玩意在边界上导数不存在。（又被硬控好久

所以让我们来算对的导数

然后有一个迭代关系

通过以上关系即可求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
typedef long double ld;
const double PI = 3.141592653589793;
using namespace std;

ld f(ld w, ld r) {
  return 2 * r * r * asinl(w / (2 * r)) + w * sqrtl(r * r - w * w / 4);
}

ld df(ld w, ld r) {
  return r * w / sqrtl(r * r - w * w / 4) - w / sqrtl(1 - w * w / (4 * r * r)) +
         4 * r * asinl(w / (2 * r));
}

void solve() {
  ld l, w, s;
  cin >> l >> w >> s;
  ld r = w / 2;
  if (f(w, r) > s || s > PI * l * l / 4) {
    printf("-1\n");
    return;
  }
  r = w / 2 + 1e-3; // 导数在r=w/2处间断，为了可以计算，我们加上一个微扰
  ld dr = (f(w, r) - s) / df(w, r);
  while (fabs(f(w, r) - s) > 1e-6) {  // 跳出条件直接就是计算面积与实际面积差的绝对值 <= 1e06
    r -= dr;
    dr = (f(w, r) - s) / df(w, r);
  }
  if (w <= 2 * r && 2 * r <= l) // 判断r的范围是否符合条件
    printf("%.15Lf\n", r);
  else
    printf("-1\n");
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  cin >> t;
  while (t--) solve();
  return 0;
}

K Yet Another Card Game I

题目描述

<% note info no-icon %> Please note: Statement of this problem is in English. <% endnote %>

Rheanna and her friend Yasmine are about to play a game with a deck of cards, where the face values form a permutation of length . They split the deck into two equal piles and each takes one. In the game consisting of rounds, they select and play a card from their respective hands, comparing face values during each round. The player with the higher value scores a point, and the loser scores nothing. After rounds, the player with the higher total score wins. Rheanna plays first in each round, but she felt that this is unfair to her, so she turned to you before game started, expecting you can tell her if there's a sure-fire way to win. In other words, you need to determine who would win if both players play optimally.
A permutation of length is an array consisting of distinct integers from to in arbitrary order. For example, is a permutation, but is not a permutation (2 appears twice in the array), and is also not a permutation ( but there is in the array).

输入描述

Each test contains multiple test cases. Let be the number of test cases, the input file consists of lines.
The first line contains the number of test cases . The description of the test cases follows.
The first line of each test case contains one integer , as described in the problem statement.
The next line contains integers -- the face values of cards held by Rheanna.
The last line also contains integers -- the face values of cards held by Yasmine.

输出描述

You should output lines.
For each test case, output Rheanna if Rheanna wins, or Yasmine if Yasmine wins. It can be easily proven that the game will not end in a draw, namely there will always be a clear winner and loser.

示例

示例 1

输入
1
2
3
4
5
6
7
2
5
1 7 8 9 10
6 5 4 3 2
7
12 10 9 4 3 13 8
5 7 2 6 14 11 1
输出
1
2
Rheanna
Yasmine

备注:

【Constraints】

and is odd.
Arrat is a permutation of length
The sum of over all test cases does not exceed

Solution

其实是田忌赛马的加强版，没刷过同类型的，做复杂了，抄的leetcode 870.优势洗牌
参考了一下佬的代码和同学的思路，其实是双指针

  • 首先将两组数升序排序
  • 因为 Rheanna 是先手，所以我们只调整 Yasmine 的策略

对于每一轮，最优化的出牌可以用贪心来思考：

  • 因为先手，所以 Rheanna 从小到大出牌，否则大牌会被 Yasmine 的小牌浪费掉，不会是最优解
  • 如果在 Yasmine 现有的牌中能找到一张比 Rheanna 此时出的牌大且最小的牌，那么出这张牌即可得分
  • 如果找不到这样一张牌，那么我们从未使用过的牌中抽一张最小的出了摆烂，这样可以保证尽可能多的把大的牌留到最后出

具体的实现是使用双指针

  • 外层是 Rheanna 的出牌，内层是按升序找 Yasmine 中第一个比 Rheanna 出牌大的牌
  • 因为 Rheanna 出牌是递增的，所以 Yasmine 出牌（能找的话）一定是递增的，因此每次从上一个位置往后找，而不是整个序列里扫描
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define pb push_back
using namespace std;
void solve() {
  vector<int> a, b;
  int x, n, ans = 0;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> x;
    a.pb(x);
  }
  for (int i = 0; i < n; ++i) {
    cin >> x;
    b.pb(x);
  }
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  for (int i = 0, j = 0; i < n && j <= n; ++i) {
    while (j < n && b[j] < a[i]) j++;   // 尝试找到b中未使用过的，最小的比a[i]大的数
    if (j < n) ans++, j++;              // 找到了，那么这个round得分
  }
  if (ans * 2 < n)
    cout << "Rheanna" << endl;
  else
    cout << "Yasmine" << endl;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  cin >> t;
  while (t--) solve();
  return 0;
}

Reference

  • Bezime 提交的代码
  • coord_axis 提交的代码

L Acronyms

题目描述

在众多例如科学、医学和工程等涉及大量复杂术语的领域，为了简化交流、提高信息传递的效率以及加快阅读与写作速度，人们常常对专业名词进行缩写，创造简称。一种常见的缩写方式是首字母缩略词（Acronyms），即通过组合每个词的首位字母来构成新的词语。例如，"Very Important Person" 的首字母缩略词为 "VIP"。
现在，给定一个仅由小写英文字母和空格组成的词组以及一个仅由小写英文字母组成的单词，请判断该词组的首字母缩略词是否等于给定的英文单词。

输入描述

本题的单个测试点内含有多个测试数据。记 为测试点内测试数据组数，输入数据共 行：
输入第一行仅包含一个正整数 ，代表该测试点内测试数据组数。
随后 行，为 组测试数据。每组测试数据包含两行，如下：
测试样例的第一行包含一个字符串 ，代表给出的词组。词组中词与词间的空格以 "_" 字符表示。随后一行包含一个字符串 ，代表给出的英文单词。

输出描述

输出 行。
对每组测试样例，输出一行 YES 表示给出的单词等于对应词组的首字母缩略词，反之则输出一行 NO。
你可以以任何大小写形式输出，即输出 Yes，yEs，YEs，YeS，yES 与 yes 均等同 YES，NO 同理。

示例

示例 1

输入
1
2
3
4
5
6
7
3
competitive_programming
cp
hebei_university_of_technology
hebut
crychic
mygo
输出
1
2
3
YES
NO
NO

备注:

【数据规模与限制】
记 代表字符串 的长度，对于所有测试点，保证：


单个测试点中所有数据的 与 之和各自均不超过

与 为仅由小写字母和 "_" 字符所组成的字符串，保证 "_" 字符在 内部出现，且不存在两个及以上连续的 "_" 字符。

Solution

无他，唯基本字符串处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
void solve() {
  string wds;
  cin >> wds;
  string wd = "";
  string res = "";
  string a;
  cin >> a;
  for (auto c : wds) {
    if (c == '_') {
      res += wd[0];
      wd = "";
    } else {
      wd += c;
    }
  }
  if (wd != "") {
    res += wd[0];
  }
  if (res == a)
    cout << "YES" << "\n";
  else
    cout << "NO" << "\n";
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  cin >> t;
  while (t--) solve();
  return 0;
}