提高组专题测验-算法进阶二总结

Tommy_Keen · 2021-06-23 08:25:01 · 个人记录

examinatime:\;3.5h

	T1	T2	T3	T4	sum
估分	0	0	0	10	10
得分	0	0	10	27	37

\textcolor{purple}{\text{T177771 修墙}}

题意：

这堵墙由 N 个宽度为一的砖块构成，其中第 i 块砖的高度为 hi。你需要执行下列操作让这 N 块砖的高度变得全部相等，且高度不能小于 H。

使一块砖的高度加一，这需要花费 A 分钟。
使一块高度为正的砖的高度减一，这需要花费 R 分钟。
使一块高度为正的砖的高度减一，另一块砖的高度加一，这需要花费 M 分钟。

给定 N,A,R,M,H ,你需要求出使所有砖的高度变得相同最少要花费的分钟数。

1<=N<=2*10^5,A,R,M<=10^,H,hi<=10^9

当局者发言：

考试时看到 3 个操作，贪心试过不可，于是考虑二分。二分答案的时候发现答案不具有单调性，但是瞬间意识到答案有一个极值点，且两边单调，考虑三分。但是三分的模板几乎已经忘了，转而写暴力。但是这题写不了暴力啊（至少我不会），所以猜了一个答案并打上样例。
后来知道是三分，直接断了肠，但在写的时候有一个问题： l 和 r 的值不确定。

错误： l = H, r = 1e18

正确： l = max(min(h_i),H), r = max(h_i) ，且当 H >= r 时，应当直接输出 \operatorname f(H)。
贴一个三分模板吧：

while(r-l >= 3) {
    int lmid = l+(r-l)/3;
    int rmid = r-(r-l)/3;
    if(f(lmid) < f(rmid)) r = rmid;
    else l = lmid;
}

旁观者发言：

三分的理由当局者发言已给出。在判断的函数里用到贪心：
1. 如果 M>=A+R ，显然操作 3 没有用处了，这个时候直接填到指定高度即可。
2. 如果 M<A+R ，那么应该尽量用操作 3 ，用完剩下的该补补，该去去。
long long
code：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+10;
int n,A,R,M,H,h[N];
int l = 1e18,r = 0;
void input() {
    scanf("%lld%lld%lld%lld%lld",&n,&A,&R,&M,&H);
    for(int i = 1; i <= n; i++) {
        scanf("%lld",&h[i]);
        l=min(l,h[i]);
        r=max(r,h[i]);
    }
    l=max(H,l);
}
int f(int x) {
    int tim = 0, upup = 0, down = 0;
    for(int i = 1; i <= n; i++) {
        if(x > h[i]) down += x - h[i];
        else upup += h[i] - x;
    }
    if(M >= A+R) {
        tim = upup * R + down * A;
    } else {
        if(upup > down) {
            int now = upup - down;
            tim = M*down + R*now;
        } else {
            int now = down - upup;
            tim = M*upup + A*now;
        }
    }
    return tim;
} 
int trisec() {
    if (H>=r){
        return f(H);
    }
    while(r-l >= 3) {
        int lmid = l+(r-l)/3;
        int rmid = r-(r-l)/3;
        if(f(lmid) < f(rmid)) r = rmid;
        else l = lmid;
    }
    int ans = 1e18;
    for(int i = l; i <= r; i++)
        ans = min(f(i),ans);
    return ans;
}
signed main() {
    input();
    printf("%lld",trisec());
    return 0;
}

\textcolor{lightgreen}{\text{T133431 草地浇水}}

题意：

长 L 米，宽 W 米的草坪里装有 n 个浇灌喷头。每个喷头都装在草坪中心线上（离两边各 W/2 米）。我们知道每个喷头的位置（离草坪中心线左端的距离），以及它能覆盖到的浇灌范围。

请问：如果要同时浇灌整块草坪，最少需要打开多少个喷头？

n<=15000,L,W<=10^9

当局者发言：

就这题，我调了 3h ，考试的时间全部砸进去，结果抱灵了。
考试的时候回忆贪心做法，画图得出要处理圆和方形草坪的长的交点，调了好久的精度，干脆把喷头的位置和范围全开double，问题才算结束。之后就是几段区间要覆盖整个区间的问题，按左端点排序去找右端点最大的（贪心策略及思路当时我是完全知道的），这里出了问题，至今没有解决。考后理解了正确做法，也知道我的做法肯定是错的，但还是说不上来我的错误做法为什么错了，这是心头之憾。

贴上错误部分code，希望以后的Tommy可以看出来：

