USACO Section 1.3 题解 (洛谷OJ P1209 P1444 P3650 P2693)

时间:2023-03-09 00:40:16
USACO Section 1.3 题解 (洛谷OJ P1209 P1444 P3650 P2693)

usaco ch1.4

sort(d , d + c, [](int a, int b) -> bool { return a > b; });
生成与过滤 generator&&filter
dfs:简化多重循环,枚举点对与判环
洛谷OJ
P1209 [USACO1.3]修理牛棚 Barn Repair
P1444 [USACO1.3]虫洞wormhole
P3650 [USACO1.3]滑雪课程设计Ski Course Design
P2693 [USACO1.3]号码锁 Combination Lock

Barn Repair

题意

数轴上有给你c个点,问用m个线段覆盖这些点的最小总长度。


题解

贪心

原题等价于在一条线段上有c个点,让你切出m-1条线段(不包含任何一个点),使得切的线段长度和最大。

所以直接处理出任意相邻两点的距离,取前m-1大的即可


代码

/*
ID: suuttt2
TASK: barn1
LANG: C++
*/ #include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <set>
#include<algorithm>
#include<map>
typedef long long ll;
using namespace std;
#define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)
#define md(x) x=(x+mod)%mod int smain();
#define ONLINE_JUDGE int main() {
//ios::sync_with_stdio(false);
#ifdef ONLINE_JUDGE
FILE *myfile;
myfile = freopen("barn1.in", "r", stdin);
if (myfile == NULL)
fprintf(stdout, "error on input freopen\n");
FILE *outfile;
outfile = freopen("barn1.out", "w", stdout);
if (outfile == NULL)
fprintf(stdout, "error on output freopen\n"); #endif
smain(); return 0;
}
const int maxn = 2e2 + 5;
//#define x first
//#define y second
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr) int n, m, k; int st[maxn];
int del[maxn]; int smain() {
FAST_IO;
int m, s, c;
cin >> m >> s >> c;
rep(i, 1, c) {
cin >> st[i];
}
sort(st + 1, st + 1 + c);
rep(i, 2, c) {
del[i] = st[i] - st[i - 1];
}
sort(del + 2, del + 1 + c, [](int a, int b) -> bool { return a > b; });
int ans = 0;
rep(i, 2, 2 + m - 2)ans += del[i] - 1;
ans = st[c] - st[1] + 1 - ans;
if (m >=c)ans = c;
cout << ans << endl;
cin >> n;
//cin >> N;
return 0;
} /* */

Combination Lock

题意

你有一个海关锁(行李箱上的那种),有三个数字,每个数字可以转到1~n。

有两个正确密码。

现在锁破了,如果某位和正确密码对应的一位绝对值差小于2,那么就被认为是正确密码,求有几个密码可以开锁?


题解

我的实现是生成。

dfs 生成正确答案,存在set里面。

标程暴力枚举,然后筛出正解。

是for三层,过滤出正确答案。

另外关于数字环:

我用了mod来模拟转数字,而标程用了其他的方法,避免了1,2 的特判。


代码

