第二次周赛的题解，本次的题目以 3 为特征，ABC 题都与 3 有关，我觉得吧，不也挺好的吗.jpg

TA 那你可曾听说过我?

听说有些人是不会数 3 的。

输入一个平衡三进制整数，转换为十进制输出

平衡三进制以-1，0，1为基本数码，若用F表示-1，规定第一个非0的数码为F则是负数，为1则是正数

1F 表示为 2，即 $3^1\times1+3^0\times(-1)= 3-1 = 2$
F1 表示为 -2，即 $3^1\times(-1)+3^0\times1 = -3+1 = -2$
1F10 = $27-9+3=21$

输入格式

一个字符串(只含有F，1，0三种字符)，代表一个平衡三进制整数。

输出格式

平衡三进制整数对应的十进制整数

输入样例

FFF

输出样例

-13

数据范围与提示

保证对应的十进制整数在 16 位整型范围内

solution

其实跟二进制转换十进制是一个道理，只是相对的，幂底数被换成了 $3^n$ 而已，对应的计算方式与二进制转换十进制并无二致，使用循环遍历整个平衡三进制数的每一位，将其的值乘算相加即可。

正解代码如下。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int i, b = 0;
    string x;
    cin >> x;
    for (i = 0; i < x.size(); i++)
    {
        if (x[i] == '1')
            b = b + 1 * pow(3, x.size() - 1 - i);
        else if (x[i] == '0')
            continue;
        else if (x[i] == 'F')
            b = b - 1 * pow(3, x.size() - 1 - i);
    }
    cout << b << endl;
}

TB 你看我有几分像从前?

三进制是由 0,1,2 组成的序列，平衡三进制是由-1,0,1 组成的序列。为了方便，平衡三进制的-1 由 F 表示。输入一个三进制整数，如果为负数则开头为‘-’号输出对应的平衡三进制整数

输入格式

一个字符串，表示三进制整数(只含有0,1,2或负号)

输出格式

一个字符串，表示转换后的平衡三进制整数。

输入样例

-111

输出样例

FFF

数据范围与提示

参考文献
http://e-maxx.ru/algo/balanced_ternary
https://cp-algorithms.com/algebra/balanced-ternary.html
保证输入数据长度 $n<20$

solution

本段描述来自平衡三进制-OIWiki

根据本题的描述，我们将平衡三进制中的-1写作F。

该计数体系的负数表示起来很容易：只需要将正数的数字倒转即可(F 变成 1,1 变成 F)。

十进制正数	平衡三进制	十进制负数	平衡三进制
1	1	-1	F
2	1F	-2	F1
3	10	-3	F0
4	11	-4	FF
5	1FF	-5	F11

很容易就可以看到，负数最高位是 F，正数最高位是 1。

在平衡三进制的转转换法中，需要先写出一个给定的数 x 在标准三进制中的表示。

当 x 是用标准三进制表示时，其数字的每一位都是 0、1 或 2

从最低的数字开始迭代，我们可以先跳过任何的 0 和 1
如果遇到 2 应将其变成 F，下一位数字再加上 1
而遇到数字 3 应转换为 0 ，下一位数字再加上 1。

正解代码如下，由于进制转换会产生进位，故此处使用栈的数据结构能更方便地进行每一位的操作。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    char opre;
    cin >> opre;
    stack<char> s;
    if (opre != '-') //如果读入的第一个字符不是负数则需要将其压入栈内
        s.push(opre);
    string ans;
    while (cin >> c)
        s.push(c); //读入剩下的所有位，将其压入栈内
    int cache = 0; //创建变量存储进位信息
    while (s.size())
    {
        int top = s.top() + cache;
        cache = 0; //进位操作完毕，将其置零
        if (top == '2')
            ans += 'F',
                cache++;
        else if (top == '3')
            ans += '0',
                cache++;
        else
            ans += top;
        s.pop();
    }
    if (cache != 0)
        ans += '1'; //处理最后的进位信息，若不处理，则进位多出的最高位会丢失
    if (opre != '-')
        for (int i = ans.size() - 1; i >= 0; i--)
            putchar(ans[i]);
    else
        for (int i = ans.size() - 1; i >= 0; i--) //负数转换
        {
            if (ans[i] == '1')
                putchar('F');
            else if (ans[i] == 'F')
                putchar('1');
            else
                putchar(ans[i]);
        }

    return 0;
}

