2023.5.18 初二信息2班欢乐赛赛后总结

jiangmingshuai · 2023-05-20 12:00:45 · 个人记录

总叙：我打的颇为差劲的一次比赛

T1题目名称：T335940 大佬爱打牌

原题：P3078 [USACO13MAR]Poker Hands S

考点：差分/贪心

难点/易错点：要开 long long ，思路不好想

比赛时的自己的思路/想法：先算出这个数组的差分，如果出现了负数并且下一个数比零大，就说明出现了两边高中间低的情况，这时候就可以以这个负数为界限，将整一个的区间分为两个。最后把每个区间的最大值加起来(当然要减掉中间的交错部分)，就能得到结果了。在数组里实现就只用将差分数组中的正数加起来就行了。

得分情况： 100 Accepted 但耗了相当多的时间，大约有一小时左右吧，这是极为不合理的。

正确解法：同上

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
long long a[N],b[N],ans[N];
long long n,tot,xiaowei;
int q[N];
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=n;i++){
        b[i]=a[i]-a[i-1];
    }
    for(int i=1;i<=n;i++){
        if(b[i]>0) xiaowei+=b[i];
    }
    printf("%lld",xiaowei);
    return 0;
}

T2题目名称：T335898 大佬的差旅费

原题：P3406 海底高铁

考点：差分

难点/易错点：要开 long long ，要仔细读题

比赛时的自己的思路/想法：时间不够，跳了

得分情况：0 未提交

正确解法：城市中的铁路排成一字长蛇阵，所以可以当做数组来理解，这也是这题不是图论的原因。因为只有相邻的城市才有铁路相连，所以，如果想从 1号城市到 3号城市，就要先从 1号城市坐车到 2号城市,再从 2号城市坐车到 3号城市，这时候 1号铁路和 2号铁路都要走一次。综上所述，从 a 城市到 b 城市，就要把 a 到 b - 1 之间的城市都走一遍，这与差分的性质相符合，所以我们就可以用差分来求出每条铁路被走过的次数，最后比较买IC卡和不买IC卡的价格，得出最优解。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,m;
long long p[N];
long long a[N],b[N],c[N];
long long ci[N];
long long ans;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%lld",&p[i]);
    }
    for(int i=1;i<n;i++){
        scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
    }
    for(int i=1;i<m;i++){
        int x=min(p[i],p[i+1]),y=max(p[i],p[i+1]);
        ci[x]+=1,ci[y]-=1;
    }
    for(int i=1;i<n;i++){
        ci[i]+=ci[i-1];
    } 
    for(int i=1;i<=n;i++){
        if(c[i]+ci[i]*b[i]<a[i]*ci[i]) ans+=c[i]+ci[i]*b[i];
        else ans+=a[i]*ci[i];
    }
    printf("%lld",ans);
    return 0;
}

T3题目名称：T337356 大佬的课后任务

原题：P1387 最大正方形

考点：前缀和

难点/易错点：边界问题

比赛时的自己的思路/想法：做过的原题，遍历一个 k 作为边长，如果有以 ( i , j )为右下端点的正方形符合条件，就记下。最后输出 k 的最大值。

得分情况：0 TLE 因为最后太急了，所以遍历 k 的时候打错了

正确解法：同上

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N][N],b[N][N];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            b[i][j]=-b[i-1][j-1]+b[i-1][j]+b[i][j-1]+a[i][j];
        }
    }
    int nm=min(n,m);
    for(int k=nm;k>=1;k--){
        for(int i=k;i<=n;i++){
            for(int j=k;j<=m;j++){
                if(b[i][j]-b[i-k][j]-b[i][j-k]+b[i-k][j-k]==k*k){
                    cout<<k<<endl;
                    return 0;
                }
            }
        }
    }
    return 0;
}

T4题目名称：T335936 大佬的生日

原题：P1714 切蛋糕

考点：前缀和、单调队列

难点/易错点：要推墙开门（我不配想出思路）

比赛时的自己的思路/想法：刚开始觉得是前缀和，就每次都求出 a_i 到 a_{i+k} 的和，再输出最大的。但后来发现大佬不一定要吃完 k 个蛋糕，所以又删了打了一个单调队列的模板，但不知道怎么取值（直接遍历会超时），最后没有打出来

得分情况：0 未提交

正确解法：先算出前缀和维护一个单增队列（队尾最大），借此找出 a_i 到 a_{i-k} 之间最小的前缀和，相减再和本身比较，取出最大值就可以了。代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
long long n,m,ans;
long long a[N],q[N],b[N]; 
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        b[i]=b[i-1]+a[i];
    }
    long long h=1,t=0;
    for(int i=1;i<=n;i++){
        while(h<=t&&i-q[h]>m)h++;
        while(h<=t&&b[q[t]]>b[i]) t--;
        q[++t]=i;
        long long x=max(a[i],b[i]-b[q[h]]);
        ans=max(ans,x);
    }
    printf("%lld",ans);
    return 0;
}

总结：

这次比赛的策略没有把握好，第一题差不多打了一个小时，再加上开机开题目用了二十多分钟，最后又 ~~灵光一现~~ 脑子一抽先去做第四题，导致本来能稳稳拿分的两题丢了。以后一定不要偷懒，先把所有题目浏览一遍，避免再出现这种情况！！！

2023.5.18 初二信息2班欢乐赛 赛后总结

总叙：我打的颇为差劲的一次比赛

总结：

2023.5.18 初二信息2班欢乐赛赛后总结