USACO铜级模拟赛题解
第一题：学术影响力优化
问题概述
Bessie拥有N篇论文，第i篇被引用了ci次。她可以通过撰写综述额外引用L篇自己的论文（每篇最多引用一次），使被引次数+1。求操作后的最大h指数。
核心思路
h指数的定义：存在至少h篇论文，每篇被引次数≥h的最大h值。
关键观察：增加引用只能让某些论文的引用数+1，因此h指数最多增加1。
策略：先计算原始h指数，再判断是否可以通过L次引用将其提升。
算法实现
#include <bits/stdc++.h>
using namespace std;
int paperCnt, refLimit;
int citations[100010];
int main() {
freopen("prob1.in", "r", stdin);
freopen("prob1.out", "w", stdout);
cin >> paperCnt >> refLimit;
for (int i = 1; i <= paperCnt; i++) {
cin >> citations[i];
}
sort(citations + 1, citations + paperCnt + 1);
// 从大到小找h指数
int idx = paperCnt;
while (idx >= 1 && citations[idx] >= paperCnt - idx + 1) {
idx--;
}
int hVal = paperCnt - idx; // 当前h指数
// 检查能否提升到h+1
if (citations[idx] == hVal) {
// 需要让引用数恰好为h的论文数量不超过L
int need = 0;
for (int i = paperCnt; i > idx; i--) {
if (citations[i] == hVal) need++;
}
if (need <= refLimit) {
cout << hVal + 1 << endl;
} else {
cout << hVal << endl;
}
} else {
cout << hVal << endl;
}
fclose(stdin);
fclose(stdout);
return 0;
}
第二题：实验室资历推断
问题概述
根据K篇论文的作者排序，推断N位成员间的资历关系。规则：贡献多者在前；贡献相同时按字典序排。资历高者贡献不会多于资历低者。
关键推理
若在某篇论文中，成员A排在B前面，但A的字典序大于B，则A的贡献必然多于B，故A资历更浅。
若A排在B前面且字典序更小，则无法直接判断（可能贡献多，也可能贡献相等）。
算法实现
#include <bits/stdc++.h>
using namespace std;
int pubCnt, memberCnt;
char relation[110][110];
string members[110];
string authors[110][110];
void init() {
for (int i = 1; i <= memberCnt; i++) {
for (int j = 1; j <= memberCnt; j++) {
relation[i][j] = '?';
}
relation[i][i] = 'B';
}
}
int findIndex(const string& name) {
for (int i = 1; i <= memberCnt; i++) {
if (members[i] == name) return i;
}
return -1;
}
void analyze(int p) {
for (int i = 1; i <= memberCnt; i++) {
for (int j = i + 1; j <= memberCnt; j++) {
int idx1 = findIndex(authors[p][i]);
int idx2 = findIndex(authors[p][j]);
// 检查i到j这一段是否严格字典序递增
bool sorted = true;
for (int k = i + 1; k <= j; k++) {
if (authors[p][k-1] > authors[p][k]) {
sorted = false;
break;
}
}
if (!sorted) {
// 位置靠前但字典序大，说明贡献更多，资历更浅
relation[idx1][idx2] = '0';
relation[idx2][idx1] = '1';
}
}
}
}
int main() {
freopen("prob2.in", "r", stdin);
freopen("prob2.out", "w", stdout);
cin >> pubCnt >> memberCnt;
for (int i = 1; i <= memberCnt; i++) {
cin >> members[i];
}
for (int i = 1; i <= pubCnt; i++) {
for (int j = 1; j <= memberCnt; j++) {
cin >> authors[i][j];
}
}
init();
for (int i = 1; i <= pubCnt; i++) {
analyze(i);
}
for (int i = 1; i <= memberCnt; i++) {
for (int j = 1; j <= memberCnt; j++) {
cout << relation[i][j];
}
cout << endl;
}
fclose(stdin);
fclose(stdout);
return 0;
}
第三题：草地社交匹配
问题概述
在N×M的网格中，'C'表示奶牛，'G'表示草地。两头相邻（上下左右）奶牛可通过共有的草地格子建立友谊，每个草地只能用一次。求最大友谊对数。
核心观察
每块草地最多被一对奶牛使用。问题转化为：统计能作为"会面点"的草地数量，但需排除重复计数的情况。
特殊情况：当四头奶牛形成"×"形对角分布，中心草地被多对奶牛共享时，只能算一次。
算法实现
#include <bits/stdc++.h>
using namespace std;
int rows, cols;
char grid[1010][1010];
int cowNeighbor[1010][1010]; // 每块草地相邻的奶牛数
int main() {
freopen("prob3.in", "r", stdin);
freopen("prob3.out", "w", stdout);
cin >> rows >> cols;
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
cin >> grid[i][j];
}
}
// 统计每块草地周围有多少头奶牛
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
if (grid[i][j] == 'C') {
if (grid[i-1][j] == 'G') cowNeighbor[i-1][j]++;
if (grid[i+1][j] == 'G') cowNeighbor[i+1][j]++;
if (grid[i][j-1] == 'G') cowNeighbor[i][j-1]++;
if (grid[i][j+1] == 'G') cowNeighbor[i][j+1]++;
}
}
}
int ans = 0;
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
if (grid[i][j] != 'G') continue;
if (cowNeighbor[i][j] >= 3) {
ans++; // 3头或4头奶牛，必然能匹配
} else if (cowNeighbor[i][j] == 2) {
// 检查是否为"×"形的重复情况
bool dup1 = (cowNeighbor[i+1][j-1] == 2 &&
grid[i+1][j] == 'C' && grid[i][j-1] == 'C');
bool dup2 = (cowNeighbor[i+1][j+1] == 2 &&
grid[i+1][j] == 'C' && grid[i][j+1] == 'C');
if (!dup1 && !dup2) ans++;
}
}
}
cout << ans << endl;
fclose(stdin);
fclose(stdout);
return 0;
}
