1001
簽到。輸出A&B，當（A&B == 0）時特判。
1002 HDU - 6703 array
因為給的數字是1-n的全排列，對于操作2，可以轉換為查詢區間[r+1,n]裡面第一個大于等于k的數字。（考慮到該區間可能沒有大于等于k的數字，可以在n+1位置插入數字n+1，就一定能查詢到了。是以每次查詢區間[r+1,n+1]第一個大于等于k的數字。）對于操作1，可以将加了1e7的數字放在一個set裡面，無論查詢的r給的是多少，答案都可以從set裡面的數字更新。（即lower_bound找到第一個大于等于k的數字）
這樣就隻剩下一個問題了，如何查詢區間第一個大于等于k的數字。可以考慮主席樹。因為對于操作1隻需要把更新的數字放入set是以就不需要更新主席樹。每次操作2，如果k小于等于左子樹最大值，則遞歸左子樹。找到答案則直接return，否則遞歸右子樹（這時候右子樹的所有值都大于k）。
ps：這題用cin關同步居然沒用，導緻我一度懷疑模闆有問題。
具體看代碼：
#include <bits/stdc++.h>
using namespace std;
#define sz(a) a.size()
#define all(x) (x).begin(), (x).end()
#define foo(i, s, e) for(int i=(s);i<=(e);i++)
#define fod(i, s, e) for(int i=(e);i>=(s);i--)
#define endl '\n'
#define debug(a) cout<<#a<<": "<<a<<'\n'
#define mod(x) (((x)%MOD+MOD)%MOD)
#define mem(a) memset((a),0,sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int maxn = 2e5 + 7;
int a[maxn], b[maxn], T[maxn];
int len = 0, tot;
struct node {
int L, R;
int sum;
} tree[maxn * 30];
int update(int root, int x, int l, int r) {
int newroot = ++tot;
tree[newroot] = tree[root]; tree[newroot].sum++;
if(l == r) return newroot; int mid = (l + r) / 2;
if(x <= mid) tree[newroot].L = update(tree[root].L, x, l, mid);
else tree[newroot].R = update(tree[root].R, x, mid + 1, r);
return newroot;
}
int sear(int left_root, int right_root, int l, int r, int k) {
if(tree[right_root].sum == tree[left_root].sum) return INF;
if(l == r) return l;
int ans = INF; int mid = (l + r) / 2;
if(k <= mid)
ans = sear(tree[left_root].L, tree[right_root].L, l, mid, k);
if(ans == INF)
ans = sear(tree[left_root].R, tree[right_root].R, mid + 1, r, k);
return ans;
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// ios::sync_with_stdio(false);
int Tx; scanf("%d", &Tx);
while(Tx--) {
tot = 0; int n, m; scanf("%d%d", &n, &m);
set<int> se; se.insert(n + 1);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
len = n + 1; T[0] = 0; tree[0].sum = tree[0].L = tree[0].R = 0;
for(int i = 1; i <= n; i++)
T[i] = update(T[i - 1], a[i], 1, len);
T[n + 1] = update(T[n], n + 1, 1, len);
int ans = 0;
while(m--) {
int op; scanf("%d", &op);
if(op == 1) {
int x; scanf("%d", &x);
x ^= ans;
se.insert(a[x]);
} else {
int r, k; scanf("%d%d", &r, &k);
r ^= ans, k ^= ans;
ans = *se.lower_bound(k);
ans = min(ans, sear(T[r], T[n + 1], 1, n + 1, k));
printf("%d\n", ans);
}
}
}
return 0;
}
1004 HDU - 6705 path
直接優先隊列+bfs，優先隊列按照路的權值從小到大排序，每次取出頭就是目前最小權值的路。
問題在于如何拓展才能不逾時超記憶體。首先将初始化每個點的出邊按照權值排序，将每個點最小權值出路放入優先隊列。在bfs時當你取出頭，如果将目前點的所有出邊全部放入有點隊列則肯定會超，考慮到我們隻需要目前最短的邊，而最短的邊隻有2種可能：
1.目前路擴充目前點最小的出邊
2.目前路的前一個節點x拓展到x的下一條邊（按權值大小排序了）。
所有優先隊列裡面需要儲存目前節點，前一個節點，目前的路長度，和最後邊在前一個節點的出邊的位置。
#include <bits/stdc++.h>
using namespace std;
#define sz(a) a.size()
#define all(x) (x).begin(), (x).end()
#define foo(i, s, e) for(int i=(s);i<=(e);i++)
#define fod(i, s, e) for(int i=(e);i>=(s);i--)
#define endl '\n'
#define debug(a) cout<<#a<<": "<<a<<'\n'
#define mod(x) (((x)%MOD+MOD)%MOD)
#define mem(a) memset((a),0,sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int maxn = 2e5 + 7;
struct node {
int x, y;
ll v;
int id;
node(int _x, int _y, ll _v, int _id) {
x = _x, y = _y, v = _v, id = _id;
}
friend bool operator <(node a, node b) {
return a.v > b.v;
}
};
struct path {
ll v; int y;
path(ll V, int Y) {
v = V; y = Y;
}
friend bool operator <(path a, path b) {
return a.v < b.v;
}
};
vector<path> dge[maxn];
ll ans[maxn]; int que[maxn];
priority_queue< node > pq;
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
ios::sync_with_stdio(false);
int T; cin >> T;
while(T--) {
int n, m, q; cin >> n >> m >> q;
int x, y; ll v;
for(int i = 1; i <= n; i++)
dge[i].clear();
while(!pq.empty()) pq.pop();
while(m--) {
cin >> x >> y >> v;
dge[x].push_back(path(v, y));
}
int maxk = 0;
for(int i = 1; i <= q; i++) {
cin >> que[i];
maxk = max(maxk, que[i]);
}
for(int i = 1; i <= n; i++) {
if(dge[i].size() >= 2)
sort(all(dge[i]));
}
for(int i = 1; i <= n; i++) {
if(dge[i].size() >= 1)
pq.push(node(i, dge[i][0].y, dge[i][0].v, 0));
}
int cntk = 0;
while(!pq.empty()) {
node now = pq.top(); pq.pop();
ans[++cntk] = now.v;
if(cntk == maxk) break;
if(now.id < dge[now.x].size() - 1)
pq.push(node(now.x, dge[now.x][now.id + 1].y, now.v - dge[now.x][now.id].v + dge[now.x][now.id + 1].v, now.id + 1));
if(dge[now.y].size() >= 1)
pq.push(node(now.y, dge[now.y][0].y, now.v + dge[now.y][0].v, 0));
}
for(int i = 1; i <= q; i++)
cout << ans[que[i]] << endl;
}
return 0;
}
1006
簽到，可以用棧，每次放入頭部，輸出時标記已經輸出過的不輸出。也可以用連結清單模拟。
1007
簽到題
1008
題解講的挺好。
#include <bits/stdc++.h>
using namespace std;
#define sz(a) a.size()
#define all(x) (x).begin(), (x).end()
#define foo(i, s, e) for(int i=(s);i<=(e);i++)
#define fod(i, s, e) for(int i=(e);i>=(s);i--)
#define endl '\n'
#define debug(a) cout<<#a<<": "<<a<<'\n'
#define mod(x) (((x)%MOD+MOD)%MOD)
#define mem(a) memset((a),0,sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int maxn = 2e5 + 7;
ll s[maxn];
vector<ll> ve;
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
ios::sync_with_stdio(false);
int T; cin >> T;
while(T--) {
int n; ll k; ve.clear();
cin >> n >> k;
ll sum1 = 0; ll ans = k; ll sum = 0;
for(int i = 1; i <= n; i++) {
cin >> s[i];
sum += s[i];
sum1 += s[i] / k;
if(s[i] % k != 0)
ve.push_back(k - s[i] % k);
}
if(sum1 >= n - 1)
ans += sum;
else {
int y = n - 1 - sum1;
sort(all(ve));
for(int i = 0; i < y; i++)
ans += ve[i];
ans += sum;
}
cout << ans << endl;
}
return 0;
}