B-Random

https://ac.nowcoder.com/acm/contest/120563/B

题意：给定一个长度为n的数组，从中选出两个不同位置的数，要求两个数的最大公约数大于1，如果存在这样的一对元素，输出它们的位置（或值）；如果不存在，输出-1。

特殊的：数组元素是在范围内独立均匀随机生成

思路：这题可以直接暴力，只要找到两个偶数就可以直接输出，他们的gcd最小为2，原因是独立均匀随机生成，比如数组长度是200000，每个数是偶数的概率为0.5，就是有100000个偶数,把200000个数每31个分成一组，就是有6452个组，然后把100000偶数均匀分在这些组里就是每个组有15个偶数，那必然有两个偶数距离小于30

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        long long n;
        cin>>n;
        vector<long long>arr(n);
        for(long long j=0;j<n;j++)
        {
            cin>>arr[j];
        }
        int f=0;
        for(long long j=0;j<n&&!f;j++)
        {
            for(long long m=j+1;m<n&&!f;m++)
            {
                if(__gcd(arr[j],arr[m])>1)
                {
                    cout<<arr[j]<<" "<<arr[m]<<endl;
                    f=1;
                }
            }
        }
        if(f==0)
        {
            cout<<-1<<endl;
        }
    }
    return 0;
}

H

https://ac.nowcoder.com/acm/contest/120563/H

题意：给出A,B两点，让你在横坐标上找到一个点O(x,0),使得这三个点组成面积为2的三角形，找出一个x即可，找不到输出no answer

思路：三角形的面积知道三个点的坐标就用向量的叉乘来算，|((xa-x),ya)((xb-x),yb)|/2=2, 所以|((xa-x),ya)((xb-x),yb)|=4，x=4+xbya-xayb/(ya-yb)或-4+xbya-xayb/(ya-yb)，需要分类判断ya是否等于yb，再算出x的值

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int xa, ya, xb, yb;
    cin >> xa >> ya >> xb >> yb;
    int D = ya - yb;
    long double C = (long long)xb * ya - (long long)xa * yb;

    if (D == 0) {
        if (abs(C) == 4) {
            cout << fixed << setprecision(12) << 0.0 << endl;
        } else {
            cout << "no answer" << endl;
        }
    } else {
       long double x1 = C - 4.0;
        x1 /= D;
        long double x2 =C + 4.0;
        x2 /= D;
        cout << fixed << setprecision(12) << x1<< endl;
    }
    
    return 0;
}

F

https://ac.nowcoder.com/acm/contest/120563/F

题意：有一个 2 行 n 列的网格，所有格子初始为空，小小红从左上角 (1, 1) 出发，每次可以向上下左右相邻格子移动一步，且始终选择最短步数到达第 n 列的任意空格子。小红和小紫轮流在空且非起点的格子上放置障碍，要求放置后仍存在从起点到第 n 列的路径；若无法放置满足条件的障碍，博弈结束。两人都按最优策略行动：小红希望最终最短步数尽量小，小紫希望它尽量大。

思路：小小红每次以最小路径走就是说最好走直线，小红希望小小红走的最少，就要把障碍摆在上面或者下面，使小小红以直线走，而小紫希望他走的多，就要把障碍摆在小小红的前面，使小小红往上或者下走，可以得到下图

alt

按照规律可得最短路为 n-1+n/5

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long t;
    cin>>t;
    for(long long i=0;i<t;i++)
    {
        long long n;
        cin>>n;
        cout<<n-1+n/5<<endl;
    }
    return 0;
}

C

https://ac.nowcoder.com/acm/contest/120563/C

题意：给定一个仅由字符 0 和 1 组成的字符串 s。你可以进行任意次操作：选择一个非空子序列（该子序列中任意两个相邻元素必须不同），对这个子序列进行01 反转（即 0 变 1，1 变 0）。目标是：通过最少次数的操作，使得最终字符串 s 中任意两个相邻元素都不相同。输出这个最少操作次数。

思路：最终的字符串必然是1010...或0101...则要比较变为这两种字符串的次数，先将原本的字符串与最终的字符串比较，标记出不同的字符，算将这些字符翻转的最小次数。比如110110，将这个字符串翻转的次数可以先开两个变量a,b存末尾为0的子序列数和末尾为1的子序列数，如果遍历到1，则需要把它接到末尾为0的序列后面，则放完后a--,b++，遍历到0则相反，不断更新末尾为0和1的序列数，最终a+b就是翻转次数

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long t;
    cin>>t;
    for(long long i=0;i<t;i++)
    {
        long long n;
        cin>>n;
        string arr;
        cin>>arr;
        vector<char> mp1;
        vector<char> mp2;
        char tar;
        char f;
        for(long long j=0;j<n;j++)
        {
            if((j+1)%2==0)
            {
                tar='1';
                f='0';
            }
            else
            {
                tar='0';
                f='1';
            }
            if(arr[j]!=tar)
            {
                mp1.push_back(arr[j]);
            }
            if(arr[j]!=f)
            {
                mp2.push_back(arr[j]);
            }
        }
        long long a=0;//计0
        long long b=0;//计1
        long long x=0;//计0
        long long y=0;//计1
        for(char m:mp1)
        {
            if(m=='0')
            {
                if(b==0)
                {
                    a++;
                }
                else
                {
                    b--;
                    a++;
                }
            }
            else
            {
                if(a==0)
                {
                    b++;
                }
                else
                {
                    a--;
                    b++;
                }
            }
        }
        for(char l:mp2)
        {
            if(l=='0')
            {
                if(y==0)
                {
                    x++;
                }
                else
                {
                    y--;
                    x++;
                }
            }
            else
            {
                if(x==0)
                {
                    y++;
                }
                else
                {
                    x--;
                    y++;
                }
            }
        }
        cout<<min(a+b,x+y)<<endl;
    }
    return 0;
}

题解 |

B-Random

H

F

C