2022杭电多校（二）

一、比赛小结

比赛链接：Problems (hdu.edu.cn)

二、题目分析及解法（基础题）

1001、Static Query on Tree

题目链接：Problem - 7150 (hdu.edu.cn)

题意：

有一棵有向树，所有节点均可到达根节点，然后给出三个集合，$A、B、C$ ，对于集合中的元素进行染色，具体地，是向元素的子树进行染色，最后问这棵树上同时染三种色的节点有多少个

题解：

很直接的一道树剖，但在用线段树染色这个子问题上，比较麻烦，自己还不太会实现QWQ ，参考了一个大佬的博客：2022杭电多校第二场 A.Static Query on Tree（树剖）

代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
//#define int long long
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define yesno if(fg)yes;else no;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int inf=8e18;
const int maxn=2e5+100;
vector<int>g[maxn];
int a[maxn],b[maxn],c[maxn],son[maxn],siz[maxn],fa[maxn];
int dep[maxn],top[maxn],dfn[maxn],rk[maxn],clk,out[maxn];
template <typename T> inline void read(T& x)
{x=0;T f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x=x*f;return;
}
template <typename T,typename ...Arg>void read(T& x,Arg& ...arg)
{read(x);read(arg...);
}
template <typename T>inline void write(T x)
{if(x<0)putchar('-'),x=-x;if(x<10)putchar(x+'0');else write(x/10),putchar(x%10+'0');
}
template <typename T,typename ...Arg>void write(T& x,Arg& ...arg)
{write(x);putchar(' ');write(arg...);
}struct node
{int l,r;int sum;int s[8];int lazy;int lazy2;//清空标志
} t[maxn*4];
void dfs(int x,int f)
{fa[x]=f;dep[x]=dep[f]+1;siz[x]=1;son[x]=-1;for(auto it:g[x]){if(it==f)continue;dfs(it,x);siz[x]+=siz[it];if(son[x]==-1||siz[it]>siz[son[x]])son[x]=it;}
}
void dfs2(int x,int t)
{top[x]=t;dfn[x]=++clk;rk[clk]=x;if(son[x]==-1){out[x]=clk;return ;}dfs2(son[x],t);for(auto it:g[x]){if(it==fa[x])continue;if(it==son[x])continue;dfs2(it,it);}out[x]=clk;
}
void push_down(int k)
{if(t[k].l==t[k].r){t[k].lazy=0;t[k].lazy2=0;return ;}if(t[k].lazy2)//清空 {t[k<<1].lazy2=t[k<<1|1].lazy2=1;t[k<<1].lazy=t[k<<1|1].lazy=0;//notefor(int i=0; i<=7; i++){t[k<<1].s[i]=t[k<<1|1].s[i]=0;}t[k<<1].s[0]=t[k<<1].r-t[k<<1].l+1;t[k<<1|1].s[0]=t[k<<1|1].r-t[k<<1|1].l+1;t[k].lazy2=0;}if(t[k].lazy>0){for(int i=7; i>=0; i--){if((i|t[k].lazy)==i)continue;t[k<<1].s[i|t[k].lazy]+=t[k<<1].s[i];t[k<<1].s[i]=0;t[k<<1|1].s[i|t[k].lazy]+=t[k<<1|1].s[i];t[k<<1|1].s[i]=0;}t[k<<1].lazy|=t[k].lazy;t[k<<1|1].lazy|=t[k].lazy;t[k].lazy=0;}}
void push_up(int k)
{if(t[k].l!=t[k].r){for(int i=0; i<8; i++){t[k].s[i]=t[k<<1].s[i]+t[k<<1|1].s[i];}}
}void build(int l,int r,int k)
{t[k].l=l;t[k].r=r;t[k].sum=0;for(int i=0; i<8; i++)t[k].s[i]=0;t[k].s[0]=t[k].r-t[k].l+1;t[k].lazy=0;t[k].lazy2=0;if(l==r){return ;}int mid=(l+r)>>1;build(l,mid,k<<1);build(mid+1,r,k<<1|1);push_up(k);
}
void update(int l,int r,int k,int type,int val)
{if(r<t[k].l||l>t[k].r)return ;push_down(k);if(l<=t[k].l&&t[k].r<=r){if(val==1){t[k].lazy=type;for(int i=7; i>=0; i--){if((i|type)==i)continue;t[k].s[i|type]+=t[k].s[i];t[k].s[i]=0;}}else{t[k].lazy2=1;for(int i=0; i<8; i++)t[k].s[i]=0;t[k].s[0]=t[k].r-t[k].l+1;}push_down(k);return ;}update(l,r,k<<1,type,val);update(l,r,k<<1|1,type,val);push_up(k);
}int querysum(int l,int r,int k)
{if(r<t[k].l||l>t[k].r)return 0;push_down(k);if(l<=t[k].l&&t[k].r<=r){return t[k].s[7];}int ans=0;ans+=querysum(l,r,k<<1);ans+=querysum(l,r,k<<1|1);return ans;
}
int na,nb,nc;
int n,q;
signed main()
{int tt;read(tt);int cas=0;while(tt--){cas++;clk=0;read(n,q);for(int i=2; i<=n; i++){int x;read(x);g[x].pb(i);g[i].pb(x);}dfs(1,0);dfs2(1,0);build(1,n,1);while(q--){read(na,nb,nc);for(int i=1; i<=na; i++){read(a[i]);int x=1,y=a[i];while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]]) swap(x,y);update(dfn[top[x]],dfn[x],1,1,1);x=fa[top[x]];}if(dfn[x]<dfn[y]) swap(x,y);update(dfn[y],dfn[x],1,1,1);}for(int i=1; i<=nb; i++){read(b[i]);int x=1,y=b[i];while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]]) swap(x,y);update(dfn[top[x]],dfn[x],1,2,1);x=fa[top[x]];}if(dfn[x]<dfn[y]) swap(x,y);update(dfn[y],dfn[x],1,2,1);}for(int i=1; i<=nc; i++){read(c[i]);int x=c[i];update(dfn[x],out[x],1,4,1);}int ans=querysum(1,out[1],1);write(ans);printf("\n");update(1,out[1],1,1,-1);}build(1,n,1);for(int i=0; i<=n+2; i++){g[i].clear();a[i]=b[i]=c[i]=son[i]=siz[i]=fa[i]=0;dep[i]=top[i]=dfn[i]=rk[i]=clk=out[i]=0;}}
}

