#include <bits/stdc++.h> using namespace std; /* Head ends here */ void median(vector<char> s,vector<int> X) { multiset<ll> st1,st2; for(int i=0;i<X.size();i++){ if(s[i]=='a'){ if(st1.size()==0){ st1.insert(X[i]); }el...

#include <bits/stdc++.h> using namespace std; long int mod=1000000007 ; int main(){ int n;cin>>n; multiset<int> set1; int arr[n]; for(int i=0;i<n;i++){ cin>>arr[i]; set1.insert(arr[i]); } multiset<int> set2=set1;//拷贝一个集合 i...

解析 题目要求在满足子树装饰物数量的情况下，求花费时间的最小值，首先用邻接表存下各根节点的子节点，dfs遍历树，用一个数组吧维护每个子树的每个节点中花费时间最少的那个，dfs返回子树已有的装饰物数，若小于更节点则更新，并加入答案 #include<bits/stdc++.h> using namespace std; const int N=100010; int p[N],c[N],t[N],m[N]; vector<int> s[N]; long long ans=0; long long dfs(int x){ // if(!s[x].size()){//...

解析 由于本题数据量较小，考虑直接用dfs解决，根据题意可得，若要把矩形切n-1次使之体积相等的块，考虑对每个x/n与y/n 进行枚举，dfs返回当前的矩形的最小的最大边长比即可 #include <bits/stdc++.h> #define inf 1000000007 #define eps 0.000001 using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn=100005; double seg=0; double dfs(double x,d...

题意描述 给定一个数组arr,对数组a[id[i]]进行q次更新为val，每次统计数组中连续子数组（不一定连续）的最少数量seq[i]，在询问结束后结束后，输出sigma（i*seq[i]); 连续子子数组定义为： 解析 先用set计算出现有最少连续子序列的数量count；对于每次更新，相应判断count的值，即可，详见代码 #include <bits/stdc++.h> using namespace std; long int mod=1000000007 ; int main(){ int n;cin>>n; multiset<int...

题意描述 对一棵树，给出每条edge的颜色（红或黑），从树中取三个节点，定义若三个节点每两两之间的路径中都有红色的edge，则该取法为一种有效取法，求总共有多少种取法。 解析 本题的做法是对于，每对用黑色相连的节点用并查集维护，形成多组仅用黑色相连节点集合，在任意三组中各取一个节点即为有效取法，求和即可。 此题中一个值得注意的点是，若直接用三重循环枚举，或是稍微优化用一个前缀和数组，复杂度都大于 O(n^2),所以我们从反面入手，求可能性总和，并排除掉三个点在有两个或三个在同一集合的情况，复杂度降到O(n)。 #include <cmath> #include <cstd...

记录一下错误点 #include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int fa[102000]; int sz[102000]; int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); } void merge(int x,int y){ int py=find(y),px=find(x);...

解析 用结构体记录每个空格的位置，把已填过的空格数量作为搜索的深度，处理宫的时候可以打表进行坐标到宫的编号的转换，dfs即可 代码 #include<bits/stdc++.h> using namespace std; struct ty{ int x,y; }space[90]; int mp[12][12]; int h[12][12],l[12][12],gong[12][12]; int cnt=0; const int g[10][10]={{0,0,0,0,0,0,0,0,0,0}, {0,1,1,1,2,2,2,3,...

题目链接：https://ac.nowcoder.com/acm/problem/51097 题意描述 输入给出了多组区间[xi,yi]中数字1的数量的奇偶性，要求我们根据已有的条件判断该下一数据是否能成立，若能成立则将其纳入条件，反之输出该条件的编号。 解析 对于已有条件我们可以这样考虑，将区间[xi,yi]中数字1的数量的奇偶性转换为区间[0,xi-1]与区间[xi,yi]中数字1的奇偶性是否相同。 开一个unordered_map维护一个并查集，并查集分为两部分，一部分为奇数个1的前缀和，另一部分为偶数个1前缀和，由于从第一组数据开始就形成两种可能性，分别形成两组集合，若某组区间两前缀和...

#include<bits/stdc++.h> using namespace std; int a[100010]; queue<pair<int,int>> q; int main(){     int t;cin>>t;     while(t--){         int n;cin>>n;         for(int i=1;i<=n;i++){             scanf("%d ",&a[i]);         }         int maxn=-1,l=-1,r=-...