//头文件省略
int n, m, k; int a[4], b[4];
set<int> ans;
void fix(int &x) {
if (x < 0)x += n;
if (x == 0)x = n;
if(x>n){
if(n==1)x=n;
else if(n==2)x=(x%2?2:1);
else x=x%n;
}
}
int harsh(int a[]) {
return (a[1]*(n + 1) +a[2])*(n + 1) +a[3];
}
void dfs(int n,int a[]) {
if (n == 4) { ans.insert(harsh(a)); return; }
rep(i, -2, 2) {
int tmp = a[n];
a[n] += i;
fix(a[n]);
dfs(n + 1,a);
a[n] = tmp;
} }
int smain() {
FAST_IO; cin >> n;
int mod = n;
rep(i, 1, 3)cin >> a[i];
rep(i, 1, 3)cin >> b[i]; dfs(1, a);
dfs(1, b); cout << ans.size() << endl;
cin >> n;
return 0;
}
//标程代码
#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std; int N; bool close(int a, int b)
{
if (abs(a-b) <= 2) return true;
if (abs(a-b) >= N-2) return true;
return false;
} bool close_enough(int n1, int n2, int n3,
int c1, int c2, int c3)
{
return close(n1,c1) && close(n2,c2) && close(n3,c3);
} int main(void)
{
int f1, f2, f3;
int m1, m2, m3; ifstream fin("combo.in");
fin >> N;
fin >> f1 >> f2 >> f3;
fin >> m1 >> m2 >> m3;
fin.close(); int total = 0;
for (int n1=1; n1<=N; n1++)
for (int n2=1; n2<=N; n2++)
for (int n3=1; n3<=N; n3++)
if (close_enough(n1,n2,n3,f1,f2,f3) ||
close_enough(n1,n2,n3,m1,m2,m3))
total++; ofstream fout("combo.out");
fout << total << "\n";
fout.close(); return 0;
}

Wormholes

题意

给你二维坐标系上12个点,两两分组,组内的点会互相传送。有一头牛在平面上沿x正方向移动。如果走到某个点,就必须被传送到另一个。

问有几种分组方法,使得牛会进入死循环?

sample input
4
0 0
0 1
1 0
1 1 sample output
2 hint
(1,2)(3,4):1->2->1...
(1,4)(3,2):1->2->3->4->1...

题解

枚举再筛选。

先枚举所有点对组合,然后判环。

具体实现可以用建图,也可以用两个数组指针。

枚举点对的方法,就是dfs。

判环的方法,可以dfs中记录层数,如果跑了足够多步(实测21),就有环。也可以在把0设置在最右边,跑足够多此,看有没有跑到0点。


代码

int n, ans;

pii p[maxn];
vector<int> E[maxn];
vector<int> EE[maxn*13+14];
set<int> c;
int s[13];
vector<int> v;
set<int> tmps;
map<int, int> jump;
void test(int n) {
cout << n << endl;
for (auto t : v)cout << t << ' '; cout << endl;
cout << endl;
} bool iscyc(int N, int cnt) {
if (cnt > 21)return 1;
if (jump[N])N = jump[N]; cnt++;
for (auto t : E[N]) {
if (iscyc(t, cnt + 1))return 1;
}
return 0; } bool hascyc() {
rep(i,1,n) { if (iscyc(i,1)) {
return 1;
}
}
return 0;
} int minele(int s[]) {
rep(i, 1, n)if (s[i])return i;
return 1;
}
void all(int N) {
if (N == 2) {
rep(i,1,n)if(s[i])v.push_back(i);
//用map缩点
rep(i, 1, n)if (i % 2) {
jump[v[i]] = v[i - 1];
jump[v[i - 1]] = v[i];
}
if (hascyc()) ans++; jump.clear();
rep(i, 1, 2)v.pop_back();
return;
}
int mn = minele(s);
s[mn] = 0;
v.push_back(mn); rep(i,1,n) if (s[i]) {
v.push_back(i);
s[i] = 0;
all(N - 2);
v.pop_back();
s[i] = 1;
} s[mn] = 1;
v.pop_back();
}
int smain() {
FAST_IO;
cin >> n;
rep(i, 1, n)cin >> p[i].x >> p[i].y;
sort(p + 1, p + 1 + n, [](pii a, pii b)->bool {return a.y == b.y ? a.x < b.x : a.y < b.y; });
rep(i, 1, n-1) {
if(p[i].y == p[i+1].y)E[i].pb(i+1);
}
rep(i, 1, n)s[i]=1;
all(n);
cout << ans << endl;
cin >> n;
return 0;
}
//标程
//用的数组指针判环,数组枚举数对
#include <iostream>
#include <fstream>
using namespace std;
#define MAX_N 12 int N, X[MAX_N+1], Y[MAX_N+1];
int partner[MAX_N+1];
int next_on_right[MAX_N+1]; bool cycle_exists(void)
{
for (int start=1; start<=N; start++) {
// does there exist a cylce starting from start
int pos = start;
for (int count=0; count<N; count++)
pos = next_on_right[partner[pos]];
if (pos != 0) return true;
}
return false;
} // count all solutions
int solve(void)
{
// find first unpaired wormhole
int i, total=0;
for (i=1; i<=N; i++)
if (partner[i] == 0) break; // everyone paired?
if (i > N) {
if (cycle_exists()) return 1;
else return 0;
} // try pairing i with all possible other wormholes j
for (int j=i+1; j<=N; j++)
if (partner[j] == 0) {
// try pairing i & j, let recursion continue to
// generate the rest of the solution
partner[i] = j;
partner[j] = i;
total += solve();
partner[i] = partner[j] = 0;
}
return total;
} int main(void)
{
ifstream fin("wormhole.in");
fin >> N;
for (int i=1; i<=N; i++) fin >> X[i] >> Y[i];
fin.close(); for (int i=1; i<=N; i++) // set next_on_right[i]...
for (int j=1; j<=N; j++)
if (X[j] > X[i] && Y[i] == Y[j]) // j right of i...
if (next_on_right[i] == 0 ||
X[j]-X[i] < X[next_on_right[i]]-X[i])
next_on_right[i] = j; ofstream fout("wormhole.out");
fout << solve() << "\n";
fout.close();
return 0;
}