1002、C++ to Python

题目链接：Problem - 7151 (hdu.edu.cn)

题意：

给出一段 python 代码，将其翻译成 c++ 代码

题解：

无视其他杂余字符即可

代码：

#include <bits/stdc++.h>
using namespace std;
string s, ans;
bool judge(char c) {if (c == '-' || c == ',') return true;if (c == '(' || c == ')') return true;if ('0' <= c && c <= '9') return true;return false;
}
int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int _;cin >> _;while (_--) {cin >> s;int len = s.length();ans = "";for (int i = 0; i < len; i++)if (judge(s[i])) ans += s[i];cout << ans << endl;}return 0;
}

1003、Copy

题目链接：Problem - 7152 (hdu.edu.cn)

题意：

给出一串序列，和两种操作，一种是将序列中的一段区间复制粘贴到序列结尾，另一种是查询某个位置的元素的值，最后对这个值求个异或和

题解：

比赛时是暴力过的，标程还没暴力快。。。

标答是用离线+bitset暴力优化过的，考试时也没想到。关于思路来源，可以这么去分析，既然是离线，那先把这些东西给存起来，更容易优化起来。然后思考一下操作1对操作2的影响，若 $x\le r$ 那么不会产生影响，若 $x>r$ 那么相当于查询 $x-(r-l+1)$ 。于是我们从后往前分析，设dp是用来存储是否对相应位要进行异或的一个 bitset 。这样就把 $O(n)$ 的移位操作变成了 $O(1)$ 的bitset操作了。

