洛谷习题V^V

1.帮贡排序

解题思路：按照题意，排序模拟即可

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;struct Member {string name;string position;int contribution;int level;int original_order;
};int getPriority(const string& pos) {if (pos == "BangZhu") return 0;if (pos == "FuBangZhu") return 1;if (pos == "HuFa") return 2;if (pos == "ZhangLao") return 3;if (pos == "TangZhu") return 4;if (pos == "JingYing") return 5;return 6; // BangZhong
}bool compareDisplay(const Member& a, const Member& b) {int pa = getPriority(a.position);int pb = getPriority(b.position);if (pa != pb) return pa < pb;if (a.level != b.level) return a.level > b.level;return a.original_order < b.original_order;
}bool compareContribution(const Member& a, const Member& b) {if (a.contribution != b.contribution) return a.contribution > b.contribution;return a.original_order < b.original_order;
}int main() {int n;cin >> n;vector<Member> members(n);vector<Member> leaders;  vector<Member> others;  for (int i = 0; i < n; ++i) {cin >> members[i].name >> members[i].position >> members[i].contribution >> members[i].level;members[i].original_order = i;if (members[i].position == "BangZhu" || members[i].position == "FuBangZhu") {leaders.push_back(members[i]);} else {others.push_back(members[i]);}}sort(others.begin(), others.end(), compareContribution);int huFaCount = 0, zhangLaoCount = 0, tangZhuCount = 0, jingYingCount = 0;for (auto& member : others) {if (huFaCount < 2) {member.position = "HuFa";huFaCount++;} else if (zhangLaoCount < 4) {member.position = "ZhangLao";zhangLaoCount++;} else if (tangZhuCount < 7) {member.position = "TangZhu";tangZhuCount++;} else if (jingYingCount < 25) {member.position = "JingYing";jingYingCount++;} else {member.position = "BangZhong";}}vector<Member> allMembers = leaders;allMembers.insert(allMembers.end(), others.begin(), others.end());sort(allMembers.begin(), allMembers.end(), compareDisplay);for (const auto& member : allMembers) {cout << member.name << " " << member.position << " " << member.level << endl;}return 0;
}

2.阶乘数码

解题思路：高精度，单精度问题，套用模版，最后统计一遍即可

#include<bits/stdc++.h>
#define ll long long
#define endl "\n"using namespace std;
void dis_time() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);
}void mult(vector<int>& ans, int x) {reverse(ans.begin(), ans.end());int up = 0;for (int i = 0; i < ans.size(); i++) {ans[i] = ans[i] * x + up;up = ans[i] / 10;ans[i] %= 10;}while (up) {int cur = up % 10;ans.push_back(cur);up /= 10;}reverse(ans.begin(), ans.end());
}void solve() {int n, m;cin >> n >> m;vector<int>ans;ans.push_back(1);for (int i = 2; i <= n; i++) {mult(ans, i);}int res = 0;for (auto i : ans) {if (i == m)res++;}cout << res << endl;
}int main() {dis_time();int t; cin >> t;while(t--)solve();return 0;
}

3.最大乘积

解题思路：对于一个数学结论，如果可以相同经量分成3的多少次方，但是这里不一样，由

可知，尽可能把数变的小，这样就多，乘积也就最大，即用贪心的思路去解题即可

#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;const int MAXN = 10003;   
const int MAXL = 100003;  
const int INF = 2147483647;struct BigNumber {int digits[MAXL]; int length;     BigNumber() : length(0) {memset(digits, 0, sizeof(digits));}BigNumber multiply(int num) {BigNumber result;for (int i = 1; i <= length; i++) {result.digits[i] = digits[i] * num;}for (int i = 1; i <= length + 10; i++) {result.digits[i + 1] += result.digits[i] / 10;result.digits[i] %= 10;if (result.digits[i]) {result.length = i;}}return result;}
};int main() {int n;cin >> n;double logValues[MAXN];for (int i = 1; i <= n; i++) {logValues[i] = log(i);}double dp[MAXN];int path[MAXN]; for (int i = 1; i <= n; i++) {dp[i] = -INF;}dp[0] = 0;for (int i = 1; i <= n; i++) {for (int j = n; j >= i; j--) {if (dp[j - i] + logValues[i] > dp[j]) {dp[j] = dp[j - i] + logValues[i];path[j] = j - i;}}}vector<int> decomposition;for (int p = n; p != 0; p = path[p]) {decomposition.push_back(p - path[p]);}sort(decomposition.begin(), decomposition.end());for (int num : decomposition) {cout << num << " ";}cout << endl;BigNumber product;product.length = 1;product.digits[1] = 1;for (int num : decomposition) {product = product.multiply(num);}for (int i = product.length; i >= 1; i--) {cout << product.digits[i];}cout << endl;return 0;
}

4.[NOIP 1998 提高组] 拼数

解题思路：按照ASCII码来排序，排序一下，输出即可

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;string s[21];int n;
bool cmp(const string &a,const string &b) { return (a+b > b+a);
}
int main(void) {cin >> n;for(int i=1;i<=n;++i) cin >> s[i];sort(s+1,s+n+1,cmp);for (int i=1;i<=n;++i) cout << s[i];return 0;
}

5.统计方形（数据加强版）

