HDU - 5578

题意：

给出一个字符串，问你相邻最接近的俩个相同字母的间距

题解：

遍历一遍即可

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
string s;
map<char ,int > mp;
int main()
{
    int t;
    cin>>t;
    for(int cas = 1;cas <= t;cas++)
    {
        cin>>s;
        mp.clear();
        int l = s.length(),ans = 100005;
        for(int i=0;i<l;i++){
            if(mp[s[i]] == 0){
                mp[s[i]] = i;
            }
            else{
                ans = min(ans , i - mp[s[i]]);
                mp[s[i]] = i;
            }
        }
        printf("Case #%d: ",cas);
        if(ans == 100005){
            printf("-1\n");
            continue ;
        }
        printf("%d\n",ans);
    }
    return 0;
}

HDU - 5584

题意:

在一个正二维平面上，点(x,y)可以走到(x , y + lcm(x,y))或者(x + lcm(x,y) , y)

现给出一个终止点(xx,yy),问你起点有多少个？

题解：

我们可以发现当前位置是(x,y)时,如果x>y,那么当前位置一定是由(x1,y)走到的,如果x<y,当前位置一定是由(x,y1)走到的,由这点确定了路径的唯一性。

设gcd(x,y)=k,x=nk,y=mk,lcm(x,y)=nmk,那么下一步能走到(n(m+1)k,mk)或者(nk,m(n+1)k),并且由于n(m+1)与m互质,n与m(n+1)互质,所以下一步的gcd依然是k。

根据以上两点,就可以用逆推找出答案,每次都假设x>y,x=nk,y=mk,当前点就是由(x/(y/k+1),y)走到的,如果x不再是(y+k)的倍数(即:(y/k+1)*k的倍数),则表示不能再逆推。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    int t;
    ll n,m;
    cin>>t;
    for(int cas = 1;cas <= t; cas++)
    {
        int ans = 1;
        scanf("%lld%lld",&n,&m);
        ll gc = __gcd(n,m);
        if(n < m)
            swap(n,m);
        while( n%(m + gc) == 0 ){
            ans++;
            n = n/(m/gc + 1);
            if(n < m)
                swap(n,m);
        }
        printf("Case #%d: %d\n",cas,ans);
    }

    return 0;
}

HDU - 5573

题解：

构造题，有一颗满二叉树，编号1 ~ n，现在你要从根节点往下走，初始手里的值 V 为 0，每路过一个节点，可以选择 V 加上或者减去节点的编号值。问你走 k 层，值 V 能否达到 n。（题目保证可以达到）最后输出路径，怎么走的。

1 <= n <= 1e9,n <= 2^k

题解：

题目给出的数据范围非常巧妙，我们可以通过二进制，利用树的最左边的俩条路构造出来任意1-n的答案，我们只需要找到需要减少的值，然后二进制输出即可

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    int t;
    cin>>t;
    for(int cas = 1;cas <= t;cas++)
    {
        ll n,k,ans = 0;
        int flag = 0;
        cin>>n>>k;
        printf("Case #%d: \n",cas);
        ll cnt = ( 1<<(k) ) - 1 - n;
        if(cnt&1)
            cnt++;
        cnt /= 2;
        for(int i=1;i<k;i++){
            flag = cnt%2,cnt /= 2;
            printf("%lld " ,(1ll*1<<(i-1)));
            if(flag){
                printf("-\n");
                ans -= (1<<(i-1));
            }else{
                printf("+\n");
                ans += (1<<(i-1));
            }
        }
        printf("%lld +\n",n - ans);
    }
    return 0;
}