其实做法也挺自然的，需要对 bitset 有较熟的操作。

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn];
bitset<maxn> dp, low, high;
array<int, 3> v[maxn];
int n, q;int main() {//   freopen("in.txt", "r", stdin);//   freopen("out.txt", "w", stdout);ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int _;cin >> _;while (_--) {cin >> n >> q;for (int i = 1; i <= n; i++) cin >> a[i];for (int i = 1; i <= q; i++) {cin >> v[i][0];if (v[i][0] == 1)cin >> v[i][1] >> v[i][2];elsecin >> v[i][1];}dp = 0;for (int i = 1; i >= 1; i--) {if (v[i][0] == 1) {int l = v[i][1], r = v[i][2];low = dp & (~bitset<maxn>(0) >> (maxn - r - 1));high = dp & (~bitset<maxn>(0) << (r + 1));dp = low ^ (high >> (r + 1 - l));} else {int x = v[i][1];dp[x] = !dp[x];}}int ans = 0;for (int i = 1; i <= n; i++)if (dp[i]) ans ^= a[i];cout << ans << endl;}return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n, q;
int a[maxn * 2];
int main() {// freopen("in.txt", "w", stdin);// freopen("out.txt", "w", stdout);ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int _;cin >> _;while (_--) {int ans = 0;cin >> n >> q;for (int i = 1; i <= n; i++) cin >> a[i];while (q--) {int op;cin >> op;if (op == 1) {int l, r;cin >> l >> r;int x = r - l + 1;for (int i = n; i >= r + 1; i--) a[i] = a[i - x];} else {int x;cin >> x;ans = ans ^ a[x];}}cout << ans << endl;}return 0;
}

1004、Keychains

题目链接：Problem - 7153 (hdu.edu.cn)

题意：

给出两个圆环，查询两个圆环是否互锁

题解：

思路还是很好想的，让一个圆环与另一个圆环所在平面求交点，对这两个交点分类讨论即可

代码：

#include <bits/stdc++.h>
using namespace std;typedef double lf;struct vec {lf x, y, z;vec() {}vec(lf x, lf y, lf z) : x(x), y(y), z(z) {}vec operator-(vec b) { return vec(x - b.x, y - b.y, z - b.z); }vec operator+(vec b) { return vec(x + b.x, y + b.y, z + b.z); }vec operator*(lf k) { return vec(k * x, k * y, k * z); }lf sqr() { return x * x + y * y + z * z; }lf len() { return sqrt(x * x + y * y + z * z); }vec trunc(lf k = 1) { return *this * (k / len()); }friend vec cross(vec a, vec b) {return vec(a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z,a.x * b.y - a.y * b.x);}friend lf dot(vec a, vec b) { return a.x * b.x + a.y * b.y + a.z * b.z; }void scan() { scanf("%lf%lf%lf", &x, &y, &z); }
};void inter_ff(vec p1, vec dir1, vec p2, vec dir2, vec &res1, vec &res2) {vec e = cross(dir1, dir2), v = cross(dir1, e);lf d = dot(dir2, v);if (abs(d) < 1e-9) return;vec q = p1 + v * (dot(dir2, p2 - p1) / d);res1 = q;res2 = q + e;
}lf dist_pp(vec p1, vec p2) { return (p2 - p1).len(); }lf dist_pl(vec p, vec l1, vec l2) {return cross(l2 - l1, p - l1).len() / (l2 - l1).len();
}vec perpendicular_pl(vec p, vec l1, vec l2) {return l1 + (l2 - l1) * (dot(l2 - l1, p - l1) / (l2 - l1).sqr());
}void solve() {vec p1, d1, p2, d2;lf r1, r2;p1.scan();d1.scan();scanf("%lf", &r1);p2.scan();d2.scan();scanf("%lf", &r2);vec dir = cross(d1, d2);if (dir.sqr() < 0.1) {puts("No");return;}vec l1, l2;inter_ff(p1, d1, p2, d2, l1, l2);lf dis = dist_pl(p2, l1, l2);if (dis > r2) {puts("No");return;}vec delta = (l2 - l1).trunc(sqrt(r2 * r2 - dis * dis));vec mid = perpendicular_pl(p2, l1, l2);vec a = mid + delta;vec b = mid - delta;if ((dist_pp(a, p1) < r1) ^ (dist_pp(b, p1) < r1)) {puts("Yes");} else {puts("No");}
}int main() {int T;scanf("%d", &T);while (T--) {solve();}return 0;
}

1007、Snatch Groceries

题目链接：Problem - 7156 (hdu.edu.cn)

题意：

阅读理解题，有 n 个人，每人有一个对应的时间区间，题目问，在区间重叠前有多少个区间。

题解：

sort 排个序，再对相邻两个区间进行比较即可。

代码：

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
const int maxn = 1e5 + 5;
int n;
pii b[maxn];
int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int _;cin >> _;while (_--) {int res = 0;cin >> n;for (int i = 1; i <= n; i++) cin >> b[i].first >> b[i].second;sort(b + 1, b + 1 + n);bool flag = true;for (int i = 1; i < n; i++)if (b[i].first < b[i + 1].first && b[i].second < b[i + 1].first)res++;else {flag = false;break;}if (flag) res++;cout << res << endl;}return 0;
}

