总结

Q1-Retype

/***********************************************
♡        Filename : 2020H-Q1-Retype.cpp
♡  
♡     Description : ---
♡          Author : Li Xudong
♡         Contact : 757264690@qq.com
♡         Created : 2020-11-27 00:24:16
***********************************************/
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;

typedef long long ll;
// 根据题意，直接模拟两种方法，输出min值即可。
const int maxnn = 1e9+20;
void solve()
{
    ll N, K, S;
    cin>>N>>K>>S;

    ll ans1,ans2;
    ans1 = K-1+1+N;
    ans2 = (K-1)+(K-S)+(N-S+1);
    cout<<min(ans1,ans2)<<endl;

}

int main()
{
    int t;
    cin >> t;
    for(int i=1; i<=t; ++i) {
        cout << "Case #" << i << ": ";
        solve();
    }
    return 0;
}

Q2-BoringNumber

/***********************************************
♡        Filename : 2020H-Q2-BoringNumber.cpp
♡
♡     Description : ---
♡          Author : Li Xudong
♡         Contact : 757264690@qq.com
♡         Created : 2020-11-26 22:22:28
***********************************************/
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <strstream>
using namespace std;

// 如果直接遍历，然后对每个数的每一位求奇偶性，则test1可以通过
// 但是test2数据太大，直接遍历则超时。
// 可以用组合数学的思想来做。
// 比如我们有一个数9734，我们计算1000到9734间一共有多少个符合题目的数字。
// 对于第1位（奇位），而小于9的奇数有4个，则如果以这4个奇数为第1位，则有4*5*5*5个数。
// 因为第1位为9，是奇数，因此可以考虑对第2位进行计算，
// 对于第2位（偶位），而小于7的偶数有4个，则如果以9为第一位，这4个偶数为第2位，则有1*4*5*5个数。
// 因为第2位为7，是奇数，因此结束计算（后面的数一定不符合）
//
// 那么0-9734中有多少个满足条件的数呢？
// 对于4位的数，可以按照上面的方法做；对于3位数，应该有5^3个；对于2位数，应该有5^2个；对于1位数，应该有5^1个。
//
// 那么比如计算123-9734中有多少个满足的数呢？
// 我们可以转化为求(0-9724)的个数减去(0-123)的个数。
//
// 其中，因为对于2位数和1位数，两者是重复的，减去之后为0，因此可以免去计算。


// L 和 R 范围是1-1e18，longlong比较保险
typedef long long ll;

// 1,2,3……之前（包括）一共有多少个偶数
int under_even[10]={1,1,2,2,3,3,4,4,5,5};
// 一共有少个奇数
int under_odd[10]={0,1,1,2,2,3,3,4,4,5};

// longlong转string
string lltoString(long long t)
{
    std::string result;
    std::strstream ss;
    ss <<  t;
    ss >> result;
    return result;
}

// 对每一位，计算 剩余的奇/偶数，然后乘以len-1个5
ll cnt_part(int res, int len)
{
    ll ans = 0;
    int i;
    ans = res;
    for(i=1; i<len; i++)
    {
        ans *= 5;
    }
    return ans;
}

// 计算个数，例如1000-1234之间符合条件的个数
ll cnt_ans(string num)
{
    int len = num.length();
    int i;
    // 奇偶位标记
    bool flag = false;
    ll ans = 0;
    ll res = 0;
    // 对每一位进行遍历
    for(i=0; i<len; i++)
    {
        flag = !flag;
        // 当前是奇数位
        if(flag)
        {
            // 计算可选择的奇数个数
            if((num[i]-'0')%2) res = under_odd[num[i]-'0']-1;
            else res = under_odd[num[i]-'0'];
            // 可选择数*5*5*5……
            if(res>0) ans += cnt_part(res, len-i);

            // 如果当前的数也是奇数，则可以对下一位进行计算
            if((num[i]-'0')%2)
                continue;
            // 如果当前数不是奇数，则后面的数都不是了，则停止遍历
            else
                break;

        }
        // 当前是偶数位
        else
        {
            if(!((num[i]-'0')%2)) res = under_even[num[i]-'0']-1;
            else res = under_even[num[i]-'0'];
            if(res>0) ans += cnt_part(res, len-i);

            if(!((num[i]-'0')%2))
                continue;
            else 
                break;
        }
    }
    // 因为之前判断可选择的奇偶个数的时候，没有包括这个数本身
    // 因此遍历到最后一位的时候，需要再特殊判断一下最后一位是否满足，若满足加1
    // i==len 遍历到最后一位
    // len%2 判断最后一位是奇数还是偶数
    if(i==len && len%2 && (num[len-1]-'0')%2)
        ans++;

    if(i==len && !(len%2) && !((num[len]-'0')%2))
        ans ++;

    return ans;
}
void solve()
{
    ll L,R;
    string num_L, num_R;
    long long ans1, ans2, ans3;
    int i,j;
    ans1 = ans2 = ans3 = 0;
    scanf("%lld %lld", &L, &R);
    num_L = lltoString(L-1);
    num_R = lltoString(R);
    ans1 = cnt_ans(num_L);
    ans2 = cnt_ans(num_R);

    // 若两个数的位数不一样
    // 比如，56-1575
    // 函数计算的是0-55之间的个数和1000-1575之间的个数
    // 因此对于后者，需要加上位数为3和位数为2时，符合条件的个数
    // 分别是5^3,5^2
    for(i=num_L.length(); i<num_R.length(); i++)
        ans3 += pow(5,i);

    printf("%lld\n", ans2+ans3-ans1);
}
int main()
{
    int t,T;
    scanf("%d", &T);
    for(t=1; t<=T; t++)
    {
        printf("Case #%d: ", t);
        solve();
    }
}

