• 2022牛客多校第一场解题报告

    A.Villages: Landlines
     

    思路:签到,直接划分区间,然后计算这些区间的距离之和即可

    代码:

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8. #include 
    9. #include 
    10. #include 
    11. #include 
    12. #include 
    13. #include 
    14. #include 
    15. #include 
    16. #include 
    17. #include 
    18. #define IOS ios::sync_with_stdio(false), cin.tie(0)
    19. #define int long long
    20. #define ll long long
    21. #define ull unsigned long long
    22. #define PII pair
    23. #define PDI pair
    24. #define PDD pair
    25. #define debug(a) cout << #a << " = " << a << endl
    26. #define all(x) (x).begin(), (x).end()
    27. #define mem(x, y) memset((x), (y), sizeof(x))
    28. #define lbt(x) (x & (-x))
    29. #define SZ(x) ((x).size())
    30. #define wtn(x) wt(x), printf("\n")
    31. #define wtt(x) wt(x), printf(" ")
    32. #define inf 0x3f3f3f3f
    33. #define INF 0x3f3f3f3f3f3f3f3f
    34. #define MOD 998244353
    35. #define eps 1e-8
    36. int T = 1;
    37. using namespace std;
    38. inline int rd() {
    39.     int x = 0, y = 1; char c = getchar();
    40.     while (!isdigit(c)) { if (c == '-') y = -1; c = getchar(); }
    41.     while (isdigit(c)) { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
    42.     return x *= y;
    43. }
    44. inline void wt(int x) {
    45.     if (x < 0)x = -x, putchar('-'); ll sta[100], top = 0;
    46.     do sta[top++] = x % 10, x /= 10; while (x);
    47.     while (top) putchar(sta[--top] + '0');
    48. }
    49. const int N = 2e5 + 10;
    50. int n;
    51. struct rec {
    52. 	int l, r;
    53. 	bool operator< (const rec& i) {
    54. 		return l < i.l;
    55. 	}
    56. } cor[N];
    57. void solve() {
    58. 	cin >> n;
    59. 	for (int i = 1; i <= n; ++i) {
    60. 		int x, r;
    61. 		cin >> x >> r;
    62. 		cor[i].l = x - r, cor[i].r = x + r;
    63. 	}
    64. 	sort(cor + 1, cor + 1 + n);
    65. 	vector seg;
    66. 	int cur, l_;
    67. 	for (int i = 1, j = 0; i <= n; ++i) {
    68. 		l_ = cor[i].l;
    69. 		cur = cor[i].r;
    70. 		while (j + 1 <= n && cor[j + 1].l <= cur) {
    71. 			cur = max(cur, cor[j + 1].r);
    72. 			++j;
    73. 		}
    74. 		seg.emplace_back(l_, cur);
    75. 		i = j;
    76. 	}
    77. 	int ans = 0;
    78. 	for (int i = 1; i < SZ(seg); ++i) {
    79. 		ans += seg[i].first - seg[i - 1].second;
    80. 	}
    81. 	cout << ans << "\n";
    82. }
    83. signed main() {
    84. 	IOS;
    85. 	// cin >> T;
    86. 	while (T--) solve();
    87. }

    C-Grab the Seat!

     思路:

    我们要求被留下的格子,可以对每一行单独求,注意到,每一行最多留下的格子取决于上边界延申的直线与这行的交点最左边与下边界延申的直线与这行的交点的最左边的靠左边的点决定(图中该行是蓝色部分).然后我们对每一行直线上下边界延申的直线求交点,然后取最左边的值,最后累加起来就是答案了.

    技巧:分开枚举

    代码:

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8. #include 
    9. #include 
    10. #include 
    11. #include 
    12. #include 
    13. #include 
    14. #include 
    15. #include 
    16. #include 
    17. #include 
    18. #define IOS ios::sync_with_stdio(false), cin.tie(0)
    19. #define int long long
    20. #define ll long long
    21. #define ull unsigned long long
    22. #define PII pair
    23. #define PDI pair
    24. #define PDD pair
    25. #define debug(a) cout << #a << " = " << a << endl
    26. #define all(x) (x).begin(), (x).end()
    27. #define mem(x, y) memset((x), (y), sizeof(x))
    28. #define lbt(x) (x & (-x))
    29. #define SZ(x) ((x).size())
    30. #define wtn(x) wt(x), printf("\n")
    31. #define wtt(x) wt(x), printf(" ")
    32. #define inf 0x3f3f3f3f
    33. #define INF 0x3f3f3f3f3f3f3f3f
    34. #define MOD 998244353
    35. #define eps 1e-8
    36. int T = 1;
    37. using namespace std;
    38. inline int rd() {
    39.     int x = 0, y = 1; char c = getchar();
    40.     while (!isdigit(c)) { if (c == '-') y = -1; c = getchar(); }
    41.     while (isdigit(c)) { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
    42.     return x *= y;
    43. }
    44. inline void wt(int x) {
    45.     if (x < 0)x = -x, putchar('-'); ll sta[100], top = 0;
    46.     do sta[top++] = x % 10, x /= 10; while (x);
    47.     while (top) putchar(sta[--top] + '0');
    48. }
    49. const int N = 2e5 + 10;
    50. int n;
    51. struct rec {
    52. 	int l, r;
    53. 	bool operator< (const rec& i) {
    54. 		return l < i.l;
    55. 	}
    56. } cor[N];
    57. void solve() {
    58. 	cin >> n;
    59. 	for (int i = 1; i <= n; ++i) {
    60. 		int x, r;
    61. 		cin >> x >> r;
    62. 		cor[i].l = x - r, cor[i].r = x + r;
    63. 	}
    64. 	sort(cor + 1, cor + 1 + n);
    65. 	vector seg;
    66. 	int cur, l_;
    67. 	for (int i = 1, j = 0; i <= n; ++i) {
    68. 		l_ = cor[i].l;
    69. 		cur = cor[i].r;
    70. 		while (j + 1 <= n && cor[j + 1].l <= cur) {
    71. 			cur = max(cur, cor[j + 1].r);
    72. 			++j;
    73. 		}
    74. 		seg.emplace_back(l_, cur);
    75. 		i = j;
    76. 	}
    77. 	int ans = 0;
    78. 	for (int i = 1; i < SZ(seg); ++i) {
    79. 		ans += seg[i].first - seg[i - 1].second;
    80. 	}
    81. 	cout << ans << "\n";
    82. }
    83. signed main() {
    84. 	IOS;
    85. 	// cin >> T;
    86. 	while (T--) solve();
    87. }

    D-Mocha and Railgun

    思路:注意到,当AB方向平行与OQ方向时,答案最大.

    然后用简单的勾股定理和三角函数知识可以解得ans

    代码:

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8. #include 
    9. #include 
    10. #include 
    11. #include 
    12. #include 
    13. #include 
    14. #include 
    15. #include 
    16. #include 
    17. #include 
    18. #define IOS ios::sync_with_stdio(false), cin.tie(0)
    19. #define int long long
    20. #define ll long long
    21. #define ull unsigned long long
    22. #define PII pair
    23. #define PDI pair
    24. #define PDD pair
    25. #define debug(a) cout << #a << " = " << a << endl
    26. #define all(x) (x).begin(), (x).end()
    27. #define mem(x, y) memset((x), (y), sizeof(x))
    28. #define lbt(x) (x & (-x))
    29. #define SZ(x) ((x).size())
    30. #define wtn(x) wt(x), printf("\n")
    31. #define wtt(x) wt(x), printf(" ")
    32. #define pi acos(-1)
    33. #define inf 0x3f3f3f3f
    34. #define INF 0x3f3f3f3f3f3f3f3f
    35. #define MOD 998244353
    36. #define eps 1e-8
    37. int T = 1;
    38. using namespace std;
    39. inline int rd() {
    40.     int x = 0, y = 1; char c = getchar();
    41.     while (!isdigit(c)) { if (c == '-') y = -1; c = getchar(); }
    42.     while (isdigit(c)) { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
    43.     return x *= y;
    44. }
    45. inline void wt(int x) {
    46.     if (x < 0)x = -x, putchar('-'); ll sta[100], top = 0;
    47.     do sta[top++] = x % 10, x /= 10; while (x);
    48.     while (top) putchar(sta[--top] + '0');
    49. }
    50. void solve() {
    51. 	double rc, x, y, d;
    52. 	scanf("%lf %lf %lf %lf", &rc, &x, &y, &d);
    53. 	double n = sqrt(x * x + y * y);
    54. 	double l = n - d, r = n + d;
    55. 	double d1 = sqrt(rc * rc - l * l), d2 = sqrt(rc * rc - r * r);
    56. 	double dd = abs(d1 - d2), len = sqrt(d * d * 4 + dd * dd);
    57. 	double cost = len / (rc * 2.0), theta = acos(cost);
    58. 	theta = pi - theta * 2.0;
    59. 	printf("%.6f\n", rc * theta);
    60. }
    61. signed main() {
    62. 	// IOS;
    63. 	// cin >> T;
    64. 	T = rd();
    65. 	while (T--) solve();
    66. }

    G.签到题

    I.Chiitoitsu

    思路:设f(i,j)为还剩i张牌没拿,手中还剩j张单牌,然后有一个贪心策略就是,如果拿到跟手上配对以后就配对,没配对直接扔掉.有状态转移

    f(i,j)=1+\left\{\begin{matrix} \frac{i-j*3}{i}*f(i-1,j) & \\ \frac{j*3}{i}*f(i-1,j-2)& \end{matrix}\right.

    然后用记忆化搜索实现(期望dp倒着来)

    代码:

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8. #include 
    9. #include 
    10. #include 
    11. #include 
    12. #include 
    13. #include 
    14. #include 
    15. #include 
    16. #include 
    17. #include 
    18. #define IOS ios::sync_with_stdio(false), cin.tie(0)
    19. #define int long long
    20. #define ll long long
    21. #define ull unsigned long long
    22. #define PII pair
    23. #define PDI pair
    24. #define PDD pair
    25. #define debug(a) cout << #a << " = " << a << endl
    26. #define all(x) (x).begin(), (x).end()
    27. #define mem(x, y) memset((x), (y), sizeof(x))
    28. #define lbt(x) (x & (-x))
    29. #define SZ(x) ((x).size())
    30. #define wtn(x) wt(x), printf("\n")
    31. #define wtt(x) wt(x), printf(" ")
    32. #define inf 0x3f3f3f3f
    33. #define INF 0x3f3f3f3f3f3f3f3f
    34. #define MOD 1000000007
    35. #define eps 1e-8
    36. int T = 1;
    37. using namespace std;
    38. inline int rd() {
    39.     int x = 0, y = 1; char c = getchar();
    40.     while (!isdigit(c)) { if (c == '-') y = -1; c = getchar(); }
    41.     while (isdigit(c)) { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
    42.     return x *= y;
    43. }
    44. inline void wt(int x) {
    45.     if (x < 0)x = -x, putchar('-'); ll sta[100], top = 0;
    46.     do sta[top++] = x % 10, x /= 10; while (x);
    47.     while (top) putchar(sta[--top] + '0');
    48. }
    49. int qmi(int a, int k, int p) {
    50. 	int res = 1;
    51. 	while (k) {
    52. 		if (k & 1) res = res * a % p;
    53. 		k >>= 1;
    54. 		a = a * a % p;
    55. 	}
    56. 	return res;
    57. }
    58. int inv(int x) {return qmi(x, MOD - 2, MOD);}
    59. int f[150][30];
    60. int dp(int i, int j) {
    61. 	if (j == -1) return 0;
    62. 	if (f[i][j] != -1) return f[i][j];
    63. 	int ans = 0;
    64. 	ans += (i - j * 3) * inv(i) % MOD * dp(i - 1, j) % MOD;
    65. 	ans += (j * 3) * inv(i) % MOD * dp(i - 1, j - 2) % MOD;
    66. 	return f[i][j] = (ans + 1) % MOD;
    67. }
    68. void solve() {
    69. 	string s;
    70. 	cin >> s;
    71. 	mapint> cnt;
    72. 	int cc = 0;
    73. 	for (int i = 0; i < SZ(s); i += 2) {
    74. 		string ts;
    75. 		ts += s[i]; ts += s[i + 1];
    76. 		if (cnt[ts]) ++cc;
    77. 		++cnt[ts];
    78. 	}
    79. 	cout << (dp(123, 13 - cc * 2) + MOD) % MOD << '\n';
    80. }
    81.  
    82. signed main() {
    83. 	IOS;
    84. 	mem(f, -1);
    85. 	cin >> T;
    86. 	// T = rd();
    87. 	for (int i = 1; i <= T; ++i) {cout << "Case #" << i << ": "; solve();}
    88. }

    J.Serval and Essay

    思路:如果发现一个集合只有两个元素,直接合并两个点能通向的点,然后修改那个点的from点,然后每次从小集合合并到大集合,也就是启发式合并,时间复杂度是O(nlogn)级别的.

    代码:

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8. #include 
    9. #include 
    10. #include 
    11. #include 
    12. #include 
    13. #include 
    14. #include 
    15. #include 
    16. #include 
    17. #include 
    18. #define IOS ios::sync_with_stdio(false), cin.tie(0)
    19. #define int long long
    20. #define ll long long
    21. #define ull unsigned long long
    22. #define PII pair
    23. #define PDI pair
    24. #define PDD pair
    25. #define debug(a) cout << #a << " = " << a << endl
    26. #define all(x) (x).begin(), (x).end()
    27. #define mem(x, y) memset((x), (y), sizeof(x))
    28. #define lbt(x) (x & (-x))
    29. #define SZ(x) ((x).size())
    30. #define wtn(x) wt(x), printf("\n")
    31. #define wtt(x) wt(x), printf(" ")
    32. #define inf 0x3f3f3f3f
    33. #define INF 0x3f3f3f3f3f3f3f3f
    34. #define MOD 1000000007
    35. #define eps 1e-8
    36. int T = 1;
    37. using namespace std;
    38. inline int rd() {
    39.     int x = 0, y = 1; char c = getchar();
    40.     while (!isdigit(c)) { if (c == '-') y = -1; c = getchar(); }
    41.     while (isdigit(c)) { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
    42.     return x *= y;
    43. }
    44. inline void wt(int x) {
    45.     if (x < 0)x = -x, putchar('-'); ll sta[100], top = 0;
    46.     do sta[top++] = x % 10, x /= 10; while (x);
    47.     while (top) putchar(sta[--top] + '0');
    48. }
    49. //记录每个点的入点和出点
    50. //当一个点的入点只有一个时,就合并两个出点的集合,最后最大的集合的大小就是能到达的点的最大数量
    51. const int N = 2e5 + 10;
    52. set<int> from[N], to[N];
    53. int n, fa[N], sz[N];
    54. int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
    55. void merge(int x, int y) {
    56. 	x = find(x), y = find(y);
    57. 	if (x == y) return;
    58. 	if (SZ(to[x]) < SZ(to[y])) swap(x, y);
    59. 	fa[y] = x, sz[x] += sz[y];
    60. 	vector meg;
    61. 	for (auto t : to[y]) {
    62. 		to[x].insert(t);
    63. 		from[t].erase(y);
    64. 		from[t].insert(x);
    65. 		if (SZ(from[t]) == 1) meg.emplace_back(t, x);
    66. 	}
    67. 	for (auto [x, y] : meg) merge(x, y);
    68. }
    69. void solve() {
    70. 	n = rd();
    71. 	for (int i = 1; i <= n; ++i) {
    72. 		int k = rd();
    73. 		for (int j = 1, x; j <= k; ++j) {
    74. 			x = rd();
    75. 			to[x].insert(i);
    76. 			from[i].insert(x);
    77. 		}
    78. 	}
    79. 	for (int i = 1; i <= n; ++i) fa[i] = i, sz[i] = 1;
    80. 	for (int i = 1; i <= n; ++i) if (SZ(from[i]) == 1) merge(i, *from[i].begin());
    81. 	int ans = 0;
    82. 	for (int i = 1; i <= n; ++i) ans = max(ans, sz[i]);
    83. 	wtn(ans);
    84. 	for (int i = 1; i <= n; ++i) to[i].clear(), from[i].clear();
    85. }
    86. signed main() {
    87. 	// IOS;
    88. 	// cin >> T;
    89. 	T = rd();
    90. 	for (int i = 1; i <= T; ++i) { printf("Case #%d: ", i); solve();}
    91. }

  • 相关阅读:
    喜报 | 迪捷软件荣获“首位立区幸福越城突出贡献奖”
    uni-app下载文件、获取文件夹下的文件、删除文件夹里的文件
    zabbix安装部署
    Python之并发编程一背景知识
    案例：恒流负载导致的启动故障
    【SpringBoot】SpringBoot 读取配置文件中的自定义属性的 5 种方法
    git&&gitHub
    查找算法思想及代码——C语言
    【php毕业设计源码】PHP实验室安全系统设计与实现
    Dubbo:DubboAdmin简介及安装
  • 原文地址：https://blog.csdn.net/CK1513710764/article/details/126011949