寒假每日一题"/>
【AcWing】寒假每日一题
寒假每日一题
- week 1
- AcWing104.货仓选址
- week 2
- AcWing756.蛇形矩阵
- AcWing1113.红与黑
- AcWing1346.回文平方
- AcWing1227分巧克力
- AcWing680.剪绳子
- AcWing429.奖学金
- week 3
- AcWing422.校门外的树
- AcWing1381.阶乘
- AcWing1208.翻硬币
- AcWing1532.找硬币
- AcWing1341.十三号星期五
- AcWing754.平方矩阵II
- AcWing1432.棋盘挑战
- AcWing1371.货币系统
- week 4
- AcWing1353.滑雪场设计
- AcWing1603.整数集合划分
- AcWing482.合唱队形
- AcWing420.火星人
week 1
AcWing104.货仓选址
#include <algorithm>using namespace std;const int N = 100010;int n, res;
int a[N];int main()
{scanf("%d", &n);for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);sort(a, a + n);for (int i = 0; i < n; i ++ ) res += abs(a[i] - a[n / 2]);printf("%d\n", res);return 0;
}
week 2
AcWing756.蛇形矩阵
#include<iostream>using namespace std;const int N = 110;int n, m;
int q[N][N];int main()
{cin >> n >> m;int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};int x = 0, y = 0, d = 1;for (int i = 1; i <= n * m; i ++){q[x][y] = i;int a = x + dx[d], b = y + dy[d];if (a < 0 || a >= n || b < 0 || b >= m || q[a][b]){d = (d + 1) % 4;a = x + dx[d], b = y + dy[d];}x = a, y = b; }for (int i = 0; i < n; i ++){for (int j = 0; j < m; j ++)cout << q[i][j] << ' ';cout << endl;}return 0;
}
AcWing1113.红与黑
BFS
#include<iostream>
#include<queue>
#include<algorithm>#define x first
#define y secondusing namespace std;typedef pair<int, int> PII;
const int N = 25;int n, m;
char g[N][N];int bfs(int sx, int sy)
{queue<PII> q;q.push({sx, sy});g[sx][sy] = '#';int res = 0;int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};while (q.size()){auto t = q.front();q.pop();res ++ ;for (int i = 0; i < 4; i ++){int x = t.x + dx[i], y = t.y + dy[i];if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] != '.') continue;q.push({x, y});g[x][y] = '#';}}return res;
}int main()
{while(cin >> m >> n, n || m){for (int i = 0; i < n; i ++) cin >> g[i];int x, y;for (int i = 0; i < n; i ++)for (int j = 0; j < m; j ++)if (g[i][j] == '@'){x = i;y = j;}cout << bfs(x, y) << endl;}return 0;
}
DFS
#include<iostream>using namespace std;const int N = 25;int n, m;
char g[N][N];int dfs(int x, int y)
{int res = 1;g[x][y] = '#';int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};for (int i = 0; i < 4; i ++){int a = x + dx[i], b = y + dy[i];if (a < 0 || a >= n || b < 0 || b >= m || g[a][b] != '.') continue;res += dfs(a, b);}return res;
}int main()
{while(cin >> m >> n, n || m){for (int i = 0; i < n; i ++) cin >> g[i];int x, y;for (int i = 0; i < n; i ++)for (int j = 0; j < m; j ++)if (g[i][j] == '@'){x = i;y = j;}cout << dfs(x, y) << endl;}return 0;
}
AcWing1346.回文平方
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;char get(int x)//将x转换为字符形式
{if (x <= 9) return x + '0';return x - 10 + 'A';
}string base(int n, int b)//将n转换为b进制，返回对应字符串
{string res;while (n){res += get(n % b);n /= b;}reverse(res.begin(), res.end());//翻转回高位在左return res;
}bool check(string s)//检查s是否是回文
{for (int i = 0, j = s.size() - 1; i < j; i ++, j -- )if (s[i] != s[j])return false;return true;
}int main()
{int b;cin >> b;for (int i = 1; i <= 300; i ++ )//暴力{string num = base(i * i, b);if (check(num))cout << base(i, b) << ' ' << num << endl;}return 0;
}思考：如何将其他进制转化为十进制？秦九韶算法
#include<iostream>using namespace std;int uget(char c)
{if (c <= '9') return c - '0';//'0' 代表 字符0 ,对应ASCII码值为 0x30 (也就是十进制 48)return c + 10 - 'A';
}
int base10(string num, int b)
{int res = 0;for (auto c: num)res = res * b + uget(c);return res;
}int main()
{string a;cin >> a;cout << base10(a, 2);return 0;
}
AcWing1227分巧克力
区分是向上取整还是向下取整关键看mid，如果mid属于左区间则向下取整，mid属于右区间则向上取整。
//二分模板
bool check(int x) {/* ... */} // 检查x是否满足某种性质// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{while (l < r){int mid = l + r >> 1; // 下取整if (check(mid)) r = mid; // check()判断mid是否满足性质else l = mid + 1;}return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{while (l < r){int mid = l + r + 1 >> 1;// 上取整if (check(mid)) l = mid;else r = mid - 1;}return l; // 最后这里其实不过返回l 或者 r 都是一样，因为只有相等的时候才会结束。
}
题目代码：
//cpp
#include<iostream>using namespace std;typedef long long LL;
const int N = 100010;int n, m;
int h[N], w[N];bool check(int mid)
{LL res = 0; //res 别忘了初始化for (int i = 0; i < n; i ++)res += (LL)h[i] / mid * (w[i] / mid);return res >= m;
}int main()
{cin >> n >> m;for (int i = 0; i < n; i ++) cin >> w[i] >> h[i];int l = 1, r = 1e5;while (l < r){int mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;}cout << r << endl;return 0;
}
AcWing680.剪绳子
二分的本质是将一个最优化问题转化为判定性问题。假定一个值是最优值，然后不断check 并更新此判定条件。每次只需判定下二分得到的值成不成立就可以
#include<iostream>using namespace std;const int N = 100010;int n, m;
int w[N];bool check(double mid)
{int cnt = 0;for (int i = 0; i < n; i ++)cnt += w[i] / mid;return cnt >= m;
}int main()
{cin >> n >> m;for (int i = 0; i < n; i ++) cin >> w[i];double l = 0, r = 1e9;while (r - l > 1e-4){double mid = (l + r) / 2;if (check(mid)) l = mid;else r = mid;}printf("%.2f\n", r);return 0;
}
AcWing429.奖学金
//解法一： 重载小于号
#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N = 310;int n;
struct Person
{int id, sum, a, b, c;bool operator< (const Person& t) const{if (sum != t.sum) return sum > t.sum;if (a != t.a) return a > t.a;return id < t.id;}
}q[N];int main()
{cin >> n;for (int i = 1; i <= n; i++){int a, b, c;cin >> a >> b >> c;q[i] = {i, a + b + c, a, b, c};}sort(q + 1, q + n + 1);for (int i = 1; i <= 5; i++)cout << q[i].id << ' ' << q[i].sum << endl;return 0;}
#include <iostream>
#include <algorithm>using namespace std;const int N = 100010;struct Student
{int id, a, b, c, sum;void calc(){sum = a + b + c;}bool operator< (const Student& t)const{if (sum != t.sum) return sum > t.sum;if (a != t.a) return a > t.a;return id < t.id;}
}q[N];int main()
{int n;cin >> n;for (int i = 1; i <= n; i ++){int a, b, c;cin >> a >> b >> c;q[i].id = i;q[i].a = a;q[i].b = b;q[i].c = c;q[i].calc();}sort(q + 1, q + n + 1);for (int i = 1; i <= 5; i ++)cout << q[i].id << ' ' << q[i].sum << endl;return 0;
}
// 解法二
#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N = 310;int n;
struct Person
{int id, sum, a, b, c;
}q[N];bool cmp(Person& a, Person& b)
{if (a.sum != b.sum) return a.sum > b.sum;if (a.a != b.a) return a.a > b.a;return a.id < b.id;
}int main()
{cin >> n;for (int i = 1; i <= n; i++){int a, b, c;cin >> a >> b >> c;q[i] = {i, a + b + c, a, b, c};}sort(q + 1, q + n + 1, cmp);for (int i = 1; i <= 5; i++)cout << q[i].id << ' ' << q[i].sum << endl;return 0;}
week 3
AcWing422.校门外的树
#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N = 10010;int L, n;
bool st[N];int main()
{cin >> L >> n;for (int i = 0; i <= L; i ++) st[i] = true;while (n --){int a, b;cin >> a >> b;for (int i = a; i <= b; i ++) st[i] = false;}int res = 0;for (int i = 0; i <= L; i ++) res += st[i];cout << res << endl;return 0;
}
//区间合并算法
//将所有区间按左端点从小到大排序
//从左到右遍历每个区间#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N = 110;int m, n;
struct Segment
{int l, r;bool operator< (const Segment& t) const{return l < t.l;}
}seg[N];int main()
{cin >> m >> n;for (int i = 0; i < n; i ++) cin >> seg[i].l >> seg[i].r;sort(seg, seg + n);int sum = 0;int L = seg[0].l, R = seg[0].r;for (int i = 1; i < n; i ++)if (seg[i].l <= R) R = max(R, seg[i].r);else{sum += R - L + 1;L = seg[i].l, R = seg[i].r;}sum += R - L + 1;cout << m + 1 - sum << endl;return 0;
}
AcWing1381.阶乘
#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;int main()
{int n;cin >> n;int res = 1, d2 = 0, d5 = 0;for (int i = 1; i <= n; i ++){int x = i;while (x % 2 == 0) x /= 2, d2 ++;while (x % 5 == 0) x /= 5, d5 ++;res = res * x % 10; }int k = min(d2, d5);for (int i = 0; i < d2 - k; i ++) res = res * 2 % 10;for (int i = 0; i < d5 - k; i ++) res = res * 5 % 10;cout << res << endl;return 0;
}
AcWing1208.翻硬币
#include<iostream>
#include<cmath>
#include<algorithm>using namespace std;const int N = 310;string a, b;void turn(int i)
{if (a[i] == '*') a[i] = 'o';else a[i] = '*';
}int main()
{cin >> a >> b;int res = 0;for (int i = 0; i + 1 < a.size(); i ++)if (a[i] != b[i]){res ++;turn(i), turn(i + 1);}cout << res << endl;return 0;
}
AcWing1532.找硬币
哈希表 哈希碰撞
#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_set>using namespace std;const int INF = 100000;int main()
{int n, m;cin >> n >> m;unordered_set<int> hash;int v1 = INF, v2;for (int i = 0; i < n; i ++){ int a, b;cin >> a;b = m - a;if (hash.count(b)){hash.insert(a);if (a > b) swap(a, b);if (a < v1) v1 = a, v2 = b;}else hash.insert(a);}if (v1 == INF) puts("No Solution");else cout << v1 << ' ' << v2 << endl;return 0;
}
- 双指针算法需要用到单调性
判断能不能用双指针算法，只需看一个指针向后走的同时，另一个指针是不是一定往前走。
#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N = 100010;int n, m;
int w[N];int main()
{cin >> n >> m;for (int i = 0; i < n; i ++) cin >> w[i];sort(w, w + n);for (int i = 0, j = n - 1; i < j; i ++){while (i < j && w[i] + w[j] > m) j --;if (i < j && w[i] + w[j] == m){cout << w[i] <<' '<< w[j] << endl;return 0;}}puts("No Solution");return 0;}
AcWing1341.十三号星期五
- 口诀：一三五七八十腊（12月），三十一天永不差；四六九冬（11月）三十日；平年二月二十八，闰年二月把一加。
#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;int month[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int weekday[7];int main()
{int n;cin >> n;int days = 0;for (int year = 1900; year < 1900 + n; year ++){for (int i = 1; i <= 12; i ++){weekday[(days + 12) % 7] ++;days += month[i];if (i == 2){if (year % 100 && year % 4 == 0 || year % 400 == 0)days ++;}}}
// for (int i = 5, j = 0; j < 7; i = (i + 1) % 7, j ++)
// cout << weekday[i] << ' ';for (int j = 0, i = 5; j < 7; j ++){cout << weekday[i] << ' ';i = (i + 1) % 7;}cout << endl;return 0;
}
AcWing754.平方矩阵II
#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N = 110;int n;
int a[N][N];int main()
{while (cin >> n, n){for (int i = 1; i <= n; i ++){for (int j = i, k = 1; j <= n; j ++, k ++){a[i][j] = k;a[j][i] = k;}}for (int i = 1; i <= n; i ++){for (int j = 1; j <= n; j ++)cout << a[i][j] << ' ';cout << endl;}cout << endl;}return 0;
}#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N = 110;int n;
int main()
{while (cin >> n, n){for (int i = 1; i <= n; i ++){for (int j = i; j >= 1; j --) cout << j << ' ';for (int j = i + 1; j <= n; j ++) cout << j - i + 1 << ' ';cout << endl;}cout << endl;}
}
AcWing1432.棋盘挑战
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 15;int n;
bool col[N], dg[N * 2], udg[N * 2];
int path[N], ans;void dfs(int x)
{if (x > n){ans ++;if (ans <= 3){for (int i = 1; i <= n; i ++)cout << path[i] << ' ';cout << endl;}return;}for (int y = 1; y <= n; y ++)if (!col[y] && !dg[x + y] && !udg[x - y + n]){path[x] = y;col[y] = dg[x + y] = udg[x - y + n] = true;dfs(x + 1);col[y] = dg[x + y] = udg[x - y + n] = false;path[x] = 0;}
}int main()
{cin >> n;dfs(1);cout << ans << endl;return 0;
}
AcWing1371.货币系统
DP问题
week 4
AcWing1353.滑雪场设计
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1010;int n;
int h[N];int main()
{cin >> n;for (int i = 0; i < n; i ++) cin >> h[i];int res = 1e8;for (int i = 0; i + 17 <= 100; i ++){int cost = 0, l = i, r = i + 17;for (int j = 0; j < n; j ++)if (h[j] < l) cost += (l - h[j]) * (l - h[j]);else if (h[j] > r) cost += (h[j] - r) * (h[j] - r);res = min(res, cost);}cout << res << endl;return 0;
}
AcWing1603.整数集合划分
AcWing482.合唱队形
动态规划
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 110;int n;
int h[N];
int f[N], g[N];int main()
{scanf("%d", &n);for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);for (int i = 1; i <= n; i ++ ){f[i] = 1;for (int j = 1; j < i; j ++ )if (h[j] < h[i])f[i] = max(f[i], f[j] + 1);}for (int i = n; i; i -- ){g[i] = 1;for (int j = n; j > i; j -- )if (h[j] < h[i])g[i] = max(g[i], g[j] + 1);}int res = 0;for (int i = 1; i <= n; i ++ ) res = max(res, f[i] + g[i] - 1);printf("%d\n", n - res);return 0;
}
AcWing420.火星人
#include <iostream>
#include <algorithm>using namespace std;const int N = 10010;int n, m;
int w[N];int main()
{cin >> n >> m;for (int i = 1; i <= n; i ++) cin >> w[i];while (m --){int k = n;while (w[k - 1] > w[k]) k --;int t = k;while (w[t + 1] > w[k - 1]) t ++;swap(w[k - 1], w[t]);reverse(w + k, w + n + 1); }for (int i = 1; i <= n; i ++) cout << w[i] << ' ';cout << endl;return 0;
}
更多推荐
【AcWing】寒假每日一题
发布评论