-
题目给出了不同状态之间的转化关系,想到可以构成一张有向图,在 \((a,b)\) 和 \((A_{a,b},B_{a,b})\) 之间连边。但是 \(k\) 的数量级十分巨大,直接跑 \(k\) 个点计算答案肯定是不行的。
-
事实上状态数最多只有 \(9\) 种,也就是最多只有 \(9\) 个点,图上一定存在一个环。我们只需要把图拆成两部分,一部分是环外的链(可能没有),一部分是环。链上的点直接统计;对于环上的点,先算出循环一圈的贡献,再计算一共循环多少圈以及最后不满一圈还需要额外走几步。跑一圈最多走 \(9\) 个点,直接统计即可。
-
连边其实没有必要,只需记录每个状态对应的编号。从 \(1\) 开始,对于第 \(i\) 个状态 \((a,b)\),若 \((A_{a,b},B_{a,b})\) 的编号小于 \(i+1\),就找到了环。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<utility>
#include<vector>
#include<queue>
#include<bitset>
#include<map>
#define int long long
#define FOR(i,a,b) for(register int i=a;i<=b;i++)
#define ROF(i,a,b) for(register int i=a;i>=b;i--)
#define mp(a,b) make_pair(a,b)
#define pll pair<long long,long long>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
inline int read();
typedef long long ll;
typedef double db;
const int N=1e5+5;
const int INF=0x3f3f3f3f;
int n,m,k;
int ans1=0,ans2=0;
map<pll,int>pos;
map<int,pll>pos2;
int Pos=0;
void toNum(int u,int v){
if(pos.find(mp(u,v))==pos.end())
pos[mp(u,v)]=++Pos,pos2[Pos]=mp(u,v);
}
int A[4][4],B[4][4];
int calcA(pll x){
if(x.fi==x.se) return 0;
if(x.fi==1&&x.se==3) return 1;
if(x.fi==2&&x.se==1) return 1;
if(x.fi==3&&x.se==2) return 1;
return 0;
}
int calcB(pll x){
if(x.fi==x.se) return 0;
if(x.fi==3&&x.se==1) return 1;
if(x.fi==1&&x.se==2) return 1;
if(x.fi==2&&x.se==3) return 1;
return 0;
}
signed main()
{
k=read();
int a=read(),b=read();
FOR(i,1,3) FOR(j,1,3) A[i][j]=read();
FOR(i,1,3) FOR(j,1,3) B[i][j]=read();
int temp=0;//环和链的分界点
while(1){
if(pos.find(mp(A[a][b],B[a][b]))!=pos.end()){
toNum(a,b),toNum(A[a][b],B[a][b]);
temp=pos[mp(A[a][b],B[a][b])];
break;
}
toNum(a,b),toNum(A[a][b],B[a][b]);
int t=a;
a=A[a][b];
b=B[t][b];
}
FOR(i,1,temp-1){//统计链上的贡献
ans1+=calcA(pos2[i]);
ans2+=calcB(pos2[i]);
k--;
if(k<=0) break;//走不到环,要及时退出
}
int f=0,loop=0,ans1l=0,ans2l=0,re;
FOR(i,1,Pos){//统计环上一圈的贡献
if(i<temp) continue;
if(i==temp) f++;
if(f==2) break;
loop++;//环长
ans1l+=calcA(pos2[i]);
ans2l+=calcB(pos2[i]);
}
re=k%loop;
ans1l=ans1l*(k/loop);
ans2l=ans2l*(k/loop);
FOR(i,1,Pos){//最后剩下不满一圈的贡献
if(i<temp) continue;
if(re==0) break;
re--;
ans1l+=calcA(pos2[i]);
ans2l+=calcB(pos2[i]);
}
printf("%lld %lld",ans1+ans1l,ans2+ans2l);
return 0;
}
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return f*x;
}
标签:return,int,&&,fi,include,CF863C,se
From: https://www.cnblogs.com/LHLeisus/p/17766779.html