本周进行了标准模考训练
得分情况：
| 编号 | 算法 | 预期得分 | 实际得分 |
|---|---|---|---|
| A 比较数字 | 语法、数学 | 100 | 100 |
| B 修建灌木 | 桶计数 | 10 | 0 |
| C 最小成本 | dp动态规划 | 20 | 0 |
| D 赛跑 | 语法、数学 | 29 | 0 |
接下来是
题目解析：
A 比较数字
首先看到题目有一个大聪明思路：用字符串存 n ，然后把所有0变成1
但是后来我发现了，这个思路有时候会出错
例如：
n=1099， 的时候，我的思路输出1199，但是正确输出是1111，因为题目所需要最小的
于是我想到了另一个思路，遍历字符串，遍历到第一个0就把这个数位以及后面所有数字全部设为1，此思路AC
code
cin >> s;
int len = s.size();
for (i = 0 ; i < len ; i++) {
if (s[i] == '0' && !flag) {
s[i] = '1';
flag = 1;
}
if (flag) {
s[i] = '1';
}
}
cout << s;
B 修建灌木
第一眼看到，我想先排序再暴力，但后来我不知道怎么暴力了，就一直空着
后来输出个1没骗到分
正解：
跑一遍所有灌木，分别修建一下，看看用多少时间能修建成几棵灌木，存在t数组与cnt数组里面，最后跑一遍，看看cnt[i] >= k 的时候打擂台就好了
code
cin >> n >> k;
int mx = 0;
for (i = 1; i <= n; i++) {
int cnt = 0, x;
cin >> x;
mx = max(mx, x);
do {
qpzc[x].push_back(cnt);
x /= 2, cnt++;
} while (x >= 1);
}
for (i = 1; i <= mx; i++) {
if (qpzc[i].size() >= k) {
sort (qpzc[i].begin(), qpzc[i].end());
int sum = 0;
for (j = 0; j < k; j++) {
sum += qpzc[i][j];
qpzc[i].pop_back();
}
ans = min(ans, sum);
}
}
cout << ans << "\n";
我这数组名乱起的，不要在意这种细节
C 最小成本
进去的时候立即想到是搜索，但是他那个魔法我不会做
本来我想用那 20% 的特殊数据骗分的，结果我的read快读写在freopen前面所以TLE0分，呜呜呜呜呜呜呜
正解：（稍微有一点长）
对于前 20% 的数据由于 $ai,j$都相同，暴力求出起点到终点额最短路径即可。
对于后 20% 的数据，由于 n,m 的数据都很小，暴力枚举出所有转移的情况，然后对每一种情况跑一遍暴力。
对于 100% 的数据，
给定一个 n×m 的数字矩阵和常数 K，初始位于 (1,1) 点，只能通过向下或者向右走来到达 (n,m) 点。
存在某种操作，可以选择任意一行 ，将其所有列元素逆时针旋转 1 个单位，这个操作可以对任意行进行任意次（下面称这个操作为“旋转”）。
设最后总操作次数为 x，经过的所有元素和为 S，最后的代价就是 K×x+S，求出这个代价可能的最小值。
注意：所有“旋转”操作需要在出发之前确定，或者等效来讲，不可以在某一行上移动时，对该行进行“旋转”操作。
每一行的旋转与否、旋转的次数是彼此之间独立的。
任意一行的旋转次数不会超过 m−1 次，否则就是无用功。
那么就可以很自然的得到 DP 的定义：dp[i][j][k],k∈[0,m−1] 为 到达 (i,j) 点，当前行旋转了 k 次的最小代价。
那么对于某个点 (i,j)，其只会从 (i−1,j) 和 (i,j−1) 转移。
从 (i−1,j) 转移的时候，完全可以不用关心 i−1 行旋转了多少次，正如上文 “1” 所说，行与行之间的旋转操作是独立的，我只需要知道到达 (i−1,j) 这个点的最小代价即可。这一过程可以通过在 DP 过程中随手记录下最小值实现。
从 (i,j−1) 转移的时候，dp[i][j][k] 仅可从 dp[i][j−1][k] 转移，这一点在 “注意” 中已经指出。
code
#include<bits/stdc++.h>
using namespace std;
int T,n,m,k;
const int N=2e5+10;
typedef long long ll;
const ll INF=1e15+1;
ll a[300][300];
inline ll get(int i,int j,int add)
{
int tmp=(j+add)%m;
return tmp==0?a[i][m]:a[i][tmp];
}
inline void solve()
{
cin>>n>>m>>k;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
cin>>a[i][j];
vector<vector<vector<ll> > > dp(n+1,vector<vector<ll> >(m+1,vector<ll>(m+1,INF)));
vector<vector<ll>> mdp(n+1,vector<ll>(m+1,INF));
mdp[0][1]=mdp[1][0]=0;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
for(int x=0;x<=m-1;++x)
{
dp[i][j][x]=min(dp[i][j][x],mdp[i-1][j]+get(i,j,x)+1ll*x*k);//防止溢出
dp[i][j][x]=min(dp[i][j][x],dp[i][j-1][x]+get(i,j,x));
mdp[i][j]=min(mdp[i][j],dp[i][j][x]);
}
}
}
cout<<mdp[n][m]<<'\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
freopen("D.in","r",stdin);
freopen("D.out","w",stdout);
cin>>T;
while(T--)
{
solve();
}
}
D 赛跑
题目传送门（洛谷）
本来我想在 n = 2 的时候设ans为-1，每超过另一个人就++，否则–，最后如果ans是负数就输出0，可惜得了mvpWA0分
后来在考试快结束的时候我想到了正解，可惜每多少时间了所以每写完就结束了
题解传送门
洛谷题解
code
#include<bits/stdc++.h>
using namespace std;
signed main(){
int n,q;
cin >> n >> q;
vector<int> behind(n,-1); //贪心思路，默认一开始都在小信前面
int curr = 0;//当前跑多圈数
while(q--){
int p;
cin >> p;
if(p>0){
//确定某个人在小信后面，此时小信又超过了他，就需要跑一圈
if(behind[p] < curr) behind[p]=curr;//记录被小信超过的圈数
else {
//注意到，小信跑一圈，可以超过多人
//只有当被小信超过的圈数大于当前圈数，才需要跑一圈
curr++;
behind[p]=curr;
}
}
else {
p *= -1;
behind[p]=-1; //标记超过了小信，不在他后面
}
}
cout << curr;
return 0;
}
总结：
这一次比上一次有明显进步
进步
学会自己造样例测数据
上一次我第一题因为没注意细节导致WA50分，这一次，我在A题里说过了，我本来30分，后面测了一些自己造的样例而想到了没注意到的细节，改完就100分了