题目链接

A、造数

从二进制的角度从末尾开始考虑，如果最后一位是1，那么执行-1操作；如果最后两位是10，执行-2操作；否则执行/2操作即移位。
tips：去除10可以先/2再-1，也可以-2再除2，这两个步骤只有在只剩10的时候第二种只需要一步，而第一种则需要两步。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <vector>
#include <cmath>
#include <stack>
#include <map>
#include <queue>
#include <set>

using namespace std;
#define PII pair<int,int>
const int N = 1010;

int main()
{
    int n; cin >> n;

    int cnt = 0;
    while (n)
    {
        if (!n) break;
        if (((n & 1) == 0) && ((n >> 1 & 1) == 1)) n -= 2, cnt ++;
        else if (n & 1) n -= 1, cnt ++;
        else n >>= 1, cnt ++;
    }

    cout << cnt << endl;

    return 0;
}

B、爱探险的朵拉

使用tarjan算法缩点为有向无环图，然后建立超级原点计算拓扑图上的最长路

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <vector>
#include <cmath>
#include <stack>
#include <map>
#include <queue>
#include <set>

using namespace std;
#define PII pair<int,int>
typedef long long LL;
const int N = 1e5 + 10, M = N * 3;
int h[N], hs[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, Size[N];
int dist[N];

void add(int h[], int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[++ top] = u,in_stk[u] = true;

    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }

        else if(in_stk[j]) low[u] = min(low[u], dfn[j]);
    }

    if(dfn[u] == low[u])
    {
        ++ scc_cnt;
        int y;
        do
        {
            y = stk[top --];
            id[y] = scc_cnt;
            in_stk[y] = false;
            Size[scc_cnt] ++;
        }while(y != u);
    }
}

int main()
{
    memset(h, -1, sizeof h);
    memset(hs, -1, sizeof hs);
    int n; cin >> n;
    for (int i = 1; i <= n; i ++) 
    {
        int x; cin >> x;
        add(h, i, x);
    }

    for (int i = 1; i <= n; i ++)
        if (!dfn[i]) tarjan(i);

    for (int i = 1; i <= n; i ++)
    {
        for (int j = h[i]; ~j; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b)
                add(hs, a, b); // 连接两个联通块
        }
    }

    // 建立超级原点求解最长路
    int c = 0;
    for (int i = 1; i <= scc_cnt; i ++) add(hs, scc_cnt + 1, i), c += Size[i];
    Size[scc_cnt + 1] = c;

    // 拓扑序
    int res = 0;
    for (int i = scc_cnt + 1; i; i --)
    {
        for (int j = hs[i]; ~j; j = ne[j])
        {
            int k = e[j];
            dist[k] = max(dist[k], dist[i] + Size[k]);
            res = max(res, dist[k]);
        }
    }

//  cout << res << endl;

    return 0;
}

C、有大家喜欢的零食吗

这道题是二分图的最大匹配模板题

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <vector>
#include <cmath>
#include <stack>
#include <map>
#include <queue>
#include <set>

