1001 ^ & ^

 

当a&b不为0时,c=a&b。否则c=a,b中最低一位的1。用x&-x可以直接得到最低位1,当时是队友写的用了循环,也能过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>

using namespace std;

int main()
{
int T;
cin >> T;
while (T--) {
long long a, b;
cin >> a >> b;
if (a & b) cout << (a & b) << endl;
else {
int i = 1;
while (!(a & i) && !(b & i))
i <<= 1;
cout << i << endl;
}
}
return 0;
}

 

1002 array

 

权值线段树

每个节点存对应区间的数在原序列中的编号最大值。对于不在原序列中的数,存0.

因为r和k是小于等于n的,所以对每一次询问,n+1必定是满足的,只是可能不是最小值,但是这说明只要把n+1加入答案集合中,就一定能对每个询问给出答案。

每次对一个询问,要求查找大于等于k,且编号大于r的最小的数。则查找线段树上区间k到n+1,并且编号大于r的最小数,要找编号大于r,所以线段树上存区间编号最大值,这样对于编号最大值都小于等于r的区间,就可以直接跳过了。要找到满足条件的最小的数,则每次优先找左子树,因为左边数字小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
#define mid ((l+r)>>1)
#define lson l,mid,2*rt
#define rson mid+1,r,2*rt+1
const int maxn = 1e5 + 5;
int T, ans, n, m;
int a[maxn], b[maxn];
int tree[maxn << 2];
void pushup(int rt) {
tree[rt] = max(tree[rt << 1], tree[(rt << 1) | 1]);
}
void build(int l, int r, int rt) {
if (l == r) {
tree[rt] = a[l];
return;
}
build(lson);
build(rson);
pushup(rt);
}
void update(int o,int l,int r,int rt) {
if (l == r) {
tree[rt] = n + 1;
return;
}
if (o <= mid)update(o, lson);
else update(o, rson);
pushup(rt);
}
bool query(int R, int k, int l, int r, int rt) {
if (l == r) {
if (tree[rt] > R) {
ans = l;
return true;
}
else return false;
}
bool flg = 0;
if (k <= mid && tree[rt << 1] > R)flg |= query(R, k, lson);
if (!flg)flg |= query(R, k, rson);
return flg;
}
int main() {
//freopen("out.txt", "w", stdout);
scanf("%d", &T);
while (T--) {
ans = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
int u;
scanf("%d", &u);
b[i] = u;
a[u] = i;
}
a[n + 1] = n + 1;
build(1, n + 1, 1);
while (m--) {
int op;
scanf("%d", &op);
if (op == 1) {
int t1;
scanf("%d", &t1);
t1 ^= ans;
update(b[t1], 1, n + 1, 1);
}
else {
int r, k;
scanf("%d%d", &r, &k);
r ^= ans;
k ^= ans;
query(r, k, 1, n + 1, 1);
printf("%d\n", ans);
}
}
}
return 0;
}

 

1003 K-th occurrence

 

后缀数组,st表,主席树

用后缀数组找一个子串所有出现的地方,可以知道这是一段区间,因此问题变为确定区间端点,并找到区间的第k小。

二分分别确定区间左右端点,st表用来查找lcp,因为只有lcp大于等于子串长度,才是子串出现了。

把后缀数组存入主席树中,因为我们是找后缀数组的区间最值,确定区间之后,主席树查第k小,经典应用。

