1 条题解

  • 0
    @ 2024-6-19 15:19:17

    我们把kk颗球看做是一轮

    对于每一轮来说,如果在这一轮开始前,比分是a:b,那么这一轮结束后,比分是多少就是确定的。

    很明显可以看出来的一点是,开始时候两个人的当前局得分如果都>11>11的话,同时把两个人的分数减去同样的分数,使得两个人的分数都11\leq 11,是不会影响这一轮结果的。

    那么,我们开三个数组t,sa,sbt,sa,sb,分别记录:

    t[a][b]t[a][b]:最早什么时候,遇到这一轮开始前,比分是a:ba:b

    sa[a][b],sb[a][b]sa[a][b],sb[a][b]:这个时候,小明/小红一共赢了多少局。

    那么,当我下一次在timtim时候(此时总比分是A:BA:B)模拟遇到同样的a,ba,b时,就可以视作,模拟的过程是每timt[a][b]tim-t[a][b]一个周期,每个周期内,大局的得分都是Asa[a][b]:Bsb[a][b]A-sa[a][b]:B-sb[a][b]

    直接跳过这个超级大周期,然后模拟完剩余的时间即可。

    由于开始的比分最多只有12×12+1=14512\times 12+1=145种,因此模拟的总次数不会超过145×k145\times k

    #include <bits/stdc++.h>
    #define maxn 1000005
    #define ll long long
    #define mod 998244353
    using namespace std;
    ll t[17][17];
    ll sa[17][17],sb[17][17];
    ll n,k;
    string s;
    ll a=0,b=0,A=0,B=0;
    ll tim=0;
    void moni()
    {
    	for (int i=0;i<k;i++)
    	{
    		tim++;
    		if (s[i]=='A') a++; else b++;
    		if (max(a,b)>=11 && abs(a-b)>=2)
    		{
    			if (a>b) A++; else B++;
    			a=b=0;	
    		}
    		if (tim==n) {cout<<A<<":"<<B<<endl; exit(0);}
    	}
    }
    int main()
    {
    	cin>>n>>k; 
    	cin>>s;
    	memset(t,-1,sizeof(t));
    	t[0][0]=0;
    	while (true)
    	{
    		moni();
    		if (a==b && a>11) a=b=11;
    		if (min(a,b)>=11 && a!=b) {if (a>b) a=12,b=11; else a=11,b=12;}
    		if (t[a][b]!=-1) //曾经出现过 
    		{
    			ll da=A-sa[a][b],db=B-sb[a][b]; //deltaA,deltaB
    			ll zhouqi=tim-t[a][b]; //周期大小
    			ll quan=(n-tim)/zhouqi;
    			A+=da*quan; B+=db*quan;
    			tim+=quan*zhouqi;
    			if (tim==n) {cout<<A<<":"<<B<<endl; return 0;}
    			while (true) moni();
    		}
    		else
    		{
    			t[a][b]=tim; sa[a][b]=A; sb[a][b]=B;
    		}
    	}
    	return 0;
    }
    
    • 1

    信息

    ID
    1426
    时间
    1000ms
    内存
    512MiB
    难度
    9
    标签
    (无)
    递交数
    211
    已通过
    15
    上传者