A握手问题

【问题描述】
    小蓝组织了一场算法交流会议，总共有 50 人参加了本次会议。在会议上，
大家进行了握手交流。按照惯例他们每个人都要与除自己以外的其他所有人进
行一次握手（且仅有一次）。但有 7 个人，这 7 人彼此之间没有进行握手（但
这 7 人与除这 7 人以外的所有人进行了握手）。请问这些人之间一共进行了多
少次握手？
    注意 A 和 B 握手的同时也意味着 B 和 A 握手了，所以算作是一次握手。
【答案提交】
    这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分

这题数学知识或者是直接暴力 C(50,2)-C(7,2);

暴力代码如下

void solve()
{
    int ans = 0, sum = 0;
    for (int i = 1; i <= 49; i++)
    {
        for (int j = i + 1; j <= 50; j++)
        {
            ans++;
        }
    }
    for (int i = 1; i <= 6; i++)
    {
        for (int j = i + 1; j <= 7; j++) sum++;
    }
    cout << ans - sum << "\n";
}

答案为1204

B 小球反弹

【问题描述】
    有一长方形，长为 343720 单位长度，宽为 233333 单位长度。在其内部左
上角顶点有一小球（无视其体积），其初速度如图所示且保持运动速率不变，分
解到长宽两个方向上的速率之比为 dx : dy = 15 : 17。小球碰到长方形的边框时
会发生反弹，每次反弹的入射角与反射角相等，因此小球会改变方向且保持速
率不变（如果小球刚好射向角落，则按入射方向原路返回）。从小球出发到其第
一次回到左上角顶点这段时间里，小球运动的路程为多少单位长度？答案四舍
五入保留两位小数。
【答案提交】
    这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个小数，在提交答案时只填写这个小数，填写多余的内容将无法得分。

对于b题来说赛事思考许久，发现一个规律：要返回起点的时候，x和y轴需要所用时间一样，那么我们就可以推出
a * 343720 / 17 = b * 233333/15

即为 a * 343720 * 15 = b * 233333 *17

由于这题是一个填空题 直接2重for找到a和b即可。
但是这个求出的结果只是第一次到达其他顶点，但是题目说的是返回到原点，可以证明返回起点的小球，一定是由其他顶点到达出发点。所以求出来的结果为
2 * sqrt(a * a * 343720 * 343720 + b * b * 233333 * 233333)

暴力求出a b即可

void solve()
{
    int xx = 343720, yy = 233333;
    int ax = 15, ay = 17;
    for (int i = 1; i <= 10000; i++)
    {
        int ok = 1;
        for (int j = 1; j <= 10000; j++)
        {
            if (i * xx * 17 == j * yy * 15)
            {
                cout << i << " " << j << "\n";
                double x = sqrt(xx * xx * i * i + yy * yy * j * j) * 2;
                printf("%.2lf", x);
                ok = 0;
                break;
            }
        }
        if (ok == 0) break;
    }
}

答案1100325199.77

赛事写了暴力跑了2min没跑出来，才找规律的（bushi

C 好数

【问题描述】
    一个整数如果按从低位到高位的顺序，奇数位（个位、百位、万位 · · · ）上
的数字是奇数，偶数位（十位、千位、十万位 · · · ）上的数字是偶数，我们就称
之为“好数”。
    给定一个正整数 N，请计算从 1 到 N 一共有多少个好数。
【输入格式】
    一个整数 N。
【输出格式】
    一个整数代表答案。
【样例输入 1】
    24
【样例输出 1】
    7
【样例输入 2】
    2024
【样例输出 2】
    150
【样例说明】
    对于第一个样例，24 以内的好数有 1、3、5、7、9、21、23，一共 7 个。

【评测用例规模与约定】
    对于 10% 的评测用例，1 ≤ N ≤ 100。
对于 100% 的评测用例，1 ≤ N ≤ 107。

赛事看见就想到了数位dp，但发现这是🏀第一题，应该不难，于是就想着直接暴力7n。

dev上面跑的还挺快

代码如下

void solve()
{
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int x = i, ok = 1, num = 0;
        while (x)
        {
            num++;
            if (num % 2 == 1)
            {
                if ((x % 10) % 2 != 1) ok = 0;
            }
            else
            {
                if ((x % 10) % 2 != 0) ok = 0;
            }
            x = x / 10;
        }
        //cout << i << " ";
        ans += ok;
    }
    cout << ans;
}

