梦.:如此短暂

SGU175 解题手记
　　看起来有这样的递推关系，用pos[n,q]表示有n个字符的word中第q个字符在phi(word)中的位置（也就是题目所求），k=n/2，则：

pos[1,1]=1
pos[n,q]=n-k+pos[k,k-q+1] (q<=k)
        =pos[n-k,n-k-q+1] (q>k)

　　Submit 1: WA on 3。没看清范围，错用了int，应该long。
　　Submit 2: WA on 3。……难道我对这个递推式的化简有错？交一遍朴素的。
　　Submit 3: WA on 3。算法是错的……不明白什么地方错了。算法思想是对的，但有一个地方错了：pos[n-k,n-k-q+1] (q>k)改成pos[n-k,n-q+1] (q>k)。
　　Submit 4: AC。太失败了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

//AC
#include <iostream>
using namespace std;
 
int main()
{
    long n,q,c(1);
    cin>>n>>q;
    while (n>1)
    {
        long k=n/2;
        if (q<=k)
        {
            c+=n-k; n=k; q=n-q+1;
        }
        else
        {
            q=n-q+1; n-=k;
        }
    }
    cout<<c<<endl;
    return 0;
}