（1）题目大意
给定我们一个序列，你可以给每个ai*i，你最多给每个ai乘一个i，问最后是否能使这个序列的乘积能整除2^n。
（2）解题思路
很明显我们只需要2的因子个数达到n就行，我们首先遍历一遍原序列，然后看是否需要额外的2，如果需要我们需要从2的因子多的i开始进行贪心的拿，此时我们可以先预处理出来每个i2的因子的个数，如果把所有i拿完依旧不满足的话，那么则输出-1。
（3）代码实现
#include "bits/stdc++.h"
using namespace std;
const int N = 2e5 + 10;
int num[N];
void init(int n)
{
for(int i = 1;i <= n;i++) {
int cnt = 0,p = i;
while(p % 2 == 0) cnt ++,p /= 2;
num[i] = cnt;
}
}
void solve()
{
int n,cnt = 0,x;
cin >> n;
vector <int> cost;
for(int i = 1;i <= n;i++) {
cin >> x;
cost.push_back(num[i]);
while(x % 2 == 0) cnt ++,x /= 2;
}
sort(cost.rbegin(),cost.rend());
int op = 0;
for(auto x:cost) {
if(cnt < n) cnt += x,op ++;
else break;
}
if(cnt >= n) cout << op << endl;
else cout << -1 << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
init(2e5);
int T;
cin >> T;
while(T --) {
solve();
}
return 0;
}（1）题目大意
给你四个数a，b，c，d，现在需要让求一个x和y，满足a<x<=c，b<y<=d，并且xy % ab==0。
（2）解题思路
因为我们x*y要整除a和b，那么x和y中肯定要包含a和b的因子，我们可以枚举每个a和b的因子，大概使log级别的组合，因此不会特别大，所以我们可以通过枚举a和b的因子，凑出x和y，若满足条件，则输出，否则枚举完所有的后，没有则输出-1 -1。
（3）代码实现
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
void solve()
{
ll a,b,c,d;
cin >> a >> b >> c >> d;
vector <ll> fac1,fac2;
for(ll i = 1;i <= sqrtl(a);i++) {
if(a % i == 0) {
fac1.push_back(i);
fac1.push_back(a / i);
}
}
for(ll i = 1;i <= sqrtl(b);i++) {
if(b % i == 0) {
fac2.push_back(i);
fac2.push_back(b / i);
}
}
for(auto A:fac1)
for(auto B:fac2) {
ll v1 = A * B;
ll v2 = a * b / A / B;
ll x = a + 1,y = b + 1;
if(x % v1) x += v1 - (x % v1);
if(y % v2) y += v2 - (y % v2);
if(x <= c && y <= d) {
cout << x << ' ' << y << endl;
return ;
}
}
cout << -1 << ' ' << -1 << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin >> T;
while(T --) {
solve();
}
return 0;
}（1）题目大意
给定你一个序列，问你有多少个连续的子区间[l,r]满足mex([l,r]) > med([l,r])。mex指区间最小的为出现的非负整数，med是区间的中位数。
（2）解题思路
对于这个题，我们考虑固定其中一个，然后看跑的时候是否满足条件就行，对于固定中位数，显然是不太容易的，你得上数据结构。那么考虑固定mex，我们枚举每个mex，从1-n，对于每个mex，他顶多能二倍mex区间长度，因为大于这个区间长度的中位数至少大于等于这个mex。因此我们记录每个数的位置，从0的位置开始枚举。
考虑四种情况
1.若两倍长度已经小于当前枚举区间长度，显然答案已经被算过或者不存在，continue
2.若当前这个数已经处于枚举的[l,r]中，那么显然答案已经被算过了，因此直接continue
3.若当前这个数的位置在l左边，那么显然每移动一次都会让答案加上当前这个i+2*mex-1-R+1。（也就是固定当前这个i点，右边能给答案的贡献是可以o1算出来的）
4.若当前之个数的位置在r右边，那么显然每移动一次都会让答案加上当前这个i-2*mex+1-l+1。（也就是固定当前这个i点，左边能给答案的贡献是可以o1算出来的）
（3）代码实现
#include "bits/stdc++.h"
using namespace std;
const int N = 2e5 + 10;
int p[N],a[N];
void solve()
{
int n;
long long ans = 0;
cin >> n;
memset(p,0,sizeof(p));
for(int i = 1;i <= n;i++) {
cin >> a[i];
p[a[i]] = i;
}
int l,r;
l = r = p[0];
for(int len = 1;len <= n;len ++) {
if(len != n && p[len] >= l && p[len] <= r) continue;
int dblen = 2 * len;
if(dblen >= (r - l + 1)) {
if(p[len] > r) {
for(int i = r;i < p[len];i++) {
int j = max(1,i - dblen + 1);
ans += max(0,l - j + 1);
}
}
else {
for(int i = p[len] + 1;i <= l;i++) {
int j = min(n,i + dblen - 1);
ans += max(0,j - r + 1);
}
}
}
l = min(l,p[len]);r = max(r,p[len]);
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin >> T;
while(T --) {
solve();
}
return 0;
}