1009、ShuanQ

题目链接：Problem - 7158 (hdu.edu.cn)

题意：

给出 p q d 三个数，p 和 q 是关于某个素数的逆元，并且这个素数大于 d 。问你是否可以唯一确定这个素数。

题解：

对 p*q-1 进行素因子分解即可

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e6 + 6;
int prime[maxn], pn;
bool isp[maxn];
void table() {memset(isp, true, sizeof(isp));isp[0] = isp[1] = false;for (int i = 2; i < maxn; i++) {if (isp[i]) prime[pn++] = i;for (int j = 0; j < pn; j++) {if (i * prime[j] > maxn) break;isp[i * prime[j]] = false;if (i % prime[j] == 0) break;}}
}
signed main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);table();int _;cin >> _;while (_--) {int p, q, d;cin >> p >> q >> d;int M = max(d, max(p, q));int N = p * q - 1ll;vector<int> res;res.clear();for (int i = 2ll; i * i <= N; i++)if (N % i == 0) {while (N % i == 0) N /= i;if (i > M) res.push_back(i);}if ((N != 1) && (N > M)) res.push_back(N);if (res.size() == 1ll)cout << d * q % res[0] << endl;elsecout << "shuanQ\n";}return 0;
}

1011、DOS Card

题目链接：Problem - 7160 (hdu.edu.cn)

题意：

给定一段序列，以及一些询问，查询区间 $[l,r]$ 内最大的 $a_u^2-a_v^2+a_x^2-a_y^2$

题解：

一对匹配的值 = 左 ∗ 左 − 右 ∗ 右

线段树上维护以下8个变量：

区间最大值

区间次大值

区间最小值

区间次小值

选了一对的最大值

选了两对的最大值

（一对的值 + 剩下的最大值）的最大值

