校内周赛题（思维题）

这次周赛的题目没有什么很难的代码实现，基本上都是对思路的把握。

与君共勉🌹

选取x个数，看能不能使得这x个数相加的结果是奇数。

如果x是偶数，他的分布肯定是一个奇数+一个偶数+若干个两两配对的奇数+若干个两两配对的偶数。

如果x是奇数，他的分布肯定是一个奇数+若干个两两配对的奇数+若干个两两配对的偶数。

我们只需要记录奇数个数和偶数个数，然后判断条件是否成立即可。

注意奇数偶数后面必须成对，化简之后cnt1+cnt2>x (这样子是过不了的)

#include <bits/stdc++.h>
using namespace std;
void solve(){long long a, n, m, x;cin >> n >> x;long long cnt1 = 0, cnt2 = 0;for(int i = 1; i <= n; i++){cin >> a;  // 输入数组元素if(a % 2 == 1){  // 判断是否为奇数cnt1++;  // 奇数计数增加}else{cnt2++;  // 偶数计数增加}}if(x % 2 == 1){  // 当需要选取的元素个数x为奇数时// 需要至少1个奇数，且剩下的x-1个数可以组成(x-1)/2对（每对可以是奇+奇或偶+偶）if(cnt1 >= 1 && (cnt1 - 1) / 2 + (cnt2 / 2) >= (x - 1) / 2){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}else{  // 当需要选取的元素个数x为偶数时// 需要至少1个奇数和1个偶数，剩下的x-2个数可以组成(x-2)/2对if(cnt1 >= 1 && cnt2 >= 1 && (cnt1 - 1) / 2 + (cnt2 - 1) / 2 >= (x - 2) / 2){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}
}
int main(){int T;cin >> T;while(T--)solve();return 0;
}

考虑到当a>b的时候，n名第一类客人会拿a，否则拿b。m名第二类客人反之。所以说n位客人总是拿比较多的类型的曲奇，m位客人总是拿比较少的类型的曲奇。

首先a+b一定要大于等与n+m，其次考虑m位客人。

考虑到无论怎么安排顺序，m位客人可以拿到的曲奇的个数始终不会超过刚开始的min（a，b），所以我们首先判断曲奇的个数是否够，然后再判断min(a，b)是否比m大就可以了。

#include <bits/stdc++.h>
using namespace std;
void solve(){long long a,b,n,m;cin>>a>>b>>n>>m;if(a+b<n+m){cout<<"Yes"<<endl;}else if(min(a,b)<m){cout<<"No"<<endl;}else{cout<<"Yes"<<endl;}
}int main(){int T;cin>>T;while(T--)solve();return 0;
}

 

 

首先我们考虑到一种通解，便是选定整个数组，第一次随机打乱，第二次按序排回，就可以直接完成了，也就是说答案最大是2。答案是0的情况我们一上来特判掉就可以了。

最后我们的判断的就是什么时候输出1，什么时候输出2。

首先先对该数组进行排序，要进行改变的就打一个vis判断，最后看有几段vis的连在一起，

=1就输出1，>=2就输出2.

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
#define int long long
int a[maxn], cnt[maxn], b[maxn], vis[maxn];
inline void solve() {int n;cin >> n;for (int i = 1; i <= n; i++) {vis[i] = 0;cnt[i] = 0;}for (int i = 1; i <= n; i++) {cin >> a[i];b[i] = a[i];cnt[a[i]]++;}sort(b + 1, b + n + 1);int p = n + 1, fla1 = 1;  // p记录第一个不匹配的位置，fla1标记是否找到第一个不匹配for (int i = 1; i <= n; i++) {if (a[i] != b[i]) {if (fla1 == 1) {fla1 = 0;p = i;  // 记录起始位置}vis[i] = 1;  // 标记该位置需要处理}}if (p == n + 1) {  // 如果所有位置都匹配cout << 0 << endl;return;}long long r = n + 1;  // 记录第一个不需要处理的位置for (int i = p; i <= n; i++) {if (vis[i] == 0) {  // 如果当前位置不需要处理r = i;  // 记录位置break;}}for (int i = r; i <= n; i++) {if (vis[i] == 1) {  // 如果在不需要处理的区域发现需要处理的位置cout << 2 <<endl;return;}}cout << 1 <<endl;// 否则只需要一次交换
}signed main() {int T;cin >> T;while (T--) solve();return 0;
}

异或和与的结合，异或状态前后，每一位1的个数都是相同的，也就是在与的情况下，1的位置会有转移，所以我们找最大值，就是从后往前塞1，直到塞不下为止。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int  cnt[32];
int kuaisu(int a,int b){int sum=1;while(b){if(b&1)sum=sum*a;a*=a;b>>=1;}return sum;
}
inline void solve(){int n,a;cin>>n;for(int i=1;i<=n;i++){cin>>a;for(int w=0;w<=31;w++){if(a&(1<<w)){//判断第w位上是否是1cnt[w]++;}}}//cnt就是统计每一位上有多少个1，最后对他们进行统一分配int ans=0;for(int i=1;i<=n;i++){int now=0;for(int w=0;w<=31;w++){if(cnt[w]){now+=(1<<w);cnt[w]--;}}ans+= kuaisu(now,2);}cout<<ans<<endl;
}