USACO近年全部测试数据_usaco测试数据资源-CSDN文库

共683个文件

html：455个

zip：228个

USACO

oj平台

测试数据

信息学竞赛

需积分: 48 7 浏览量 2022-10-08 11:35:19 上传评论 1 收藏 973.44MB ZIP 举报

USACO，全称为United States of America Computing Olympiad，是一项针对中学生的国际知名信息学竞赛。这个竞赛旨在激发学生对计算机科学的兴趣，提高他们的编程和算法设计能力。近年来，USACO吸引了全球众多优秀的学生参与，是提升信息学素养的重要途径之一。本压缩包包含了从2018年至2022年的所有USACO比赛的测试数据，这对于参赛者或者想要练习信息学竞赛题目的学习者来说是一份极其宝贵的资源。每个年度的文件（如"USACO 2022"）内部可能按照月份和难度等级（金银铜白金组别）进行组织，便于参赛者有针对性地进行训练。测试数据是编程竞赛中的关键部分，它们是验证程序正确性的标准输入输出样本。在USACO中，每个题目都会提供一系列测试用例，包括最小规模的样例到复杂度较高的测试数据，以全面评估选手的代码能否在各种情况下正确运行。通过这些数据，选手可以对自己的解决方案进行调试和优化，确保在正式比赛中能够得分。题面是比赛题目描述的文档，通常包含问题背景、输入输出格式、限制条件以及示例等信息。理解题面是解决问题的第一步，因此，选手需要仔细阅读并理解题目要求，避免因误解而导致的错误。标程，即官方提供的参考解决方案，通常是最优或最简洁的解法。通过研究标程，选手可以学习到高效的数据结构、算法和编程技巧，这对于提升编程能力非常有帮助。同时，标程还可以帮助选手检查自己的代码是否存在效率低下或者逻辑错误等问题。题解则提供了对问题的解析和解题思路，对于初学者来说尤其有价值。通过阅读题解，选手可以了解如何分析问题，如何选择合适的算法，以及如何将算法转化为代码。这有助于培养选手的思维能力和问题解决能力。这份压缩包为参与者提供了全面的USACO比赛资料，包括历年真题的测试数据、题目描述、官方标程和解题思路，是准备信息学竞赛的宝贵教材。无论是为了参赛还是自我提升，都能从中受益匪浅。通过反复实践和学习，参赛者可以不断提高自己的编程水平，掌握更高级的算法，为未来的学术和职业生涯打下坚实基础。

资源详情

资源评论

资源推荐

收起资源包目录

USACO 近年全部测试数据（683个子文件）

sol.html 31KB

sol.html 30KB

sol.html 28KB

sol.html 25KB

sol.html 22KB

sol.html 19KB

sol.html 18KB

sol.html 17KB

sol.html 16KB

sol.html 15KB

sol.html 14KB

sol.html 13KB

sol.html 12KB

pro.html 11KB

sol.html 11KB

pro.html 11KB

sol.html 11KB

sol.html 10KB

pro.html 10KB

sol.html 10KB

pro.html 10KB

sol.html 10KB

pro.html 9KB

sol.html 9KB

pro.html 9KB

sol.html 9KB

pro.html 9KB

sol.html 9KB

pro.html 9KB

sol.html 9KB

pro.html 9KB

sol.html 9KB

pro.html 9KB

sol.html 9KB

pro.html 9KB

sol.html 9KB

pro.html 9KB

共 683 条

