第九次训练

今天训练仍然是整理过的题目，但我做的时候晚了点所以提交的题目也不多。这次做题卡在了求好数的题目上了，这个题目整理题目当天没能自己实现出来，但后来又看了一下过了，但没整理到博客中，我本来信心满满做这个题的，但改了好久测例都没过。
　　
　　我看过官方题解，也按照那个思路写了好久但没能实现，但后来想了一下，其实我简单版本的代码超时其实都在于求３的ｎ次方上，而其实需要用到的３的幂是连续的，只要用最普通的方法一点一点乘上来就能够省时。

#include<iostream>
#include<iomanip>
#include<fstream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<cstdio>
#include<map>
#include<vector>
#include<ostream>
#include<istream>
typedef long long ll;
using namespace std;
#define mod 1e9+7
#define PI acos(-1.0)
const ll maxn=2*1e3;
const int mx=(1<<20)+99;
ll n,m,k,a[maxn+10],flag,aans,ans;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    for(int o=1;o<=t;o++)
    {
        cin>>n;
        ans=0; aans=1;
        for(;ans<n;)
        {
            ans+=aans;
            aans=aans*3;
        }
        for(;aans;)
        {
            if(ans-aans>=n)
            ans-=aans;
            aans=aans/3;
        }
        cout<<ans<<endl;
    }
    return 0;
}

－
　　其实代码很简单，但因为当时拉下了３的０次方即１，所以总是不对。当然，这次的博客也就当补上自己的代码了。然后同样的是第四个题，官方题解确实也很好，但代码写起来费劲。
　　其实只需要将原本判断单个人需要的步数时的操作换成递归函数完成，然后再递归函数中完成每个人结果的记录以重用就好，比起在循环中要省劲。

#include<iostream>
#include<iomanip>
#include<fstream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<cstdio>
#include<map>
#include<vector>
#include<ostream>
#include<istream>
typedef long long ll;
using namespace std;
#define mod 1e9+7
#define PI acos(-1.0)
const ll maxn=2*1e5;
const int mx=(1<<20)+99;
ll n,m,k,a[maxn+10],flag,aans,ans[maxn+10];
void st(int i,int j)
{
    aans++;
    if(a[i]==j) { ans[i]=aans; return ; }
    else { st(a[i],j); ans[i]=aans; }
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    for(int o=1;o<=t;o++)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            ans[i]=0;
        }
        for(int i=1;i<=n;i++)
        {
            if(ans[i]==0)
            {
                aans=0;
                st(i,i);
            }
        }
        for(int i=1;i<=n;i++)
        {
            cout<<ans[i]<<" ";
        }
        cout<<endl;
    }
    return 0;
}