Q3-Rugby

/***********************************************
♡        Filename : 2020H-Q3-Rugby.cpp
♡  
♡     Description : ---
♡          Author : Li Xudong
♡         Contact : 757264690@qq.com
♡         Created : 2020-12-01 13:28:20
***********************************************/
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;


// 感觉像是考数学思维的一道题，反正看完题没有想到怎么做
// 官方的题解是：
// https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff49/000000000043b027#analysis
//
// x和y轴分开计算，计算每个人最终的理想x和理想y。
//
// 首先看y，最终所有的人要移动到同一行上，因此所有人都是垂直移动。
// 通过证明可以得到，如果理想的y是所有y的中位数，则垂直移动的总步数是最优的。
//
// 接下来看x，移动后保持原来的X轴从小到大顺序，可以保证总移动次数最少
// 那每个人的理想x应该是多少呢？
// 对于每个人，他前面有i个人，如果第一个人firstx的位置是x-i，则他将不需要移动
// 每个人都有一个理想的firstx, 分别是x0-0, x1-1, x2-2, x3-3...
// 则最优的firstx应该是所有的firstx的中位数
// 知道了最优的第一个人的位置，则后面所有人的位置也就知道了
const int maxn = 1e5+20;

int x[maxn];
int y[maxn];
long long solve()
{
    int N;
    memset(x, 0, sizeof(0));
    memset(y, 0, sizeof(0));
    int i, mid;
    int firstx, midy;
    long long ansx = 0;
    long long ansy = 0;

    scanf("%d", &N);
    for(i=0; i<N; i++)
        scanf("%d %d", &x[i], &y[i]);

    sort(x, x+N);

    // 每个人的理想firstx
    for(i=0; i<N; i++)
        x[i] -= i;


    sort(x, x+N);
    sort(y, y+N); 

    mid = N/2;

    // 第一个人的理想x位置
    // 每个人的理想y位置
    firstx = x[mid]; 
    midy = y[mid];
    for(i=0; i<N; i++)
    {
        ansx += abs(x[i]-firstx);
        ansy += abs(y[i]-midy);
    }
    return ansx+ansy;
}
int main()
{
    int t, T;
    scanf("%d", &T);
    for(t=1; t<=T; t++)
    {
        printf("Case #%d: %lld\n", t, solve());
    }
}

Q4-Friends

/***********************************************
♡        Filename : 2020H-Q4-Friends.cpp
♡  
♡     Description : ---
♡          Author : Li Xudong
♡         Contact : 757264690@qq.com
♡         Created : 2020-12-09 10:31:14
***********************************************/
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;


