A.再来一瓶

题解

如果你注意力惊人的话，根据样例你就可以推得Orange喝饮料瓶数的期望是：

$$\frac{1}{1-p}$$

所以直接输出这个就好了XD。 本题正解如下： 用一种递推的思想，把每一次都当第一瓶来看，你必然会已经喝了一瓶那么就记作$1$瓶,喝完一瓶之后，你有$p$的概率得到“再来一瓶”，此时剩下的期望瓶数和当前的情形是相同的（继续从头开始）,所以就设总期望值是E,那么就有： $$E = 1 + p \times E $$ 移项得$(1-p)E=1$，从而： $$\frac{1}{1-p}$$

标准代码如下

#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
typedef vector<vector<int>> mat;
using pii = pair<int, int>;
using pdd = pair<double,double>;
constexpr int N = 2e5 + 10;
void solve()
{
    double p;
    cin>>p;
    double ans=1.0/(1.0-p);

    cout<<ans<<'\n';
}
signed main()
{
    IOS;
    int _= 1;
    //cin >> _;
    while(_--)
    {
        solve();
    }
    return 0;
}

B.星际坐标

题解

由题意，我们只需要把字符串中每一个数字字符拿出来并且从小到大排一次序就好了

标准程序代码

#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
typedef vector<vector<int>> mat;
using pii = pair<int, int>;
using pdd = pair<double,double>;
constexpr int N = 2e5 + 10;
void solve()
{
    string s,ss;
    getline(cin,s);
    vector<int> a;
    int sum=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]<='9'&&s[i]>='0')//找出数字字符
        {
            a.push_back(s[i]-'0');
        }
    }
    sort(a.begin(),a.end(),greater());//从大到小排序
    for(auto i :a) cout<<i;//全部输出
}
signed main()
{
    IOS;
    int _= 1;
    //cin >> _;
    while(_--)
    {
        solve();
    }
    return 0;
}

C.光之轨迹

题解

一眼定真，鉴定为纯纯的模拟题 因为是$45°$出发，所以只需要模拟每一步向四个方向走的过程就好了，一共要模拟$(K+1)$步

标准代码如下

#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
typedef vector<vector<int>> mat;
using pii = pair<int, int>;
using pdd = pair<double,double>;
constexpr int N = 2e5 + 10;
void solve()
{
    int n,m,k;
    cin>>n>>m>>k;
    int x=0,y=0;//初始坐标
    int t=k+1;//k次反射，模拟k+1步
    int dx=1,dy=1;//表示走的方向，初始方向向右上角出发，所以dx、dy都是1
    for(int i=1;i<=t;i++)
    {
        //xx为到达下一个边界的距离
        //dx==1时，向右，距离为n-x；
        //dx==-1时，向左，距离为x；
        int xx=(dx==1)?(n-x):x;
        //yy同理
        int yy=(dy==1)?(m-y):y;
        //a是下一次碰撞是光能走的最短距离（撞到水平or竖直的墙）
        int a=min(xx,yy);
        //光线移动a距离，方向为dx，dy
        x+=dx*a;
        y+=dy*a;
        //撞到墙角了，dx、dy都要翻转
        if(xx==yy)
        {
            dx=-dx;
            dy=-dy;
        }
        //撞到竖直墙了，dx方向反转
        else if(xx<yy) dx=-dx;
        //撞到水平墙了，dyy方向反转
        else dy=-dy;
    }
    
    cout<<x<<' '<<y;
}
signed main()
{
    IOS;
    int _= 1;
    //cin >> _;
    while(_--)
    {
        solve();
    }
    return 0;
}

D.家庭作业II

题解

这是家庭作业的二代目，与一代目的区别是从单选变成多选了，但是这依旧可以仅用四次就能猜出来答案是什么：

第一次提交时所有的都提交单选$A$，若返回2就代表正确答案时是A，直接跳过，若返回1，说明是部分正确，当前A选项是正确的，但是还少了选项，那么就把B选项放进去，再去继续下一轮的判断，若返回的是3，那么就代表当前存在错误选项，那么直接把最后一个选项（在这里是A选项）给踢出，换成B选项。 后面几次提交以此类推，一直到第四次提交一定会正确的

标准程序代码如下

#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
typedef vector<vector<int>> mat;
using pii = pair<int, int>;
using pdd = pair<double,double>;
constexpr int N = 2e5 + 10;
int n;
vector<int> check(vector<string> &s)
{
    for(int i=0;i<n;i++) cout<<s[i]<<' ';
    cout<<s[n]<<endl;//输出我当前的答案
    vector<int> a(n+10);
    for(int i=1;i<=n;i++) cin>>a[i];//判题系统给出你的答案是否正确
    return a;//返回答案数组
}
signed main()
{
    cin>>n;
    vector<string> c(n+1,"A");//第一次提交每一个都一定是正确的
    c[0]="?";
    for(int j=1;j<=3;j++)//进行三次猜测
    {
        vector<int> a(n+10);
        a=check(c);//接收答案数组
        for(int i=1;i<=n;i++)
        {
            if(a[i]==2) continue;//如果当前选项正确直接输出
            else if(a[i]==0) c[i].pop_back();//如果当前选项错误肯定是上一次的选项错误了，直接踢掉最后一个选项
            char ch='A'+j;//'A'+1='B','A'+2='C','A'+3='D'
            c[i].push_back(ch);//放入新的选项
        }
    }
    string s;
    s+="!";//最后一次猜测一定是正确的，直接输出
    for(int i=1;i<=n;i++)
    {
        s+=" "+c[i];
    }
    cout<<s<<endl;
    return 0;
}

