刷题-USACO Section 1 题目个人选做

时间：2023-02-12 16:30:00 控制电缆kyv绝缘电阻500m

马上就要打CSP最近准备刷一刷USACO section1和2，先刷刷section 练手吧，保证PJ1=、TG能够进入暴力分。

[P1208USACO1.3] 混合牛奶 Mixing Milk 对于相对简单的贪婪问题，首先对单价进行排序。如果单价相同，则对最大产量进行排序，然后运行成本。

#include  #include   using namespace std;  typedef long long ll; const int MAXN = 2e6   100; ll n, m; ll ans; struct node { 
         ll p, maxt; } a[MAXN];  bool cmp(node x, node y) { 
         if(x.p != y.p) return x.p < y.p;  return x.maxt > y.maxt;  }   int main() { 
         cin >> n >> m;  for(int i=1; i<=m; i ) { 
          cin >> a[i].p >> a[i].maxt;   }  sort(a 1, a 1 m, cmp);  for(int i=1; i<=m; i++) { 
       
		if(a[i].maxt <= n) { 
       
			n -= a[i].maxt;
			ans += a[i].p*a[i].maxt;
		} else { 
       
			ans += n*a[i].p;
			n = 0;
			break;
		}
	}
	cout << ans;
	return 0;
}

[P1209 USACO1.3]修理牛棚 Barn Repair 贪心，我刚开始想的是把所有牛所处的牛棚铺个木板，然后贪心地连接，但是相邻的木板处理起来码量稍大，所以可以反过来想，先把所有牛棚覆盖一个大木板，再贪心地断开就可以了，这里只需断开m-1次，因为大木板也算一个木板

#include 
#include 

using namespace std;

const int MAXN = 205; 
int m, s, c, a[MAXN], ans;
bool broke[MAXN];

int main() { 
       
	cin >> m >> s >> c;
	int l = 0x3f3f3f3f, r = 0;
	for(int i=1; i<=c; i++) { 
       
		cin >> a[i];
		l = min(l, a[i]);
		r = max(r, a[i]);
	}
	ans = r - l + 1;
	sort(a+1, a+1+c);
	for(int i=1; i<m; i++) { 
       
		int maxn = 0, pos;
		for(int j=1; j<c; j++) { 
       
			if(!broke[j] && a[j+1] - a[j] - 1 > maxn) { 
       
				maxn = a[j+1] - a[j] - 1;
				pos = j;
			}
		}
		broke[pos] = true;
		ans -= maxn;
	}
	cout << ans;
	return 0;
}

[P1444 USACO1.3]虫洞 wormhole n<=12，明显的暴力，只不过对我这种普及组菜鸟来说也不会，看了发题解。。。首先，枚举所有可能的情况，时间复杂度是(n-1)*(n-3)*(n-5)*…*1，对于12这种小数据完全足够。每搜出一种虫洞匹配情况，便枚举每个虫洞，使其作为起点（一头钻进去），用while循环判断即可。比较坑的地方有两点：

钻入和爬出同一个虫洞并不代表陷入死循环，很容易HACK一组数据，这里就不写了，题解里一大堆
输入的数据并不是行列，而是按照列行写的

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KyV8GiVR-1629874191274)(C:\Users\k\AppData\Roaming\Typora\typora-user-images\image-20210823143400532.png)]

#include 
#include 
#include 

using namespace std;

int n, f[15], ans, to[15];
bool vis[15][2];
struct node { 
       
	int x, y;
} a[15];

bool cmp(node p, node q) { 
       
	if(p.x != q.x) return p.x < q.x;
	return p.y < q.y;
}

void input() { 
       
	cin >> n;
	for(int i=1; i<=n; i++) { 
       
		cin >> a[i].y >> a[i].x;
	}
	sort(a+1, a+1+n, cmp);
}

bool check() { 
       
	for(int i=1; i<=n; i++) { 
       
		memset(vis, false, sizeof(vis));
		int now = i;
		while(1) { 
       
			now = f[now+1];
			if(vis[now][1]) return true;
			vis[now][1] = true;
			if(a[now].x != a[now+1].x) break;
			if(vis[now+1][0]) return true;
			vis[now+1][0] = true;
		}
	}
	return false;
}

void dfs(int x) { 
       
	if(f[x]) { 
       
		dfs(x+1);
		return;
	}
	if(x == n+1) { 
       
		ans += check();
		/* if(check() == 1) { for(int i=1; i<=n; i++) { cout << "(" << i << ", " << f[i] << ") "; } cout << endl; } */
		return;
	}
	for(int j=x+1; j<=n; j++) { 
       
		if(!f[j]) { 
       
			f[x] = j, f[j] = x;
			dfs(x+1);
			f[x] = 0, f[j] = 0;
		}
	}
}

