大概 7：20做完选择 8：02就写完笔试了 出乎意料的顺利 除了第一题一开始忘了0 提交了两三次 后两道本地跑通 交上去就a了
T1 用a个5和b个0组成的最大的能被5整除的数 不可能输出-1
唯一不可能的情况就是 5的个数小于9 感觉是小学奥数题
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main() {
int n;
cin >> n;
int num5 = 0, num = 0;
for (int i = 0; i < n; i ++) {
int t;
cin >> t;
if (t == 5)
++num5;
if (t == 0)
++ num;
}
if (num5 < 9 && !num) {
cout << -1;
return 0;
}
if (num5 < 9 && num) {
cout << 0;
return 0;
}
int k = num5/9;
for (int i = 0; i < k*9; i ++) {
cout << 5;
}
for (int i = 0; i < num; i++) {
cout << 0;
}
} T2 1-n n头奶牛 m个特质 每个特质有k个区间 代表该区间内奶牛都拥有该特质 由小到大输出拥有全部特质的奶牛
就 数据很水 把区间按左端点右端点排个序 之后合并下 确保区间两两不相交就行 之后遍历区间每个特质+1 得到的数和特质数相等的奶牛就是要输出的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct dis{
int l, r;
} feature[11][101];
int featureP[11];
int featurePos[11];
int temp[1001];
bool comp(const dis &a, const dis &b) {
return a.l != b.l ? a.l < b.l : a.r < b.r;
}
int main() {
int q;
cin >> q;
while (q --) {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i ++) {
cin >> featureP[i];
for (int j = 0; j < featureP[i]; j ++) {
cin >> feature[i][j].l >> feature[i][j].r;
}
sort(feature[i], feature[i] + featureP[i], comp);
}
for (int i = 0; i < m; i ++) {
int ls = 0;
for (int j = 1; j < featureP[i]; j++) {
if (feature[i][j].l <= feature[i][ls].r) {
feature[i][ls].r = max(feature[i][j].r, feature[i][ls].r);
} else {
ls ++;
feature[i][ls] = feature[i][j];
}
}
featureP[i] = ls + 1;
}
memset(temp,0,sizeof(temp));
int ans = 0;
for (int i = 0; i < m; i ++) {
for (int j = 0; j < featureP[i]; j++) {
for (int k = feature[i][j].l; k <= feature[i][j].r; k ++) {
++temp[k];
if (i == m-1 && temp[k] == m) {
ans ++;
}
}
}
}
cout << ans << endl;
for (int i = 1; i <= n; i ++) {
if (temp[i] == m) {
cout << i << " ";
}
}
cout << endl;
}
} T3 奇怪的dp，很容易看出来是dp，方程其实也很好写，感觉数据也不是很强，我动规掌握极差但这道题也写出来了 我的dp方程是不考虑一步到位的所以需要在m>=n的时候+1但 感觉这并不是坑 但是还是提一嘴吧
要是他给的数据答案刚好是0我就无了 才发现自己是>mod才%mod
#include <iostream>
#include <cstdio>
#include <cstring>
#define mod 1000000007
using namespace std;
long long dp[100001][8][8];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i ++) {
for (int j = 1; j <= m; j ++) {
if (i == j)
continue;
dp[i+j][i][j] = 1;
}
}
for (int i = 3; i <= n; i ++) {
for (int k = 1; k <= m; k ++) {
if (k + 3 > i)
continue;
for (int j = 1; j + k + 1 <= i && j <= m; j ++) {
if (j == k)
continue;
for (int t = 1; t <= m && j + k + t <= i; t ++) {
if (t == k || t == j)
continue;
dp[i][j][k] += dp[i - k][t][j];
if (dp[i][j][k] > mod)
dp[i][j][k] %= mod;
}
}
}
}
long long ans = 0;
for (int i = 1; i <= m; i ++) {
for (int j = 1; j <= m; j ++) {
ans += dp[n][i][j];
if (ans > mod)
ans %= mod;
}
}
if (m >= n) {
++ ans;
}
cout << ans;
} 
全部评论
(7) 回帖