D R 格式

【问题描述】
    小蓝最近在研究一种浮点数的表示方法：R 格式。对于一个大于 0 的浮点
数 d，可以用 R 格式的整数来表示。给定一个转换参数 n，将浮点数转换为 R格式整数的做法是：
1. 将浮点数乘以 2n;
2. 四舍五入到最接近的整数。
【输入格式】
    一行输入一个整数 n 和一个浮点数 d，分别表示转换参数，和待转换的浮
点数。
【输出格式】
    输出一行表示答案：d 用 R 格式表示出来的值。
【样例输入】
    2 3.14
【样例输出】
    13
【样例说明】
    3.14 × 2
    2 = 12.56，四舍五入后为 13。
【评测用例规模与约定】
    对于 50% 的评测用例：1 ≤ n ≤ 10，1 ≤ 将 d 视为字符串时的长度 ≤ 15。
    对于 100% 的评测用例：1 ≤ n ≤ 1000，1 ≤ 将 d 视为字符串时的长度
≤ 1024；保证 d 是小数，即包含小数点。

这题就高精度，赛事调试一个多小时。赛事代码太烂，下次再补题解。
看到考察高精度，直接懵了，根本想不到，全靠自己推到

E 宝石组合

【问题描述】
    在一个神秘的森林里，住着一个小精灵名叫小蓝。
有一天，他偶然发现了一个隐藏在树洞里的宝藏，里面装满了闪
烁着美丽光芒的宝石。这些宝石都有着不同的颜色和形状，但最引人注目的是它们各自独特的 “闪亮度” 属性。

每颗宝石都有一个与生俱来的特殊能力，可以发出不同强度的闪光。小蓝共找到了N 枚宝石，第 i 枚宝石的 “闪亮度” 属性值为 Hi，
小蓝将会从这N枚宝石中选出三枚进行组合，组合之后的精美程度 S 可以用以下公式来衡量：
S = HaHbHc·LCM(Ha, Hb, Hc)/( LCM(Ha, Hb) · LCM(Ha, Hc) · LCM(Hb, Hc) )
其中 LCM 表示的是最小公倍数函数。
    小蓝想要使得三枚宝石组合后的精美程度 S 尽可能的高，请你帮他找出精
美程度最高的方案。如果存在多个方案 S 值相同，优先选择按照 H 值升序排列
后字典序最小的方案。
【输入格式】
    第一行包含一个整数 N 表示宝石个数。
第二行包含 N 个整数表示 N 个宝石的 “闪亮度”。
【输出格式】
    输出一行包含三个整数表示满足条件的三枚宝石的 “闪亮度”。
【样例输入】
    5
    1 2 3 4 9
【样例输出】
    1 2 3
【评测用例规模与约定】
    对于 30% 的评测用例：3 ≤ N ≤ 100，1 ≤ Hi ≤ 1000。
    对于 60% 的评测用例：3 ≤ N ≤ 2000。
    对于 100% 的评测用例：3 ≤ N ≤ 105，1 ≤ Hi ≤ 105。

对于此题来说相当于三个数 a * b * c * lcm(a,b,c) /( lcm(a,b) * lcm(a,c) * lcm(b,c) );
当时发现三个数互质的时候答案一直是1，于是大胆猜测，这个答案就是gcd(a,b,c)的值，然后打表for循环进行判断。更加证实了我的猜想。

猜想代码

int lcm(int a, int b)
{
    return a * b / __gcd(a, b);
}
void solve()
{
    for (int i = 1; i <= 50; i++)
    {
        for (int j = 1; j <= 50; j++)
        {
            for (int k = 1; k <= 50; k++)
            {
                int x = i * j * k * lcm(i, lcm(j, k));
                int y = lcm(i, j) * lcm(i, k) * lcm(j, k);
                x = x / y;
                cout << x << " " << __gcd(i, __gcd(j, k)) << "\n";
            }
        }
    }
}

那这样就直接求的是最大gcd(a[i],a[j],a[k])，里面的最小的三个数

代码如下

