第114场周赛 - AcWing

2的整数次幂

给定一个整数 n，请你判断 n 是否是 2 的整数次幂。

输入格式

第一行包含整数 T，表示共有 T 组测试数据。

每组数据占一行，包含一个整数 n。

输出格式

每组数据输出一行结果，如果 n 是 2的整数次幂，则输出 YES，否则输出 NO。

数据范围

所有测试点满足 1≤T≤10，2≤n≤10^9^.

输入样例：

4
2
3
4
5

输出样例：

YES
NO
YES
NO

我的代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

bool flag(int n) {
    if (n <= 0) {
        return false;
    }
    return (n & (n - 1)) == 0;
}
int main(){
    int T;
    cin>>T;
    while (T--) {
        int n;
        cin >> n;
        if(flag(n)){
           cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
         }
    }
}

截断数组

给定一个长度为 n 的正整数数组 a1,a2,…,an1,2,…, 和一个正整数 p。

现在，要将该数组从中间截断，得到两个非空子数组。

我们规定，一个数组的价值等于数组内所有元素之和模 p 的结果。

我们希望，将给定数组截断后，得到的两个非空子数组的价值之和尽可能大。

请你输出这两个非空子数组的价值之和的最大可能值。

输入格式

第一行包含两个整数 n 和 p。

第二行包含 n 个整数 a1,a2,…,an1,2,…,。

输出格式

一个整数，表示价值之和的最大可能值。

数据范围

前 3个测试点满足 2≤n≤10. 所有测试点满足 2≤n≤10^5^，2≤p≤10000，1≤a~i~≤10^6^.

输入样例1：

4 10
3 4 7 2

输出样例1：

16

输入样例2：

10 12
16 3 24 13 9 8 7 5 12 12

输出样例2：

13

我的代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int maxx(int n, int p, vector<int>& a) {
    vector<long long> aa(n + 1, 0);
    for (int i = 1; i <=n; i++) {
        aa[i] = (aa[i - 1] + a[i - 1]) % p;
    }   
    long long maxSum = 0;
    for (int i = 1; i < n; ++i) {
        long long sum1 = aa[i];
        long long sum2 = (aa[n] - aa[i] + p) % p;
        maxSum = max(maxSum, sum1 + sum2);
    }
    return maxSum;
}

int main(){
    int n,p;  
    cin>>n>>p; 
    vector<int> a(n);
    for(int i =0; i < n; i++){
        cin>>a[i];
    }
    int sum = maxx(n,p,a);
    cout << sum<<endl;  
}

双色球

约翰和贝茜玩抽球游戏。

一个盒子中有 n 个白球和 m 个黑球。

双方轮流行动，由约翰先行。

每当轮到一方行动时，其从盒中随机抽出一个球，盒子中的每个球被抽出的概率相同。

率先抽出白球的一方获胜。

此外，由于贝茜的手比较笨拙，所以每当她抽出一个球后，盒子都会剧烈摇晃，随后就会有恰好一个球掉出盒子（如果盒中有球的话），盒子中的每个球掉出的概率相同。

掉出的球无论是什么颜色，都予以作废。

当盒子中没有球时，如果仍未分出胜负，则判定为贝茜获胜。

请你计算，约翰获胜的概率。

输入格式

一行，两个整数 n,m,。

输出格式

一个实数，表示约翰获胜的概率。

输出结果与正确答案的绝对误差不超过 10^−9^，则视为正确。

数据范围

前 44个测试点满足 0≤n,m≤1000. 所有测试点满足 0≤n,m≤10000;

输入样例1：

1 3

输出样例1：

0.500000000

输入样例2：

5 5

输出样例2：

0.658730159

我的代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
double f[N][N];

int main(){
 scanf("%d%d",&n,&m);
    for(int i = 1 ;i<=n;i++)
    {
        for (int j = 0; j <=m; j++)
        {
            double p1 = 0, p2 = 0, p3 = 0;
            p1 = i * 1.0 /(i+j);
            double p4 = j *1.0 /(i+j)*(j-1)/(i+j-1);
            if(j>=2)
                p2 = p4 * i /(i+j-2) * f[i-1][j-2];
            if(j>=3)
                p3 = p4 * (j-2)/(i+j-2) * f[i][j-3];
                f[i][j] = p1 + p2 + p3;
        }
    }
    printf("%.10lf\n",f[n][m]);
    return 0;
}