因为写代码时,字符串以0开头,所以对所有询问编号都-1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5;
int t, n, q;
int cnt, root[maxn];
int rk[maxn], tmp[maxn], k, sa[maxn];
int lcp[maxn], st[maxn][21];
char s[maxn];
int read() {
int x = 0, f = 1; char s = getchar();
for (; s > '9' || s < '0'; s = getchar()) if (s == '-') f = -1;
for (; s >= '0'&&s <= '9'; s = getchar()) x = x * 10 + s - '0';
return x * f;
}
void clear() {
cnt = 0;
k = 0;
memset(root, 0, sizeof(root));
memset(rk, 0, sizeof(rk));
memset(tmp, 0, sizeof(tmp));
memset(sa, 0, sizeof(sa));
memset(lcp, 0, sizeof(lcp));
memset(st, 0x3f, sizeof(st));
}
//----------------------------------------------
struct node
{
int l, r, sum;
}T[maxn*40];
void update(int l, int r, int &x, int y, int pos) {
T[++cnt] = T[y];
T[cnt].sum++;
x = cnt;
if (l == r)return;
int mid = (l + r) >> 1;
if (mid >= pos)update(l, mid, T[x].l, T[y].l, pos);
else update(mid + 1, r, T[x].r, T[y].r, pos);
}
int query(int l, int r, int x, int y, int k) {
if (l == r)return l;
int mid = (l + r) >> 1;
int sum = T[T[y].l].sum - T[T[x].l].sum;
if (sum >= k)return query(l, mid, T[x].l, T[y].l, k);
else return query(mid + 1, r, T[x].r, T[y].r, k - sum);
}
//--------------------------------------------------------------
bool compare_sa(int i, int j) {
if (rk[i] != rk[j])return rk[i] < rk[j];
else {
int ri = i + k <= n ? rk[i + k] : -1;
int rj = j + k <= n ? rk[j + k] : -1;
return ri < rj;
}
}
void constract_sa(const char* S) {
for (int i = 0; i <= n; i++) {
sa[i] = i;
rk[i] = i < n ? S[i] : -1;
}
for (k = 1; k <= n; k *= 2) {
sort(sa, sa + n + 1, compare_sa);
tmp[sa[0]] = 0;
for (int i = 1; i <= n; i++) {
tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);
}
for (int i = 0; i <= n; i++) {
rk[i] = tmp[i];
}
}
}
void constract_lcp(const char* S) {
for (int i = 0; i <= n; i++) {
rk[sa[i]] = i;
}
int h = 0;
lcp[1] = 0;
for (int i = 0; i < n; i++) {
int j = sa[rk[i] - 1];
if (h > 0)h--;
for (; j + h < n&&i + h < n; h++) {
if (S[j + h] != S[i + h])break;
}
lcp[rk[i]] = h;
}
for(int i=1;i<=n;i++) st[i][0] = lcp[i];
for (int j = 1; j <= 20; j++)
for (int i = 1; i + (1 << j) - 1 <= n; ++i)
st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
int LCP(int i, int j) {//j>=i
if (i - 1 == j)return n - sa[i - 1];
int x = log2(j - i + 1);
return min(st[i][x], st[j - (1 << x) + 1][x]);
}
//------------------------------------------------------
void solve(int S, int T, int k) {
int L, R, l, r;
l = 1; r = rk[S];
while (l <= r) {
int mid = (l + r) / 2;
//cout << LCP(mid, rk[S]);
if (LCP(mid+1, rk[S]) >= (T - S + 1)) {
L = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
l = rk[S]; r = n;
while (l <= r) {
int mid = (l + r) / 2;
//cout << LCP(rk[S], mid);
if (LCP(rk[S]+1, mid) >= (T - S + 1)) {
R = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
if (R - L + 1 < k) {
cout << "-1" << endl;
return;
}
cout << query(1, n, root[L - 1], root[R], k) << endl;
}
int main() {
t = read();
while (t--) {
clear();
n = read(); q = read();
scanf("%s", s);
constract_sa(s);
constract_lcp(s);
for (int i = 1; i <= n; i++) {
update(1, n, root[i], root[i - 1], sa[i]+1);
}
while (q--) {
int l, r, K;
l = read(); r = read(); K = read();
l--; r--;
solve(l, r, K);
}
}
return 0;
}

 

1004 path

 

队友赛后补的题。

要求找第k小的路径和。

bfs+优先队列

对询问排序。优先队列中对路径和从小到大排序,记录节点间的边权时也是从小到大排序。每次取出优先队列顶上的路径和,路径末端的点向外扩展一条最短的边权,入队;假设设刚才那个路径末端节点是其父节点第id小的边得到的,则还要将刚才那个路径末端点的父节点的第id+1小的子节点入队。

将两个路径入队是因为它们都有可能是下一个大小的路径和。而其它路径不需要入队,因为它们都必定大于这两条路径。

还未补题,网上找的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
#define INF 1e18
using namespace std;
typedef long long ll;
const int N = 5e4 + 10;
int t, n, m, k, y[N];
struct node {
int v;
ll w;
bool operator<(const node &a)const {
return w < a.w;
}
};
struct no {
int now, fa, id;
ll w;
bool operator<(const no&a)const {
return w > a.w;
}
};
vector<node> mp[N];
vector<ll> ans;
priority_queue<no> q;
void init() {
for(int i = 1; i <= n; i++)
mp[i].clear();
ans.clear();
while(!q.empty())
q.pop();
}
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d%d%d", &n, &m, &k);
init();
int mx = 0;
for(int u, v, w, i = 1; i <= m; i++) {
scanf("%d%d%d", &u, &v, &w);
mp[u].push_back(node{v, w});
}
for(int i = 1; i <= n; i++)
sort(mp[i].begin(), mp[i].end());
for(int i = 1; i <= n; i++)
if(mp[i].size())
q.push(no{mp[i][0].v, i, 1, mp[i][0].w});
for(int i = 1; i <= k; i++) {
scanf("%d", &y[i]);
mx = max(mx, y[i]);
}
for(int pp = 1; pp <= mx; pp++) {
no z = q.top();
q.pop();
ans.push_back(z.w);
int id = z.id;
if(mp[z.fa].size() > id)
q.push(no{mp[z.fa][id].v, z.fa, id + 1, mp[z.fa][id].w + z.w - mp[z.fa][id - 1].w});
if(mp[z.now].size() > 0)
q.push(no{mp[z.now][0].v, z.now, 1, mp[z.now][0].w + z.w});
}
for(int i = 1; i <= k; i++)
printf("%lld\n", ans[y[i] - 1]);
}
return 0;
}

 

1006 Shuffle Card

 

队友写的,听说直接模拟就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<cstdio>
#include<iostream>
using namespace std;

int main()
{
int n, m, tmp;
bool vis[100010];
int q[100010];
scanf("%d %d", &n, &m);
for (int i=1;i<=n;i++) {
vis[i] = 0;
scanf("%d", &tmp);
}
for (int i=0;i<m;i++)
scanf("%d", &q[i]);
for (int i=m-1;i>=0;i--) {
if (!vis[q[i]]) {
printf("%d ", q[i]);
vis[q[i]] = 1;
}
}
for (int i=1;i<=n;i++)
if (!vis[i])
printf("%d ",i);
return 0;
}

 

1007 Windows Of CCPC

 

找规律递归

第i个等于先将第i-1个正写两边,再反写一边,再正写一边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdio.h>
#include <math.h>
void f(int n, int s, int t)
{
if(n==2)
{
if(t==1) {
if(s==1)
printf("CC");
else printf("PC");
}
else {
if(s==1)
printf("PP");
else printf("CP");
}
return ;
}
int x=s%(n/2);
if(x==0)
x=n/2;
if(t==1)
{
if(s>n*1.0/2)
f(n/2, x, 0);
else f(n/2, x, 1);
f(n/2, x, 1);
}
else if(t==0){
if(s>n*1.0/2)
f(n/2, x, 1);
else f(n/2, x, 0);
f(n/2, x, 0);
}
}
int main()
{
int t, n;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
n=pow(2, n);
for(int i=1; i<=n; i++) {
f(n, i, 1);
printf("\n");
}
}
return 0;
}

 

1008 Fishing Master

 

贪心+优先队列

首先,若当前手里的鱼数量大于0时,可以不去捕鱼,我们先用煮一条鱼时间中捕鱼时间的整数倍时间出去捕鱼,当所有整数时间都被用完了,而总的捕鱼数小于n时,说明鱼不够了,必须用零碎的时间捕鱼,也就是说此时必须让锅或者人干等着了,对于每一条鱼,优先队列中存入它对捕鱼时间的模,即它提供的零碎时间,每次取出最长的零碎时间,这样可以使干等着的时间最短。

比赛时候有点乱,一边更新整数时间,一边压入零碎时间,实际上把煮鱼时间排完序之后,整数时间只能是前几条鱼提供,到后面的鱼只能提供零碎时间,而一定是不需要考虑在煮前几条鱼时用零碎时间捕鱼的,那么可以先把所有整数时间一次性更新完,接着只考虑用零碎时间捕鱼。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<set>
#include<iterator>
#include<queue>
#include<fstream>
#include<random>
using namespace std;
#define ll long long
const int maxn = 1e5 + 100;
int T;
int a[maxn];
bool cmp(int a, int b) {
return a > b;
}
bool vis[maxn];
int main() {
scanf("%d",&T);
while (T--) {
memset(vis, 0, sizeof(vis));
ll ans = 0;
int cnt = 0;
int n, k;
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
ans += a[i];
}
sort(a + 1, a + n + 1, cmp);
ans += k;
cnt = 1;
priority_queue<int>q;
cnt += a[1] / k;
q.push(a[1] % k);
vis[1] = 1;
int now = 1;
while (cnt < n) {
int tmp = cnt;
for (int i = now; i <= cnt&&i<=n; i++) {
if (vis[i])continue;
cnt += (a[i] / k);
q.push(a[i] % k);
vis[i] = 1;
}
now = tmp;
if (cnt >= n)break;
int tp = q.top();
ans += (k - tp);
q.pop();
cnt++;
}
printf("%lld\n", ans);
}
return 0;
}