#include <bits/stdc++.h>
using namespace std;
const int N = 15010;
int t,n;
double l,w;
struct node {
    double lef, rig, pos, r;
    bool operator < (const node &k) const {
        return rig < k.rig;
    }
} a[N];
int main() {
//  freopen("B.in","r",stdin);
//  freopen("out.txt","w",stdout);
    scanf("%d",&t);
    while(t--) {
        int ans = 0;
        scanf("%d%lf%lf",&n,&l,&w);
        double tmp = 0;
        for(int i = 1; i <= n; i++) {
            scanf("%lf%lf",&a[i].pos,&a[i].r);
            tmp = max(tmp,a[i].r);
        }
        if(tmp < w/2) {
            puts("0");
            continue;
        }
        double minn = l+1, maxn = 0;
        for(int i = 1; i <= n; i++) {
            double len = sqrt(pow(a[i].r,2)-pow(w/2,2));
            a[i].lef = a[i].pos - len;
            a[i].rig = a[i].pos + len;
            minn = min(minn,a[i].lef);
            maxn = max(maxn,a[i].rig);
        }
        if(minn > 0 || maxn < l) {
            puts("0");
            continue;
        }
        sort(a + 1, a + n + 1);
//      for(int i = 1; i <= n; i++) {
//          printf("%lf %lf %lf %lf\n",a[i].pos,a[i].r,a[i].lef,a[i].rig);
//      }
        for(int i = 1, pos = 0, las = 0; i <= n; i++) {
            if(a[i].lef <= a[las].rig) {
                if(a[pos].rig < a[i].rig) {
                    pos = i;
                }
            } else {
                las = pos;
                ans++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

这个code在算大样例的话，处理 lef 和 rig 的时候出现了 nan ，应该是根号下的数小于零了，这个我没判真的裂开。

旁观者发言：

思路的话当局者发言已经提及，这里不多阐述。
考后看了正确的 code ，有几个很妙的点罢：
1. 输入的时候 r<=w/2 的点直接不管，便可以避免“根号下的数小于零”的问题。而且把小于 0 和大于 l 的部分直接砍掉了，这一步考试的时候我没写。

for(int i = 1; i <= n; i++) {
        scanf("%lf%lf",&x,&r);
        if(r <= w/2) continue;
        double len = sqrt(r*r-w/2*w/2);
        a[++num].lef = max(0.0,x-len);
        a[num].rig = min(l,x+len);
    }

覆盖的时候的模拟真的《通俗易懂》， pos 指选到哪里了， p1 指现在选的左端点， p2 是正在物色的最大右端点。如果找了一圈 p2 还是 p1 的话，就不可能凑成了。（比我的判断方式好得多）

int pos = 1;
double p1 = 0,p2 = 0;
bool ok = 0;
while(p1 < l) {
        for(int i = pos; i <= num; i++) {
            if(a[i].lef > p1) {
                pos = i;
                break;
            }
            p2 = max(p2,a[i].rig);
        }
        if(p1 == p2) {
            ok = 1;
            break;
        }
        p1 = p2;
        ans++;
    }
    if(ok) puts("0");
    else printf("%d\n",ans);
}

真的心头之恨啊，思路完全正确，实现出了问题。

\textcolor{blue}{\text{T177818 移动玩具}}

题意：

在一个 5 * 5 的方框内摆放了若干个相同的玩具，某人想将这些玩具重新摆放成为他心中理想的状态，规定移动时只能将玩具向上下左右四个方向移动，并且移动的位置不能有玩具，请你用最少的移动次数将初始的玩具状态移动到目标状态。

数据保证有解。

弱化版：P4289 [HAOI2008]移动玩具

当局者发言：

这题 bfs 能看出来，问题是 T2 占了好多好多无效的时间，打算写 bfs 的时候已经只剩 30 min 了，故放掉。
这也能骗 10 pts

#include <bits/stdc++.h>
using namespace std;
int main(void){puts("18");}

旁观者发言：

双向 bfs 能加速，具体就是把图压成二进制数，然后决策的时候展开（~~好像也不具体~~）。
code（调了 2h 没调过版本）：

#include <bits/stdc++.h>
using namespace std;
const int MOV[4][2] = {{1,0},{0,1},{-1,0},{0,-1}}; 
const int N = 1<<26;
int vis[N],ans[N],st,nd;
bool a[10][10];
queue <int> q;
void input() {
    char tmp;
    for(int emm = 1; emm <= 5; emm++) {
        for(int i = 1; i <= 5; i++) {
            tmp = getchar();
            st = st<<1|(tmp-'0');
        }
        tmp =  getchar();
    }
    tmp = getchar();
    for(int emm = 1; emm <= 5; emm++) {
        for(int i = 1; i <= 5; i++) {
            tmp = getchar();
            nd = nd<<1|(tmp-'0');
        }
        tmp =  getchar();
    }
//  for(int i = 24; i >= 0; i--) {
//      cout<<(st&1);
//      st >>= 1;
//  }
//  cout<<endl;
//  for(int i = 24; i >= 0; i--) {
//      cout<<(nd&1);
//      nd >>= 1;
//  }
}
void double_bfs() {
    q.push(st);
    vis[st] = 1; ans[st] = 0;
    q.push(nd);
    vis[nd] = 2; ans[nd] = 0;
    int x, now;
    while(!q.empty()) {
        x = now = q.front();
        q.pop();
        for(int i = 5; i; i--) {
            for(int j = 5; j; j--) {
                a[i][j] = x&1;
                x >>= 1;
            }
        }
        for(int i = 1; i <= 5; i++) {
            for(int j = 1; j <= 5; j++) {
                if(a[i][j]) {
                    for(int k = 0; k < 4; k++) {
                        int nx = i+MOV[k][0];
                        int ny = j+MOV[k][1];
                        x = 0;
                        if(a[nx][ny] || nx<1 || nx>5 || ny<1 || ny>5) continue;
                        a[i][j] = 0; a[nx][ny] = 1;
                        for(int k = 1; k <= 5; k++) {
                            for(int p = 1; p <= 5; p++) {
                                x = (x<<1)+a[k][p];
                            }
                        }
                        a[i][j] = 1; a[nx][ny] = 0;
                        if(vis[x]+vis[now] == 3) {
                            printf("%d",ans[x]+ans[now]+1);
                            return;
                        }
                        if(vis[x]) continue;
                        vis[x] = vis[now];
                        ans[x] = ans[now]+1;
                        q.push(x);
                    }
                }
            }
        }
    }
}
int main() {
    input();
    if(st == nd) {
        puts("0");
        return 0;
    }
    double_bfs();
    return 0;
}

\textcolor{lightgreen}{\text{T159440 自动AC机}}

题意：

自动AC机会瞬间得出题目的正确做法，然后开始写程序。每秒，自动AC机的代码生成模块会有两种可能的结果：

1.写了 x 行代码；

2.删掉了之前写的 y 行代码。如果 y 大于当前代码长度，则相当于全部删除。

对于一个 OJ，存在某个固定的长度 n (n>0) ，一旦自动AC机在某秒结束时积累了大于等于 n 行的代码，它就会自动提交并 AC 此题，然后新建一个文件（即弃置之前的所有代码）并开始写下一题。

你在某个 OJ 上跑了一天的自动AC机，得到了很多条关于写代码的日志信息。你突然发现自己没有记录这个 OJ 的 n 究竟是多少。所幸你通过自己在 OJ 上的 Rank 知道了自动AC机一共切了 k 道题。请问 n 可能的最小值和最大值。

l<=10^5,k<=10^4,|xi|<=10^9

当局者发言：

时间都拿去 T2 的 debug 了，心想 T1 都没想出来，T2是我认为最简单的也没写对，那不知道 T4 有多难，故没看，粗看一眼也没看懂，所以也放弃了。
这个code也能骗 27 pts ，离谱。（ -1 的点就 27 pts ）

#include <bits/stdc++.h>
using namespace std;
int main(void) {
    int a,b,c,d,e,f;
    cin>>a>>b>>c>>d>>e>>f;
    if(a==4&&b==2&&c==2&&d==5&&e==-3&&f==9) {
        cout<<"3 7";
    } else puts("-1");
}

旁观者发言：

最小值，最大值，而且要知道 n 是多少才好办得多，考虑二分答案。找小于等于 k 的最大值和大于等于 k 的最小值。
code不必放了，说下有个部分很精彩：当找到的 n 去计算后的值不是 k 的话就不行。这个判断方法挺妙的。

if(check(findmax())!=k || check(findmin())!=k) puts("-1");

这次考试真是打脸，问题出在码力上。思路本来完全正确的，但一下键盘就是抱灵神。
还有，对于三分我也不太熟悉了，那时我记牢了理论，也是码的时候出的问题。怎么说呢，前期本来练得就比同窗少，然后导致现在机械效率和功率变慢，从而实现恶性循环。
现在想的是先把模板打熟，之后再刷题。

提高组专题测验-算法进阶二 总结

\textcolor{purple}{\text{T177771 修墙}}

当局者发言：

旁观者发言：

\textcolor{lightgreen}{\text{T133431 草地浇水}}

当局者发言：

旁观者发言：

\textcolor{blue}{\text{T177818 移动玩具}}

\textcolor{lightgreen}{\text{T159440 自动AC机}}

向太阳系的星辰大海挺进！

提高组专题测验-算法进阶二总结