A.数字游戏

题意：

我们可以对一个非零数的二进制进行以下操作：

1.若二进制中有奇数个1，我们将其二进制最低位取反

2.若二进制中有偶数个1，我们将其二进制中非前导0最高位取反。

问给你个数x，需要操作几次变成0.

思路：

先把数转换为二进制，通过枚举找到规律如下：

令该数为n，其二进制中1的个数为x。

1.若n为0，ans = 0。

2.若n为偶数,且x也为偶数，则ans = 2 * x。

3.若n为偶数，且x为奇数，则ans = 2 * x - 2。

4.若n为奇数，且x为奇数，则ans = 2 * x - 1。

5.若n为奇数，且x为偶数，则ans = 2 * x + 1。

 

代码：

#include <bits/stdc++.h>
typedef long long LL;

using namespace std;

int work(LL n)
{
    int ans = 0;
    while(n)
    {
        if(n % 2 == 1) ans ++;
        n /= 2;
    }
    return ans;
}

void solve()
{
    LL n;
    scanf("%lld",&n);
    int ans = 0;
    int x = work(n);
    if(n == 0){
        ans = 0;
    }
    else if(x % 2 == 0){
        if(n % 2 == 0) ans = 2 * x;
        else ans = 2 * x - 2;
}
    else 
    {
        if(n % 2 == 0){
            ans = 2 * x + 1;
        }else{
            ans = 2 * x - 1;
        }
    }
    printf("%d\n",ans);
}

int main()
{
    int T = 1;
    scanf("%d",&T);
    while(T -- )
    {
        solve();
    }
    return 0;
}

 B.跳跳跳

题意：

有一个n个格子呈环状分布，每个格子都有一个权值a[i],dd可以选择任意一个格子开始跳，每次只能跳到其当前位置左边或者右边最近的且未被跳过的位置，每次获得 k * a[i]的得分，k为当前跳跃次数，a[i]为当前格子上的权值。问如何跳使得总得分最大，求出最大总分。

思路：

这是一个区间dp。dd左右跳形成一个个区间，我们令dp[i][j]表示从编号为i的格子跳到编号为j的格子中得分最大。

很明显状态转移只有两种情况：

1.从dp[i +1][j] ——> dp[i[j]

2.从dp[i][j - 1] ——> dp[i][j]

所以 dp[i][j] = max(dp[i + 1][j] + a[i] * (j - i + 1), dp[i][j - 1] + a[j] * (j - i + 1));

然后枚举下长度为n的区间，寻找下最大值就OK。

本题是环形难以处理需要不断取模，我们可以将原数组复制成原来的两倍再加以处理。

其次是从状态转移方程来看，想要计算出dp[i][j]，先必须要计算出dp[i +1][j]和dp[i][j - 1]，所以外层循环要从大到小枚举，内层循环需要从小到大枚举。

代码：

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

int n;
int a[4010];
LL dp[4010][4010];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> a[i], a[i + n] = a[i];
    for(int i = 1; i <= 2 * n; i ++ ) dp[i][i] = a[i];
    for(int i = 2 * n; i >= 1; i -- )
        for(int j = i + 1; j <= n + i - 1; j ++ )
            dp[i][j] = max(dp[i + 1][j] + a[i] * (j - i + 1), dp[i][j - 1] + a[j] * (j - i + 1));

    LL ans = -1;
    for(int i = 1; i <= n + 1; i ++ )   ans = max(ans, dp[i][n + i - 1]);
    cout << ans << endl;
    return 0;
}

C.数字匹配

题意：

对于任意两个正整数x,y（x≠y），当且仅当x,y的二进制非前导零部分最大连续重合位数≥k时，x,y是匹配的。

让你寻找1~n中x与y的匹配数，x < y。

思路：

暴力处理1~n中所有数的二进制，再暴力查找匹配的x,y的数目。

代码：

#include <bits/stdc++.h>

using namespace std;

int n, k;
string a[2010];

vector<int> binary(int n)
{
    vector<int>q;
    while(n)
    {
        q.push_back(n % 2);
        n /= 2;
    }
    reverse(q.begin(),q.end());
    return q;
}

bool check(int x, int y)
{
    for(int i = 0; i + k <= a[x].length(); i ++ )
        for(int j = 0; j + k <= a[y].length(); j ++ )
            if(a[x].substr(i, k) == a[y].substr(j, k)) return true;         
    return false;
}

int main()
{
    scanf("%d %d",&n, &k);
    for(int i = 1; i <= n; i ++ )
    {
        vector<int>q = binary(i);
        for(int j = 0; j < q.size(); j ++ ) a[i] += (q[j] + '0');
    }
    int ans = 0;
    for(int i = 1; i <= n; i ++ )
        for(int j = i + 1; j <= n; j ++ )
            if(check(i, j)) ans ++;

    cout << ans << endl;
    return 0;
}

D.优美字符串

题意：

给你个字符串，问你至少需要插入多少字符使得相邻的两个字符串不相等。

思路：

暴力枚举，统计出有多少相邻两个字符相等的数目。

#include <bits/stdc++.h>
typedef long long LL;

using namespace std;

string s;
void solve()
{
    cin >> s;
    int ans = 0;
    for(int i = 0; i + 1 < s.length(); i ++ )
    {
        if(s[i + 1] == s[i]) ans ++;
    }
    cout << ans  + s.length() << endl;
}

int main()
{
    int T = 1;
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> T;
    while(T -- )
    {
        solve();
    }
    return 0;
}

E.分组

题意：

