小红的签到题

思路

输出 即可。

复杂度

时间复杂度 ，空间复杂度 。

代码实现

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

int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    cout<<c/a;
}

异或故事

思路

如果 二进制下表示有两个及以上的 ，可以把其中的一个 拿出来作为 ，剩下的部分作为 。 比如 二进制表示下为 ，可以把 取出来作为 , 作为 ，当然， 和 也是可以的。

否则，这个数就是个二次幂，如果是 的话，可以把 作为答案，不然就是 这样大于 的二次幂，可以将 和 分别作为 。

综上，其实总存在一个二次幂 可以作为答案的一项， 做为答案的另一项。

（异或的交换律：若 ，可以得到 ）

复杂度

时间复杂度 O(1)$

代码实现

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

int main()
{
    int T;
    cin>>T;
    int r = 1e9;
    while(T--){
        int x;
        cin>>x;
        for(int i=0;i<32;i++){
            int a = 1<<i;
            int b = x^a;
            if(a<=r && b<=r && a>0 && b>0){
                cout<<a<<' '<<b<<'\n';
                break;
            }
        }
    }
}

石子合并

思路

有 堆石子，每次选择减少一堆，最后剩下一堆，会有 次选择。

因为每次都是删取较小的数，所以最后一定剩下最大值。

有一个想法是不如每次都选择最大值和最大值相邻的数，直到选完 次，这样的做法是可以使得最后的价值最大的。

因为每次选择都会累加两个选择的数到价值里面，所以如果除了一个最大值外的总和为 ，最大值为 ，那么按上面的想法得到的价值为 。

如果不按上面的想法进行选择，那么至少会有一次，选择的两个数 都不是最大值，会剩下 中的较大值 ，然后 可能与一个数 选择在一起，累加的总和为 。

如果按上面的想法，这两个数是分别与最大值 选择了一次，累加的总和为 。

显然，，，不按上面的想法进行选择，是不会让价值变得更大的。

（这里只是讨论了不按上面的想法进行选择，改变了原来两次选择的情况，可能还有改变到 次选择的情况，但是把改变前累加的总和与改变后累加的总和进行比较，可以发现总是后者总是不超过前者的）

复杂度

时间复杂度 ，空间复杂度

代码实现

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

int main()
{
    int n;
    cin>>n;
    long long sum = 0,ma = 0;
    for(int i=1;i<=n;i++){
        long long x;
        cin>>x;
        sum += x;
        ma = max(ma,x);
    }
    long long ans = (sum-ma) + (n-1)*ma;
    cout<<ans;
}

小红的口罩

思路

因为每个口罩使用后不舒适度都会翻倍，翻倍到大于 时，这个口罩显然一定不能使用，所以每个口罩的使用次数是 级别的，换句话说，每个口罩不舒适度的变化序列，有效的范围是 级别的。

可以将所有口罩变化序列有效的部分（不大于 的部分）都放到一起，然后把所有的可能的不舒适度从小到大排序，从最小的不舒适度开始累加（因为累加小的可以给后面累加的有更多空间，使得累加的数量尽可能大），直到累加到超过 为止。

复杂度

时间复杂度 ，空间复杂度

代码实现

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

#define int long long

signed main()
{
    int n,k;
    cin>>n>>k;
    vector<int>all;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        while(x<=k){
            all.push_back(x);
            x *= 2;
        }
    }
    sort(all.begin(),all.end());
    
    int cnt = 0,sum = 0;
    for(int x:all){
        if(sum+x>k) break;
        cnt++;
        sum+=x;
    }
    cout<<cnt;
}