心路历程:

这个section留到最后的一道题。

想着这个专题的题都是很骚的循环枚举,

那这题肯定也是,其实不是啊QAQ。

所以昨天就一直想不用dfs的方法。

今天开始写dfs枚举点对和判环。

说实话以前都没写过orz。

枚举点对本来打算用set优化一下数组,最后发现set不能在for(auto t:set)里面插入删除,结果还是用了个cnt数组。

然后写判环,先要建图,发现这个图还要删边(现在想想暴力加边就够了QAQ),于是想建两个图,写到一半突然根据图的形态想到可以缩点(我用了hash)。写完了以后wa了一组数据,debug半天,发现缩点是错的QAQ,因为到某点时必须要转移到另一个点。于是想了一下,把两个点用map互相联系一下(其实用个数组也行),每次搜到某点时 v=map[v]一下。

dfs的话一开始想用map判环,最后都要写宽搜了。然后想到其实只要记录走的步数大于12个的话就有环了,但不知道为什么,至少要走21步才行QAQ

结论:图论不要瞎搞,全想清楚了再实现

#include<algorithm>
#include<iostream>
#include<sstream>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<math.h>
#include<stdio.h>
#include<vector>
#include<queue>
#include<string>
#include<ctime>
#include<stack>
#include<map>
#include<set>
#include<list>
using namespace std;
#define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)
#define REP(i,j,k) for(int i = (int)j;i < (int)k;i ++)
#define per(i,j,k) for(int i = (int)j;i >= (int)k;i --)
#define debug(x) cerr<<#x<<" = "<<(x)<<endl
#define mmm(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define MD(x) x%=mod
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define pii pair<int,int>
#define x first
#define y second
typedef double db;
typedef long long ll;
const int MAXN = 1e6;;
const int maxn = 10 + 5;
const int INF = 1e9;
const db eps = 1e-7;
const int mod = 1e9 + 7;
int n, ans; pii p[maxn];
vector<int> E[maxn];
vector<int> EE[maxn*13+14];
set<int> c;
int s[13];
vector<int> v;
set<int> tmps;
void test(int n) {
cout << n << endl;
for (auto t : v)cout << t << ' '; cout << endl;
cout << endl;
}
bool iscyc(int N, int cnt) {
if (cnt > 12)return 1;
for (auto t : EE[N]) {
if (iscyc(t, cnt + 1))return 1;
}
return 0; } bool hascyc() {
for(auto t:tmps) { if (iscyc(t,1)) {
return 1;
}
}
return 0;
} int minele(int s[]) {
rep(i, 1, n)if (s[i])return i;
return 1;
}
void all(int N) {
if (N == 2) {
rep(i,1,n)if(s[i])v.push_back(i);
//
//缩点对判环前先判掉两点环
int ok = 0; rep(i, 0, n-1) if(i%2){
tmps.insert(v[i-1] * 13 + v[i]); } rep(i,1,n)
rep(j, 0, E[i].size()-1) {
if (tmps.count(i * 13 + E[i][j])|| tmps.count(i + E[i][j] * 13)) {
ok = 1;
}
}
if (ok == 1)ans++,test(1); else {//建缩点后的图,判环 rep(i, 1, n)
rep(j, 0, E[i].size() - 1) {
int V = E[i][j];
int xx=0, yy=0;
for (auto t : tmps)if (t % 13 == i || t / 13 == i)xx = t;
for (auto t : tmps)if (t % 13 == V || t / 13 == V)yy = t;
EE[xx].push_back(yy);
int lala = 1;
}
if (hascyc())ans++,test(2); }
for(auto t:tmps)EE[t].clear();
tmps.clear();
rep(i, 1, 2)v.pop_back();
return;
}
int mn = minele(s);
s[mn] = 0;
v.push_back(mn); rep(i,1,n) if (s[i]) {
v.push_back(i);
s[i] = 0;
all(N - 2);
v.pop_back();
s[i] = 1;
} s[mn] = 1;
v.pop_back();
}
int main() {
FAST_IO;
cin >> n;
rep(i, 1, n)cin >> p[i].x >> p[i].y;
sort(p + 1, p + 1 + n, [](pii a, pii b)->bool {return a.y == b.y ? a.x < b.x : a.y < b.y; });
rep(i, 1, n-1) {
if(p[i].y == p[i+1].y)E[i].pb(i+1);
}
rep(i, 1, n)s[i]=1;
all(n);
cout << ans << endl;
cin >> n;
} /*
6
1 1
2 1
3 1
4 1
5 1
2 2
*/

