总结
代码地址 | 题目地址 | 关键算法 | 难度 |
---|---|---|---|
Q1-Retype.cpp | Retype | 直接计算 | 简单 |
Q2-BoringNumber.cpp | Boring Numbers | 排列组合 | 简单 |
Q3-Rugby.cpp | Rugby | 最优解 | 较难 |
Q4-Friends.cpp | Friends | 最短路径+trik | 较难 |
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();
}
}
0
super post