（一对的值 − 剩下的最小值）的最大值

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>inline void MAX(T &x,T y){if(y>x)x=y;}
template<class T>inline void MIN(T &x,T y){if(y<x)x=y;}
template<class T>inline void rd(T &x){x=0;char o,f=1;while(o=getchar(),o<48)if(o==45)f=-f;do x=(x<<3)+(x<<1)+(o^48);while(o=getchar(),o>47);x*=f;
}
template<class T>inline void print(T x,bool op=1){static int top,stk[105];if(x<0)x=-x,putchar('-');if(x==0)putchar('0');while(x)stk[++top]=x%10,x/=10;while(top)putchar(stk[top--]+'0');putchar(op?'\n':' ');
}
const int M=1e5+5;
int cas,n,m,A[M];
struct node{int len;ll max1,max2,min1,min2,res1,res2,res1_max,res1_min;node(int len=0){this->len=len;max1=max2=-1e18;min1=min2=1e18;res1=res2=res1_max=res1_min=-1e18;}void update_max(ll v){if(v>max1)max2=max1,max1=v;else if(v>max2)max2=v;}void update_min(ll v){if(v<min1)min2=min1,min1=v;else if(v<min2)min2=v;}node operator +(const node &A)const{if(len==0)return A;if(A.len==0)return *this;node T(len+A.len);T.update_max(max1);T.update_max(max2);T.update_max(A.max1);T.update_max(A.max2);T.update_min(min1);T.update_min(min2);T.update_min(A.min1);T.update_min(A.min2);MAX(T.res2,res2);MAX(T.res2,A.res2);MAX(T.res2,res1+A.res1);MAX(T.res2,max1+max2-A.min1-A.min2);MAX(T.res2,res1_max-A.min1);MAX(T.res2,max1+A.res1_min);MAX(T.res1,res1);MAX(T.res1,A.res1);MAX(T.res1,max1-A.min1);MAX(T.res1_max,res1_max);MAX(T.res1_max,A.res1_max);MAX(T.res1_max,res1+A.max1);MAX(T.res1_max,A.res1+max1);if(A.len>=2)MAX(T.res1_max,max1-A.min1+A.max1);if(len>=2)MAX(T.res1_max,max1-A.min1+max2);MAX(T.res1_min,res1_min);MAX(T.res1_min,A.res1_min);MAX(T.res1_min,res1-A.min1);MAX(T.res1_min,A.res1-min1);if(A.len>=2)MAX(T.res1_min,max1-A.min1-A.min2);if(len>=2)MAX(T.res1_min,max1-A.min1-min1);return T;}
}tree[M<<2];
void build(int l=1,int r=n,int p=1){if(l==r){tree[p]=node(1);tree[p].max1=tree[p].min1=1ll*A[l]*A[l];return;}int mid=l+r>>1;build(l,mid,p<<1);build(mid+1,r,p<<1|1);tree[p]=tree[p<<1]+tree[p<<1|1];
}
node query(int a,int b,int l=1,int r=n,int p=1){if(l>b||r<a)return node(0);if(l>=a&&r<=b)return tree[p];int mid=l+r>>1;return query(a,b,l,mid,p<<1)+query(a,b,mid+1,r,p<<1|1);
}signed main(){
#ifndef ONLINE_JUDGE
//	freopen("jiedai.in","r",stdin);
//	freopen("jiedai.out","w",stdout);
#endifrd(cas);while(cas--){rd(n),rd(m);for(int i=1;i<=n;i++)rd(A[i]);build();while(m--){int l,r;rd(l),rd(r);print(query(l,r).res2);}}return (0-0);
}

1012、Luxury cruise ship

题目链接：Problem - 7161 (hdu.edu.cn)

题意：

给你一个 N ，对于方程 $7x_1+31x_2+365x_3=N,x\in \mathbb{N}$ ，求 $x_1+x_2+x_3$ 的最小值。

题解：

有点类似于《小凯的疑惑》这道题，对 ab+a+b 内的答案进行枚举即可

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 0x3f3f3f3f;
int n;
signed main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);int _;cin >> _;while (_--) {cin >> n;int x = 0, y = 0, z = 0;z = n / 365;n %= 365;bool flag = false;for (int i = n / 31; i >= 0; i--)if ((n - 31 * i) % 7 == 0) {y = i;x = (n - 31 * i) / 7;flag = true;break;}if (flag)cout << x + y + z << endl;else if (!flag && z == 0)cout << -1 << endl;else {z--;n += 365;for (int i = n / 31; i >= 0; i--)if ((n - 31 * i) % 7 == 0) {y = i;x = (n - 31 * i) / 7;break;}cout << x + y + z << endl;}}return 0;
}

三、题目分析及解法（进阶题）

不会做X

1005、Slayers Come

1006、Bowcraft

1008、Keyboard Warrior

1010、Assassination