TC 我都说了这次的主题是 3

在 n 个小球中，有且只有一个小球的重量比其他小球轻。给你一个天平，你最少需要称多少次才能在最坏情况下找出重量不同的那个小球？

输入格式

一个整数， $n$

输出格式

输出称的次数

输入样例

输出样例

数据范围与提示

$0<n<2^{15}$

solution

n 次称量最多可以在 $\frac{3^n-3}{2}$ 个球中找到不同的球，

则我们直接循环除 3 即可找到答案。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n, m, count = 0;
    cin >> n;
    m = n;
    while (m)
        m = m / 3, count++;
    cout << ((pow(3, count - 1) == n) ? (count - 1) : count);
}

TD 1010: 三色堇

出题人你有病吧

三色堇就是这个小 fafa()

出题人发病了，我也来发病，嘿嘿……三色堇……嘿嘿……

print(5)

#include<stdio.h>
int main(int argc, char const *argv[])
{
	printf("5");
	return 0;
}

#include<iostream>
int main(int argc, char const *argv[])
{
	std::cout<<"5";
	return 0;
}

public class TestJava {
	public static void main(String[] args) {
		System.out.println("5");
	}
}

1	<?each "5";?>

puts "5"

package main
import "fmt"
func main(){
    fmt.Printf("5");
}

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <title>出题人有病吧</title>
  </head>
  <body>
    5
  </body>
</html>

<!DOCTYPE html>
<html lang="en">
<head>
	<meta charset="UTF-8">
	<title>出题人有病吧</title>
	<script type="text/javascript">
		document.write("5");
	</script>
</head>
<body>
</body>
</html>

TE 1011: A+B Problem

输入 a，b，输出一个整数，a 与 b 的和

数据范围与提示

$0<a,b<10^{1000}$

solution

这个就是高精度加法的裸题，这个 1000 长度的数显然不是任何类型能装下的，我们只能把它当做字符串处理。下面给一个运算符重载的模板，我的建议是善用搜索引擎，关键字可以搜高精度加法

#include <bits/stdc++.h>
using namespace std;
#define max(a, b) ((a) > (b) ? (a) : (b))
struct Data
{
    int a[100001], len;
    Data() //初始值
    {
        memset(a, 0, sizeof(a));
        len = 1;
    }
    Data operator+(const Data &A) const
    {
        Data B;
        B.len = max(len, A.len);
        for (int i = 0; i < B.len; i++) //边界需要注意
        {
            B.a[i] += A.a[i] + a[i];
            if (B.a[i] >= 10)
            {
                B.a[i] -= 10; //由于不会超过10，故用 -=10 代替 %10 效率更高
                B.a[i + 1]++; //进位
            }
        }
        if (B.a[B.len]) //考虑是否会进到B.len的下一位
            B.len++;
        return B;
    }
    void read() //读入函数
    {
        char d[100001];
        scanf("%s", d);
        int l = strlen(d);
        for (int i = 0; i < l; i++)
            a[i] = d[l - i - 1] - '0';
        len = l;
    }
    void write() //输出函数
    {
        for (int i = len - 1; i >= 0; i--)
            printf("%d", a[i]);
    }
};
Data A, B, C;
int main()
{
    A.read();
    B.read();
    C = A + B; //在进行Data之间的计算时可直接使用‘+’，原来int之间的加法运算不会被改变
    C.write();
    return 0;
}

TF 1012: 两只舔狗

舔狗往往会对于女神无条件的支持，他们的想法往往没法理解，当他们向往的女神是flower的时候，他们哪怕是变成float或者floor都可以，因为开头相同。

请你设计一个程序，帮助舔狗识别一下是不是跟自己的女神有开头相似的地方。

输入格式

第一行输入字符串 $S1$

第二行输入字符串 $S2$

第三行输入字符串 $S3$

字符串长度范围 $0< S1,S2,S3\le100$

输出格式

如果 $S1,S2,S3$ 有相同的开头字符子串，则输出最长的子串

若没有相同的开头字符子串，则输出WangWang!

输入样例

1
2
3

aniudeiuio
anicdah
aniquysdqdwet

输出样例

ani

数据范围与提示

