A. Static Query on Tree
题意：
给定一棵树，1是根节点，所有结点都可以到根节点。每次询问给定三个点集 A , B , C A,B,C A,B,C ，询问从 A A A内点到 C C C中点，从 B B B中点到 C C C中点，经过相同点的数目
解析：
对点集 C C C 中的点 u u u ，树上能够到 u u u 的点一定在 u u u 的子树内。对点集 A A A 中的点 u u u， u u u 能够到达的点为 r o o t root root 到 u u u 路径上的点，集合 B B B 同理。
树链剖分将树上问题转化成区间问题。对于给定的点集 A A A ，求出根节点 r o o t root root 到所有点的路径，然后将区间合并求并集。集合 B B B 同理。对于集合 C C C ,求出集合 C C C 中点的所有子树，然后将区间合并。最后求三个区间的交集。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
typedef pair<int, int> pii;
int head[maxn], tot;
struct edge{
int to, nxt;
}e[maxn<<1];
void add(int a, int b){
e[++tot].nxt = head[a];
e[tot].to = b;
head[a] = tot;
}
int siz[maxn], dep[maxn], son[maxn], fa[maxn];
int dfn[maxn], top[maxn], cnt;
vector<pii> a, b, c;
void dfs(int u, int p){
fa[u] = p;
dep[u] = dep[p]+1;
siz[u] = 1;
for(int i = head[u]; i; i = e[i].nxt){
int to = e[i].to;
if(to == p)
continue;
dfs(to, u);
siz[u] += siz[to];
if(siz[son[u]] < siz[to])
son[u] = to;
}
}
void dfs2(int u, int t){
dfn[u] = ++cnt;
top[u] = t;
if(!son[u])
return ;
dfs2(son[u], t);
for(int i = head[u]; i; i = e[i].nxt){
int to = e[i].to;
if(to == son[u] || to == fa[u])
continue;
dfs2(to, to);
}
}
void query_path(int u, int v, vector<pii> &s){
while(top[u] != top[v]){
if(dep[top[u]] < dep[top[v]]) swap(u, v);
s.push_back({dfn[top[u]], dfn[u]});
u = fa[top[u]];
}
if(dep[u] < dep[v])
swap(u, v);
s.push_back({dfn[v], dfn[u]});
}
void merge(vector<pii> &segs) {
if (segs.empty()) return;
vector<pii> res;
sort(segs.begin(), segs.end());
int st = segs[0].first, ed = segs[0].second;
for(int i = 0; i < segs.size(); i++){
if (segs[i].first > ed) {
res.push_back({st, ed});
st = segs[i].first, ed = segs[i].second;
}
else ed = max(ed, segs[i].second);
}
res.push_back({st, ed});
segs = res;
}
vector<pii> intersection(vector<pii> a, vector<pii> b) {
vector<pii> res;
int i = 0, j = 0;
while (i < a.size() && j < b.size()) {
int l = max(a[i].first, b[j].first);
int r = min(a[i].second, b[j].second);
if (l <= r) res.push_back({l, r});
if (a[i].second < b[j].second) i++;
else j++;
}
return res;
}
int n, q;
void solve(){
cin >> n >> q;
tot = cnt = 0;
for(int i = 0; i <= n; i++){
head[i] = son[i] = 0;
}
for(int i = 2, x; i <= n; i++){
cin >> x;
add(i, x);
add(x, i);
}
dfs(1, 0);
dfs2(1, 1);
for(int i = 1; i <= q; i++){
int x, y, z, u;
a.clear(), b.clear(), c.clear();
cin >> x >> y >> z;
while(x--){
cin >> u;
query_path(1, u, a);
}
while(y--){
cin >> u;
query_path(1, u, b);
}
while(z--){
cin >> u;
c.push_back({dfn[u], dfn[u]+siz[u]-1});
}
merge(a), merge(b), merge(c);
a = intersection(a, b);
a = intersection(a, c);
int ans = 0;
for(int i = 0; i < a.size(); i++){
ans += a[i].second-a[i].first+1;
}
//cout << "ans = " << ans << endl;
cout << ans << endl;
}
return ;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
int T;
cin >> T;
while(T--)
solve();
return 0;
}
B. C++ to Python
解析：
签到。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3+10;
char s[maxn];
void solve(){
memset(s, 0, sizeof(s));
scanf("%s", s+1);
int len = strlen(s+1);
for(int i = 1; i <= len; i++){
if((s[i]>='0'&&s[i]<='9') || s[i] == '-'|| s[i]=='(' || s[i] == ')' || s[i] == ',')
printf("%c", s[i]);
}
printf("\n");
}
int main(){
int T;
cin >> T;
while(T--)
solve();
return 0;
}
C. Copy
题意：
复制一段区间，插入到原区间的后面，询问第 x x x 位的异或和
解析：
假设复制的区间是 [ l , r ] [l,r] [l,r]，对于以后的询问 x > r x > r x>r，相当于询问复制之前位置 x − ( r − l + 1 ) x-(r-l+1) x−(r−l+1)的值。如果正向处理询问和修改，每次修改都会影响之后的询问。考虑离线，从后向前操作。
本题询问的是异或和，每个位置对答案的贡献只能有一次，如果查询同一个位置两次则会抵消。利用bitset进行优化，用bitset记录询问的位置。
对于询问位置 x x x，将对应位置取反；对于复制操作 [ l , r ] [l,r] [l,r]，对 [ 1 , r ] [1,r] [1,r]位置没有影响，对于 x > r x > r x>r时，询问相当于是 x − ( r − l + 1 ) x-(r-l+1) x−(r−l+1)位置，对bitset进行右移。
#include<iostream>
#include<bitset>
using namespace std;
const int maxn = 1e5+10;
const int N = 1E5+10;
bitset<maxn> f, high, low, s;
int n, m;
int a[maxn];
int q[maxn][3];
void solve(){
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> a[i];
int x, y, z;
for(int i = 1 ; i <= m ; i ++ ) {
cin >> q[i][0];
if(q[i][0] == 1)
cin >> q[i][1] >> q[i][2];
else
cin >> q[i][1];
}
f.reset();
for(int i = m; i >= 1; i--){
if(q[i][0] == 1){//修改
int l = q[i][1], r = q[i][2];
s = s.set() >> (maxn-r-1);
low = f & s;
s = s.set() << (r+1);
high = f & s;
f = low ^ (high >> (r-l+1));
}
if(q[i][0] == 2){
int x = q[i][1];
f[x] = !f[x];
}
}
int res = 0;
for(int i = 1; i <= n; i++){
if(f[i])
res ^= a[i];
}
cout << res << endl;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
int T;
cin >> T;
while(T--)
solve();
}
G. Snatch Groceries
题意：
给定一些区间，区间相交之前有多少不相交的区间
解析：
左端点从小到大排序，遍历一遍，如果冲突直接结束遍历。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
struct node{
int l, r;
bool operator < (const node &b) const{
if(l == b.l)
return r < b.r;
else
return l < b.l;
}
}a[maxn];
int n, ans;
void solve(){
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i].l >> a[i].r;
sort(a, a+1+n);
ans = 0;
int nowl = a[1].l, nowr = a[1].r;
for(int i = 2; i <= n; i++){
if(a[i].l <= nowr)
break;
else{
ans++;
nowr = a[i].r;
}
}
if(ans == n-1)
ans++;
cout << ans << endl;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
int T;
cin >> T;
while(T--)
solve();
}
I. ShuanQ
解析：
P Q ≡ 1 ( m o d M ) PQ \equiv1 (modM) PQ≡1(modM) 可得 P Q − 1 = k M PQ-1 = kM PQ−1=kM
对 P Q − 1 PQ-1 PQ−1质因数分解，找到最大的质因数，判断是否大于加密之后的数，然后计算加密前的数。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p, q, r;
ll find(ll p, ll q){
ll num = q*p-1;
for(int i = 2; i <= sqrt(num); i++){
if(num % i == 0)
while(num % i == 0)
num /= i;
}
if(num > 1)
return num;
else
return 0;
}
void solve(){
cin >> p >> q >> r;
ll m = find(q, p);
if(!m){
cout << "shuanQ" << endl;
return;
}
if(m <= r){
cout << "shuanQ" << endl;
return;
}
ll ans = q*r%m;
cout << ans << endl;
return;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
int T;
cin >> T;
while(T--)
solve();
}
K. DOS Card
题意：
询问一段区间 [ l , r ] [l,r] [l,r]，选择4个位置， l ≤ i < j < k < s ≤ r l \le i < j < k < s \le r l≤i<j<k<s≤r，两两配对，计算两个配对的最大值。每个配对 ( i , j ) (i,j) (i,j)的值为 ( a [ i ] + a [ j ] ) × ( a [ i ] − a [ j ] ) , ( i < j ) (a[i]+a[j]) \times (a[i]-a[j]),(i<j) (a[i]+a[j])×(a[i]−a[j]),(i<j)
解析：
平方差。用线段树维护，对于4个位置，匹配的情况有两种，“+ + - -” 和 “+ - + -”，每种情况的极值可以由数量更少的极值转移得到。枚举一下，用线段树维护多个值。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
const ll INF = 0X3F3F3F3F3F3F3F3F;
inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}
ll max(ll a, ll b){return a > b ? a : b;}
ll min(ll a, ll b){return a < b ? a : b;}
ll a[maxn];
int n, m;
struct tree{
int l, r;
ll ans1, ans2; // ++-- +-+-
ll a, b; // + -
ll c, d, e, f; // ++ +- -+ --
ll g, h, i, j; // ++1 +-- +-+ -+-
void init(int l, int r){
this->l = l; this->r = r;
ans1 = ans2 = a = b = c = d = e = f = g = h = i = j = -INF;
}
}t[maxn << 2];
void pushup(tree &k, tree ls, tree rs){
k.ans1 = max(ls.ans1, rs.ans1);
k.ans2 = max(ls.ans2, rs.ans2);
k.a = max(ls.a, rs.a);
k.b = max(ls.b, rs.b);
k.c = max(ls.c, rs.c);
k.d = max(ls.d, rs.d);
k.e = max(ls.e, rs.e);
k.f = max(ls.f, rs.f);
k.g = max(ls.g, rs.g);
k.h = max(ls.h, rs.h);
k.i = max(ls.i, rs.i);
k.j = max(ls.j, rs.j);
k.ans1 = max(k.ans1, ls.a + rs.g);
k.ans1 = max(k.ans1, ls.c + rs.f);
k.ans1 = max(k.ans1, ls.h + rs.b);
k.ans2 = max(k.ans2, ls.a + rs.j);
k.ans2 = max(k.ans2, ls.d + rs.d);
k.ans2 = max(k.ans2, ls.i + rs.b);
k.c = max(k.c, ls.a + rs.a);
k.d = max(k.d, ls.a + rs.b);
k.e = max(k.e, ls.b + rs.a);
k.f = max(k.f, ls.b + rs.b);
k.g = max(k.g, ls.a + rs.f);
k.g = max(k.g, ls.d + rs.b);
k.h = max(k.h, ls.a + rs.d);
k.h = max(k.h, ls.c + rs.b);
k.i = max(k.i, ls.a + rs.e);
k.i = max(k.i, ls.d + rs.a);
k.j = max(k.j, ls.b + rs.d);
k.j = max(k.j, ls.e + rs.b);
}
void pushup(int k){
pushup(t[k], t[ls(k)], t[rs(k)]);
}
void build(int k, int l, int r){
t[k].init(l, r);
if(l == r){
t[k].a = a[l];
t[k].b = -a[l];
return;
}
int mid = (l+r) >> 1;
build(ls(k), l, mid);
build(rs(k), mid+1, r);
pushup(k);
}
tree query(int k, int x, int y){
if(x <= t[k].l && y >= t[k].r)
return t[k];
int mid = t[k].l + t[k].r >> 1;
if(y <= mid)
return query(ls(k), x, y);
if(x > mid)
return query(rs(k), x, y);
tree res;
res.init(0, 0);
pushup(res, query(ls(k), x, y), query(rs(k), x, y));
return res;
}
void solve(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> a[i];
a[i] *= a[i];
}
build(1, 1, n);
for(int i = 1, l, r; i <= m; i++){
cin >> l >> r;
tree ans = query(1, l, r);
cout << max(ans.ans1, ans.ans2) << endl;
}
return;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
int T = 1;
cin >> T;
while(T--)
solve();
return 0;
}
L. Luxury cruise ship
题意：
体积为 7，31，365的三个物品，询问装满体积为m的背包的最少物品数
解析：
贪心。尽可能装365，剩下的装31和7，如果装不满，少装1个365，然后装31和7。可以证明，解一定存在（参考小凯的疑惑）。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll a, b, c;
ll n, res;
int f(ll &a, ll &b, int x){
b = x/31;
int rem = x-b*31;
a = 0;
a += rem/7;
rem %= 7;
if(rem == 0){
return 1;
}
if(b - (rem*2)%7 < 0)
return 0;
else{
b -= (rem*2)%7;
a += (((rem*2)%7)*31 + rem)/7;
return 1;
}
}
void solve(){
cin >> n;
c = n/365;
ll rem = n-c*365;
ll ans = INF;
if(f(a, b, rem))
ans = min(ans, a+b+c);
if(c >= 1 && f(a, b, rem+365))
ans = min(ans, a+b+c-1);
if(ans == INF)
cout << -1 << endl;
else
cout << ans << endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while(T--)
solve();
return 0;
}
本文含有隐藏内容，请 开通VIP 后查看