当前位置： 首页 > article >正文

HBU 2023 Simple problem set

article 2024/11/14 12:50:34

目录

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个切割位置：C_{11}^{n}

代码：

#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;
}


http://www.kler.cn/a/11774.html

相关文章：

  • Autosar CP 基于CAN的时间同步规范导读
  • C/C++精品项目之图床共享云存储（3）：网络缓冲区类和main
  • 【p2p、分布式，区块链笔记 DAM】GUN/SEA（Security, Encryption, Authorization） 模块genkey
  • [HarmonyOS]简单说一下鸿蒙架构
  • C++ QT 工具日志异步分批保存
  • go reflect 反射
  • win10彻底永久关闭自动更新【亲测有效】
  • 刷题_32：淘宝网店 and 斐波那契凤尾
  • Parcel 实践指南
  • 【已解决】加载模型时报错：model_config = json.loads(model_config.decode(‘utf-8‘))
  • 室内P1.8超清LED无缝拼接LED显示屏详细介绍及显示效果和尺寸长高比例
  • 轨迹相似度整理
  • FMC子卡设计资料：ADRV9002双窄带宽带射频收发器 AD9361双收双发射频 DA子卡 ADRV9009双收双发射频FMC子卡
  • 用孕妇的思维和孕妇对话——《用孩子的思维和孩子对话》
  • vue+springboot 上传文件、图片、视频，回显到前端。
  • 立体图
  • Huawei交换机链路聚合eth-trunk配置
  • SQL笔记（2）——MySQL的表操作与索引(收藏吃灰版)
  • 远程组态管理的好处
  • 我的创作纪念日-哈市雪花
  • 快排（动图详细版，快速理解）
  • HTML表单和CSS属性以及DOM实现网页版计算器
  • tpm2-tools源码分析之tpm2_create.c（3）
  • 【嵌入式环境下linux内核及驱动学习笔记-（3-字符设备驱动详解）】
  • 牛客乔迁新居，新址在……
  • STM32CubeMx+HAL库实现USB CDC+MSC复合设备