using namespace std;
#define PII pair<int,int>
const int N = 510, M = 2e5 + 10;
int h[N], e[M], ne[M], idx;
bool st[N];
int match[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool find(int x)
{
    for (int i = h[x]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true;
            if (!match[j] || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    memset(h, -1, sizeof h);
    int n; cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        int k; cin >> k;
        for (int j = 0; j < k; j ++)
        {
            int x; cin >> x;
            add(i, x);
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i ++)
    {
        memset(st, 0, sizeof st);
        if (find(i)) res ++;
    }

    if (n == res) cout << "Yes" << endl;
    else
    {
        cout << "No" << endl;
        cout << n - res << endl;
    }

    return 0;
}

D、小蓝的二进制询问

如上图所示我们需要维护从[1, x]中1的个数，并逐位计算1的个数，然后使用前缀和技巧进行计算即可。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <vector>
#include <cmath>
#include <stack>
#include <map>
#include <queue>
#include <set>

using namespace std;
#define PII pair<int,int>
#define int long long
const int N = 1010, mod = 998244353;

int get(int x,int k)
{
    int res = 0;
    int y = 1ll << (k + 1); // 每隔y次出现c个1
    int c = y / 2;
    x ++; // 将0的情况也算进来方便计算
    res += x / y * c;
    int r = x % y;
    res += max(0ll, r - c);
    return res;
}

signed main()
{
    int t; cin >> t;
    while (t --)
    {
        int l, r; cin >> l >> r;

        int res = 0;
        for (int i = 0; i < 62; i ++)
        {
            res += (get(r, i) % mod - get(l - 1, i) % mod + mod) % mod;
            res %= mod;
        }

        cout << res % mod << endl;
    }

    return 0;
}

F、两难抉择新编

调和级数求和，时间复杂度到不了O(n^2)，所以直接进行枚举即可

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <vector>
#include <cmath>
#include <stack>
#include <map>
#include <queue>
#include <set>

using namespace std;
#define PII pair<int,int>
#define int long long
const int N = 2e5 + 10;
int n, a[N];

signed main()
{
    int res = 0;
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i], res ^= a[i];

    int maxv = res;
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= n / i; j ++)
        {
            int t1 = a[i] + j, t2 = a[i] * j;
            maxv = max(maxv, max(res ^ a[i] ^ t1, res ^ a[i] ^ t2));
        }
    }

    cout << maxv << endl;

    return 0;
}

G、旅途的终点

二分答案然后使用优先队列进行判断即可，时间复杂度为O(nlog^2)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <vector>
#include <cmath>
#include <stack>
#include <map>
#include <queue>
#include <set>

using namespace std;
#define PII pair<int,int>
#define int long long
const int N = 2e5 + 10;
int a[N], n, m, k;

bool check(int x)
{
    priority_queue<int>q;
    for (int i = 1; i <= x; i ++) q.push(a[i]);
    int t = k;
    while (t && !q.empty())
    {
        t --;
        q.pop();
    }
    if (t) return true;
    t = m;
    while (!q.empty())
    {
        t -= q.top();
        if (t <= 0) return false;
        q.pop();
    }
    return true;
}

signed main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++) cin >> a[i];

    int l = 0, r = n;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }

    cout << l << endl;

    return 0;
}

H、两难抉择

操作最大的数即可

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <vector>
#include <cmath>
#include <stack>
#include <map>
#include <queue>
#include <set>

using namespace std;
#define PII pair<int,int>
typedef long long LL;
const int N = 2e5 + 10;
LL a[N];

int main()
{
    int n; cin >> n;
    LL s = 0;
    for (int i = 0; i < n; i ++) cin >> a[i], s += a[i];
    sort(a, a + n, greater<int>());

    cout << max(s + n, s + a[0] * n - a[0]) << endl;

    return 0;
}

I、除法移位

我们的目的肯定是将尽可能大的数放到第一位，所以我们枚举所有能移动到第一位的数找到最大的即可

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <vector>
#include <cmath>
#include <stack>
#include <map>
#include <queue>
#include <set>

using namespace std;
#define PII pair<int,int>
const int N = 2e5 + 10;
int a[N];

int main()
{
    int n, t;
    cin >> n >> t;
    for (int i = 0; i < n; i ++) cin >> a[i];

    int maxv = a[0], idx = 0;
    for (int i = max(0, n - t); i < n; i ++)
    {
        if (maxv <= a[i])
        {
            maxv = a[i];
            idx = i;
        }
    }

    if (idx == 0) idx = n;
    cout << n - idx << endl;

    return 0;
}

K、图上计数(Easy)

给定一个数，求将其拆成两个数使得乘积最大

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <vector>
#include <cmath>
#include <stack>
#include <map>
#include <queue>
#include <set>

using namespace std;
#define PII pair<int,int>
typedef long long LL;
const int N = 1010;

int main()
{
    LL n, m; cin >> n >> m;
    for (int i = 0; i < m; i ++)
    {
        int a, b; 
        cin >> a >> b;
    }

    cout << (n / 2) * (n - n / 2) << endl;
    return 0;
}

官方题解