2022年山东省赛总结

虽然三个人规定的是7：30楼下集合，但6点多就醒了，等到7点多一块去吃了早饭，这是我这学期第一次在食堂吃早饭，然后就是无聊的等待比赛开始，比赛前我也没去再看整理的板子，感觉只会徒增焦虑，所以就和队友聊些有的没的，偶尔也会说一些比赛的注意事项和策略；

比赛开始后，zsy负责读的是A~E，我负责读的是F~J，wtl负责剩下的题目，zsy读完A就给我讲了，我思考了一会感觉这不是签到题，他又说了句看数据范围可能是搜索，我一看数据范围才50，感觉搜索可以，然后我一直在想如何搜，中途wtl又来给我讲K题（不知道是不是我坐在中间的原因，他们俩读完题就找我说，一开始搞得我有点不知所措），我看了看K题感觉还是先做A好，我把搜索的思路给zsy说了遍后zsy去看别的题了，我又给wtl讲，他说可以打表但很快他就意识到没有那么简单，这搜索的思路时间复杂度直接爆炸，但是我那时候也想不出别的思路，我就说我先打表试一试，但是打代码的过程中遇到了很多问题，这搜索写的我都怀疑人生了，我看了看榜发现过的最多的是A题，加上我们前边大一的队伍过了这个题，顿时有点心慌，这时wtl想出了个思路，虽然比我那个合理点，但我感觉还是不行，我就先让他打着，我再想想，之后他也卡到了一个实现上，他让我帮忙去想那个实现，我也没想到，然后我就去重新分析了下题目，把n==5的算式写了出来，然后我从1写到十几只写了数字，然后发现有些数是可以抵消的，比如6，7，8，9；6+9==7+8，所以这四个数就相当于没有呀，接着我又枚举了很多，开始让wtl帮我写7和8的算式，然后我发现5,6,7,8可以把5后面的所有数都表示出来，然后我就开写了，但是wa了，wtl检查了一遍，然后我又去想4可不可以，没想到，最终以为是\n的错误改掉又交了一发还是wa了，这时候我们真是有点慌了，wtl说如果我找不出4的算式就把这题放了，我心里想着这题很大可能要寄了，但wtl找出来了(wtl牛逼)，交上去a了，过了两小时才把签到a掉，，，

A题代码

#include <bits/stdc++.h>
 
using namespace std;
int n;
string s[5]={"","3*5+4-1*2","1+3+4+5+6-2","1*2+3+4+6+7-5","1*2+3+6+7+8-4-5"};
int main()
{
    int n;
    cin>>n;
    if(n>=1&&n<4)
    cout<<"-1";
    else if(n==4){
        cout<<"(1+4)*3+2";
    }
    else{
        if(n%4==1){
            cout<<s[1];
            int cnt=0;
            for(int i=6;i<=n;i+=2){
                cnt++;
                if(cnt%2==1){
                    printf("+");
                    printf("%d",i);
                    if(i+1>n) break;
                    printf("-");
                    printf("%d",i+1);
                }
                else{
                    printf("-");
                    printf("%d",i);
                    if(i+1>n) break;
                    printf("+");
                    printf("%d",i+1);
                }
            }
        }
        if(n%4==2){
            cout<<s[2];
            int cnt=0;
            for(int i=7;i<=n;i+=2){
                cnt++;
                if(cnt%2==1){
                    printf("+");
                    printf("%d",i);
                    if(i+1>n) break;
                    printf("-");
                    printf("%d",i+1);
                }
                else{
                    printf("-");
                    printf("%d",i);
                    if(i+1>n) break;
                    printf("+");
                    printf("%d",i+1);
                }
            }
        }
        if(n%4==3){
            cout<<s[3];
            int cnt=0;
            for(int i=8;i<=n;i+=2){
                cnt++;
                if(cnt%2==1){
                    printf("+");
                    printf("%d",i);
                    if(i+1>n) break;
                    printf("-");
                    printf("%d",i+1);
                }
                else{
                    printf("-");
                    printf("%d",i);
                    if(i+1>n) break;
                    printf("+");
                    printf("%d",i+1);
                }
            }
        }
        if(n%4==0){
            cout<<s[4];
            int cnt=0;
            for(int i=9;i<=n;i+=2){
                cnt++;
                if(cnt%2==1){
                    printf("+");
                    printf("%d",i);
                    if(i+1>n) break;
                    printf("-");
                    printf("%d",i+1);
                }
                else{
                    printf("-");
                    printf("%d",i);
                    if(i+1>n) break;
                    printf("+");
                    printf("%d",i+1);
                }
            }
        }
    }
    return 0;
}

