先提醒一下！！！多测不清空，爆零两行泪！！！
模拟赛二补题报告
日期：\(2023\)—\(10\)—\(3\) 学号：\(S11390\)
一、总分：
\(T1\) 人员借调:\(30\) 分
\(T2\) 计算:\(30\) 分
\(T3\) 智能公交:\(50\) 分
\(T4\) 异或和:\(0\) 分
共：\(110\) 分
二、比赛过程
-
在第一题中，只想到了一种情况，其中有几种情况没有想到，读题也有些偏差，因此只想到了一种情况因此只得了 \(30\) 分。
-
在第二题中，想到了预处理的优化方法，但一直搞不出来，就没有继续用这样的方法了，最后就用暴力来进行了骗分，也是骗了 $30 $ 分。
-
在第三题中，也是没有想到正确的想法，因此也只能进行歪解骗分。用暴力双层循环的方式进行骗了 \(50\) 分。
-
在第四题中，没有啥思路，因此只能试着写一些，但直到最后也没有做出来，就得了 \(0\) 分。
三、题目分析
\(T1\) 人员借调
本题就主要找到几个模拟条件就能够做对了。本题需要前缀和思想，算出这一阶段耗费的时间。
假设小可需要在B地处理n件事情，耗时分别为 \(a_1, a_2, ..., a_n\) 分钟。
- 如果其中有一个时间超过 \(240\)。那么就一直在那里干，最后加上待机的 \(10080\) 和往返的 \(400\) 分钟。
- 只要时间相加不超过 \(240\) 那么就在那里一直干，最后加上往返的 \(400\) 分钟。
- 如果超过的话，将所有干完加上待机的 \(10080\) 和往返的 \(400\) 分钟，和干一段加上往返的 \(400\) 分钟，进行判断，取最小值，进行输出。
正解
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define swap(a, b) a ^= b, b ^= a, a ^= b
#define pb push_back
const int N = 1e6 + 10;
int n;
int a[N];
int sum;
bool flag;
int s[N];
int w;
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
s[i]=s[i-1]+a[i];
}
for(int i=1;i<=n;i++)
{
if(a[i]>=240)
{
flag=1;
}
}
if(flag)
{
sum=s[n]+10480;
cout<<sum<<endl;
return 0;
}
else
{
if(s[n]<240)
{
cout<<s[n]+400;
return 0;
}
int sum1=s[n]+400+10080;
int sum2=s[n]+400;
int l=1,r=1;
while(r<=n)
{
if(s[r]-s[l-1]<240)
{
r++;
}
else
{
sum2+=400;
l=r;
}
}
cout<<min(sum2,sum1)<<endl;
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
\(T2\) 计算
本题因为数据范围较大，所以要进行将前 \(5e6\) 的数据，先进行预处理，求出每个数位的和与乘积。
he[i]=he[i/10]+he[i%10] //求 \(5e6\) 数位和
ji[i]=ji[i/10]+ji[i%10] //求 \(5e6\) 数位积
通过暴力枚举，时间复杂度为 \(O(m-n)\)，只要枚举数位和与 \(k\)，相等的，取出数位积最大值，即为答案。
正解
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define swap(a, b) a ^= b, b ^= a, a ^= b
#define pb push_back
const int N = 5e6 + 10;
int sum[N]={0,1,2,3,4,5,6,7,8,9};
int s[N]={0,1,2,3,4,5,6,7,8,9};
int n,m;
int k,t;
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
for(int i=10;i<=N;i++)
{
sum[i]=sum[i/10]+sum[i%10];
s[i]=s[i/10]*s[i%10];
}
cin>>t;
while(t--)
{
int maxx=-10;
int maxn=0;
cin>>n>>m>>k;
for(int i=n;i<=m;i++)
{
if(sum[i]==k)
{
if(s[i]>maxx)
{
maxx=s[i];
maxn=i;
}
}
}
cout<<maxn<<" "<<maxx<<endl;
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
\(T3\) 智能公交
本体思路就通过双指针的思想，进行加和，我们通过模拟可以知道。
- 公交车的位置就在，\(v[cnt/2]\)，的地方，此时就为最短距离的点。
求出最短距离的点后。
- 根据双指针枚举，将这个点的左右两边的总距离进行加和，此时就为最短距离。
我们可以画个图。
这时，红色部分加上橙色部分，就为最短路径。
正解
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define swap(a, b) a ^= b, b ^= a, a ^= b
#define pb push_back
const int N = 1e6 + 10;
int n,m;
int a[N],b[N];
int v[N];
int cnt;
int sum;
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>a[i]>>b[i];
sum+=abs(b[i]-a[i]);
v[++cnt]=a[i];
v[++cnt]=b[i];
}
sort(v+1,v+cnt+1);
int pos=v[cnt/2];
for(int l=1,r=m*2;l<r;l++,r--)
{
sum+=(v[r]-v[l]);
}
cout<<pos<<" "<<sum<<endl;
// fclose(stdin);
// fclose(stdout);
return 0;
}
\(T4\) 异或和 \(01\)背包
这道题也是没有任何思路啊……
但是我们将这个代码分开来看，这道题就是用了 \(dp\)，背包来进行做的。但是，额，我好像也不是很会，那就给我这种蒟蒻来普及一下什么是背包吧。
背包
-
\(01\)背包
-
完全背包
-
多重背包
-
分布背包
-
…………
背包问题最主要的就是搞清楚数组表示的含义。
-
\(dp[i][j]\) 集合：为从前 \(i\) 个物品中选且所耗费重量 \(<=j\) 的所有选法。从中选出的最大价值。
-
\(w[i]\) 集合: 第 \(i\) 个物品的重量。
-
\(v[i]\) 集合：第 \(i\) 个物品的价值。
-
\(dp[i-1][j]\) 集合: 不含第 \(i\) 个物品。
-
\(dp[i-1][j-w[i]]+c[i]\) 集合：含第 \(i\) 个物品。
此时我们就可以进行状态转移了，这样就可以通过 \(dp[i-1]\) 层 来划分第 \(dp[i]\) 层。我们求含 \(i\) 和不含 \(i\) 中的最大值。
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i]);
这个就是二维背包问题的状态转移方程。
\(01\)背包二维数组
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define swap(a, b) a ^= b, b ^= a, a ^= b
#define pb push_back
const int N = 1e6 + 10;
int n,m;
int dp[1000][1000],w[1000],c[1000];
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>m>>n;
for(int i=1;i<=n;i++)
cin>>w[i]>>c[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(j>=w[i])
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i]);
else
dp[i][j]=dp[i-1][j];
cout<<dp[n][m]<<endl;
// fclose(stdin);
// fclose(stdout);
return 0;
}
接着，我们来进行优化，这里优化就是将二维数组转化成一维数组。
由于 \(f[i][j]\) 是由第 \(i-1\) 层推出的，就可以用它来存储第 \(i\) 层,所以我们其实只需要一层就行了。
dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
这个就是一维背包问题的状态转移方程。
原来我们的 \(j\) 是从小到大进行枚举的。但我们想要的是 \(f[i-1] [j-w[i]]\)。 此时只需要将 \(j\) 从大到小进行枚举即可,因为 \(j\) 从大到小的话,在计算 \(f[i]\) 时,就不需要进行判断是否超过背包容量。\(f[j-w[i]]\),就是第 \(i-1\) 层恰好符合状态转移方程。
\(01\)背包一维数组
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define swap(a, b) a ^= b, b ^= a, a ^= b
#define pb push_back
const int N = 1e6 + 10;
int c[N],w[N];
int dp[N];
int n,m;
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>m>>n;
for(int i=1;i<=n;i++)
cin>>w[i]>>c[i];
for(int i=1;i<=n;i++)
for(int j=m;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
cout<<dp[m]<<endl;
// fclose(stdin);
// fclose(stdout);
return 0;
}
\(T4\) 正解—但是我不会……
#include <bits/stdc++.h>
using namespace std;
int n, m, dp[2005][2050], num[2005][2005], dpp[2050], zz[2005];
// dp[i][j]表示看到前i个数，得到收益j至少所需要的数字个数,num[i][j]表示第i组j个数最大的收益值
vector<int> ve[2005];
int main() {
cin >> n >> m;//n个数字，最多选m个数字
for (int i = 1; i <= n; i++) {//输入n个数字
int x, y;//x是数字大小，y是所属集合编号
cin >> x >> y;
ve[y].push_back(x);//y集合的vector进入一个x
zz[y]++;//集合y的元素个数加一个
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 2047; j++) {
dp[i][j] = 1e9;
}
}
for (int zu = 1; zu <= 2000; zu++) {//遍历所有的组 ，一组一组的处理
if (zz[zu] != 0)//如果这一组的元素不为空
dp[1][ve[zu][0]] = 1; //第一个数 得到这一组的第一个数的收益值通过选择这一个数做到
for (int i = 2; i <= zz[zu]; i++) {//遍历这一组剩下的数字
// 前i个数，得到这个组的第i个数的收益可以通过直接选择这个数本身做到
dp[i][ve[zu][i - 1]] = 1;
for (int j = 1; j <= 2047; j++) {//遍历所有可能的数字（收益值）
if (dp[i - 1][j] != 1e9) {//如果前i-1个数字产生这个收益所用的最小数字个数存在（不为初始值）
//前i个数产生j这个数字（收益）的数字应用个数是前i个数和前i-1个数的使用数字个数的最小值
dp[i][j] = min(dp[i][j], dp[i - 1][j]);
//前i个数字产生j^这一组的第i个数字产生的新数字（收益）的数字使用个数是产生j的数字个数+1，和本来就有的数字个数的最小值
dp[i][j ^ ve[zu][i - 1]] =min(dp[i - 1][j] + 1, dp[i][j ^ ve[zu][i - 1]]);
}
}
}
for (int j = 1; j <= 2047; j++) {//遍历所有的收益
if (dp[zz[zu]][j] != 1e9)//如果这一组的数字个数对应产生j这个数字（收益），所使用的最小数字个数存在，即能异或出这个数字
//num数组记录这一组对应 这些数字个数 能得到的最大数字
num[zu][dp[zz[zu]][j]] = j;
}
for (int i = 1; i <= zz[zu]; i++) {//dp数组重新初始化一下
for (int j = 1; j <= 2047; j++) {
dp[i][j] = 1e9;
}
}
}
for (int i = 1; i <= 2000; i++) {//遍历所有组
for (int j = m; j >= 1; j--) {//能选的数字个数最多是m个
for (int k = 1; k <= zz[i];k++) { // 最后的枚举，只枚举到本组的个数
if (j >= k)//能选这个组的k个数字
//j个数字产生的数字收益最大值要么不变，要么就是往前推k个数，从第i组选k个数字的最大收益累加
dpp[j] = max(dpp[j], dpp[j - k] + num[i][k]);
}
}
}
cout << dpp[m];//输出m个数字的最大收益
}