1.第一题 没有看
2. 由于数据范围很小，所以每一层需要全排列，寻找最小的花费，然后所有层加起来就是最后的结果。
1 #include<bits/stdc++.h> 2 #define pb push_back 3 typedef long long ll; 4 using namespace std; 5 typedef pair<int, int> pii; 6 const int maxn = 1e3 + 10; 7 int n; 8 int m; 9 int a[110][10][2]; 10 int p[10]; 11 12 void solve() { 13 cin >> n >> m; 14 ll res = 0; 15 for (int j = 0; j < n; j++) { 16 cin >> a[0][j][0] >> a[0][j][1]; 17 } 18 for (int i = 1; i <= m; i++) { 19 for (int j = 0; j < n; j++) { 20 cin >> a[i][j][0] >> a[i][j][1]; 21 } 22 if(i == 0) continue; 23 for (int j = 0; j < n; j++) 24 p[j] = j; 25 ll mr = INT_MAX; 26 do { 27 ll t = 0; 28 for (int j = 0; j < n; j++) { 29 t += abs(a[i][p[j] ][0] - a[i - 1][j][0] ) + abs(a[i][p[j] ][1] - a[i - 1][j][1] ); 30 } 31 mr = min(t, mr); 32 } while(next_permutation(p, p + n)); 33 res += mr; 34 } 35 cout << res << endl; 36 37 } 38 39 int main() { 40 freopen("test.in", "r", stdin); 41 //freopen("test.out", "w", stdout); 42 ios::sync_with_stdio(0); 43 cin.tie(0); cout.tie(0); 44 solve(); 45 return 0; 46 }
3.数据范围也是很小，枚举每一条边，然后存在不存在，进行判断累加。边的个数6 * 5 / 2 = 15. 1 << 15 = 32000. 然后乘上判断连通的复杂度，结果也是很小。
判断连通可以用bfs或者dfs， dsu都是可以的。
1 #include<bits/stdc++.h> 2 #define pb push_back 3 typedef long long ll; 4 using namespace std; 5 typedef pair<int, int> pii; 6 const int maxn = 1e3 + 10; 7 int n, m; 8 //set<pii> se; 9 int f[10]; 10 int a[10][10]; 11 int b[10][10]; 12 void init() { 13 for (int i = 0; i <= n; i++) f[i] = i; 14 } 15 int fd(int x) { 16 if(x == f[x]) return x; 17 return f[x] = fd(f[x]); 18 } 19 bool check() { 20 int sz = n; 21 for (int i = 1; i <= n; i++) { 22 for (int j = i + 1; j <= n; j++) { 23 if(a[i][j]) { 24 int t1 = fd(i); 25 int t2 = fd(j); 26 if(t1 != t2) { 27 sz--; 28 f[t1] = t2; 29 } 30 } 31 } 32 } 33 return sz == 1; 34 } 35 ll res; 36 37 void work(int x, int y) { 38 //cout << x << " " << y << endl; 39 if(x > n) { 40 init(); 41 res += check(); 42 return; 43 } 44 if(y > n) { 45 work(x + 1, x + 2); 46 return; 47 } 48 work(x, y + 1); 49 if(b[x][y]) return; 50 a[x][y] = a[y][x] = 1; 51 work(x, y + 1); 52 a[x][y] = a[y][x] = 0; 53 } 54 void solve() { 55 cin >> n >> m; 56 int x, y; 57 for (int i = 0; i < m; i++) { 58 cin >> x >> y; 59 //if(x > y) swap(x, y); 60 //se.insert({x, y}); 61 b[x][y] = b[y][x] = 1; 62 } 63 work(1, 2); 64 cout << res << endl; 65 } 66 67 int main() { 68 freopen("test.in", "r", stdin); 69 //freopen("test.out", "w", stdout); 70 ios::sync_with_stdio(0); 71 cin.tie(0); cout.tie(0); 72 solve(); 73 return 0; 74 }
4. 第四题稍微花了一些时间。 首先题目求解满足条件的最小， 那就是比这个大的都是可以满足条件的， 满足二分的性质。
然后给定答案，如何快速的判断是否满足要求， 贪心策略进行。由于 n = 1e4， 这个数其实挺小的， 排序， 贪心 可以的。
1 #include<bits/stdc++.h> 2 #define pb push_back 3 typedef long long ll; 4 using namespace std; 5 typedef pair<int, int> pii; 6 const int maxn = 1e4 + 10; 7 int n, a, b; 8 ll h[maxn]; 9 ll tmp[maxn]; 10 int tot; 11 bool check(ll x) { 12 ll ra, rb; 13 ra = rb = 0; 14 tot = 0; 15 for (int i = 0; i < n; i++) { 16 if(h[i] >= x) { 17 ll c = h[i] / x; 18 if(ra + c > a) { 19 ll t = h[i] - x * (a - ra); 20 ra = a; 21 if(t > 0) tmp[tot++] = t; 22 } else { 23 ra += h[i] / x; 24 int t = h[i] % x; 25 if(t > 0) tmp[tot++] = t; 26 } 27 28 } else { 29 tmp[tot++] = h[i]; 30 } 31 //if(ra > a) return 0; 32 } 33 sort(tmp, tmp + tot, greater<ll>()); 34 for (int i = 0; i < tot; i++) { 35 if(ra < a) { 36 ra++; 37 } else { 38 rb += tmp[i]; 39 } 40 } 41 return ra + rb <= b; 42 } 43 void solve() { 44 cin >> n >> a >> b; 45 for (int i = 0; i < n; i++) { 46 cin >> h[i]; 47 } 48 sort(h, h + n, greater<ll>()); 49 ll left = 1, right = 1e9 + 10; 50 while(left < right) { 51 ll mid = (left + right) / 2; 52 //cout << mid << " " << left << " " << right << endl; 53 if(check(mid)) right = mid; 54 else left = mid + 1; 55 56 } 57 if(check(left)) cout << left << endl; 58 else cout << -1 << endl; 59 } 60 61 int main() { 62 //freopen("test.in", "r", stdin); 63 //freopen("test.out", "w", stdout); 64 ios::sync_with_stdio(0); 65 cin.tie(0); cout.tie(0); 66 solve(); 67 return 0; 68 }