<!DOCTYPE html> <html><head> <title>Contest Results</title> <META HTTP-EQUIV="EXPIRES" CONTENT="0"> <META HTTP-EQUIV="CACHE-CONTROL" CONTENT="NO-CACHE"> <META HTTP-EQUIV="PRAGMA" CONTENT="NO-CACHE"> <script type="text/x-mathjax-config"> MathJax.Hub.Config({ tex2jax: {inlineMath: [['$','$'], ['\$','\$']]} }); </script> <script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> <script src="https://google-code-prettify.googlecode.com/svn/loader/run_prettify.js"></script> </head> <body> (Analysis by Andi Qu, Benjamin Qi, Danny Mittal) For any subrectangle we can construct a graph where there exists an edge separating two cells if they are of different colors. For example, the graph for <pre> AAB BBA BBB </pre> would be <pre> ._._._. | | | ._._._. | | | . . ._. | | ._._._. </pre> The main idea is to use <a href='https://en.wikipedia.org/wiki/Euler_characteristic'>Euler's formula</a> for planar graphs. This equation states that $F = E - V + C + 1$, where <ul><li>$F\implies$# of faces</li><li>$E\implies$# of edges</li><li>$V\implies$# of vertices</li><li>$C\implies$# of connected components</li></ul> So in the above example, <ul><li>$F=4+1=5,$ where $1$ comes from the face consisting of everything outside of the subrectangle.</li><li>$E=18,$ the total number of cell borders (horizontal and vertical unit segments).</li><li>$V=4\cdot 4=16,$ one for each cell corner (dot).</li><li>$C=2,$ one for the vertex that has no edges coming out of it and one for the remaining vertices.</li></ul> So the answer for each candidate is just $E - V + C.$ $V$ depends only on the dimensions of the subrectangle, and $E$ can be found in $O(1)$ time using prefix sums. The main challenge is finding $C$, the number of connected components completely inside the subrectangle (plus one for the component corresponding to the border). We can use the same concept as <a href='https://csacademy.com/contest/romanian-ioi-2017-selection-1/task/rooms/'>Romanian IOI Selection 2017 "Rooms"</a>, which was the inspiration for this problem. For each component, call its topmost vertex "special". Then the number of special vertices that lie strictly within the border of the subrectangle is a good approximation for the number of components completely inside the subrectangle, and can also be computed via prefix sums. However, it is possible that a component does not lie completely within the subrectangle but its special vertex does, leading to an overcount. Notice that such components must have at least one vertex on the border of the subrectangle, so simply traverse the border of the subrectangle and delete all such components from the count. This solution takes $\mathcal{O}(MN + Q(M + N))$ time in total. <pre class='prettyprint'> /* Paint by Letters Andi Qu - F = E - V + C + 1 - Every corner of a cell is a node - Every side of a cell is an edge if it is between 2 different colours - DFS to find connected components - To check if a component is completely inside a query rectangle, traverse the perimeter of the rectangle - Complexity: O(MN + Q(M + N)) */ #include <bits/stdc++.h> #define FOR(i, x, y) for (int i = x; i < y; i++) using namespace std; int n, m, q; char grid[2001][2001]; pair<int, int> special[2002][2002], d[4]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int s_pref[2002][2002], v_pref[2002][2002], h_pref[2002][2002]; bool deleted[2002][2002]; bool inside(int x, int y, int nx, int ny) { if (!(~nx && ~ny && nx <= n + 1 && ny <= m + 1)) return false; if (nx == x + 1) return grid[x][y] != grid[x][y - 1]; if (nx == x - 1) return grid[nx][y] != grid[nx][y - 1]; if (ny == y + 1) return grid[x][y] != grid[x - 1][y]; return grid[x][ny] != grid[x - 1][ny]; } bool outside(int x, int y, int x1, int y1, int x2, int y2) { int a = special[x][y].first, b = special[x][y].second; if (a > x1 && a <= x2 && b > y1 && b <= y2 && !deleted[a][b]) { deleted[a][b] = true; return true; } return false; } void deactivate(int x, int y) { int a = special[x][y].first, b = special[x][y].second; deleted[a][b] = false; } void dfs(int x, int y) { FOR(i, 0, 4) { int nx = x + d[i].first, ny = y + d[i].second; if (inside(x, y, nx, ny)) { if (nx == x + 1) v_pref[x][y] = 1; else if (nx == x - 1) v_pref[nx][y] = 1; else if (ny == y + 1) h_pref[x][y] = 1; else h_pref[x][ny] = 1; if (!special[nx][ny].first) { special[nx][ny] = special[x][y]; dfs(nx, ny); } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); // freopen("paint.in", "r", stdin); // freopen("paint.out", "w", stdout); cin >> n >> m >> q; FOR(i, 1, n + 1) FOR(j, 1, m + 1) cin >> grid[i][j]; FOR(i, 1, n + 2) FOR(j, 1, m + 2) if (!special[i][j].first) { s_pref[i][j] = 1; special[i][j] = {i, j}; dfs(i, j); } FOR(i, 1, n + 2) FOR(j, 1, m + 2) { s_pref[i][j] += s_pref[i - 1][j] + s_pref[i][j - 1] - s_pref[i - 1][j - 1]; v_pref[i][j] += v_pref[i - 1][j] + v_pref[i][j - 1] - v_pref[i - 1][j - 1]; h_pref[i][j] += h_pref[i - 1][j] + h_pref[i][j - 1] - h_pref[i - 1][j - 1]; } while (q--) { int x1, x2, y1, y2; cin >> x1 >> y1 >> x2 >> y2; if (x1 > x2) swap(x1, x2); if (y1 > y2) swap(y1, y2); int E = v_pref[x2][y2] - v_pref[x2][y1] - v_pref[x1 - 1][y2] + v_pref[x1 - 1][y1] + h_pref[x2][y2] - h_pref[x2][y1 - 1] - h_pref[x1][y2] + h_pref[x1][y1 - 1]; int V = (x2 - x1) * (y2 - y1); int C = s_pref[x2][y2] - s_pref[x2][y1] - s_pref[x1][y2] + s_pref[x1][y1]; // Delete connected components not entirely inside the query rectangle FOR(i, x1, x2 + 2) { if (outside(i, y2 + 1, x1, y1, x2, y2)) C--; if (outside(i, y1, x1, y1, x2, y2)) C--; } FOR(i, y1, y2 + 2) { if (outside(x2 + 1, i, x1, y1, x2, y2)) C--; if (outside(x1, i, x1, y1, x2, y2)) C--; } FOR(i, x1, x2 + 2) { deactivate(i, y2 + 1); deactivate(i, y1); } FOR(i, y1, y2 + 2) { deactivate(x2 + 1, i); deactivate(x1, i); } cout << E - V + C + 1 << '\n'; } return 0; } </pre> A similar approach involves treating cells as vertices, two adjacent cells of the same color as an edge, and a cycle of a single color (as described in the problem statement) which contains no smaller cycles as a face. Then we can use Euler's formula to count the number of connected components ($V-E+F$). Partial credit corresponded to no faces, faces of a single type (a $2\times 2$ square of a single color), and faces of two types (in addition to the one previously mentioned, a $3\times 3$ square with the border of a single color and the center square of a different color). Some additional problems for which you can use Euler's formula can be found <a href='https://usaco.guide/adv/eulers-formula'>here.</a> A completely different approach is to simply optimize th