int a[N], b[N];
vector<int> g[N];
int n;
void solve()
{
    cin >> n;
    int ma = 0;
    for (int i = 1; i <= n; i++) cin >> a[i], b[a[i]]++, ma = max(ma, a[i]);
    sort(a + 1, a + 1 + n);
    for (int i = 2; i <= ma; i++)
    {
        for (int j = i; j <= ma; j += i)
        {
            for (int x = 1; x <= b[j]; x++)
            {
                if (g[i].size() >= 3) break;
                g[i].push_back(j);
            }
        }
    }
    int ans = 1;
    for (int i = ma; i >= 2; i--)
    {
        if (g[i].size() >= 3)
        {
            ans = i;
            break;
        }
    }
    if (ans == 1)
    {
        cout << a[1] << " " << a[2] << " " << a[3] << "\n";
        return;
    }
    cout << g[ans][0] << " " << g[ans][1] << " " << g[ans][2];
}

    for(int i=2;i<=n;i++)
    {
        for(int j=i;j<=n;j+=i)
    }
这个时间复杂度为nlogn

利用这个代码来求max gcd 同时又保证了最小的三个数
希望🏀杯别卡vector

F 数字接龙

【问题描述】
    小蓝最近迷上了一款名为《数字接龙》的迷宫游戏，游戏在一个大小为
N × N 的格子棋盘上展开，其中每一个格子处都有着一个 0 . . . K − 1 之间的整数。游戏规则如下：
    1. 从左上角 (0, 0) 处出发，目标是到达右下角 (N − 1, N − 1) 处的格子，每一
步可以选择沿着水平/垂直/对角线方向移动到下一个格子。
    2. 对于路径经过的棋盘格子，按照经过的格子顺序，上面的数字组成的序列要满足：
    0, 1, 2, . . . , K − 1, 0, 1, 2, . . . , K − 1, 0, 1, 2 . . . 。
    3. 途中需要对棋盘上的每个格子恰好都经过一次（仅一次）。
    4. 路径中不可以出现交叉的线路。例如之前有从 (0, 0) 移动到 (1, 1)，那么再
从 (1, 0) 移动到 (0, 1) 线路就会交叉。
为了方便表示，我们对可以行进的所有八个方向进行了数字编号，如下图2 所示；
因此行进路径可以用一个包含 0 . . . 7 之间的数字字符串表示，如下图 1
是一个迷宫示例，它所对应的答案就是：41255214。
现在请你帮小蓝规划出一条行进路径并将其输出。如果有多条路径，输出字典序最小的那一个；如果不存在任何一条路径，则输出 −1。

【输入格式】
    第一行包含两个整数 N、K。
接下来输入 N 行，每行 N 个整数表示棋盘格子上的数字。
【输出格式】
    输出一行表示答案。如果存在答案输出路径，否则输出 −1。
【样例输入】
3 3
0 2 0
1 1 1
2 0 2
【样例输出】
41255214
【样例说明】
    行进路径如图 1 所示。
【评测用例规模与约定】
    对于 80% 的评测用例：1 ≤ N ≤ 5。
    对于 100% 的评测用例：1 ≤ N ≤ 10，1 ≤ K ≤ 10。

本题就是简单的dfs但是要判断交叉这个问题，所以我使用四维数组进行判断交叉。ss[x][y][ax][ay] 表示xy坐标到达axay。

代码如下