Ski Course Design

题意

有1000座山,每座山的高度为0~100,现在要使任意两座山的高度差小于等于17。你可以改变一座山的长度,cost=deltaH^2。求最小花费。


题解

注意到,我们只要知道最低的那座山的高度,即可O(n)得到最终花费。所以枚举最低高度即可,复杂度为O(n*100).

相对的如果你要枚举每座山的高度,那么将是指数级别的。


代码

/*
ID: suuttt2
TASK: skidesign
LANG: C++
*/ #include <iostream>
#include<algorithm> using namespace std;
#define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) int smain();
//#define ONLINE_JUDGE int main() {
//ios::sync_with_stdio(false);
#ifdef ONLINE_JUDGE
FILE *myfile;
myfile = freopen("skidesign.in", "r", stdin);
if (myfile == NULL)
fprintf(stdout, "error on input freopen\n");
FILE *outfile;
outfile = freopen("skidesign.out", "w", stdout);
if (outfile == NULL)
fprintf(stdout, "error on output freopen\n"); #endif
smain(); return 0;
}
const int maxn = 1000 + 5; int n; int h[maxn]; int smain() { cin >> n;
rep(i, 1, n) {
cin >> h[i];
}
sort(h + 1, h + 1 + n);
int ans = 100 * 100 * 1000+1;
rep(mn, 0, 100-17) {
int tmp = 0;
rep(i, 1, n) {
if(h[i]<mn)
tmp += (h[i] - mn)*(h[i] - mn);
if (h[i] > mn + 17)
tmp += (h[i] - mn - 17)*(h[i] - mn - 17);
}
ans = min(ans, tmp);
}
cout << ans << endl;;
//cin >> n;
return 0;
}

心路历程

发现了洛谷有usaco专题,但是不能交#define ONLINE_JUDGE封装orz