Problem: http://codeforces.com/contest/1154
手速场，暴力场
A:
1 /* basic header */ 2 #include <iostream> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <string> 6 #include <cstring> 7 #include <cmath> 8 #include <cstdint> 9 #include <climits> 10 #include <float.h> 11 /* STL */ 12 #include <vector> 13 #include <set> 14 #include <map> 15 #include <queue> 16 #include <stack> 17 #include <algorithm> 18 #include <array> 19 #include <iterator> 20 /* define */ 21 #define ll long long 22 #define dou double 23 #define pb emplace_back 24 #define mp make_pair 25 #define fir first 26 #define sec second 27 #define init(a,b) fill(begin(a),end(a),b) 28 #define sot(a,b) sort(a+1,a+1+b) 29 #define rep1(i,a,b) for(int i=a;i<=b;++i) 30 #define rep0(i,a,b) for(int i=a;i<b;++i) 31 #define repa(i,a) for(auto &i:a) 32 #define eps 1e-8 33 #define int_inf 0x3f3f3f3f 34 #define ll_inf 0x7f7f7f7f7f7f7f7f 35 #define lson curPos<<1 36 #define rson curPos<<1|1 37 /* namespace */ 38 using namespace std; 39 /* header end */ 40 41 int a[5]; 42 43 int main() 44 { 45 cin >> a[1] >> a[2] >> a[3] >> a[4]; 46 sot(a, 4); 47 cout << a[4] - a[1] << " " << a[4] - a[2] << " " << a[4] - a[3] << endl; 48 return 0; 49 }
B: 一开始看错题了
1 /* basic header */ 2 #include <iostream> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <string> 6 #include <cstring> 7 #include <cmath> 8 #include <cstdint> 9 #include <climits> 10 #include <float.h> 11 /* STL */ 12 #include <vector> 13 #include <set> 14 #include <map> 15 #include <queue> 16 #include <stack> 17 #include <algorithm> 18 #include <array> 19 #include <iterator> 20 /* define */ 21 #define ll long long 22 #define dou double 23 #define pb emplace_back 24 #define mp make_pair 25 #define fir first 26 #define sec second 27 #define init(a,b) fill(begin(a),end(a),b) 28 #define sot(a,b) sort(a+1,a+1+b) 29 #define rep1(i,a,b) for(int i=a;i<=b;++i) 30 #define rep0(i,a,b) for(int i=a;i<b;++i) 31 #define repa(i,a) for(auto &i:a) 32 #define eps 1e-8 33 #define int_inf 0x3f3f3f3f 34 #define ll_inf 0x7f7f7f7f7f7f7f7f 35 #define lson curPos<<1 36 #define rson curPos<<1|1 37 /* namespace */ 38 using namespace std; 39 /* header end */ 40 41 set<int>s; 42 int n, x; 43 44 int main() 45 { 46 s.clear(); 47 cin >> n; 48 rep1(i, 1, n) 49 { 50 cin >> x; 51 s.insert(x); 52 } 53 if (s.size() == 1) puts("0"); 54 else if (s.size() == 2) 55 { 56 int b[2], p = 0; 57 for (auto i : s) b[p++] = i; 58 sort(b, b + 2); 59 if ((b[1] - b[0]) % 2 == 0) 60 cout << (b[1] - b[0]) / 2 << endl; 61 else 62 cout << b[1] - b[0] << endl; 63 } 64 else if (s.size() >= 4) puts("-1"); 65 else 66 { 67 int b[3], p = 0; 68 for (auto i : s) b[p++] = i; 69 sort(b, b + 3); 70 if (b[2] - b[1] == b[1] - b[0]) cout << b[1] - b[0] << endl; 71 else puts("-1"); 72 } 73 return 0; 74 }
C:
1 /* basic header */ 2 #include <iostream> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <string> 6 #include <cstring> 7 #include <cmath> 8 #include <cstdint> 9 #include <climits> 10 #include <float.h> 11 /* STL */ 12 #include <vector> 13 #include <set> 14 #include <map> 15 #include <queue> 16 #include <stack> 17 #include <algorithm> 18 #include <array> 19 #include <iterator> 20 /* define */ 21 #define ll long long 22 #define dou double 23 #define pb emplace_back 24 #define mp make_pair 25 #define fir first 26 #define sec second 27 #define init(a,b) fill(begin(a),end(a),b) 28 #define sot(a,b) sort(a+1,a+1+b) 29 #define rep1(i,a,b) for(int i=a;i<=b;++i) 30 #define rep0(i,a,b) for(int i=a;i<b;++i) 31 #define repa(i,a) for(auto &i:a) 32 #define eps 1e-8 33 #define int_inf 0x3f3f3f3f 34 #define ll_inf 0x7f7f7f7f7f7f7f7f 35 #define lson curPos<<1 36 #define rson curPos<<1|1 37 /* namespace */ 38 using namespace std; 39 /* header end */ 40 41 int a, b, c, ans = 0; 42 43 int main() 44 { 45 scanf("%d%d%d", &a, &b, &c); 46 int week = min(a / 3, min(b / 2, c / 2)); 47 a -= week * 3, b -= week * 2, c -= week * 2, ans += week * 7; 48 int pre = ans; 49 rep1(i, 1, 7) 50 { 51 int x = a, y = b, z = c, tmp = pre; 52 rep1(j, i, i + 6) 53 { 54 int curr = j > 7 ? j - 7 : j; 55 if (curr == 1 || curr == 4 || curr == 7) 56 { 57 if (x)x--, tmp++; else break; 58 } 59 else if (curr == 2 || curr == 6) 60 { 61 if (y) y--, tmp++; else break; 62 } 63 else if (curr == 3 || curr == 5) 64 { 65 if (z) z--, tmp++; else break; 66 } 67 } 68 ans = max(ans, tmp); 69 } 70 printf("%d ", ans); 71 return 0; 72 }
D:
1 /* basic header */ 2 #include <iostream> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <string> 6 #include <cstring> 7 #include <cmath> 8 #include <cstdint> 9 #include <climits> 10 #include <float.h> 11 /* STL */ 12 #include <vector> 13 #include <set> 14 #include <map> 15 #include <queue> 16 #include <stack> 17 #include <algorithm> 18 #include <array> 19 #include <iterator> 20 /* define */ 21 #define ll long long 22 #define dou double 23 #define pb emplace_back 24 #define mp make_pair 25 #define fir first 26 #define sec second 27 #define init(a,b) fill(begin(a),end(a),b) 28 #define sot(a,b) sort(a+1,a+1+b) 29 #define rep1(i,a,b) for(int i=a;i<=b;++i) 30 #define rep0(i,a,b) for(int i=a;i<b;++i) 31 #define repa(i,a) for(auto &i:a) 32 #define eps 1e-8 33 #define int_inf 0x3f3f3f3f 34 #define ll_inf 0x7f7f7f7f7f7f7f7f 35 #define lson curPos<<1 36 #define rson curPos<<1|1 37 /* namespace */ 38 using namespace std; 39 /* header end */ 40 41 int n, a, b; 42 43 int main() 44 { 45 scanf("%d%d%d", &n, &a, &b); 46 int ans = 0, tmp = b; 47 rep1(i, 1, n) 48 { 49 int x; scanf("%d", &x); 50 if (x == 1 && a && tmp > b) 51 { 52 ++ans, --a, b = min(++b, tmp); 53 } 54 else if (b) ++ans, --b; 55 else if (a) ++ans, --a; 56 else break; 57 } 58 printf("%d ", ans); 59 return 0; 60 }
E:
1 /* basic header */ 2 #include <iostream> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <string> 6 #include <cstring> 7 #include <cmath> 8 #include <cstdint> 9 #include <climits> 10 #include <float.h> 11 /* STL */ 12 #include <vector> 13 #include <set> 14 #include <map> 15 #include <queue> 16 #include <stack> 17 #include <algorithm> 18 #include <array> 19 #include <iterator> 20 /* define */ 21 #define ll long long 22 #define dou double 23 #define pb emplace_back 24 #define mp make_pair 25 #define fir first 26 #define sec second 27 #define init(a,b) fill(begin(a),end(a),b) 28 #define sot(a,b) sort(a+1,a+1+b) 29 #define rep1(i,a,b) for(int i=a;i<=b;++i) 30 #define rep0(i,a,b) for(int i=a;i<b;++i) 31 #define repa(i,a) for(auto &i:a) 32 #define eps 1e-8 33 #define int_inf 0x3f3f3f3f 34 #define ll_inf 0x7f7f7f7f7f7f7f7f 35 /* namespace */ 36 using namespace std; 37 /* header end */ 38 39 const int maxn = 2e5 + 10; 40 int n, k, p = 1, a[maxn], l[maxn], r[maxn], ans[maxn]; 41 priority_queue<int>q; 42 43 int main() 44 { 45 scanf("%d%d", &n, &k); 46 l[0] = r[0] = 0; l[n + 1] = r[n + 1] = n + 1; 47 rep1(i, 1, n) 48 { 49 int x; scanf("%d", &x); 50 q.push(x); 51 a[x] = i, l[i] = i - 1, r[i] = i + 1; 52 } 53 while (!q.empty() && p++) 54 { 55 while (!q.empty() && ans[a[q.top()]]) q.pop(); 56 if (q.empty()) break; 57 int pos = a[q.top()]; q.pop(); 58 ans[pos] = p % 2 + 1; 59 int lpos = pos, rpos = pos; 60 rep1(i, 1, k) 61 { 62 lpos = l[lpos], rpos = r[rpos]; 63 ans[lpos] = ans[rpos] = p % 2 + 1; 64 } 65 l[r[rpos]] = l[lpos], r[l[lpos]] = r[rpos]; 66 } 67 rep1(i, 1, n) printf("%d", ans[i]); 68 puts(""); 69 return 0; 70 }
F: 简单dp。注释掉的部分是自己写的，但是过不了。看了一下大佬的思路
1 /* basic header */ 2 #include <iostream> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <string> 6 #include <cstring> 7 #include <cmath> 8 #include <cstdint> 9 #include <climits> 10 #include <float.h> 11 /* STL */ 12 #include <vector> 13 #include <set> 14 #include <map> 15 #include <queue> 16 #include <stack> 17 #include <algorithm> 18 #include <array> 19 #include <iterator> 20 /* define */ 21 #define ll long long 22 #define dou double 23 #define pb emplace_back 24 #define mp make_pair 25 #define fir first 26 #define sec second 27 #define init(a,b) fill(begin(a),end(a),b) 28 #define sot(a,b) sort(a+1,a+1+b) 29 #define rep1(i,a,b) for(int i=a;i<=b;++i) 30 #define rep0(i,a,b) for(int i=a;i<b;++i) 31 #define repa(i,a) for(auto &i:a) 32 #define eps 1e-8 33 #define int_inf 0x3f3f3f3f 34 #define ll_inf 0x7f7f7f7f7f7f7f7f 35 #define lson curPos<<1 36 #define rson curPos<<1|1 37 /* namespace */ 38 using namespace std; 39 /* header end */ 40 41 const int maxn = 2e3 + 10; 42 const int maxm = 2e5 + 10; 43 int n, m, k, a[maxm], off[maxn], dp[maxn], s[maxn]; 44 45 int calc(int num) 46 { 47 // if (num > k) return 0; 48 // ll ret = 1e17; 49 // rep1(i, 1, k) 50 // { 51 // if (!off[i]) continue; 52 // ret = min(ret, calc(num - i) + s[num] - s[num - i + off[i]]); 53 // } 54 // ret = min(ret, s[num]); 55 // return dp[num] = ret; 56 if (num > k) return 0; 57 int &ans = dp[num]; 58 if (~ans) return ans; 59 ans = int_inf; 60 ans = min(ans, calc(num + 1) + a[num]); 61 rep1(i, 1, k) 62 { 63 int x = i, y = off[i]; 64 if (!y) continue; 65 if (num + x <= k + 1) 66 ans = min(ans, calc(num + x) + s[num + x - 1] - s[num + y - 1]); 67 } 68 return ans; 69 } 70 71 int main() 72 { 73 scanf("%d%d%d", &n, &m, &k); 74 rep1(i, 1, n) scanf("%d", &a[i]); 75 sot(a, n); 76 rep1(i, 1, k) 77 { 78 dp[i] = -1; 79 s[i] = s[i - 1] + a[i]; 80 } 81 rep1(i, 1, m) 82 { 83 int num, y; scanf("%d%d", &num, &y); 84 if (num > k) continue; 85 off[num] = max(off[num], y); 86 } 87 printf("%d ", calc(1)); 88 return 0; 89 }
G: 枚举gcd
1 /* basic header */ 2 #include <iostream> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <string> 6 #include <cstring> 7 #include <cmath> 8 #include <cstdint> 9 #include <climits> 10 #include <float.h> 11 /* STL */ 12 #include <vector> 13 #include <set> 14 #include <map> 15 #include <queue> 16 #include <stack> 17 #include <algorithm> 18 #include <array> 19 #include <iterator> 20 /* define */ 21 #define ll long long 22 #define dou double 23 #define pb emplace_back 24 #define mp make_pair 25 #define fir first 26 #define sec second 27 #define init(a,b) fill(begin(a),end(a),b) 28 #define sot(a,b) sort(a+1,a+1+b) 29 #define rep1(i,a,b) for(int i=a;i<=b;++i) 30 #define rep0(i,a,b) for(int i=a;i<b;++i) 31 #define repa(i,a) for(auto &i:a) 32 #define eps 1e-8 33 #define int_inf 0x3f3f3f3f 34 #define ll_inf 0x7f7f7f7f7f7f7f7f 35 #define lson curPos<<1 36 #define rson curPos<<1|1 37 /* namespace */ 38 using namespace std; 39 /* header end */ 40 41 const int maxn = 1e7 + 10; 42 int n, vis[maxn], qu[5]; 43 ll ansLcm = ll_inf, a, b; 44 45 int main() 46 { 47 scanf("%d", &n); 48 rep1(i, 1, n) 49 { 50 int x; scanf("%d", &x); 51 if (vis[x]) 52 { 53 if (ansLcm > x) 54 { 55 ansLcm = x; 56 a = vis[x]; 57 b = i; 58 } 59 } 60 else vis[x] = i; 61 } 62 rep1(i, 1, 1e7) 63 { 64 int len = 0; 65 for (int j = i; j <= 1e7; j += i) 66 { 67 if (vis[j]) qu[len++] = j; 68 if (len == 2) break; 69 } 70 if (len == 2) 71 { 72 ll num1 = qu[0], num2 = qu[1], tmpLcm = num1 * num2 / i; 73 if (tmpLcm < ansLcm) 74 { 75 ansLcm = tmpLcm, a = vis[num1], b = vis[num2]; 76 } 77 } 78 } 79 if (a > b) swap(a, b); 80 printf("%lld %lld ", a, b); 81 return 0; 82 }