解题思路：找规律，对于每个格子，假设都为方形的右下角，对于正方形，有这个格子在内的正方形个数为min（x,y）,对于这个格子的所有的长方形（包括正方形）为x*y,既如此，遍历每个格子为右下角的情况，相加求解

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int main(){ll n,m,i,j,sum=0,sum1=0;cin>>n>>m;for(i=1;i<=n;i++){for(j=1;j<=m;j++){sum+=min(i,j);sum1+=i*j;}}cout<<sum<<" "<<sum1-sum<<endl;return 0;
}

6.P1618 三连击（升级版）

解题思路：这个就dfs,找全排列在A:B:C的条件下有多少个

#include<bits/stdc++.h>
#define ll long long
#define endl "\n"using namespace std;
void dis_time() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);
}
bool vis[10];
int num[11];
int a, b, c;
int key = 0;
void dfs(int x) {if (x > 9) {int num1 = num[1] * 100 + num[2] * 10 + num[3];int num2 = num[4] * 100 + num[5] * 10 + num[6];int num3 = num[7] * 100 + num[8] * 10 + num[9];if (num1 * b == num2 * a && num1 * c == num3 * a) {key = 1;cout << num1 << " " << num2 << " " << num3 << endl;}return;}for (int i = 1; i <= 9; i++) {if (!vis[i]) {vis[i] = true;num[x] = i;dfs(x + 1);vis[i] = false;}}
}void solve() {cin >> a >> b >> c;dfs(1); if (!key)cout << "No!!!" << endl;
}int main() {dis_time();solve();return 0;
}

6.P3654 First Step (ファーストステップ)

解题思路：对于这个题，可以直接对没列，每行统计就行，但是我最开始写的是dfs，计算出所有的可能然后/2,但是要特判k为1时

#include<bits/stdc++.h>
#define ll long long
#define endl "\n"using namespace std;
void dis_time() {ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
}
int ans = 0;
char graph[110][110];
int n, m, k;void dfs(int x, int y) {if (x >= k) {int key = 0;for (int i = x; i > x - k; i--) {if (graph[i][y] != '.') {key = 1;break;}}if (!key)ans++;}if (n - x >= k - 1) {int key = 0;for (int i = x; i <= x + k - 1; i++) {if (graph[i][y] != '.') {key = 1;break;}}if (!key)ans++;}if (y >= k) {int key = 0;for (int i = y; i > y - k; i--) {if (graph[x][i] != '.') {key = 1;break;}}if (!key)ans++;}if (m - y >= k - 1) {int key = 0;for (int i = y; i <= y + k - 1; i++) {if (graph[x][i] != '.') {key = 1;break;}}if (!key)ans++;}}void solve() {cin >> n >> m >> k;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> graph[i][j];}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (graph[i][j] == '.' && k != 1)dfs(i, j);}}if (k != 1)cout << ans / 2;elsecout << ans/4;}int main() {dis_time();solve();return 0;
}

6.P1149 [NOIP 2008 提高组] 火柴棒等式

解题思路：就是枚举出每个数字他们所需的火柴个数，然后暴力即可

#include<bits/stdc++.h>
#define ll long long
#define endl "\n"using namespace std;
void dis_time() {ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
}int num[2500] = { 6,2,5,5,4,5,6,3,7,6 };
void solve() {int n; cin >> n;n -= 4;for (int i = 10; i <= 2000; i++) {int temp = i;while (temp) {num[i] += num[temp % 10];temp /= 10;}}int ans = 0;int t = 0;for (int i = 0; i <= 1000; i++) {for (int j = 0; j <= 1000; j++) {int temp = i + j;if (num[i] + num[j] + num[temp] == n && i != j) {ans ++;}else if (num[i] + num[j] + num[temp] == n && i == j) {ans++; t++;}}}cout << ans - t / 2;}int main() {dis_time();solve();return 0;
}

7.P3799 小 Y 拼木棒

解题思路：对于这个题，有a = b = c + d,只要去找a,c就够了,也就是双层for循环，但是常规的双层for循环会时间超限，所有可以用离散化map来存储，元素和元素个数，然后求解

#include <bits/stdc++.h>
#define ll long long
#define endl "\n"using namespace std;const int MOD = 1e9 + 7;
void dis_time(){ios::sync_with_stdio(false);cin.tie(nullptr);
}void solve() {int n; cin >> n;unordered_map<int, int> freq;int max_len = 0;for (int i = 0; i < n; ++i) {int temp; cin >> temp;freq[temp]++;if (temp > max_len) {max_len = temp;}}ll ans = 0;for (auto& a : freq) {if (a.second < 2) continue;ll cnt_a = (ll)a.second * (a.second - 1) / 2 % MOD;for (auto& c : freq) {int d = a.first - c.first;if (d <= 0 || c.first >= d) continue;if (freq.count(d)) {ll cnt_cd = (ll)c.second * freq[d] % MOD;ans = (ans + cnt_a * cnt_cd % MOD) % MOD;}}if (a.first % 2 == 0) {int c = a.first / 2;if (freq.count(c) && freq[c] >= 2) {ll cnt_c = (ll)freq[c] * (freq[c] - 1) / 2 % MOD;ans = (ans + cnt_a * cnt_c % MOD) % MOD;}}}cout << ans << endl;
}int main() {dis_time();solve();return 0;
}