int dx[8]={-1,-1,0,1,1,1,0,-1},dy[8]={0,1,1,1,0,-1,-1,-1};
int n,k;
bool st[101][101],ss[11][11][11][11];
int a[101][101];
vector<string> s;
void dfs(int x,int y,string q)
{
    if(x==n-1&&y==n-1)
    {
        if(q.size()==n*n-1) s.push_back(q);
        //一定是需要n*n-1的长度
        return;
    }
    for(int i=0;i<8;i++)
    {
        int ax=x+dx[i],ay=y+dy[i];
        if(ax<0||ay<0||ax>=n||ay>=n) continue;
        if((a[ax][ay])!=(a[x][y]+1)%k) continue;
        if(!st[ax][ay]&&i%2==0)
        {
            st[ax][ay]=1;
            char qq=i+'0';
            dfs(ax,ay,q+qq);
            st[ax][ay]=0;
        }
        else if(!st[ax][ay]&&i%2==1&&!ss[x][y][ax][ay])
        {
            // 只有i为奇数的时候才会有交叉
            st[ax][ay]=1;
            char qq=i+'0';
            ss[x][y][ax][ay]=1;
            if(i==1||i==7)
            {
                // 从xy到ax ay 那么就从下面到上面，则交叉就算从上面到下面，所以
                // x-1 y 到 ax+1 y 或者是 ax+1 y 到x-1 y
                ss[x-1][y][ax+1][ay]=1;
                ss[ax+1][ay][x-1][y]=1;
            }
            if(i==3||i==5)
            {
                // 与上面同理
                ss[x+1][y][ax-1][ay]=1;
                ss[ax-1][ay][x+1][y]=1;
            }
            dfs(ax,ay,q+qq);
            ss[x][y][ax][ay]=0;
            st[ax][ay]=0;
            if(i==1||i==7)
            {
                ss[x-1][y][ax+1][ay]=0;
                ss[ax+1][ay][x-1][y]=0;
            }
            if(i==3||i==5)
            {
                ss[x+1][y][ax-1][ay]=0;
                ss[ax-1][ay][x+1][y]=0;
            }
        }
    }
}
void solve()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++) cin>>a[i][j];
    }
    string q="";
    st[0][0]=true;
    dfs(0,0,q);
    if(s.size()==0)
    {
        cout<<"-1";
        return;
    }
    sort(s.begin(),s.end());
    // 保证字典序最小
    cout<<s[0];
}

ctgg造的数据都过了，希望能ac

G 爬山

【问题描述】
小明这天在参加公司团建，团建项目是爬山。在 x 轴上从左到右一共有 n
座山，第 i 座山的高度为hi。他们需要从左到右依次爬过所有的山，需要花费的体力值为 S = Σni=1hi。

然而小明偷偷学了魔法，可以降低一些山的高度。
他掌握两种魔法，
第一种魔法可以将高度为 H 的山的高度变为 ⌊√H⌋，可以使用 P 次；第二种魔法可以将高度为 H 的山的高度变为 ⌊H/2⌋，可以使用Q次。

并且对于每座山可以按任意顺序多次释放这两种魔法。小明想合理规划在哪些山使用魔法，使得爬山花费的体力值最少。
请问最优情况下需要花费的体力值是多少？
【输入格式】
输入共两行。
    第一行为三个整数 n，P，Q。
    第二行为 n 个整数 h1，h2，. . . ，hn。
【输出格式】
    输出共一行，一个整数代表答案。
【样例输入】
4 1 1
4 5 6 49
【样例输出】
18
【样例说明】
将第四座山变为 ⌊√49⌋ = 7，然后再将第四座山变为 ⌊/72⌋ =3。
体力值为 4 + 5 + 6 + 3 = 18。
【评测用例规模与约定】
    对于 20% 的评测用例，保证 n ≤ 8，P = 0。
    对于 100% 的评测用例，保证 n ≤ 100000，0 ≤ P ≤ n，0 ≤ Q ≤ n，0 ≤ hi ≤ 100000。

赛事直接大根堆，直接骗分，但是被hack了。

出题人的题解也是大根堆，希望能多骗点分

H 拔河

【问题描述】
小明是学校里的一名老师，他带的班级共有 n 名同学，第 i
名同学力量值为 ai。在闲暇之余，小明决定在班级里组织一场拔河比赛。
为了保证比赛的双方实力尽可能相近，需要在这n名同学中挑选出两个队伍，队伍内的同学编号连续:{al1, al1+1, ...,
ar1−1,ar1} 和 {al2, al2+1, ..., ar2−1, ar2}，其
中 l1 ≤ r1 < l2 ≤ r2。
两个队伍的人数不必相同，但是需要让队伍内的同学们的力量值之和尽可能相近。请计算出力量值之和差距最小的挑选队伍的方式。


【输入格式】
输入共两行。
    第一行为一个正整数 n。
    第二行为 n 个正整数 ai。
【输出格式】
    输出共一行，一个非负整数，表示两个队伍力量值之和的最小差距。
【样例输入】
5
10 9 8 12 14
【样例输出】
1
【样例说明】

赛事直接n4没想那么多。骗4分

压轴题吓到了（bushi

如果有不对的地方给予纠正 共同进步！