Codefoces Round 900(Div.3) A ~E

思路 ： 有 $k$ 就输出 $yes$,否则输出 $no$；

    int n, k;cin >> n >> k;bool flag = false;for (int i = 1; i <= n; i++){int x;cin >> x;if (x == k){flag = true;}}if (flag)cout << "YES" << endl;elsecout << "NO" << endl;

有我没他

思路 : 构造一个数组满足 a i + 2 a_{i + 2} ai+2​ 不能被 a i + 1 + a i a_{i+1} + a_{i} ai+1​+ai​ 整除。奇数永远不被偶数整除，我们只需要一个正奇数即可

	int n;cin >> n;int cnt = 2;for (int i = 1; i <= n; i++){cout << cnt << ' ';cnt += 3;}cout << endl;

奇数永远不会被偶数整除，就像我和她永远没有相交线

思路 : 只要在能取的最小值和能去的最大值，这个 $x$ 就是合法的

	ll n, k, x;cin >> n >> k >> x;ll a = n + (n * (n - 1)) / 2;ll m = n - k;ll b = m + (m * (m - 1)) / 2;ll c = k + (k * (k - 1))/  2;if (a - b < x || c > x){cout << "NO" << endl;}else{cout << "YES" << endl;}

思路 ：每一个区间是不相交且互不干扰的，用差分维护每一区间的需要翻转的区间；区间具有对称性， $i$ 始终与 $n-i+1$ 交换，因此翻转的时候从左边开始往翻转区间的中心点靠近即可。

	int n, k;cin >> n >> k;string s; cin >> s;s = " " + s;vector<int> l(n + 1), r(n + 1);for (int i = 1; i <= k; i++) {cin >> l[i];}for (int i = 1; i <= k; i++) {cin >> r[i];}vector<int> b(n + 2);int q; cin >> q;while (q--){int x; cin >> x;int L = 1,R = k;while (L < R) {int mid = L + R >> 1;if (r[mid] >= x) R = mid;else L = mid + 1;}int ll = min(x, l[L] + r[L] - x);int rr = max(x, l[L] + r[L] - x);b[ll] ++, b[rr + 1]--;}for (int i = 1; i <= n; i++) {b[i] += b[i - 1];}for (int i = 1; i <= k; i++) {for (int ll = l[i], rr = r[i]; ll <= rr; ll++, rr--) {if (b[ll] & 1) {swap(s[ll], s[rr]);}}}for (int i = 1; i <= n; i++) {cout << s[i];}cout << endl;

思路1 ：经典的线段树 + 二分,超级好写 ，不用懒标记，只需要pushup即可；区间维护异或值，最后用二分查询最右能 $\ge$ $k$ 的区间右值

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define fi first
#define se second
#define pb push_back
#define sz size()
#define bpt __builtin_popcountllusing namespace std;
typedef long long ll;
typedef unsigned long long ull;const int N = 2E5 + 10, INF = 0x3f3f3f3f;int p[N], inv[N];
int find(int x){if (p[x] != x){ p[x] = find(p[x]);}return p[x];}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
ll ksm(int a, int k, int p){ll res = 1;while (k){if (k & 1){ res = (ll)res * a % p; }k >>= 1;a = (ll)a * a % p;}return res;}
int exgcd(int a, int b, int& x, int& y){if (!b){x = 1, y = 0;return a;}int d = exgcd(b, a % b, y, x);y -= a / b * x;return d;}
void inv_(int p){inv[1] = 1;for (int i = 2; i <= p; i++){inv[i] = (p - p / i) * inv[p % i] % p;}}struct Node
{int l, r;ll sum;
} tr[N << 3];ll a[N];
int x, k;
void pushup(int u)
{tr[u].sum = tr[u << 1].sum & tr[u << 1 | 1].sum;
}void build(int u, int l, int r)
{tr[u] = { l, r };if (l == r){tr[u].sum = a[l];}else{int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);pushup(u);}
}ll query(int u, int l, int r)
{if (tr[u].l > r || tr[u].r < l){return (1 << 31) - 1;}if (tr[u].l >= l && tr[u].r <= r){return tr[u].sum;}int mid = tr[u].l + tr[u].r >> 1;return (query(u << 1, l, r) & query(u << 1 | 1, l, r));
}bool check(int mid)
{if (query(1, x, mid) >= k)return true;elsereturn false;
}
void solve()
{int n;cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}build(1, 1, n);int q;cin >> q;while (q--){cin >> x >> k;if (a[x] < k){cout << -1 << endl;continue;}int l = x, r = n;while (l <= r){int mid = l + r >> 1;if (check(mid)){l = mid + 1;}else{r = mid - 1;}}cout << r << endl;}cout << endl;
}
int main()
{int _;cin >> _;while (_--)solve();system("pause");
}

思路2 ：将数组$a$ 的每一个数的每一位存到数组里面，进行前缀和，同样的用二分查找最右满足条件的区间下标

	int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; i++){cin >> a[i];}for (int i = 0; i < n; i++) {for (int j = 0; j < 30; j++) {if (a[i] & (1 << j)) {sum[i + 1][j] = sum[i][j] + 1;}else {sum[i + 1][j] = sum[i][j];}}}int q;cin >> q;while (q--){int l, k;cin >> l >> k;if (a[l - 1] < k){cout << -1 << endl;continue;}int ll = l;int rr = n;int ans = l;while (ll <= rr){int mid = ll + rr >> 1;int res = 0;for (int j = 0; j < 30; j++){if (sum[mid][j] - sum[l - 1][j] == mid - l + 1){res += (1 << j);}}if (res >= k){ll = mid + 1;ans = max(ans, mid);}elserr = mid - 1;}cout << ans << endl;}cout << endl;