建筑网站新闻写那些好,网站短信验证怎么做的,在百度上怎么发布广告,国外辣妹服装设计网站推荐2.15 1.聪明的质监员#xff08;二分前缀和#xff09; 2.村村通#xff08;并查集#xff09; 3.玉蟾宫(悬线法DP) 4.随机排列#xff08;树状数组逆序对问题#xff09; 5.增进感情#xff08;DFS#xff09;
6.医院设置#xff08;floyd#xff09;
聪明的质监员…2.15 1.聪明的质监员二分前缀和 2.村村通并查集 3.玉蟾宫(悬线法DP) 4.随机排列树状数组逆序对问题 5.增进感情DFS
6.医院设置floyd
聪明的质监员https://www.luogu.com.cn/problem/P1314 题目描述 小T 是一名质量监督员最近负责检验一批矿产的质量。这批矿产共有 n 个矿石从 11 到 n 逐一编号每个矿石都有自己的重量 wi 以及价值 vi 。检验矿产的流程是 给定m 个区间 [,][li,ri] 选出一个参数 W 对于一个区间 [,][li,ri]计算矿石在这个区间上的检验值 yi ∑[≥]×∑[≥]yijli∑ri[wj≥W]×jli∑ri[wj≥W]vj 其中 j 为矿石编号。 这批矿产的检验结果 y 为各个区间的检验值之和。即∑1i1∑myi 若这批矿产的检验结果与所给标准值 s 相差太多就需要再去检验另一批矿产。小T 不想费时间去检验另一批矿产所以他想通过调整参数 W 的值让检验结果尽可能的靠近标准值 s即使得 ∣−∣∣s−y∣ 最小。请你帮忙求出这个最小值。 输入格式 第一行包含三个整数 ,,n,m,s分别表示矿石的个数、区间的个数和标准值。 接下来的 n 行每行两个整数中间用空格隔开第 1i1 行表示 i 号矿石的重量 wi 和价值 vi。 接下来的 m 行表示区间每行两个整数中间用空格隔开第 1in1 行表示区间 [,][li,ri] 的两个端点 li 和 ri。注意不同区间可能重合或相互重叠。 输出格式 一个整数表示所求的最小值。 输入输出样例 输入 #1复制 5 3 15 1 5 2 5 3 5 4 5 5 5 1 5 2 4 3 3 输出 #1复制 10 说明/提示 【输入输出样例说明】 当 W 选 44 的时候三个区间上检验值分别为 20,5,020,5,0 这批矿产的检验结果为 2525此时与标准值 S 相差最小为 1010。 【数据范围】 对于 10%10% 的数据有 1≤,≤101≤n,m≤10 对于 30%30%的数据有 1≤,≤5001≤n,m≤500 对于 50%50% 的数据有 1≤,≤5,0001≤n,m≤5,000 对于 70%70% 的数据有 1≤,≤10,0001≤n,m≤10,000 对于 100%100% 的数据有 1≤,≤200,0001≤n,m≤200,0000,≤1060wi,vi≤1060≤10120s≤10121≤≤≤1≤li≤ri≤n 。 思路每次找的时候用前缀和存不然会TLE
#include bits/stdc.h
using namespace std;
#define lowbit(x) (x - (x))
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int N2e55;int n,m,s,min1INF,maxn,minnINF,sum,ans; //矿石区间标准值int w[N],v[N],l[N],r[N],pre_v[N],pre_n[N];bool check(int k){ans0,sum0;memset(pre_v,0,sizeof(pre_v));memset(pre_n,0,sizeof(pre_n));for (int i1;in;i){if (w[i]k){pre_v[i]pre_v[i-1]v[i];pre_n[i]pre_n[i-1]1;}else{pre_v[i]pre_v[i-1];pre_n[i]pre_n[i-1];}}for (int i1;im;i){ans(pre_n[r[i]]-pre_n[l[i]-1])*(pre_v[r[i]]-pre_v[l[i]-1]);}sumabs(ans-s);if (anss) return true;else return false;
}signed main(){cinnms;for (int i1;in;i){cinw[i]v[i];maxnmax(maxn,w[i]);minnmin(minn,w[i]);} for (int i1;im;i){cinl[i]r[i];}minnminn-1,maxnmaxn2;while (minnmaxn){int midminnmaxn1;if (check(mid)) minnmid1;else maxnmid-1;if (summin1) min1sum;}coutmin1;
}
村村通https://www.luogu.com.cn/problem/P1536 题目描述 某市调查城镇交通状况得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府 村村通工程 的目标是使全市任何两个城镇间都可以实现交通但不一定有直接的道路相连只要相互之间可达即可。请你计算出最少还需要建设多少条道路 输入格式 输入包含若干组测试数据每组测试数据的第一行给出两个用空格隔开的正整数分别是城镇数目 n 和道路数目 m 随后的 m 行对应 m 条道路每行给出一对用空格隔开的正整数分别是该条道路直接相连的两个城镇的编号。简单起见城镇从 11 到 n 编号。 注意两个城市间可以有多条道路相通。 在输入数据的最后为一行一个整数 00代表测试数据的结尾。 输出格式 对于每组数据对应一行一个整数。表示最少还需要建设的道路数目。 输入输出样例 输入 #1复制 4 2 1 3 4 3 3 3 1 2 1 3 2 3 5 2 1 2 3 5 999 0 0 输出 #1复制 1 0 2 998 说明/提示 数据规模与约定 对于 100%100% 的数据保证 1≤10001≤n1000 。 思路并查集把所有的关系都连接起来然后遍历所有情况找到没有连接的计数器自增
#include bits/stdc.h
using namespace std;
#define lowbit(x) (x - (x))
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int N2e55;int f[N],n,m,cnt,p;int find(int x){if (f[x]x) return x;else if (f[x]!x){f[x]find(f[x]);return f[x];}
}void merge(int i,int j){f[find(i)]find(j);
}signed main(){while (1){cnt0;cinn;if (n0) return 0;cinm;for (int i1;in;i) f[i]i;for (int i0;im;i){int a,b;pa;cinab;merge(a,b);}for (int i1;in;i){if (find(i)!find(p)){cnt;merge(i,p);}}coutcntendl;;}
}
玉蟾宫https://www.luogu.com.cn/problem/P4147 题目背景 有一天小猫 rainbow 和 freda 来到了湘西张家界的天门山玉蟾宫玉蟾宫宫主蓝兔盛情地款待了它们并赐予它们一片土地。 题目描述 这片土地被分成 ×N×M 个格子每个格子里写着 R 或者 FR 代表这块土地被赐予了 rainbowF 代表这块土地被赐予了 freda。 现在 freda 要在这里卖萌。。。它要找一块矩形土地要求这片土地都标着 F 并且面积最大。 但是 rainbow 和 freda 的 OI 水平都弱爆了找不出这块土地而蓝兔也想看 freda 卖萌她显然是不会编程的……所以它们决定如果你找到的土地面积为 S它们每人给你 S 两银子。 输入格式 第一行两个整数 NM表示矩形土地有 N 行 M 列。 接下来 N 行每行 M 个用空格隔开的字符 F 或 R描述了矩形土地。 输出格式 输出一个整数表示你能得到多少银子即 (3×最大 ’F’ 矩形土地面积3×最大 ’F’ 矩形土地面积) 的值。 输入输出样例 输入 #1复制 5 6 R F F F F F F F F F F F R R R F F F F F F F F F F F F F F F 输出 #1复制 45 说明/提示 对于 50%50% 的数据1≤,≤2001≤N,M≤200。 对于 100%100% 的数据1≤,≤10001≤N,M≤1000。 思路用悬线法写l数组存每个点向左最多可以到哪里r数组为右h数组存的是向上最多可以到哪里但是在找h数组的时候需要同时判断垂直的点lr数组的关系
#include bits/stdc.h
using namespace std;
#define lowbit(x) (x - (x))
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int N1010;int h[N][N],m,n,l[N][N],r[N][N];
char a[N][N];signed main(){cinnm;for (int i1;in;i){for (int j1;jm;j){cina[i][j];if (a[i][j]F)h[i][j]1;l[i][j]j;r[i][j]j;}}for (int i1;in;i){for (int j2;jm;j){if (a[i][j]F a[i][j-1]F){l[i][j]l[i][j-1];}}for (int jm-1;j1;--j){if (a[i][j]F a[i][j1]F){r[i][j]r[i][j1];}}}int ans0;for (int i1;in;i){for (int j1;jm;j){if (a[i][j]F a[i-1][j]F){h[i][j]h[i-1][j]1;l[i][j]max(l[i][j],l[i-1][j]);r[i][j]min(r[i][j],r[i-1][j]);}if (a[i][j]F)ansmax(ans,(r[i][j]-l[i][j]1)*h[i][j]);}}coutans*3;
}
随机排列https://www.acwing.com/problem/content/5469/ 给定一个 1∼n1∼ 的排列 a1,a2,…,an1,2,…,。 我们规定交换操作指从排列中随机选择两个不同元素并交换彼此位置。 给定两种打乱排列的方式 对排列连续进行 3n3 次交换操作。对排列连续进行 7n171 次交换操作。 已知给定排列 a1∼an1∼ 就是由 1,2,…,n1,2,…, 经过上述两种打乱方式之一得到的。 请你判断给定排列具体是由哪一种打乱方式得到的。 输入格式 第一行包含整数 n。 第二行包含 n 个整数 a1,a2,…,an1,2,…,。 输出格式 如果给定排列是由方式 11 打乱得到的则输出 11如果给定排列是由方式 22 打乱得到的则输出 22。 保证给定排列一定是由两种打乱方式之一得到的。 数据范围 前 33 个测试点满足 2≤n≤102≤≤10。 所有测试点满足 2≤n≤1062≤≤106保证 a1∼an1∼ 是一个 1∼n1∼ 的排列。 输入样例 5
2 4 5 1 3输出样例 1 思路本质上是找逆序数由于每次改变都会改变逆序数的奇偶性所以当前数组的逆序数个数的奇偶性与改变次数的奇偶性相同
#include iostream
#include cstring
#include algorithm
using namespace std;const int N 1e65;
int tr[N],w[N];int lowbit(int x){return x -x;
}void update(int x, int k){while(xN){tr[x]k;xlowbit(x);}
}int query(int x){int res0;while (x0){restr[x];x-lowbit(x);}return res;
}int main()
{int n;cinn;int res0;for (int i 0; i n; i ){int x;cinx;res(resquery(n)-query(x))%2;update(x,1);}if (res 3*n%2) cout1;else cout 2;
}
增进感情https://www.luogu.com.cn/problem/P2080 题目背景 小明和小红的感情是慢慢发展起来的。 题目描述 他们对对方分别有一个好感值。定义两人的亲密程度为两人的好感值之和。 如果他们的亲密程度达到 v则他们将走到一起。他们以后的生活将取决于两人的好感值之差的绝对值这个值越小他们的生活将越幸福。 现在他们对对方的好感值都为 00小明有 n 件事可以干每件事可以增加他对小红的好感 ai 点并且增加小红对他的好感 bi 点。可能为负数 小明可以任选一些事做请你帮小明求出怎样才能让他们的生活更加幸福求出两人在一起的前提下好感值之差的最小绝对值即可。 输入格式 第一行两个正整数 ,n,v。 之后 n 行每行两个空格隔开的整数 ,ai,bi。 输出格式 一行一个非负整数表示两人在一起的前提下好感值之差的最小绝对值。如果无论如何两人也无法在一起输出 -1。 输入输出样例 输入 #1复制 4 15 5 6 -1 8 7 2 1 0 输出 #1复制 3 说明/提示 数据范围与约定 对于 20%20% 数据保证 ≤10n≤10。 对于 100%100% 数据保证 1≤≤301≤n≤301≤∣∣,∣∣≤1001≤∣ai∣,∣bi∣≤100。 #include bits/stdc.h
using namespace std;
#define lowbit(x) (x - (x))
#define int long long
#define INF 0x3f3f3f3f3f3f3f3fconst int N35;int n,v,ansINF,l,r;
int a[N],b[N],vis[N];void dfs(int idx){if (lrv){ansmin(ans,abs(l-r));}if (idxn || ans0){return ;}for (int iidx;in;i){if (!vis[i]){vis[i]1;la[i],rb[i];dfs(i1);l-a[i],r-b[i];vis[i]0;}}
}signed main(){cinnv; //v是最大的好感度for (int i1;in;i){cina[i]b[i];} dfs(1);if (ansINF) cout-1;else coutans;
}
医院设置https://www.luogu.com.cn/problem/P1364 题目描述 设有一棵二叉树如图 其中圈中的数字表示结点中居民的人口。圈边上数字表示结点编号现在要求在某个结点上建立一个医院使所有居民所走的路程之和为最小同时约定相邻接点之间的距离为 11。如上图中若医院建在 11 处则距离和 4122×202×401364122×202×40136若医院建在 33 处则距离和 4×2132040814×213204081。 输入格式 第一行一个整数 n表示树的结点数。 接下来的 n 行每行描述了一个结点的状况包含三个整数 ,,w,u,v其中 w 为居民人口数u 为左链接为 00 表示无链接v 为右链接为 00 表示无链接。 输出格式 一个整数表示最小距离和。 输入输出样例 输入 #1复制 5 13 2 3 4 0 0 12 4 5 20 0 0 40 0 0 输出 #1复制 81 说明/提示 数据规模与约定 对于 100%100% 的数据保证 1≤≤1001≤n≤1000≤,≤0≤u,v≤n1≤≤1051≤w≤105。 思路n100数据量小可以用floyd算法找到最短路径然后根据权再遍历所有的点找到最适合的点
#include bits/stdc.h
using namespace std;
#define lowbit(x) (x - (x))
#define int long long
#define INF 0x3f3f3f3f3f3f3f3fconst int N105;int n,a[N][N],w[N];signed main(){cinn;for (int i1;in;i){for (int j1;jn;j){if (ij) a[i][j]0;else a[i][j]INF;}}for (int i1;in;i){int l,r;cinw[i]lr;if (l0) a[i][l]a[l][i]1;if (r0) a[i][r]a[r][i]1;}for (int k1;kn;k){for (int i1;in;i){for (int j1;jn;j){a[i][j]min(a[i][j],a[i][k]a[k][j]);}}}int sumINF;for (int i1;in;i){int cnt0;for (int j1;jn;j){cnta[i][j]*w[j]; }summin(sum,cnt);}coutsum;
}