样例中aniudeiuio
anicdah
aniquysdqdwet
其中三个字符串都具有共同的公共前缀ani

solution

舔狗舔到最后一无所有.jpg

这个题思路也很好办

有两只舔狗和一个女神，那么我们逐位去比较它们每一位上的值，当有一个与其他的不一样时跳出循环，在未跳出时记录最长的公共前缀即可

当然如果从一开始就无法舔到女神，就意味着公共前缀长度为 0，这个时候就得叫两声，挺好理解的。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string a, b, c, ans;
    cin >> a >> b >> c;
    int maxlen = max(a.size(), max(b.size(), c.size()));
    for (int i = 0; i < maxlen; i++)
        if (a[i] == b[i] && a[i] == c[i] && b[i] == c[i])
            ans += a[i];
        else
            break;
    cout << (ans.size() == 0 ? "WangWang!" : ans) << endl;
    return 0;
}

TG 1013: 国王排名

国家的丰饶程度，拥有的强者数量，以及国王本人是否像勇者一样强大，将这些综合起来进行的排名就是"国王排名"。

我们将这三个元素量化为数据，并限定最高分值均为 100，但是对于整体排名，我们应赋予相对应的权重，请输出"国王排名"排行榜上前三(若分数相同则输出所有符合条件的数据)的国家名称，总得分(保留 3 位小数)

权重计算值如下

国家的丰饶程度	强者数量	国王本人的力量
$x\%$	$y\%$	$z\%$

输入格式

第 $1$ 行,n,x,y,z，代表参与排名的国家数量，以及各项计算权值第 $2-n+1$ 行，每行四个数据，分别为国家名称，丰饶程度，强者数量，国王本人的力量

输出格式

"国王排名"排行榜上前三的国家名称(若分数相同则输出所有符合条件的数据)，以及该国家的总得分，保留 3 位小数。每输出一个国家换行。

如果有相同总分的国家，按字典序输出。

输入样例

4 70 20 10
Bob 20 30 40
Tom 90 40 50
Ansel 100 100 100
Alice 50 50 50

输出样例

1
2
3

Ansel 100.000
Tom 76.000
Alice 50.000

数据范围与提示

$0<n<60000$
国家名称长度 $n<50$

solution

这个题也是个纯纯的排序题，主要考的是一手结构体排序，我这里给一份 STL 的代码，唯一要注意的是题目中的条件，若是在第三名存在多个得分相同的国王，则要一并输出，我们可以从第三个开始往下搜索，这样就能达到我们的目的。

我希望大家都能掌握一下 STL 的sort方法，因为它实在是太好使了，这里面用的stable_sort就是sort方法的稳定版，不会改变元素内部的顺序。实乃 OI 利器。

#include <bits/stdc++.h>
using namespace std;
double n, x, y, z;
struct County
{
    string name;
    double a, b, c, sum;
    County(string Name, int A, int B, int C)
    {
        name = Name;
        a = A, b = B, c = C;
        sum = a * x + b * y + c * z;
    }
};
void PrintAns(vector<County> c)
{
    for (int i = 0; i < (c.size() <= 3 ? c.size() : 3); i++)
    {
        cout << c[i].name << ' '
             << fixed << setprecision(3) << c[i].sum << endl;
    }
    if (c.size() > 3)
    {
        int p = 3;
        while (p < c.size())
        {
            if (c[p].sum >= c[2].sum)
                cout << c[p].name << ' '
                     << fixed << setprecision(3) << c[p].sum << endl;
            else
                break;
            p++;
        }
    }
}
int comp(County a, County b)
{return a.sum > b.sum;}
int main()
{
    vector<County> county;
    int n;
    cin >> n >> x >> y >> z;
    x /= 100, y /= 100, z /= 100;
    while (n--)
    {
        string name;
        int a, b, c;
        cin >> name >> a >> b >> c;
        county.push_back(County(name, a, b, c));
    }
    stable_sort(county.begin(), county.end(), comp);
    PrintAns(county);
    return 0;
}

结语

出题人属于是集体犯病了

但是整体难度其实非常的低，没有什么特别绕的算法，也就只有最后一题弄了一个稍微难一点的排序算法，前面的除了高精度计算，用基本的循环其实都能做出来，希望大家能够认识到自己的欠缺，查漏补缺，然后往死里卷