之后我又去读过的人比较多的H，读完之后我就和wtl讲了，zsy在敲k，我们发现H就是个偏模拟的题目，只要map记录一下就可以，就在我们快讨论完时zsy说k题过了(尽管k重测了，但当时这个k题的ac对我们之后过掉H题是至关重要的，所以zsy牛逼)，我们瞬间自信满满了再加上wtl说应该是有牌了(其实打完比赛后两题悬的不得了)我斗志更是起来了，我去写H写完代码一直调不对，wtl花了很大功夫才调过来(我的码风和他的不大一样),没找出错就交了一发，T了，wtl分析了一波发现是map自动排序的锅，然后准备去用unordered_map，但是unmap里面放pair或结构体都会报错，想了得有一阵子，期间也想了很多错误思路，最后wtl让我想一个哈希把矩阵映射到一维就可以用unmap了，我之前数据结构课好像学过并且做题也用过类似的思想把矩阵压缩，即把矩阵转化成一条链，这样就可以用一维了，然后又想到一个优化的清空记录的方式mp数组里存这个点在该时刻有多少人走到了这里，cnt表示这k个人走了多少个不同的点，vis[i]表示这cnt个点中第i个点的位置，vis数组更新的方式：如果第j个人走到了该点且该点没被走过，cnt++,vis[cnt]=该点的位置；mp数组更新的方式：第j个人走到了该点，mp[该点的位置]++，这样每次清空最坏情况也就是k个人走到了k个不同的点，也只是需要清空k次就可以，复杂度减了不少，检查代码没错后就交了，不出意外的a掉了，

H题代码

#include <bits/stdc++.h>
using namespace std;
int n,m,k,t,cnt;
pair<int,int>a[2000+1000];
int mp[5000006],vis[5000006];
char s[3005][3005];
int main()
{
    scanf("%d%d%d%d",&n,&m,&k,&t);
    for(int i=1;i<=k;i++)
    {
        scanf("%d%d",&a[i].first,&a[i].second);
    }
    for(int i=1;i<=k;i++)
    {
        scanf("%s",s[i]+1);
    }
    for(int i=0;i<=t;i++)
    {
        cnt=0;
        long long ans=0ll;
        for(int j=1;j<=k;j++)
        {
            if(i==0)
            {
                int temp;
                temp=(a[j].first-1)*m+a[j].second;
                if(mp[temp]==0) vis[++cnt]=temp;
                mp[temp]++;
                ans+=mp[temp]-1;
            }
            else
            {
                if(s[j][i]=='L') a[j].second--;
                else if(s[j][i]=='R') a[j].second++;
                else if(s[j][i]=='U') a[j].first--;
                else a[j].first++;
                int temp;
                temp=(a[j].first-1)*m+a[j].second;
                if(mp[temp]==0) vis[++cnt]=temp;
                mp[temp]++;
                ans+=mp[temp]-1;
                //cout<<mp[{a[j].first,a[j].second}]<<" "<<a[j].first<<" "<<a[j].second<<" "<<s[j][i]<<endl;
            }
        }
        printf("%lld\n",ans);
        for(int k=1;k<=cnt;k++) mp[vis[k]]=0;
    }
    return 0;
}

a掉之后我由于太过兴奋连拍了三掌以至于全机房的人都在看我，之后wtl和zsy去做e了，我冷静下来后还剩一小时，我问wtl对这个题的思路有把握吗，他说他还是不确定，我就去想e，发现和我之前做的题目很类似，之前的题目是和，这次的换成积了，然后我就把我的思路和他们讲了，但是我不会判断0的情况，可能当时比较着急了，没有想出来，他们想的也不是很对，然后这题直到比赛结束后也没做出来，比赛结束后我去看我的代码可以过百分之70的数据，加上判断0的之后可以过百分之80，所以我写的代码还是有问题的，今天才发现我的代码里少一个continiu，加上之后那百分之20就过了，x==0的解决思路：如果这一段乘积为0就符合条件，那么遍历过程中第一次在i位置遇到了0那就说明以这个0为后缀的区间都是满足条件的，比如1，2，3，4，0，5，那么[1,2,3,4,0],[2,3,4,0],[3,4,0],[4,0],[0]都是满足条件的个数也就是i,ans+=i，第i+1个若不是0，那么他还是可以和0前面的乘起来为0，即以a[i],a[i+1]为后缀的区间都是满足条件的，也就是[0,5],[4,0,5]等等，所以ans还可以加，ans+=i；如果到了j位置又遇到了0，那么按照之前的思路以a[j]为后缀的区间都符合条件,ans+=j，遍历到j+1就是以a[j],a[j+1]为后缀的区间都符合条件,ans还是可以加，ans+=j；这样依次类推就可以了；

