HBU 2023 Simple problem set
目录
7-1 递推公式
7-2 存钱罐
7-3 买东西
7-4 双重子串
7-5 放小球
7-6 最短路径
7-7 统计子序列的个数
7-8 摆放灯笼
7-9 选零食
7-10 1还是2
7-11 最少的门禁数量
7-12 青春猪头之开学了要好好学习
7-13 青春猪头之毕设真头大
7-14 青春猪头之我没学过C语言
7-15 发射小球
7-16 吉利的数字
7-17 买木棒
7-18 切割木棒
7-19 幸运数字
7-20 增加硬币
7-21 三分球
7-22 老虎机
7-23 正交性
7-24 删除不喜欢的数字
7-25 锦标赛
7-1 递推公式
思路：
由于数据范围很大，模拟会TLE，考虑用矩阵运算优化这个类似斐波那契的递归式，再使用快速幂运算优化矩阵乘法，就能在要求的时间范围内通过了。
AC代码：
#include <iostream>
#include <stdio.h>
using namespace std;
typedef long long ll;const int maxn = 105;
const int P = 1000000007;struct matrix {ll m[maxn][maxn];
};
matrix a;ll n, k;matrix matrix_multi(matrix a, matrix b) {matrix ans;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {ans.m[i][j] = 0;for (int k = 1; k <= n; k++) {ans.m[i][j] = (ans.m[i][j] % P + (a.m[i][k] * b.m[k][j]) % P) % P;}}}return ans;
}matrix quick_matrix_pow(matrix a, ll t) {matrix ans;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (i == j) ans.m[i][j] = 1;else ans.m[i][j] = 0;}}while (t > 0) {if (t & 1)ans = matrix_multi(a, ans);a = matrix_multi(a, a);t >>= 1;}return ans;
}int main() {n = 3;cin >> k;a.m[1][1] = a.m[1][2] = a.m[1][3] = a.m[2][1] = a.m[3][2] = 1;matrix ans = quick_matrix_pow(a, k - 2);cout << ((ans.m[1][1] + ans.m[1][2])%P + ans.m[1][3])%P;return 0;
}7-2 存钱罐
思路：
二分，等差数列
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int T,n;
int main() {cin >> T;while (T--) {scanf("%d", &n);n *= 2;int l = 1, r = 1e5 + 10;while (l < r) {int mid = (l + r) >> 1;if ((LL)mid * (mid + 1) >= n)r = mid;else l = mid + 1;}printf("%d\\n", l);}
}7-3 买东西
思路：
贪心，由于每张券可以使物品少花一半的钱，那么给当前最大的物品使用券，一定是最优惠的，所以用一个优先队列（堆）维护当前最贵物品，每次用券，将最贵物品价格除以2，放入堆中，直至券全部用完。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 100010, M = N * 2, mod = 1e9 + 7;
int n, m;
priority_queue<int> q;int main() {cin >> n >> m;for (int i = 0; i < n; i++) {int x;cin >> x;q.push(x);}while (m--) {int x = q.top();if (x == 0)break;q.pop();q.push(x / 2);}LL sum = 0;while (!q.empty()) {sum += q.top();q.pop();}cout << sum;
}7-4 双重子串
思路：
dp 我们以dp[i][j] 表示以i为开头的字串和以j为开头的字串最长重复部分的长度。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 5010;
int f[N][N];
int n;
int res;
string s;
int dfs(int x,int y){if(x > n || y > n)return 0;if(f[x][y] != -1)return f[x][y];if(s[x] != s[y])f[x][y] = 0;else{f[x][y] = min(y - x, dfs(x+1,y+1) + 1);}return f[x][y];
}int main() {cin >> n;cin >> s;s = ' ' + s;memset(f,-1,sizeof f);for(int i=1;i<=n;i++){for(int j = i + 1;j <= n;j++){res = max(res,dfs(i,j));}}cout<<res;return 0;
}7-5 放小球
题目有一点点问题：
“对于每个i(1≤i≤n)，满足编号为i的倍数的箱子内装的小球的总数等于ai%2。”
应改为
“对于每个i(1≤i≤n)，满足编号为i的倍数的箱子内装的小球的总数%2等于ai。”
思路：
这道题其实不存在无解的情况，我们总能根据他的条件构造出来一个正解
原因：
我们从n遍历到1， 统计i的倍数放的小球的个数sum，如果sum%2符合要求，那么这个位置就不放小球，如果不符合要求，就在此位置放置小球即可。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 200010, M = N * 2, mod = 1e9 + 7;
int n, m;
int a[N],b[N];
vector<int> res;
int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}for (int i = n; i >= 1; i--) {int sum = 0;for (int k = 2; i * k <= n; k++)sum += b[i * k];if (sum % 2 == 0) {if (a[i]) {res.push_back(i);b[i] = 1;}}else {if(!a[i]) {res.push_back(i);b[i] = 1;}}}cout << res.size() << endl;for (int i = 0; i < res.size(); i++) {cout << res[i] << " ";}
}7-6 最短路径
思路：
此题点与点之间的距离是1，可以考虑bfs，只不过每次都要走3步，因此我们的st数组和d数组都应该是模3意义下的。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n, m, p;
int h[N], e[N], ne[N], idx;
void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int a, b, x, y;
bool st[N][3];
int d[N][3];int main() {scanf("%d%d", &n, &m);memset(h, -1, sizeof h);memset(st, 0, sizeof st);memset(d, -1, sizeof d);while (m--) {scanf("%d%d", &a, &b);add(a, b);}scanf("%d%d", &x, &y);st[x][0] = true;d[x][0] = 0;queue<PII> q;q.push({ x,d[x][0] });while (q.size()) {PII t = q.front();q.pop();int idx = t.first;int dist = t.second + 1;int fg = dist % 3;for (int i = h[idx]; i != -1; i = ne[i]) {int j = e[i];if (st[j][fg])continue;st[j][fg] = true;d[j][fg] = dist;if (j == y && fg == 0) {cout << d[j][0] / 3;return 0;}q.push({j,d[j][fg]});}}cout << "-1";return 0;
}7-7 统计子序列的个数
思路：
dp ，我们用dp[i][j] 来表示a数组中i位置之前，b数组中j位置之前的相同子序列的个数。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 2010, M = 1e6+10, mod = 1e9 + 7;
int n, m;
LL a[N], b[N];
LL f[N][N];
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++)cin >> a[i];for (int j = 1; j <= m; j++)cin >> b[j];for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {f[i][j] = (f[i][j - 1] + f[i - 1][j] - f[i - 1][j - 1]) % mod;if (a[i] == b[j])f[i][j] += (f[i - 1][j - 1] + 1) % mod;if (f[i][j] < 0)f[i][j] += mod;if (f[i][j] > mod)f[i][j] %= mod;}}cout << f[n][m] + 1;return 0;
}7-8 摆放灯笼
思路：
模拟即可。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1e4+10, M = 1e6+10, mod = 1e9 + 7;
int n, m;
char g[N][N];
int tran[N][N], dir[N][N];
int main()
{cin >> n >> m;for (int i = 0; i < n; i++)cin >> g[i];for (int i = 0; i < n; i++)for (int j = 0; j < m; j++) {if (j - 1 < 0 || g[i][j - 1] == '#') {int res = 0;int k = j;while (g[i][k] == '.')k++,res++;tran[i][j] = res;}else tran[i][j] = tran[i][j - 1];}for (int j = 0; j < m; j++)for (int i = 0; i < n; i++) {if (i - 1 < 0 || g[i - 1][j] == '#') {int res = 0;int k = i;while (g[k][j] == '.')k++, res++;dir[i][j] = res;}else dir[i][j] = dir[i - 1][j];}int res = 0;for(int i=0;i<n;i++)for (int j = 0; j < m; j++) {if (g[i][j] == '#')continue;else res = max(res, tran[i][j] + dir[i][j] - 1);}cout << res;return 0;
}7-9 选零食
思路：
模拟即可，枚举取几个零食，放回几个零食
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 55;int n, m;
int a[N];
int res;
int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> a[i];}int buy = min(n, m);for (int i = 1; i <= buy; i++) {int put = m - i;for (int jl = 0; jl <= i; jl++) {int sum = 0;priority_queue<int, vector<int>, greater<int>> q;int jr = n - i + jl + 1;for (int j = 1; j <= jl; j++) {q.push(a[j]);sum += a[j];}for (int j = jr; j <= n; j++) {q.push(a[j]);sum += a[j];}int x = put;while (!q.empty() && q.top() < 0 && x > 0) {sum -= q.top();q.pop();x--;}res = max(res, sum);}}cout << res;return 0;
}7-10 1还是2
思路：
考虑一件事情：如果我们得到了这样的线索：“1 和 2 、2 和3 、3和4”，我们只要知道1，就可以把2、3、4推断出来了。因此，判断线索将哪些卡片联系起来，成为了一组，每组中我们只要知道其中一个，其余的就都可以推断出来了。
使用并查集
代码：
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1e5+10, M = 1e6+10, mod = 1e9 + 7;
int n, m;
int p[N];int find(int x) {if (x != p[x])p[x] = find(p[x]);return p[x];
}int main()
{cin >> n >> m;for (int i = 1; i <= n; i++)p[i] = i;for (int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;a = find(a), b = find(b);if (a != b)p[a] = b;}set<int> st;for (int i = 1; i <= n; i++) {p[i] = find(p[i]);st.insert(p[i]);}cout << st.size();return 0;
}7-11 最少的门禁数量
思路：
典型差分，将所有大门的信息差分，求一遍前缀和，当前和等于门的数量的钥匙即满足要求
代码：
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1e5+10, M = 1e6+10, mod = 1e9 + 7;
int n, m;
int chafen[N];int main()
{cin >> n >> m;int men = m;while (m--) {int l, r;cin >> l >> r;chafen[l] += 1;chafen[r + 1] -= 1;}int res = 0;for (int i = 1; i <= n; i++) {chafen[i] += chafen[i - 1];if (chafen[i] == men)res++;}cout << res;return 0;
}7-12 青春猪头之开学了要好好学习
思路：
由于我们可以进行无限次操作，所以如果负数个数为偶数的话，我们总能将其全变为正数。
但如果负数个数为奇数，我们不管怎么翻转，最后都会留下一个负数，那我们一定会留最小的那个负数。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1e5+10, M = 1e6+10, mod = 1e9 + 7;
int n, m;
vector<LL> a;
int main()
{LL res = 0;cin >> n;for (int i = 0; i < n; i++){LL x;cin >> x;if (x < 0)m++;a.push_back(x);}if (m % 2 == 0) {for (int i = 0; i < n; i++)res += abs(a[i]);}else {for (int i = 0; i < n; i++) {a[i] = abs(a[i]);}sort(a.begin(), a.end());for (int i = 0; i < n; i++) {if (!i)res += (-1) * a[i];else res += a[i];}}cout << res;return 0;
}7-13 青春猪头之毕设真头大
思路：（双指针）
枚举每一个0序列区间，判断将其全变成1，和两边的1相连长度是多少，更新最大值
代码：
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1e5+10, M = 1e6+10, mod = 1e9 + 7;
int n, m;
string s;
int main()
{cin >> n >> m;getchar();cin >> s;int l = 0, r = 0, cnt = 0, num = 0;while (r < n) {if (s[r] == '0') {while (s[r] == '0'&& r < n - 1)r++;cnt++;}while (cnt > m) {while (s[l] == '1' && l < n - 1)l++;while (s[l] != '1' && l < n - 1)l++;cnt--;}num = max(num, r - l + 1);r++;}cout << num;return 0;
}7-14 青春猪头之我没学过C语言
思路：
从1到n的异或值有规律，可以打表观察。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1e5+10, M = 1e6+10, mod = 1e9 + 7;
int n;
LL x, y;
LL fun(LL x) {if (x % 4 == 1)return 1;else if (x % 4 == 2)return x + 1;else if (x % 4 == 3)return 0;else return x;
}
int main()
{cin >> x >> y;LL res = fun(max((LL)0,x - 1)) ^ fun(y);cout << res;return 0;
}7-15 发射小球
思路：
推公式即可
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{double sx, sy, gx, gy;double k = 0;scanf("%lf%lf%lf%lf", &sx, &sy, &gx, &gy);gy = -gy;printf("%.10lf", sx - (double)(sx-gx)/(sy-gy)*sy);return 0;
}
7-16 吉利的数字
思路：
只需要判断所有出现过的数字能组成的3位数是否是8的倍数即可。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 2e5 + 10;
int st[11];
char s[N];
int main()
{cin >> s;if (strlen(s) == 1) {if ((s[0] - '0') % 8 == 0)cout << "Yes";else cout << "No";return 0;}if (strlen(s) == 2) {int t = 0, x = 0;t += s[0] - '0';t *= 10;t += s[1] - '0';x += s[1] - '0';x *= 10;x += s[0] - '0';if (t % 8 == 0 || x % 8 == 0)cout << "Yes";else cout << "No";return 0;}for (int i = 0; i < strlen(s); i++) {int x = s[i] - '0';st[x]++;}for (int i = 1; i < 10; i++)for (int j = 1; j < 10; j++)for (int k = 1; k < 10; k++) {int t = 0;bool fg1 = false, fg2 = false, fg3 = false;if (st[i]) {t += i;st[i]--;fg1 = true;}else continue;if (st[j]) {t *= 10;t += j;st[j]--;fg2 = true;}else{ st[i]++;continue;}if (st[k]) {t *= 10;t += k;st[k]--;fg3 = true;}else{ st[i]++;st[j]++;continue;}if (fg1)st[i]++;if (fg2)st[j]++;if (fg3)st[k]++;if (t && t % 8 == 0) {cout << "Yes";return 0;}}cout << "No";return 0;
}7-17 买木棒
思路：
贪心，肯定要购买长度为n+1的木棒，考虑其能最多分割成多少个小的木棒，其余的购买。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL S, P;
int main()
{cin >> S;P = S;S++;int i = 1;while (S >= i) {S -= i;i++;}cout << P - i + 2;return 0;
}7-18 切割木棒
思路：
长度为n的木棒，找11个切割位置：
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 210;
LL f[N][13];
int main()
{for (int i = 0; i < N; i++) {for (int j = 0; j <= i && j < 13; j++) {if (j == 0)f[i][j] = (LL)1;else f[i][j] = f[i - 1][j - 1] + f[i - 1][j];}}int n; cin >> n;cout << f[n - 1][11];return 0;
}
7-19 幸运数字
思路：
预处理：线性筛法求素数，求其前缀和
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
int prime[N],cnt;
int s[N];
bool st[N];
void get_prime(int n){for(int i=2;i<=n;i++){if(!st[i]){prime[cnt++]=i;}for(int j=0;prime[j]<=n/i;j++){st[prime[j]*i]=true;if(i%prime[j]==0)break;}}
}int main()
{get_prime(N-1);for(int i=2;i<N;i++){if(!st[i] && !st[(i+1)/2] && i%2==1)s[i]=1;}for(int i=2;i<N;i++)s[i]+=s[i-1];int q;cin>>q;while(q--){int l,r;scanf("%d%d",&l,&r);printf("%d\\n",s[r]-s[l-1]);}return 0;
}
7-20 增加硬币
思路：
期望DP
来源： AT_abc184_d [ABC184D] increment of coins - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 110;
double f[N][N][N];
int d = 0;double dp(int a, int b, int c) {if (f[a][b][c] >= 0)return f[a][b][c];f[a][b][c] = 0;if (a >= 100 || b >= 100 || c >= 100)return f[a][b][c];int sum = a + b + c;f[a][b][c] += (dp(a + 1, b, c) + 1) * (1.0 * a) / sum;f[a][b][c] += (dp(a, b + 1, c) + 1) * (1.0 * b) / sum;f[a][b][c] += (dp(a, b, c + 1) + 1) * (1.0 * c) / sum;return f[a][b][c];
}
int main()
{int a, b, c;scanf("%d%d%d", &a, &b, &c);memset(f, -1, sizeof f);printf("%.9lf", dp(a, b, c));return 0;
}
7-21 三分球
自己写吧
7-22 老虎机
同上
7-23 正交性
模拟
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
int a[N];
int main()
{int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++){int x;scanf("%d",&x);a[i]*=x;a[i]+=a[i-1];}if(a[n]==0)cout<<"Yes";else cout<<"No";return 0;
}
7-24 删除不喜欢的数字
模拟
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
int a[N];
int main()
{int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){int x;scanf("%d",&x);if(x==m)continue;printf("%d ",x);}return 0;
}
7-25 锦标赛
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 20;
int n;
int res1,res2;
int d1,d2;
int main()
{cin>>n;n = 1<<n;for(int i=1;i<=n;i++){int x;scanf("%d",&x);if(i<=n/2){if(res1<x){res1=x;d1=i;}}else{if(res2<x){res2=x;d2=i;}}}if(res1>res2)cout<<d2;else cout<<d1;//if(a[n]==0)cout<<"Yes";//else cout<<"No";return 0;
}