// 用传统的最短路径算法，只能test1通过，test2会超时
// 最终还是采用了官方给的解决方法
// 
// 总体思想是 求一个点到另一个点的最短距离 转换为 求一个集合到另一个集合的最短距离
//
// 即，将名字拆分成每一个字母。然后两个字母有边当且仅当两个字母存在于同一个名字当中。
// 之后按照floyd算法计算两个字母之间的最短距离。计算得到邻接矩阵。
//
// 下面是第一个测试集的邻接矩阵
/*
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 
A 0 1 - 1 2 - - 1 1 - 2 1 - 1 1 - - 2 - 1 2 2 - - 2 2 
B 1 0 - 1 2 - - 1 2 - 2 2 - 1 1 - - 2 - 2 2 2 - - 2 3 
C - - 0 - - - - - - - - - - - - - - - - - - - - - - - 
D 1 1 - 0 2 - - 1 2 - 2 2 - 1 1 - - 2 - 2 2 2 - - 2 3 
E 2 2 - 2 0 - - 2 1 - 1 1 - 1 2 - - 3 - 2 3 1 - - 3 1 
F - - - - - 0 - - - - - - - - - - - - - - - - - - - - 
G - - - - - - 0 - - - - - - - - - - - - - - - - - - - 
H 1 1 - 1 2 - - 0 2 - 2 2 - 1 1 - - 2 - 2 2 2 - - 2 3 
I1 2 - 2 1 - - 2 0 - 1 1 - 1 2 - - 3 - 1 3 1 - - 3 1 
J - - - - - - - - - 0 - - - - - - - - - - - - - - - - 
K 2 2 - 2 1 - - 2 1 - 0 2 - 1 2 - - 3 - 2 3 1 - - 3 2 
L 1 2 - 2 1 - - 2 1 - 2 0 - 2 2 - - 3 - 1 3 2 - - 3 1 
M - - - - - - - - - - - - 0 - - - - - - - - - - - - - 
N 1 1 - 1 1 - - 1 1 - 1 2 - 0 1 - - 2 - 2 2 1 - - 2 2 
O 1 1 - 1 2 - - 1 2 - 2 2 - 1 0 - - 1 - 2 1 2 - - 1 3 
P - - - - - - - - - - - - - - - 0 - - - - - - - - - - 
Q - - - - - - - - - - - - - - - - 0 - - - - - - - - - 
R 2 2 - 2 3 - - 2 3 - 3 3 - 2 1 - - 0 - 3 1 3 - - 1 4 
S - - - - - - - - - - - - - - - - - - 0 - - - - - - - 
T 1 2 - 2 2 - - 2 1 - 2 1 - 2 2 - - 3 - 0 3 2 - - 3 2 
U 2 2 - 2 3 - - 2 3 - 3 3 - 2 1 - - 1 - 3 0 3 - - 1 4 
V 2 2 - 2 1 - - 2 1 - 1 2 - 1 2 - - 3 - 2 3 0 - - 3 2 
W - - - - - - - - - - - - - - - - - - - - - - 0 - - - 
X - - - - - - - - - - - - - - - - - - - - - - - 0 - - 
Y 2 2 - 2 3 - - 2 3 - 3 3 - 2 1 - - 1 - 3 1 3 - - 0 4 
Z 2 3 - 3 1 - - 3 1 - 2 1 - 2 3 - - 4 - 2 4 2 - - 4 0 
*/
// 之后计算LIZZIE 到 BOHDAN 的最短距离，只需要依次遍历这两个名字中的字符，
// 然后查询两个字母之间的最短距离。最后从最短距离中取最小值即可。
//
// 思维很巧妙，但是真的没有想到这种方法，可能是经验不足吧。
//
// 进一步思考，能这样做的原因有两个：
// 1.单个名字，如果有重复字符，不会影响最终结果。
// 2.所有字母之间的权值都是1，不会出现两个字母之间有多个权值。
//


// 26个字母
const int alp = 26;
// 矩阵最大值
const int inf = 1e9;
const int maxn = 5e4+20;
void solve()
{
    int N, Q;
    string s[maxn];
    int i,j,k;
    int matrix[alp][alp];
    int ans=0;
    scanf("%d %d", &N, &Q);

    // 初始化
    for(i=0; i<alp; i++)
    {
        for(j=0; j<alp; j++)
        {
            matrix[i][j] = inf;

            if(i==j)
                matrix[i][j] = 0;
        }
    }


    for(k=1; k<=N; k++)
    {
        cin>>s[k];
        // 两个字母有边
        for(i=0; i<s[k].length(); i++)
        {
            for(j=i+1; j<s[k].length(); j++)
            {
                // 相同的字符，无需边
                if(s[k][i] == s[k][j])
                    continue;

                matrix[s[k][i]-'A'][s[k][j]-'A'] = 1;
                matrix[s[k][j]-'A'][s[k][i]-'A'] = 1;
            }
        }
    }
    // floyd 算法
    for(k=0; k<alp; k++)
    {
        for(i=0; i<alp; i++)
        {
            for(j=0; j<alp; j++)
            {
                if(i!=j && (matrix[i][k]+matrix[k][j] < matrix[i][j]))
                    matrix[i][j] = matrix[i][k] + matrix[k][j];
            }
        }
    }



    // 查询
    int left,right;
    for(i=0; i<Q; i++)
    {
        ans = inf;
        scanf("%d %d", &left, &right);
        j--;
        k--;
        for(j=0; j<s[left].length(); j++)
        {
            for(k=0; k<s[right].length(); k++)
            {
                ans = min(ans, matrix[s[left][j]-'A'][s[right][k]-'A']);
            }
        }
        if(ans == inf)
            printf("-1 ");
        else
            printf("%d ", ans+2);
    }
    printf("\n");
}

int main()
{
    int t, T;
    scanf("%d", &T);
    for(t=1; t<=T; t++)
    {
        printf("Case #%d: ", t);
        solve();
    }
}