链接

最近回顾之前的比赛的时候发现了这一题,由于之前一直在刷dp类型的题目,导致我没有读题的时候认为这题是个dp类型的题目,但是我发现我找不到状态方程,果断放弃了这个想法...

之后我发现这一题根本不需要任何算法,相当于一个模拟过程了,我的思路是一条路走到死(开始向左或者向右一直走,设置两个指针li与ri来保存左右的目前的位置,如果此时的水滴数量大于等于10,则就把对应的指针进行的往左或者右的运动,最开做的时候忽略了很多东西,包括完成水滴合并的时候剩余向左或向右水滴的数量,之后才整理出ls=a[li]+ls-9,脑子不够聪明。 我还有一点错误是判断temp==2的时候忽略了此时左边或者右边的水滴以及合并完并且释放,导致了只有80%的通过率,出去溜了一圈之后恍然大悟哈哈哈。判断了一下此时是否两边存在水滴合并完毕的情况,那么可能有人问了,会不会出现li==-1&&ri==n的情况?答案是不可能的,如果这样的话就直接跳出循环了(大概吧...)

#include<bits/stdc++.h>
using namespace std;
#define int long long

void solve()
{
    int n,p;
    cin>>n>>p;
    vector<int> a(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    if(a[p-1]!=9)
    {
        cout<<"0 0"<<endl;
        return ;
    }//当目前的水滴不是9的情况直接跳出,我这里忽略10了但是问题不大
    int ls=1,rs=1,li=p-2,ri=p,temp=0;//ls与rs是当前左右游离水滴的数量,ri与li是两边的指针
    bool isl=1;//设置了一个bool类型的判断下一步的方向,其实类似于一个递归了,可以稍微简化一下写俩函数,但是我懒了...
    while(li!=-1||ri!=n)//这里是或,不能为且
    {
        if(isl)//向左边计算
        {
            if(a[li]+ls>=10&&li!=-1)
            {
                ls=a[li]+ls-9;
                rs++;
                isl=0;
                temp=0;
                li--;
            }
            else
            {
                isl=0;
                temp++;
            }
        }
        else//向右边计算
        {
            if(a[ri]+rs>=10&&ri!=n)
            {
                rs=a[ri]+rs-9;
                ls++;
                isl=1;
                temp=0;
                ri++;
            }
            else
            {
                isl=1;
                temp++;
            }
        }

        if(temp==2)//如何没有将temp重置,那么说明此时既不能往左也不能往右
        {
            if(li==-1&&ri!=n)//如果左边合并完毕
                cout<<ls<<" 0"<<endl;
            else if(ri==n&&li!=-1)//如果右边合并完毕
                cout<<"0 "<<rs<<endl;
            else//如果两边都没有合并完毕
                cout<<"0 0"<<endl;
            return ;
        }
    }
            cout<<ls<<" "<<rs<<endl;
}

signed main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    cin>>t;
    while(t--)
        solve();
    return 0;
}


**欢迎各路大佬hack我