笔试总时间2h，15单选 + 5不定选 花了40分钟！！！剩余80分钟做3道编程题，对于基础不好的我太难了！
选择题不用说了，每道题目都是正儿八经的专业题，基础好点的就没啥问题，然鹅我的基础不好！平衡二叉树忘记了！！！
编程题：
第一题：AC 赤裸裸的差分，线段树也可以，但是差分比较简单，
思路：比较简单吧，直接贴代码吧！
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int a[maxn];
int b[maxn];
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("a.txt", "r", stdin);
#endif
int t;
cin >> t;
while(t--) {
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
int len, n;
cin >> len >> n;
for(int i = 1; i <= n; ++i) {
int l, r;
cin >> l >> r;
b[l]++;
b[r+1]--;
}
for(int i = 1; i <= len; ++i) a[i] = a[i-1] + b[i];
for(int i = 1; i <= len; ++i) {
if(i < len) cout << a[i] << " ";
else cout << a[i] << endl;
}
}
return 0;
}
第二题：AC 每个人选一个满足自己角色值以上的，求最大总数量的人被提名为候选前提下的每个人的选择情况，不能选择就为-1
思路：看到数据量n <= 1000, n^2可以直接贪心，每个人按照val递增排序，每个觉得也按val递增排序，然后从最小的那个val开始寻找，找到第一个满足就跳出。下一个继续！
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define ios ios::sync_with_stdio(false),cin.tie(0);
const int maxn = 1010;
pii a[maxn];
pii b[maxn];
int ans[maxn];
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("b.txt", "r", stdin);
#endif
auto de = [](const pii& l, const pii& r){return l.second > r.second;};
auto en = [](const pii& l, const pii& r){return l.second < r.second;};
int t;
cin >> t;
while(t--) {
int n, m, val;
cin >> n >> m;
for(int i = 1; i <= n; ++i) {cin >> val; a[i] = {i, val};}
for(int i = 1; i <= m; ++i) {cin >> val; b[i] = {i, val};}
sort(a + 1, a + n + 1, en);
sort(b + 1, b + m + 1, en);
memset(ans, -1, sizeof(ans));
for(int i = 1; i <= n; ++i) {
int idx = -1;
for(int j = 1; j <= m; ++j) {
if(b[j].second == -1 || b[j].second < a[i].second) continue;
idx = j;
b[j].second = -1;
break;
}
if(idx == -1) break;
ans[a[i].first] = b[idx].first;
}
for(int i = 1; i <= n; ++i) {
if(i < n) cout << ans[i] << " ";
else cout << ans[i] << endl;
}
}
return 0;
}
第三题：
思路：
我的思路是：每一步都几下怎么走到下一步的。用一个状态记录f[i][j], 表示走j步到i的数量，枚举1 - m的步数状态，
然后要注意不能和前两步一样，因为记录了状态，直接排除相等的j就行，时间太短了，最后没有写完就到时间了！
对于动态规划的转移方程还不是很娴熟。继续学习吧！希望路过的大佬回复下你们的思路。学习！
代码：（后续参照别人的思路写出来的）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ios ios::sync_with_stdio(false),cin.tie(0);
const int maxn = 100005;
const int MOD = 1e9 + 7;
int f[maxn][8][8];
ll dfs(int n, int m, int pre1, int pre2) {
if(n <= 0) {
return (n == 0) ? 1 : 0;
}
if(f[n][pre1][pre2]) return f[n][pre1][pre2];
ll cnt = 0;
for(int i = 1; i <= m; ++i) {
if(i == pre1 || i == pre2) continue;
cnt += dfs(n-i, m, i, pre1);
}
f[n][pre1][pre2] = cnt % MOD;
return f[n][pre1][pre2];
}
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("c.txt", "r", stdin);
#endif
int n, m;
while(cin >> n >> m) {
memset(f, 0, sizeof(f));
cout << dfs(n, m, 0, 0) << endl;
}
return 0;
}
全部评论
(0) 回帖