第一次参加蓝桥杯进国赛了，今天更新一下参加国赛的心得和写出的题吧~
试题 A: 2022
思路：这题用的是三维背包，定义f[i][j][v]表示从前i个中选j个和为v的方案种数，那么可以得到状态转移方程，注意f数组开longlong，不然会爆int
选i： f[i][j][v] = f[i - 1][j - 1][v - i]
不选i: f[i][j][v] += f[i - 1][j][v]
答案：379187662194355221
代码如下：
#include <iostream>
using namespace std;
const int N = 2030;
typedef long long LL;
int n, m, k;
LL f[N][11][N];
int main()
{
cin >> n >> m >> k;
f[0][0][0] = 1;
for(int i = 1; i <= n; i ++ )
for(int j = 0; j <= m; j ++ )
for(int v = 0; v <= k; v ++ )
{
//选i
if(v - i >= 0 && j - 1 >= 0)
f[i][j][v] = f[i - 1][j - 1][v - i];
//不选i
f[i][j][v] += f[i - 1][j][v];
}
cout << f[n][m][k] << endl;
return 0;
}
试题 B: 钟表
思路：这题考试的时候一开始没看懂（不经常看这种表），白给...
答案：4 48 0
代码如下：
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
for(double s = 0; s <= 6; s ++ )
for(double f = 0; f < 60; f ++ )
for(double m = 0; m < 60; m ++)
{
double a = s / 12 + (f + m * 60 ) / (60 * 12);
double b = f / 60 + m / (60 * 60);
double c = m / 60;
double x = fabs(a - b) > 0.5 ? 1 - fabs(a - b) : fabs(a - b);
double y = fabs(b - c) > 0.5 ? 1 - fabs(b - c) : fabs(b - c);
if(fabs(x - 2 * y) < 1e-6)
cout << s << " " << f << " " << m << endl;
}
return 0;
}
试题 C: 卡牌
思路：这题聚聚们好像用的是二分，我用的是贪心用优先队列来处理，因为你能够凑出的套牌，取决于你将所有牌加入后，牌数最低的，那么用小顶堆存储pair关键字ai和这种牌能够使用空牌数然后循环处理m次，每次都将空白的牌加入最少的牌数中，最后看堆顶此时的牌数是多少即可。
代码如下：
#include <bits/stdc++.h>
//C
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6;
int n, m, a[N], b[N], res;
priority_queue<PII, vector<PII>, greater<PII> > q;
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for(int i = 1; i <= n; i ++ ) scanf("%d", &b[i]);
for(int i = 1; i <= n; i ++ )
q.push({a[i], b[i]});
while(m -- )
{
int x = q.top().first, y = q.top().second;
if(y != 0)
{
q.pop();
x ++, y -- ;
q.push({x, y});
}
else
{
// res = x;
break;
}
}
res = q.top().first;
printf("%d", res);
return 0;
}
试题 D: 最大数字
思路：一开始想用模拟分情况讨论，但是感觉这样分类会有亿点点麻烦，仔细思考了一下，10^17次方，也就是这个数最多会有17位。操作A和操作B优先对前面的数进行处理，将前面的数变成当前最大是会比去处理后面的数要好的，所以用dfs进行搜索，优先对前面的数进行操作A和操作B。对于一个数，要么一直加到最大然后break，要么一直加直到操作A用完,因为你对一个数先加后减是没有意义的(减法也是同理),那么我生成一个二进制子集，0表示对当前数+，1表示对当前数-。那么就可以枚举出所有情况，我在全部情况中去找到最大值即可。
代码如下：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
string s;
int A, B, p[100];
int k[100], n, b[100];
long long res;
void dfs(int u)
{
if(u == n)
{
int cnt1 = A, cnt2 = B;
for(int i = 0; i < n; i ++ )
b[i] = k[i];
for(int i = 0; i < n; i ++ )
if(p[i] == 0) //0表示+， 1表示-
{
while(cnt1 != 0)
{
if(b[i] == 9)
break;
b[i] ++ ;
cnt1 -- ;
}
}
else
{
while(cnt2 != 0)
{
if(b[i] == 9)
break;
b[i] -- ;
cnt2 -- ;
if(b[i] == -1) b[i] = 9;
}
}
long long sum = 0;
for(int i = 0; i < n; i ++ )
sum = sum * 10 + b[i];
res = max(res, sum);
return ;
}
for(int i = 0; i <= 1; i ++ )
{
p[u] = i;
dfs(u + 1); //生成一个二进制子集
}
}
int main()
{
cin >> s >> A >> B;
n = s.length();
for(int i = 0; i < n; i ++ )
{
k[i] = s[i] - '0';
}
dfs(0);
cout << res << endl;
return 0;
}
试题 E: 出差
思路：一道最短路的模板，在判断条件上加一个点权即可。
代码如下：
#include <iostream>
#include <cstring>
#include <algorithm>
//对
using namespace std;
const int N = 2020;
int n, m, g[N][N], w[N], dist[N];
bool st[N];
int dj()
{
memset(dist, 0x3f3f3f3f, sizeof(dist));
dist[1] = 0, w[1] = w[n] = 0;
for(int i = 1; i <= n; i ++ )
{
int t = -1;
for(int j = 1; j <= n; j ++ )
if(!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;
st[t] = true;
for(int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j] + w[t]);
}
return dist[n];
}
int main()
{
cin >> n >> m;
memset(g, 0x3f3f3f3f, sizeof(g));
for(int i = 1; i <= n; i ++ ) g[i][i] = 0;
for(int i = 1; i <= n; i ++ ) cin >> w[i];
while(m -- )
{
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c);
}
int t = dj();
cout << t << endl;
return 0;
}
试题 F: 费用报销
思路：这题读题不仔细，导致只能过30%的数据，寄，这题思路是用dp来做。将天数转化到1~365中去，w数组1~365中有不同的权值。我需要从这些点中选一些点，使得价值最大且不超过m。定义fi为决策完前i天的最大值，则
选, f[i] = f[i - k] + w[i]
不选，f[i] = f[i - 1]
应为数据范围为1000(没认真读题，以为不会重复)，所以肯定有很多股票在同一天，那么此时需要开vector数组来存储，然后再和vector数组中的股票进行决策比较。
具体细节看代码：
#include <iostream>
#include <vector>
using namespace std;
const int N = 500;
int n, m, k, f[N], vis[N], maxd, w[N];
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
vector<int> q[N];
struct state
{
int a, b, w;
}p[1010];
int getday(int x, int z)
{
int sum = z;
for(int i = 1; i < x; i ++ )
sum += days[i];
return sum;
}
int main()
{
cin >> n >> m >> k;
for(int i = 1; i <= n; i ++ ) cin >> p[i].a >> p[i].b >> p[i].w;
for(int i = 1; i <= n; i ++ )
{
int day = getday(p[i].a, p[i].b);
if(vis[day]) q[day].push_back(p[i].w);
else
{
vis[day] = true;
w[day] = p[i].w;
}
maxd = max(maxd, day);
}
for(int i = 1; i <= maxd; i ++ )
{
if(w[i] == 0) f[i] = f[i - 1]; //当前天没有股票，则只能继承i-1天的fi
else
{
f[i] = -(1 << 30); //便于转移
if(q[i].size() == 0) //当前天只有1张
{
if(f[i - 1] <= m)
f[i] = f[i - 1]; //不选该股票
if(f[i - k] + w[i] <= m)
f[i] = max(f[i], f[i - k] + w[i]); //选该股票(两者取最大)
}
else //当前天有多张
{
if(f[i - 1] <= m)
f[i] = f[i - 1];
if(f[i - k] + w[i] <= m)
f[i] = max(f[i], f[i - k] + w[i]);
for(int j = 0; j < q[i].size(); j ++ )
{
if(f[i - k] + q[i][j] <= m)
f[i] = max(f[i], f[i - k] + q[i][j]);
}
}
}
}
cout << f[maxd] << endl;
return 0;
}试题 G: 故障
不亏是G题，真的寄了，读了快半个小时没有读懂.......略过
试题 H: 机房
思路：这题用spfa打的暴力，时间复杂度为O(n*m)，拿分嘛，不丢人
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 500000;
int n, m, e[N], ne[N], h[N], w[N], idx, dist[N];
int num[N];
bool st[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int spfa(int S, int E)
{
queue<int> q;
memset(dist, 0x3f3f3f3f, sizeof dist);
memset(st, false, sizeof st);
q.push(S), dist[S] = w[S], st[S] = true;
while(q.size())
{
int t = q.front();
q.pop(), st[t] = false;
for(int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if(dist[j] > dist[t] + w[j])
{
dist[j] = dist[t] + w[j];
if(!st[j])
st[j] = true, q.push(j);
}
}
}
// for(int i = 1; i <= n; i ++ )
// cout << dist[i] << ' ';
// cout << endl;
return dist[E];
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof(h));
for(int i = 1; i < n; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
if(a == b) continue;
add(a, b), add(b, a);
num[a] ++ , num[b] ++ ;
}
for(int i = 1; i <= n; i ++ ) w[i] = num[i];
while(m -- )
{
int a, b;
scanf("%d%d", &a, &b);
cout << spfa(a, b) << endl;
}
return 0;
}试题 I: 齿轮
齿轮线速度角速度关系记不太清楚了，然后这题就没去仔细看
试题 J: 搬砖
想了一会儿，没想出来，暴力也没时间打了...
总结：这次国赛难度其实还好，但是丢了许多不该丢的分，第一次参加国赛，打完以为国三或者国优了，成绩下来居然国二靠中间的位置。这次国赛最鬼炸的就是填空题第一题，以往都觉得是送分题，但是这次居然一开始就来一道dp有点出乎意料(考试的时候想写10重循环枚举，但是想想可能的跑到我入土吧qaq，后桌的老哥小风扇一直嗡嗡嗡的响会不会就是跑这题导致的吧hhhh)。一开始压缩文件和网页出了点问题，结果拿到卷子已经过了10多分钟了，做出第一题已经快半个小时了，所以当时慌的雅痞，导致第二题没怎么看。然后费用报销那题dp，题目读错了，卒。还有机房那题，我看到题目就知道是acwing提高课里面的LCA，上个月想看来着，但是快考试那段时间有点摆烂，齿轮那题也是一分没拿，但这些都是后话了，也警示自己在考验来临前更要努力一些，在准备过程中还是收获到了很多，也磨练了自己的毅力，希望下次再接再厉。