F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
大视野在线测评-欢迎您
[ New Thread ]
Problem 1019 >> 暴力解法简单易懂
Expecto @ 2016-01-27 22:41:35
[ Quote ] [ Edit ] [ Delete ] 1#
RT ,f[x]=k*f[x-1]+b,
暴力解出f1=1,f2,f3,大功告成





#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<map>
using namespace std;
int main(){
int N;
cin>>N;
if (N==1) {
cout<<"1";
return 0;
}
map<char,int> m;
string s[7];
m['A']=0;m['B']=1;m['C']=2;
for (int i=0;i<6;i++){
cin>>s[i]; //cout<<m[s[i][0]]<<m[s[i][1]];
}
int f[5]={0};
for (int I=2;I<=3;I++){
int h[10][10]={0};
int t[30]={0};
t[0]=I;
for (int i=1;i<=I;i++) h[0][i]=I-i+1;
int last=0;
while (t[2]!=I && t[1]!=I){
for (int i=0;i<6;i++)
{
int tx=m[s[i][0]],ty=m[s[i][1]];
int x=h[tx][t[tx]],y=h[ty][t[ty]];
if ((last==x) || (x>y && y!=0) || (x==0)) continue;
h[m[s[i][1]]][++t[m[s[i][1]]]]=x;
t[m[s[i][0]]]--;
last=x;
f[I]++;
break;
}
}
if (I==N) {
cout<<f[I];return 0;
}
}
long long k=(f[3]-f[2])/(f[2]-1),b=f[2]-k,ans=f[3];
for (int i=4;i<=N;i++) ans=ans*k+b;
cout<<ans;
return 0;
}
lyhokia @ 2019-01-08 07:18:12
[ Quote ] [ Edit ] [ Delete ] 2#
请问为什么递推式是成f[x+1]=k*f[x]+b的形状啊
[Top] [Previous Page] [Next Page]

HOME Back