E题代码

e题把这个题做掉之后再结合特判x==0的情况这题也就差不多了简单子段和 - 题目 - Daimayuan Online Judge

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int n,x,a[500005];
map<int,int>mp;
int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
int getinv(int a){return qpow(a,mod-2);}
signed main()
{
    int mul=1,ans=0;
    scanf("%lld%lld",&n,&x);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    int invx=getinv(x);
    if(invx==0){
        int p=0;
        for(int i=1;i<=n;i++){
            if(a[i]==0) p=i;
            ans+=p;
        }
        cout<<ans<<endl;
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        mul=mul*a[i]%mod;
        if(mul==0){
            mul=1;mp.clear();
            continue;
        }
        if(mp[mul*invx%mod]){ans+=mp[mul*invx%mod];}
        if(mul==x) ans++;
        mp[mul]++;
    }
    printf("%lld\n",ans);
    return 0;
}

这题我大体思路对，但是判断0的情况没想出来确实有点可惜了，但是我感觉在最后的那块时间没想出来也是正常的了，我们那时候都已经是强弩之末了，，，

以前训练的时候我们都是很快就做掉签到，然后其他的题目也是在三小时之内就做出来之后就笑看纷争了，但这次一开始签到就是我们不擅长的构造，之前我做上一年的省赛题时就被构造体卡了一晚上导致心态爆炸，这次多多少少也会有阴影，但幸好这次至少想出来了，没想出来之前我觉得这把又要铁了，打完之后队友也都这么想过，但是我们这次却比之前要冷静的多，我这次的心态竟然出乎意料的好，并没有因为签到不顺利而胡思乱想啥也做不出来，反而越到后面越冷静，我想他们也是一样的，毕竟我们比赛之前做了很多题，这些题给了我们底气，并且可能是因为这次的奖对我们太重要了，我们太需要一个证明自己的机会了，比完赛后我精神还是很好，一点都不累(虽然之后头和脖子一直在痛，，)，上传完文件之后我们和老师聊了很多，之后我们去看闭幕式了，在这时候wtl听说K题重测了，然后就去看我们的排名，我们被hack掉了，，，排名直接掉到铜尾，掉了30多名，然后我们开始慌了，虽然去掉打星的我们还是有铜牌，但是我还是很慌，还是打开闭幕式去看颁奖名单，开始宣布获奖名单时我们三个都很紧张，直到发现我们在其中，wtl指着屏幕喊我们的队名，我们顿时心就放松了，在机房里喊了好一阵，本来这个呐喊方式是为银牌准备的，但是因为这次经历铜牌也让我们很开心了，总的来说是有惊无险，排名和之前训练的时候差不多，也算是对得起从寒假到现在的付出；

这次就我们一个队拿奖了，但是我们前面的那个队伍也把a题给过了，过的比我们还快，其实他这个队是很有潜力的，他们如果暑假好好学的话一定比我们优秀很多，我们一开始的学习方法还不对，我感觉我真正按正确的方法学是在这学期开学后，虽然之前学习方法不对，但也锻炼了一些代码能力(题解也不是白看的)；

这次比赛能够拿到奖心里的压力减少了很多，因为上一次比赛我很弱而且还把题目读错导致整个队都崩了，这次我还是挺有参与感的，也没坑到他们，也算是弥补了上次的遗憾和过错，比较圆满了；

这次比赛需要感谢的人太多了，没有他们我也就不会有这么多时间来训练，也不会以良好的心态去参加比赛，总之我很幸运遇到这些人，希望以后我们也可以互帮互助

过去无法挽回，未来可以改变

继续加油吧！