传送门
6702 ^&^
签到，注意特判答案为 0 的情况
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
int q[50], w[50];
int main()
{
int T;
sc("%d", &T);
while (T--)
{
ll a, b;
sc("%lld%lld", &a, &b);
for (int i = 0; i < 40; i++)
{
if (a & (1LL << i))
q[i] = 1;
else
q[i] = 0;
}
for (int i = 0; i < 40; i++)
{
if (b & (1LL << i))
w[i] = 1;
else
w[i] = 0;
}
ll ans = 0;
for (int i = 0; i < 40; i++)
{
if (q[i] == 1 && w[i] == 1)
{
ans += (1LL << i);
}
}
if (ans == 0)
{
for (int i = 0; i < 40; i++)
{
if ((q[i] == 0 && w[i] == 1) || (q[i] == 1 && w[i] == 0))
{
ans = (1LL << i);
break;
}
}
}
printf("%lld\n", ans);
}
} 6703 array
有一个 
1、由于区间是一个全排列，所以对于每一个操作2，我们可以用线段树 or 主席树找出一个区间内大于等于 val 的最小数字
2、对于操作1，因为数列长度和操作次数都是 
3、怎么使用线段树来求一个区间大于等于 val 的最小值呢。
能否直接对原数组建一颗线段树来暴力扫左右子树呢，显然是不行的，在最差的情况下，每次复杂度都是 
考虑维护下标是值，并且值是下标的线段树，那么原询问：求出区间 
然后对于每个询问，我们只需要在线段树上dfs找一下，加个剪枝，如果在左子树找到了就不在右子树找了，就可以AC。
AC代码
#include <bits/stdc++.h>
#define ll long long
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
#define sc scanf
#define pr printf
using namespace std;
int n, m, ql, qr, val;
const int MAXN = 1e5 + 5;
struct Segment_tree
{
int l;
int r;
int maxn;
}que[MAXN * 4];
int a[MAXN], in[MAXN];
int ans;
void up(int k)
{
que[k].maxn = max(que[k << 1].maxn, que[k << 1 | 1].maxn);
}
void build(int left = 1, int right = n, int k = 1)
{
que[k].l = left;
que[k].r = right;
if (left == right)
{
que[k].maxn = a[left];
return;
}
imid;
build(lson);
build(rson);
up(k);
}
void update(int left = 1, int right = n, int k = 1)
{
if (qr < left || right < ql)
return;
if (ql <= left && right <= qr)
{
que[k].maxn = 0;
return;
}
imid;
update(lson);
update(rson);
up(k);
}
//求区间[ql,qr]第一个大于等于val的值
//使用线段树将区间外的点分开，然后判一段合法区间最大值是否大于等于val
//因为这里不是求整个区间，所以需要将区间外的点分开，不然会影响区间的最大值
bool query(int left = 1, int right = n, int k = 1)
{
if (que[k].maxn < val)
return false;
if (left == right)
{
if (que[k].maxn > val)
{
ans = min(ans, left);
return true;
}
else
return false;
}
imid;
if (ql <= mid)
{
if (query(lson))
return true;
else
return query(rson);
}
else
query(rson);
}
int main()
{
int T, op, t;
sc("%d", &T);
while (T--)
{
sc("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
sc("%d", &in[i]);
a[in[i]] = i;
}
build();
set<int>s;
int pre = 0;
while (m--)
{
sc("%d", &op);
if (op == 1)
{
sc("%d", &val);
val ^= pre;
s.insert(in[val]);
ql = qr = in[val];
update();
}
else
{
sc("%d%d", &val, &ql);
val ^= pre;
ql ^= pre;
qr = n;
ans = n + 1;
query();
auto it = s.lower_bound(ql);
if (it != s.end())
ans = min(ans, *it);
printf("%d\n", ans);
pre = ans;
}
}
}
} TLE代码
#include <bits/stdc++.h>
#define ll long long
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
#define sc scanf
#define pr printf
using namespace std;
int n, m, ql, qr, val;
const int MAXN = 1e5 + 5;
struct Segment_tree
{
int l;
int r;
int maxn;
}que[MAXN * 4];
int a[MAXN];
int ans;
void up(int k)
{
que[k].maxn = max(que[k << 1].maxn, que[k << 1 | 1].maxn);
}
void build(int left = 1, int right = n, int k = 1)
{
que[k].l = left;
que[k].r = right;
if (left == right)
{
que[k].maxn = a[left];
return;
}
imid;
build(lson);
build(rson);
up(k);
}
void update(int left = 1, int right = n, int k = 1)
{
if (qr < left || right < ql)
return;
if (ql <= left && right <= qr)
{
que[k].maxn = -1;
return;
}
imid;
update(lson);
update(rson);
up(k);
}
//求区间[ql,qr]大于val的最小权值
void query(int left = 1, int right = n, int k = 1)
{
if (qr < left || right < ql)
return;
if (ql <= left && right <= qr)
{
imid;
if (left == right)
{
if (que[k].maxn >= val)
ans = min(ans, que[k].maxn);
return;
}
if (que[k << 1].maxn >= val)
query(lson);
if (que[k << 1 | 1].maxn >= val)
query(rson);
}
imid;
query(lson);
query(rson);
}
int main()
{
int T, op;
sc("%d", &T);
while (T--)
{
sc("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
sc("%d", &a[i]);
build();
set<int>s;
int pre = 0;
while (m--)
{
sc("%d", &op);
if (op == 1)
{
sc("%d", &val);
val ^= pre;
s.insert(a[val]);
ql = qr = val;
update();
}
else
{
sc("%d%d", &ql, &val);
ql ^= pre;
val ^= pre;
ql++;
qr = n;
ans = n + 1;
query();
auto it = s.lower_bound(val);
if (it != s.end())
ans = min(ans, *it);
printf("%d\n", ans);
pre = ans;
}
}
}
} 6704 K-th occurrence
多次询问，对于一个给定的串的子串，求出这个子串第K次出现的位置，不存在输出-1。
大概就是 后缀数组，套个主席树，再套个二分求区间左右端点，
（队友不会主席树，赛时也不跟我说要用主席树，然后每次sort 直接输出，T飞。）（甩锅）
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#define M(x) memset(x,0,sizeof(x))
#define ll long long
#define rep(i,a,b) for(int i = a;i<=b;i++)
#define dec(i,a,b) for(int i = a;i>=b;i--)
#define imid int mid=(left+right)/2;
const int MAXN = 100005;
const int logMAXN = 20;
struct node
{
int l;
int r;
ll cnt;
ll sum;
}tree[MAXN * logMAXN];
int root[MAXN], a[MAXN], cnt;
void init()
{
root[0] = 0;
tree[0].l = tree[0].r = tree[0].cnt = 0;
cnt = 1;
}
void build(int num, int& rot, int left, int right)
{
tree[cnt++] = tree[rot];
rot = cnt - 1;
tree[rot].cnt++;
tree[rot].sum += num;
if (left == right)
return;
imid;
if (num <= mid)
build(num, tree[rot].l, left, mid);
else
build(num, tree[rot].r, mid + 1, right);
}
//查询区间[ql, qr]里面的第K小的数字
//query(root[ql - 1], root[qr], k, 1, n);
int query(int pre, int nex, int num, int left, int right)
{
int s = tree[tree[nex].l].cnt - tree[tree[pre].l].cnt;
if (left == right)
return left;
imid;
if (num <= s)
return query(tree[pre].l, tree[nex].l, num, left, mid);
else
return query(tree[pre].r, tree[nex].r, num - s, mid + 1, right);
}
struct SufArray {
int sa[N], c[N], x[N], y[N], height[N], rk[N], f[N][22], n;
char s[N];
void clear()
{
M(sa); M(c); M(x); M(y); M(height); M(rk); M(f); M(s);
}
void build_sa()
{
int m = 128;
for (int i = 0; i <= m; i++) c[i] = 0;
for (int i = 1; i <= n; ++i) ++c[x[i] = s[i]];
for (int i = 2; i <= m; ++i) c[i] += c[i - 1];
for (int i = n; i >= 1; --i) sa[c[x[i]]--] = i;
for (int k = 1; k <= n; k <<= 1) {
int num = 0;
for (int i = n - k + 1; i <= n; ++i) y[++num] = i;
for (int i = 1; i <= n; ++i) if (sa[i] > k) y[++num] = sa[i] - k;
for (int i = 1; i <= m; ++i) c[i] = 0;
for (int i = 1; i <= n; ++i) ++c[x[i]];
for (int i = 2; i <= m; ++i) c[i] += c[i - 1];
for (int i = n; i >= 1; --i) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
swap(x, y);
x[sa[1]] = 1;
num = 1;
for (int i = 2; i <= n; ++i)
x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
if (num == n) break;
m = num;
}
}
void build_height()
{
int k = 0;
for (int i = 1; i <= n; i++) rk[sa[i]] = i;
for (int i = 1; i <= n; i++)
{
if (rk[i] == 1)
continue;
if (k) k--;
int j = sa[rk[i] - 1];
while (j + k <= n && i + k <= n && s[j + k] == s[i + k]) k++;
height[rk[i]] = k;
}
}
void build_st()
{
build_height();
for (int i = 1; i <= n; i++) f[i][0] = height[i];
for (int k = 1; (1 << k) <= n; k++)
for (int i = 1; i + (1 << k) - 1 <= n; i++)
f[i][k] = min(f[i][k - 1], f[i + (1 << (k - 1))][k - 1]);
}
int lcp(int u, int v)
{
int l = rk[u], r = rk[v];
if (l > r) swap(l, r);
if (l == r) return n - sa[l];
l++;
int k = 0;
while ((1 << (1 + k)) <= r - l + 1) k++;
return min(f[l][k], f[r - (1 << k) + 1][k]);
}//rmq
void solve(int l, int r, int k)
{
int len = (r - l + 1);
int t = rk[l];
int L = 1, R = t;
int ql, qr;
while (L + 1 < R)
{
int mid = (L + R) >> 1;
if (lcp(sa[mid], l) >= len)
R = mid;
else
L = mid;
}
ql = R;
if (lcp(sa[L], l) >= len)
ql = L;
L = t, R = n;
while (L + 1 < R)
{
int mid = (L + R) >> 1;
if (lcp(sa[mid], l) >= len)
L = mid;
else
R = mid;
}
qr = L;
if (lcp(sa[R], l) >= len)
qr = R;
if (qr - ql + 1 >= k)
printf("%d\n", query(root[ql - 1], root[qr], k, 1, n));
else
printf("-1\n");
}
}sa;
int main()
{
int T, K;
scanf("%d", &T);
while (T--)
{
sa.clear();
scanf("%d %d", &sa.n, &K);
scanf("%s", sa.s + 1);
sa.build_sa();
sa.build_st();
init();
for (int i = 1; i <= sa.n; i++)
{
a[i] = sa.sa[i];
root[i] = root[i - 1];
build(a[i], root[i], 1, sa.n);
}
for (int i = 1; i <= K; i++)
{
int l, r, k;
scanf("%d %d %d", &l, &r, &k);
sa.solve(l, r, k);
}
}
} 6706 huntian oy
//update 2019/10/14
杜教筛模板题，但。首先要知道
(考虑欧拉函数 
考虑杜教筛
#include <bits/stdc++.h>
#include <unordered_map>
#define ll long long //T了就换int 试试
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 5000005;//用板子前先改范围
const ll mod = 1e9 + 7;
bool check[MAXN + 10];//值为 false 表示素数，值为 true 表示非素数
ll phi[MAXN + 10];//欧拉函数表
//ll mu[MAXN + 10];//莫比乌斯函数
int prime[MAXN + 10];//连续素数表
int tot;//素数的个数（从0开始
void jzk()
{
//memset(check, false, sizeof(check));
phi[1] = 1;
//mu[1] = 1;
check[1] = true;//额外要加上的
tot = 0;
for (int i = 2; i < MAXN; i++)
{
if (!check[i])
{
prime[tot++] = i;
phi[i] = i - 1;
//mu[i] = -1;
}
for (int j = 0; j < tot; j++)
{
if (i * prime[j] >= MAXN)
break;
check[i * prime[j]] = true;
if (i % prime[j] == 0)
{
phi[i * prime[j]] = phi[i] * prime[j];
//mu[i * prime[j]] = 0;
break;
}
else
{
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
//mu[i * prime[j]] = -mu[i];
}
}
}
for (int i = 1; i < MAXN; i++) {
//mu[i] = (mu[i] + mu[i - 1]);
phi[i] = (phi[i] * i + phi[i - 1]) % mod;
}
}
unordered_map<ll, ll>mp;
ll inv2 = (mod + 1) / 2;
ll inv6 = (mod + 1) / 6;
ll calc(ll a, ll b)
{
ll ans = (b - a + 1) % mod * ((b + a) % mod) % mod * inv2 % mod;
return ans;
}
ll calcs(ll n)
{
ll ans = n * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod;
return ans;
}
ll djs1(ll n)// i * \phi i
{
if (n < MAXN)
return phi[n];
if (mp.count(n))
return mp[n];
ll ans = 0, j;
for (ll i = 2; i <= n; i = j + 1)
{
j = n / (n / i);
ans = (ans + calc(i, j) * djs1(n / i)) % mod;
}
ans = calcs(n) - ans;
return mp[n] = ans;
}
int main()
{
jzk();
int T;
sc("%d", &T);
while(T--)
{
ll n;
sc("%lld%*d%*d", &n);
ll ans = djs1(n);
ans = (ans - 1 + mod) * inv2 % mod;
pr("%lld\n", ans);
}
} 6707 Shuffle Card
签到。反过来扫一遍
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
int a[100005];
int qq[100005];
vector<int>ans;
bool vis[100005];
int main()
{
int n, m;
sc("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
sc("%d", &a[i]);
for (int i = 1; i <= m; i++)
sc("%d", &qq[i]);
for (int i = m; i >= 1; i--)
{
int t = qq[i];
if (vis[t] == true)
continue;
else
{
ans.push_back(t);
vis[t] = true;
}
}
for (int i = 1; i <= n; i++)
{
if (vis[a[i]] == false)
ans.push_back(a[i]);
}
for (int i = 0; i < n; i++)
printf("%d ", ans[i]);
} 6708 Windows Of CCPC
签到，递归秒
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
int s[1025][1025];
void dfs(int x, int y, int len, int op)
{
if (len == 1)
{
if (op == 0)
{
s[x][y] = 'C';
s[x][y + 1] = 'C';
s[x + 1][y] = 'P';
s[x + 1][y + 1] = 'C';
return;
}
else
{
s[x][y] = 'P';
s[x][y + 1] = 'P';
s[x + 1][y] = 'C';
s[x + 1][y + 1] = 'P';
return;
}
}
dfs(x, y, len - 1, op);
dfs(x + (1 << (len - 1)), y, len - 1, op ^ 1);
dfs(x, y + (1 << (len - 1)), len - 1, op);
dfs(x + (1 << (len - 1)), y + (1 << (len - 1)), len - 1, op);
}
int main()
{
int T;
sc("%d", &T);
while (T--)
{
int n;
sc("%d", &n);
int len = (1 << n);
for (int i = 1; i <= len; i++)
for (int j = 1; j <= len; j++)
s[i][j] = 0;
dfs(1, 1, n, 0);
for (int i = 1; i <= len; i++)
{
for (int j = 1; j <= len; j++)
printf("%c", s[i][j]);
printf("\n");
}
}
} 6709 Fishing Master
假设我们煮鱼的时候如果时间不够就不浪费时间去抓鱼，那么就不抓鱼，那么我们可以知道在不浪费时间的前提下最多能抓多少鱼，然后浪费时间的前提下抓的鱼就是总的鱼减去不浪费时间抓的鱼，，然后将所有煮鱼的时间膜上抓鱼的时间，这个时候我们肯定希望抓浪费时间的鱼最小，所以将煮的时间排个序，煮鱼时间越长说明浪费的时间越少。
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
ll a[100005];
int main()
{
int T;
sc("%d", &T);
while (T--)
{
int n, k;
sc("%d%d", &n, &k);
for (int i = 0; i < n; i++)
sc("%lld", &a[i]);
sort(a, a + n, [](int q, int w) {
return q > w;
});
ll time = 0;
ll num = n;
for (int i = 0; i < n; i++)
{
ll can = a[i] / k;
can = min(can, num);
num -= can;
time += can * k;
a[i] = a[i] - can * k;
}
sort(a, a + n, [](int q, int w) {
return q > w;
});
for (int i = 0; i < num; i++)
time += k;
for (int i = num; i < n; i++)
time += a[i];
printf("%lld\n", time);
}
}
京公网安备 11010502036488号