寒假新生复健 #001 题解

#1

C语言中按位异或的符号为^，输出二进制的时候可以用栈

#include <iostream>
#include <stack>

using namespace std;

typedef long long ll;

int main()
{
    stack<int> bin;
    ll a, b, c;
    cin >> a >> b;
    c = a ^ b;
    while (c)
    {
        bin.push(c & 1);
        c >>= 1;
    }
    while (!bin.empty())
    {
        cout << bin.top();
        bin.pop();
    }
    cout << " " << (a ^ b);
    return 0;
}

#2

找到如图中的区块输出即可

#include <iostream>
#include <cstring>

using namespace std;

struct vec2
{
    int x, y;
};

int main()
{
    int r[50], l[50];
    char graph[50][50];
    memset(r, 0, sizeof r);
    memset(l, 0, sizeof l);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> graph[i][j];
            if (graph[i][j] == '*')
            {
                r[i] |= 1;
                l[j] |= 1;
            }
        }
    }
    vec2 start, end;
    start.x = 0;
    start.y = 0;
    for (int i = 0; i < n; i++)
    {
        if (!r[i])
        {
            ++start.x;
        }
        else
        {
            break;
        }
    }
    for (int i = 0; i < m; i++)
    {
        if (!l[i])
        {
            ++start.y;
        }
        else
        {
            break;
        }
    }
    end.x = n;
    end.y = m;
    for (int i = n - 1; i >= 0; i--)
    {
        if (!r[i])
        {
            --end.x;
        }
        else
        {
            break;
        }
    }
    for (int i = m - 1; i >= 0; i--)
    {
        if (!l[i])
        {
            --end.y;
        }
        else
        {
            break;
        }
    }
    for (int i = start.x; i < end.x; i++)
    {
        for (int j = start.y; j < end.y; j++)
        {
            cout << graph[i][j];
        }
        cout << "\n";
    }
    return 0;
}

#3

（x，y）对称点坐标为（2 – x，2 – y）

#include <iostream>

using namespace std;

struct vec2
{
    int x, y;
};

inline vec2 opposite(int x, int y)
{
    vec2 ans;
    ans.x = 2 - x;
    ans.y = 2 - y;
    return ans;
}

int main()
{
    int pad[3][3];
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            char input;
            cin >> input;
            if (input == 'X')
            {
                pad[i][j] = 1;
            }
            else
            {
                pad[i][j] = 0;
            }
        }
    }
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            vec2 opposite_ = opposite(i, j);
            if (pad[i][j] ^ pad[opposite_.x][opposite_.y])
            {
                cout << "NO\n";
                return 0;
            }
        }
    }
    cout << "YES\n";
    return 0;
}

#4

暴力过一遍就好了

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, d;
    cin >> n >> d;
    vector<int> a(n);
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i < n; i++)
    {
        if (a[i] <= a[i - 1])
        {
            ans += (a[i - 1] - a[i]) / d;
            a[i] += ((a[i - 1] - a[i]) / d) * d;
            if (a[i] <= a[i - 1])
            {
                ++ans;
                a[i] += d;
            }
        }
        
    }
    cout << ans << "\n";
    return 0;
}

#5

先把1000以内的素数筛出来，然后依次检查两个相邻素数 + 1是否为小于n的素数即可

#include <iostream>
#include <vector>

using namespace std;

void sieveOfEular(vector<int>& prime, int* isNotPrime)
{
    int primeCnt = 0;
    for (int i = 2; i < 1000; i++)
    {
        if (!isNotPrime[i])
        {
            prime.push_back(i);
            ++primeCnt;
        }
        for (int j = 0; j < primeCnt && i * prime[j] < 1000; j++)
        {
            isNotPrime[i * prime[j]] = 1;
            if (!(i % prime[j]))
            {
                break;
            }
        }
    }
}

int main()
{
    vector<int> prime;
    int isNotPrime[1000] = { 1, 1 };
    sieveOfEular(prime, isNotPrime);
    int n, k;
    cin >> n >> k;
    int cnt = 0;
    int iter = 1;
    while (prime[iter] + prime[iter - 1] < n)
    {
        if (!isNotPrime[prime[iter] + prime[iter - 1] + 1])
        {
            ++cnt;
        }
        ++iter;
    }
    if (cnt >= k)
    {
        cout << "YES\n";
    }
    else
    {
        cout << "NO\n";
    }
    return 0;
}

#6

先判断给定的时间在不在界限范围内，然后贪心把多出来的时间分配一下就好了

#include <iostream>
#include <vector>

using namespace std;

struct day
{
    int minTime;
    int maxTime;
};

int main()
{
    int days, hrs;
    cin >> days >> hrs;
    int totMin = 0, totMax = 0;
    vector<day> limits(days);
    for (int i = 0; i < days; i++)
    {
        cin >> limits[i].minTime >> limits[i].maxTime;
        totMin += limits[i].minTime;
        totMax += limits[i].maxTime;
    }
    if (totMin > hrs || totMax < hrs)
    {
        cout << "NO\n";
    }
    else
    {
        cout << "YES\n";
        int allocatable = hrs - totMin;
        for (auto iter : limits)
        {
            if (allocatable)
            {
                int tmp = min(iter.minTime + allocatable, iter.maxTime);
                cout << tmp << " ";
                allocatable -= tmp - iter.minTime;
            }
            else
            {
                cout << iter.minTime << " ";
            }
        }
    }
    return 0;
}

#7

如果一个数是二的幂，则其形式为1000…0B，1000…0B & (1000…0B – 1B) = 0B = 0

#include <iostream>

using namespace std;

typedef long long ll;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll t;
    cin >> t;
    while (t--)
    {
        ll n;
        cin >> n;
        if (n & (n - 1))
        {
            cout << "NO\n";
        }
        else
        {
            cout << "YES\n";
        }
    }
    return 0;
}