翻车了
1005
没什么好说的，并查集维护就行
void solve(){int n;cin>>n;map<int,bool>vis;vector<int>a(n+1);for(int i=1;i<=n;i++){cin>>a[i];vis[i]=true;}vector<int>fa(n+1);iota(fa.begin(),fa.end(),0);auto find=[&](int x)->int{while(x!=fa[x]){x=fa[x]=fa[fa[x]];}return x;};auto merge=[&](int x,int y)->void{x=find(x),y=find(y);if(x!=y){fa[x]=y;}};for(int i=1;i<=n;i++){int x=i-a[i],y=i+a[i];if(vis[x])merge(x,i);if(vis[y])merge(y,i);}vector<int>ans;for(int i=1;i<=n;i++){if(find(i)==i){ans.push_back(i);}}cout<<ans.size()-1<<endl;
}
1010
假设配送站的位置为\((a,b)\)，那么以\((a,b)\)为原点作坐标系，客户的位置\((x,y)\)在每个象限的情况都考虑下，推出每种情况曼哈顿距离的表达式(去掉绝对值)。发现只用维护全局\(max(x+y),max(x-y),max(y-x),min(x+y)\)。这个维护输入的时候就能预处理出来。然后枚举所有的配送站位置，对每一个配送站位置计算四个象限的曼哈顿距离，求出最大值，再用最大值更新最后的答案(要求最大值最小，就是取所有最大值中的最小值)。详细见代码：
void solve(){int n,m;cin>>n>>m;int s1=-INF,s2=INF,s3=-INF,s4=-INF;for(int i=1;i<=n;i++){int x,y;cin>>x>>y;s1=max(s1,x+y);s2=min(s2,x+y);s3=max(s3,x-y);s4=max(s4,y-x);} vector<int>a(m+1),b(m+1);for(int i=1;i<=m;i++){cin>>a[i]>>b[i];}int ans=INF;for(int i=1;i<=m;i++){int r1=s1-(a[i]+b[i]);int r2=a[i]+b[i]-s2;int r3=b[i]-a[i]+s3;int r4=a[i]-b[i]+s4;int tep=max({r1,r2,r3,r4});ans=min(ans,tep);}cout<<ans<<endl;
}
1009
这个题是atcode中的原，abc395的D题。我们考虑维护三个信息\(a[i]\)表示人所在的位置，\(b[i]\)表示部落所在的位置,\(c[i]\)表示位置\(i\)上的部落的编号。对于操作2,相当于把人x所在的位置改成部落y的位置；对于操作3，相当于交换壳子，即我们不交换部落中具体的人。假设部落1所在的位置为\(ip1\),部落2所在的位置为\(ip2\),那么就有\(c[ip1]\)=部落1，\(c[ip2]\)=部落2，我们交换部落这个壳子，让\(c[ip1]\)=部落2，\(c[ip2]\)=部落1，那么原本在\(ip1\)位置上的所有人所在的部落就改成了部落2，实现了交换；对于操作4，查询人在的部落，就是查询人在的位置上的部落编号。
以上思路是\(abc395\)的解法，这道题中多了一个操作1：a 部落与 b部落结盟。结盟操作使部落合并，新部落的编号是a。两个部落结盟，那么两个部落肯定共享一个位置，直接用并查集维护，实现共享位置；新部落的编号是a，那我就找部落所在位置的根节点，然后把这个位置上的部落编号改成a就行了。查询的时候查人在的位置上的部落编号，人的位置须是根节点的位置。有点乱了，详细见代码。
struct DSU{vector<int>fa,siz;DSU(int _n):fa(_n+1,0),siz(_n+1,1){iota(fa.begin(),fa.end(),0);} int find(int x){while(x!=fa[x])x=fa[x]=fa[fa[x]];return x;}void merge(int x,int y){x=find(x),y=find(y);if(x!=y){fa[x]=y;siz[y]+=siz[x];}}
};
void solve(){int n,q;cin>>n>>q;vector<int>a(n+1);//维护人所在的位置vector<int>b(n+1);//维护部落所在的位置vector<int>c(n+1);//维护位置上的部落编号for(int i=1;i<=n;i++){a[i]=b[i]=c[i]=i;}DSU dsu(n+1);while(q--){int opt;cin>>opt;if(opt==1){int x,y;cin>>x>>y;dsu.merge(b[x],b[y]);int r=dsu.find(b[x]);c[r]=x;b[x]=b[y]=r;}else if(opt==2){int x,y;cin>>x>>y;a[x]=b[y];}else if(opt==3){int x,y;cin>>x>>y;int ip1=b[x],ip2=b[y];c[ip1]=y,c[ip2]=x;swap(b[x],b[y]);}else{int x;cin>>x;cout<<c[dsu.find(a[x])]<<endl;}}}
1003
我要补一下优先队列了，不然迟早被创死。
初始时，针对每个能力维度建立小根堆，按该维度的要求值升序排列所有公司，确保优先处理最低门槛的面试机会。每次循环遍历所有维度，从堆顶依次取出当前能力可满足的公司，并累计其已通过的维度数；当某公司所有维度均达标时，立即将其加入处理队列，同步提升各维度能力值，触发新一轮的解锁检查——此时其他公司可能因能力提升而满足新的维度要求。此过程通过多轮迭代不断“解锁”可达标的公司，直至某轮循环中无新增公司可处理为止，最终通过已处理公司总数是否等于总数量判断可行性。该策略通过贪心选择最小要求的公司优先处理，并实时更新能力状态，确保了最优的解锁顺序和全局正确性。
using T2=tuple<int,int>;
using pq=priority_queue<T2,vector<T2>,greater<>>;void solve(){int n,m;cin>>n>>m;vector<int>a(m+1);for(int i=1;i<=m;i++){cin>>a[i];}vector c(n+1,vector<int>(m+1));vector w(n+1,vector<int>(m+1));vector<pq>q(m+1);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>c[i][j];q[j].emplace(c[i][j],i);}for(int j=1;j<=m;j++){cin>>w[i][j];}}vector<int>cnt(n+1,0);int ans=0;while(true){bool flag=false;for(int j=1;j<=m;j++){while(!q[j].empty()){auto[x,y]=q[j].top();if(x>a[j]){break;}flag=true;q[j].pop();cnt[y]++;if(cnt[y]==m){for(int k=1;k<=m;k++){a[k]+=w[y][k];}ans++;}}}if(!flag) break;}if(ans==n){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
}
1007
可持久化trie的纯板子题，那个公式等价于\(a_{i}异或x\)。然后可持久化就行。学可持久化trie的第一道例题就是这个QwQ
const int N = 2e5+10;int trie[N * 33][2], rt[N], id[N*33], idx;void insert(int num, int k) {rt[k] = ++idx;id[idx] = k;int x = rt[k - 1], y = rt[k];for (int i = 31; i >= 0; i--) {int j = num >> i & 1;trie[y][!j] = trie[x][!j];trie[y][j] = ++idx;id[idx] = k;x = trie[x][j], y = trie[y][j];}
}
int query(int l, int r, int num) {int p = rt[r], ans = 0;for (int i = 31; i >= 0; i--) {int j = num >> i & 1;if (trie[p][!j]) {if (l <= id[trie[p][!j]] && id[trie[p][!j]] <= r) {ans += 1 << i;p = trie[p][!j];} else {p = trie[p][j];}} else {p = trie[p][j];}}return ans;
}void solve() {int n, q;cin >> n >> q;for (int i = 1; i <= n; i++) {int x;cin >> x;insert(x, i);}while (q--) {int l, r, num;cin >> l >> r >> num;cout << query(l, r, num) << endl;}memset(rt, 0, sizeof(rt));memset(trie, 0, sizeof(trie));idx = 0;
}