int main() { 
       
	input();
	dfs(1);
	cout << ans;
	return 0;
}

[P2693 USACO1.3]号码锁极其愚蠢的暴力枚举，甚至循环里都不需要剪枝（懒得写了），没什么好说的，感觉普及-只能勉强算上

#include 

using namespace std;

const int MAXN = 105;
int n, x, y, z, a, b, c;
bool judge[MAXN][MAXN];

int main() { 
       
	cin >> n >> x >> y >> z >> a >> b >> c;
	for(int i=1; i<=n; i++) { 
       
		if(i == n-1) judge[i][n-3] = judge[i][n-2] = judge[i][n-1] = judge[i][n] = judge[i][1] = true;
		else if(i == n) judge[i][n-2] = judge[i][n-1] = judge[i][n] = judge[i][1] = judge[i][2] = true;
		else if(i == 1) judge[i][n-1] = judge[i][n] = judge[i][1] = judge[i][2] = judge[i][3] = true;
		else if(i == 2) judge[i][n] = judge[i][1] = judge[i][2] = judge[i][3] = judge[i][4] = true;
		else judge[i][i-2] = judge[i][i-1] = judge[i][i] = judge[i][i+1] = judge[i][i+2] = true;
	}
	int ans = 0;
	for(int i=1; i<=n; i++) { 
       
		for(int j=1; j<=n; j++) { 
       
			for(int k=1; k<=n; k++) { 
       
				if(judge[i][x] && judge[j][y] && judge[k][z]
				|| judge[i][a] && judge[j][b] && judge[k][c]) { 
       
					ans ++;
				}
			}
		}
	}
	cout << ans;
	return 0;
}

[P1214 USACO1.4]等差数列 Arithmetic Progressions 一道等差数列的题目，我们先生成出所有双平方数，丢进桶里面。桶有两个好处：

去重。之后输出答案不需要一个一个判重了
优化时间。

然后枚举前2个数，因为确定2个数就能确定整个等差数列的形式。第三重循环确保存在等差数列。但是，这里需要加一个小剪枝，在第三重循环前，需要提前把末项比 $m * m + m * m$ 大的情况break（代码注释中有详细正确性证明）

#include 
#include 

using namespace std;

const int MAXN = 5e5 + 100;
int n, m, a[MAXN], cnt, bucket[MAXN], tot;
bool isnone = true;
struct node { 
       
	int a, cha;
} ans[MAXN];

bool cmp(node x, node y) { 
       
	if(x.cha != y.cha) return x.cha < y.cha;
	return x.a < y.a;
}

int main() { 
       
	cin >> n >> m;
	for(int i=0; i<=m; i++) { 
       
		for(int j=0; j<=m; j++) { 
       
			bucket[i*i+j*j] = 1;
		}
	}
	for(int i=0; i<=m*m+m*m; i++) { 
       
		if(bucket[i]) { 
       
			for(int j=i+1; j<=m*m+m*m; j++) { 
       
				if(bucket[j]) { 
       
					int b = j - i;
					bool flag = true;
					
					if(j + b*(n-2) > m*m+m*m) { 
        // 剪枝：因为此时如果继续循环，j不断增大，而b明显也在不断增大，所以在i更新前一直不会满足条件，故直接break
						break;
					}
					int k = j + b;
					for(int l=3; l<=n; l++) { 
       
						if(!bucket[k]) { 
       
							flag = false;
							break;
						}
						k += b;
					}
					if(flag) { 
       
						isnone = false;
						tot ++;
						ans[tot].a = i;
						ans[tot].cha = b;
					}
				}
			}
		}
	}
	sort(ans+1, ans+tot+1, cmp);
	if(isnone) cout << "NONE";
	else { 
       
		for(int i=1; i<=tot; i++)
			cout << ans[i].a << " " << ans[i].cha << endl;
	}
	return 0;
}

[P1215 USACO1.4]母亲的牛奶 Mother’s Milk 只要看到数据范围就知道是暴力BFS，无需任何优化。本人想到思路就没有切题了（懒得切~~），因为倒牛奶有6种可能，一个一个写太麻烦了，而且没有思维含量。。。

USACO section1 个人选做完成了，也不知道有没有什么进步鸭~~

CSP-J/S2021rp++！！！

锐单商城拥有海量元器件数据手册、IC替代型号，打造电子元器件IC百科大全！

刷题-USACO Section 1 题目个人选做

相关文章