题解 | # JYUACM新生训练周赛1#
小红的签到题
https://ac.nowcoder.com/acm/contest/98442/A
小红的签到题
思路
输出 即可。
复杂度
时间复杂度 ，空间复杂度
。
代码实现
#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;
}