E.平方因子

本题题解作者：Orange🍊

题解

根据题意，题目要求我们求出一个 $n$ 最大的平方因数，可以考虑枚举所有 $n$ 的因数，验证其是否是平方数来求。但是注意到 $T = 1e4, n = 1e12$，假设用朴素做法对 $n$ 进行因数分解，复杂度为 $O(T \sqrt n)$，在当前数据下显然会超时。

观察 $n$ 的本质，不妨将 $n$ 写成唯一素数分解的形式：

$$n = p_1^{c_1}p_2^{c_2}p_3^{c_3}...p_n^{c_n}$$

那么根据因数的定义，若 $f$ 是 $n$ 的因子，则 $f$ 应该满足 $f$ 的质因数是 $n$ 的子集，且次数均不超过 $n$，可以把 $f$ 写成如下形式：

$$f = p_1^{d_1}p_2^{d_2}p_3^{d_3}...p_n^{d_n}$$

其中，满足 $\forall d_i \le c_i$。

再来考虑平方数的性质，既然平方数要能被表示成两个相同数的乘积，因此对于平方数 $g$ 来说应该满足：

$$g = p_1^{2c_1}p_2^{2c_2}p_3^{2c_3}...p_n^{2c_n}$$

即各素数的次数必须是偶数。

那么综上所述，我们最终所求的 $n$ 最大平方因子实际上就是在 $n$ 的分解中，取走所有质因子最大的的偶数次幂。即对于质因子 $p$，如果其次数 $c$ 是偶数，则把 $p^c$ 累乘到答案，否则就把 $p^{c-1}$ 累乘到答案。

$$ans = p_1^{c_1 - c_1 \% 2}p_2^{c_2 - c_2 \% 2}p_3^{c_3 - c_3 \% 2}...p_n^{c_n - c_n \% 2}$$

但是，即使得到上述结论，对 $n$ 进行质因数分解最坏的情况也是 $O(\sqrt n)$，我们需要一个更加精细的做法。

观察朴素的质因数分解方法，我们是枚举到 $\sqrt n$ 来检验 $i$ 是否是 $n$ 的因子，我们可以考虑优化该做法：

由于我们要求的是所有质因子的偶数次幂，因此我们的质因子 $p$ 一定小于 $\sqrt n$ 才会有贡献，不妨考虑将 $p$ 分成两部分：

1. $p \le \sqrt[3] {n}$ ：对于小于立方根的因子，可以考虑暴力枚举，将其次数求出并累加到答案即可。
2. $p > \sqrt[3] n$ ：对于大于立方根的因子，一个显然的结论是其个数或者次数都一定小于3，也就是说其只可能是1或者2，对于这种情况，由于只有个数为1时其次数为2才有贡献，因此直接验证其是不是平方数来选择是否加入答案即可。

因此我们只需要枚举 $O(\sqrt[3] n)$ 内的质数对 $n$ 进行分解，再 $O(1)$ 判断剩余的部分是不是平方数即可。上述做法的复杂度为 $O(T \sqrt[3] n) \approx 1e4 \times 1e4 \approx 1e8$，可能会因为常数大的问题而超时。

考虑优化：由于我们只需要枚举质数进行分解，而 $O(n)$ 内质数的期望为 $O(\frac{n}{\ln n})$ 个，可以考虑先处理出 $\sqrt[3] n$ 内的所有质数，然后仅枚举质数进行分解即可，最终复杂度为 $O(T \frac{\sqrt[3] n}{\ln {\sqrt[3] n}})$，大约 $1e7$ 左右，可以在1s内通过。

标准程序代码如下

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

using i64 = long long;

vector<int> primes;
vector<int> vis;

// 欧拉筛
void seive(int n)
{
    vis.assign(n + 1, 0);
    for(int i = 2; i <= n; i ++)
    {
        if(!vis[i]) primes.push_back(i);
        for(auto p : primes)
        {
            if(i * p > n) break;
            vis[i * p] = 1;
            if(i % p == 0) break;
        }
    }
}

signed main()
{
    cin.tie(0) -> sync_with_stdio(0);
    // 筛出 1e12 立方根内的所有素数
    seive(cbrt(1e12) + 1);
    int t;
    cin >> t;
    while(t --)
    {
        i64 ans = 1, n;
        cin >> n;
        // 直接枚举素数，优化常数
        for(auto p : primes)
        {
            // 如果 p 已经 超过 n 或者 n 已经被除干净，则推出
            if(p > n or n == 1) break;
            int cnt = 0;
            // 求出 p 在 n 中的次数
            while(n % p == 0) cnt ++, n /= p;
            // 如果是奇数，则将cnt-1次乘入答案，偶数则全乘进去
            if(cnt & 1) cnt --;
            ans *= (i64)pow(p, cnt);
        }
        // 判断大于三次方根的因子，只需要判断是否是平方数即可
        if(n > 1)
        {
            i64 x = sqrt(n);
            // 如果是平方数，累乘进答案
            if(x * x == n) ans *= n;
        }
        cout << ans << '\n';
    }
}