给你n个同学，每个同学都有个声部，让你把他们分为m组，要满足每一组的声部都一样，求出所有组中的最大人数最小。若不能分组，输出”-1“。

思路：

若声部个数大于组数，无法进行分组, 输出-1。剩余情况，二分查找最小值即可。

代码：

#include <bits/stdc++.h>

using namespace std;

int n, m;
int a[100010];
bool st[100010];
map<int,int>mp;

bool check(int mid)
{
    int qwq = 0;
    for(auto it : mp){
        if(it.second % mid == 0){
            qwq += it.second / mid;
        }else{
            qwq = qwq + (it.second / mid) + 1;
        }
    }
    if(qwq > m) return false;
    return  true;
}

int main()
{
    cin >> n >> m;
    int cnt = 0;
    for(int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        if(st[a[i]] == false)
        {
            st[a[i]] = true;
            cnt ++;
        }
        mp[a[i]] ++;
    }
    if(cnt > m){
        cout << -1 << endl;
    }else{
        int l = 1, r = n;
        while(l < r)
        {
            int mid = (l + r) >> 1;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        cout << l << endl;
    }
    return 0;
}

F.过桥

题意:

有n个浮块，dd站在第一个浮块上，每个浮块上有一个权值，dd在第i个浮块上，可以跳到i + k（k <= a[i])个浮块上，若i + a[i] < 1， 就只能移动到1浮块上，问dd最少移动几次就能到达n，如果无法到达输出-1。

思路：

我们开一个f数组，记录到每个浮块的最小次数，然后跑一边BFS即可。若f[n]为无穷大，则无法到达。否则，输出f[n]。

#include <bits/stdc++.h>

using namespace std;

int n;
int a[20100];
int f[20100];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    memset(f, 0x3f, sizeof f);
    queue<int>q;
    f[1] = 0;
    q.push(1);
    while(!q.empty())
    {
        int tt = q.front();
        q.pop();
        if(a[tt] > 0)
        {
            for(int i = tt + 1; i <= tt + a[tt]; i ++ )
            {
                if(f[tt] + 1 < f[i])
                {
                    f[i] = f[tt] + 1;
                    q.push(i);
                }
            }
        }
        else{
            int x = max(tt + a[tt], 1);
            for(int i = 1; i <= x; i ++ )
            {
                if(f[tt] + 1 < f[i] )
                {
                    f[i] = f[tt] + 1;
                    q.push(i);
                }
            }
        }   
    }
    if(f[n] == 0x3f3f3f3f) puts("-1");
    else cout << f[n] << endl;
    return 0;
}

G.遥控

题意：

集训队每个人都有一个温度诉求a[i],当 |a[i] - k| <= p时，算达到诉求，问dd把集训队内部的温度控制为多少，才能让更多的人达到诉求。

思路：

预处理出每个温度下，队员达到诉求的人数，再暴力枚举温度，不断取在某个温度下达到诉求的人数的最大值。

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 1000100;
int n, p;
int a[N];
int b[N];
int sum[N];

int main()
{
    cin >> n >> p;
    for(int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        b[a[i]] ++;
    }
    sum[1] = b[1];
    for(int i = 2; i <= 1000000; i ++ ) sum[i] = sum[i - 1] + b[i];
    int ans = -1;
    for(int i = p + 1; i <= n - p; i ++ )
        ans = max(ans, sum[i + p] - sum[i - p - 1]);
    cout << ans << endl;
    return 0;
}

H.来点gcd

题意：

给你一个集合S,和一个数x,问你是否能找到S的一个子集，使S中所有元素的gcd等于x。

思路：

若一个集合所有元素的gcd是x，则这个集合中的元素都是x的倍数，暴力查找出集合S中的x的倍数，然后一起取gcd，若为x,则存在，否则不存在。

若集合中x的倍数不存在，显然答案也是不存在的。

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 1000100;
int t;
int n, m;
int a[N];
bool st[1000010];

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) st[i] = false;
    for(int i = 1; i <= n; i ++ )
    {
        scanf("%d",&a[i]);
        st[a[i]] = true;
    }
    while(m -- )
    {
        int x;
        scanf("%d",&x);
        vector<int> ans;
        for(int i = x; i <= n; i += x)
            if(st[i] == true) ans.push_back(i);
        if((ans.size() == 1 && ans[0] != x) || !ans.size())
            puts("NO");
        else if(ans.size() == 1) puts("YES");
        else
        {
            int qwq = __gcd(ans[0], ans[1]);
            for(int i = 2; i < ans.size(); i ++ ) qwq = __gcd(ans[i], qwq);
            if(qwq == x) puts("YES");
            else  puts("NO");
        }
    }
}
int main()
{
    scanf("%d",&t);
    while(t -- )
    {
        solve();
    }
    return 0;
}

I.体操队形

题意：

给你个数组a[i],体操队形要满足第i个人要站在a[i]的人的前面，问有几种站法？

思路：

暴力枚举所有站法，判断是否合法就行。

代码：

#include <bits/stdc++.h>

using namespace std;

int n;
int a[100];
int b[15];

bool check()
{
    int c[15];
    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 0; j < n; j ++ )
        {
            if(b[j] == i) c[i] = j;
        }
    }
    for(int i = 1; i <= n; i ++ )
        if(c[i] > c[a[i]]) return false;
    return true;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    for(int i = 0; i < n; i ++ ) b[i] = i + 1;
    int ans = 0;
    do
    {
        if(check()) ans ++;
    }while(next_permutation(b, b + n));
    cout << ans << endl;
    // system("pause");
    return 0;
}