[数据结构与算法]2021年第11月月赛题解akoj

A.4和7?
B.棋盘！！
C.分数！！！
D.小J和他的复习计划
E. 进度条
F 车牌号匹配
G.Happy Number
H.给你一个签到题
I.砝码问题
J.阵前第一功

问题A解题思路
贪心，既然要输出满足条件的最小的数字，肯定7的数量要最多，然后直接循环遍历即可求解。
A.cpp

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;
	int x = 0,y = 0,ansx = 0,ansy = 0;
	for(int i=0;i<=n/4;i++){
		x = i,y = (n - 4 * x) / 7;
		if(x * 4 + y * 7 == n && x >= 0 && y >= 0){
			if(ansx == 0 && ansy == 0 || ansx + ansy > x + y)ansx = x,ansy = y;
		}
	}
	if(ansx == 0 && ansy == 0)cout << "YingYingYing";
	else {
		for(int i=0;i<ansx;i++)cout << 4;
		for(int i=0;i<ansy;i++)cout << 7;
	}
	return 0;
}

问题B解题思路
签到题之一
B.cpp

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i&1){
				if(j&1)cout<<"0";
				else cout<<"1";
			}else{
				if(j&1)cout<<"1";
				else cout<<"0";
			}
		}
		cout<<endl;
	}
	
	return 0;
} 

问题C解题思路
一个模拟题，将分数转化为连分数，注意要化简
C.cpp

#include<bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int a, b;
        cin >> a >> b;
        printf("%d/%d = %d", a, b, a / b);
        int sum = 0;
        if (a % b != 0) {
            cout << "+1/";
            a = a % b;
            int k = __gcd(a, b);
            a /= k, b /= k;
            if (a != 1) {
                cout << "{";
            }
            while (a > 1) {
                int x = b, y = a;
                cout << x / y << "+1/";
                sum++;
                a = x % y;
                b = y;
                int k = __gcd(a, b);
                a /= k, b /= k;
                if (a != 1) {
                    cout << "{";
                }
            }
            cout << b;
            for (int i = 0; i < sum; i++) {
                cout << "}";
            }
        }
        cout << "\n";
    }
    return 0;
}

问题D解题思路
这个题是这次月赛最难的一个题，可以用前缀和加上二分，前缀和记录前n天复习的分数之和，然后再用二分查找出最优的解
D.cpp

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int maxn = 1e6+10;
LL a[maxn];
LL s1, s2, n;
bool judge(LL mid){
	for(int i=mid;i<=n;i++){
		if(a[i] - a[i - mid] >= s1 + s2)return true;
	}
	return false;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	a[0] = 0;
	while(cin >> n) {
		cin >> s1 >> s2;
		for(int i=1; i <= n; i++){
			cin >> a[i];
			a[i] += a[i-1];
		}
		if(a[n] < s1 + s2){
			cout << n << "\n";
			continue;
		}
		LL l = 1, r = n,ans = n;
		LL mid;
		while(l <= r){
			mid = (l + r) >> 1;
			if(judge(mid)) {
				ans = min(ans, mid);
				r = mid - 1;
			}
			else l = mid + 1;
		}
		cout << n - ans << "\n";
	}
	
	return 0;
}

问题E解题思路
第二个签到题
E.cpp

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << "[";
        for (int i = 0; i < 100; i++) {
            if (i < n)
                cout << ">";
            else
                cout << " ";
        }
        cout << "]";
        if (n < 10) {
            cout << "0" << n << "%" << endl;
        } else {
            cout << n << "%" << endl;
        }
    }
    return 0;
}

问题F解题思路
直接遍历找到匹配的车牌号
F.cpp

#include<bits/stdc++.h>
using namespace std;
int main() {
    char s[20];
    cin >> s;
    int n;
    cin >> n;
    int len = strlen(s);
    int sum = 0, b[100] = {
        0
    },
    k = 0;
    char a[n][20];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        int flag = 0;
        for (int j = 0; j < len; j++) {
            if (a[i][j] == s[j] || s[j] == '*') {
                continue;
            }
            else {
                flag = 1;
                break;
            }
        }
        if (flag == 0) {
            sum++;
            b[k++] = i;
        }
    }
    cout << sum << endl;
    for (int i = 0; i < k; i++) {
        cout << a[b[i]] << endl;
    }
    return 0;
}

G题解题思路
题目大意
找出第n个只含2,3,6的数

思路：没有进位的三进制
G.cpp

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;
	stack<int>s;
	while(n > 0){
		if(n % 3 == 1)s.push(2);
		else if(n % 3 == 2)s.push(3);
		else s.push(6);
		n--;
		n /= 3;
	}
	while(!s.empty()){
		cout << s.top();
		s.pop();
	}
	
	return 0;
}

H题解题思路
也算个小小的签到题吧，暴力就能解决
H.cpp

#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n,i,j;
	string a,b,c;
	cin>>n;
	while (n--)
	{
		cin>>a;
		c=a;
		for (i=0;i<a.size();i++)
		{
			for (j=i+1;j<a.size();j++)
			{
				b=a;
				if (b[i]<b[j]) swap(b[i],b[j]);
				if(c<b)	c=b;
			}
		}
		cout<<c<<"\n";
	}
	return 0;
}

I题解题思路
先求所有砝码重量总和，总和是奇数时，肯定无法满足，否则直接深搜
I.cpp

#include<bits/stdc++.h>
using namespace std;
int n, a[1000], flag, l;
void dfs(int x, int sum) {
    if (x == n) {
        if (sum == l / 2) {
            flag = 1;
        }
        return;
    }
    dfs(x + 1, sum + a[x]);
    dfs(x + 1, sum);
}
int main() {
    while (cin >> n) {
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        l = 0;
        for (int i = 0; i < n; i++) {
            l += a[i];
        }
        if (l % 2 != 0) {
            cout << "Sorry,I can't!\n";
        }
        else {
            flag = 0;
            dfs(0, 0);
            if (flag == 1) {
                cout << "Of course,I can!" << endl;
            }
            else if (flag == 0) {
                cout << "Sorry,I can't!\n";
            }
        }
    }
    return 0;
}

J题解题思路
去重排序

#include<bits/stdc++.h>
using namespace std;
int main() {
	int t;
	scanf("%d", &t);
	while(t--){
		set <int, greater<int>> s;
		int n;
		scanf("%d",&n);
		for(int i=0;i<n;i++){
			int x;
			scanf("%d", &x);
			s.insert(x);
		}
		int op;
		scanf("%d", &op);
		int cnt = 1;
		for(auto &i:s){
			if(cnt == op) {
				printf("%d\n",i);
				break;
			}
			cnt++;
		}
	}
	
	return 0;
}