2018级算法第三次上机

文章目录

2018级算法第三次上机E C3-Zexal的浩瀚星辰思路代码 D C3-排座位思路代码 G C3-等差数列思路代码

E C3-Zexal的浩瀚星辰

思路

我们应该将损失费最高的火箭尽可能快的发射（贪心），所以考虑用优先队列存放不同火箭的损失费。然后每一天每一天地进行模拟即可，这样既方便计算损失的费用，又能很轻松的满足火箭都不能早于原定时间发射的要求。

代码

#include<queue> #include<cstdio> #include<cstring> #include<algorithm> typedef long long ll; using namespace std; const int N = 500010; ll ans; int n, k; int p[N];//存放第i天的损失 int tmp; priority_queue<int> pq;//存放被每个火箭每天的损失 int main() { while (scanf("%d%d", &n, &k) != EOF)//k为延迟时间 { ans = 0; for (int i = 1; i <= n; i++)//i代表第i天 { scanf("%d", &tmp); p[i] = p[i - 1] + tmp;//有点像前缀和 pq.push(tmp);//在第i天放入原定于第i天发射的火箭，这样就可以避免提前发射 if (i >= k + 1)//到达可以发射的天数（第k+1天）后，就可以发射火箭了 { p[i] -= pq.top();//在原定于第i天即以前发射的火箭中，将费用最大的火箭发射，自然也要将其费用减掉 pq.pop(); } ans += p[i];//损失的总费用加上第i天损失的 } for (int i = n + 1; i <= k; i++) ans += p[n];//有可能k比n还大 while (!pq.empty())//将剩余的火箭一天一天地发射 { p[n] -= pq.top(); ans += p[n]; pq.pop(); } printf("%lld\n", ans); } return 0; }

D C3-排座位

思路

一开始是照着讲评PPT的思路写的，结果疯狂TLE，根本停不下来，极度自闭。（后面才知道助教大大改了数据，好烦呐）

for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { for (int k = 1; k <= x && k <= i; k++) num[i][j][0] = (num[i - k][j][1] + num[i][j][0]) % mod; }

过了好久才发现问题所在：在上述TLE代码中关于k的循环，其实是对num[i-x][j][1]到num[i-1][j][1]的求和，利用类似于前缀和的处理方法其实可以更加高效地解决。 在AC代码中，b[i][j]代表在男生结尾以及有j个女生的前提下，队伍中还有1个，2个，，，j个男生这j中情况的排队方法之和，再利用: b[i-1][j]-b[i-x-1][j],代表了上述代码中${\sum }_{k=1}^{x}num[i-k][j][1]$，然后加一些条件判断语句即可，详见代码注解。

代码

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int mod = 1000007; const int N = 2010; const int M = 2010; int a[N][M];//a[i][j]表示以女生结尾并且有i个女生前提下，1个男 到 j个男 j种方案方案总和 int b[N][M];//b[i][j]表示以男生结尾并且有j个男生前提下，1个女 到 i个女 i种方案方案总和 int n, m, x, y; int main() { while (scanf("%d%d%d%d", &n, &m, &x, &y) != EOF) { memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); for (int i = 1; i <= x; i++) a[i][0] = 1;//初始化只有女生的情况 for (int j = 1; j <= y; j++) b[0][j] = 1;//初始化只有男生的情况 for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { if (i <= x) { a[i][j] = (a[i][j - 1] + b[i - 1][j]) % mod; //当i<=x时，b[i-1][j]就等于以女生结尾，有i个男生j个女生 } else { a[i][j] = (a[i][j - 1] + b[i - 1][j] - b[i - x - 1][j] + mod) % mod; /*[i - 1][j] - b[i - x - 1][j] 代表在有j个男生的并且以男生结尾的前提下，有i-x个女生到i-1个女生的方案总数。 这个方案总数恰好等于以女生结尾,有i个女生j个男生的方案书。 */ } if (j <= y) b[i][j] = (b[i - 1][j] + a[i][j - 1]) % mod; else b[i][j] = (b[i - 1][j] + a[i][j - 1] - a[i][j - y - 1] + mod) % mod; } int out = (a[n][m] - a[n][m - 1] + b[n][m] - b[n - 1][m] + mod + mod) % mod; printf("%d\n", out); } return 0; }

G C3-等差数列

思路

hint中提到不是子序列题，即可以将数组的相对顺序打乱，于是我们事先对得到的数据进行排序。设置状态为a[i][j] (i<j)，表示num[i]为等差数列倒数第二个数，num[j]为等差数列倒数第一个数的情况下，等差数列的长度。固定i，再引入tmp向前扫，j向后扫。num[tmp]+num[j]=2*num[i]时，num[tmp],num[i],num[j]局部又形成一个等差数列。详见代码注解。

代码

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 1e4 + 10; int n; int num[N]; short int a[N][N]; //a[i][j]表示 ：num[i]为等差数列倒数第二个数，num[j]为等差数列倒数第一个数 的情况下，等差数列的长度 short int ans; int main() { while (scanf("%d", &n) != EOF) { ans = 2;//至少为2，不能初始化为1 for (int i = 1; i <= n; i++)scanf("%d", &num[i]);//将输入数据从小到大进行排列 sort(num + 1, num + 1 + n); for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) a[i][j] = 2; for (int i = 2; i <= n - 1; i++) { int tmp = i - 1, j = i + 1;//i固定，tmp向前扫，j向后扫 while (tmp >= 1 && j <= n)//边界条件 { if(num[tmp] + num[j] == 2 * num[i])//若num[tmp],num[i],num[j]局部等差 { a[i][j] = a[tmp][i] + 1;//相当于以num[tmp]，num[i]结尾的等差数列，又在尾部增加了num[j]，于是等差数列就以num[i]和num[j]结尾了。 ans = max(ans, a[i][j]);//更新答案 tmp--; j++; } else if (num[tmp] + num[j] > 2 * num[i]) tmp--;//num[tmp]+num[j]过大，将tmp减小（因为num从小到大排列） else j++; } } printf("%hd\n", ans); } return 0; }