wweiyiのblog

【解题报告】 BZOJ3032 七夕祭 题目：七夕祭（翻译过的） ps：话说今天是七夕节，我就正好做到七夕祭 解题思路： 看到这道题的题目，可以想到《均分纸牌》和我之前做的《货仓选址》两题，这样经过思考，演算和推理，我们可以得出，需要的最少步数是 ∑i=1M∣S[i]−s[k]∣\sum\limits_{i=1}^M\left|S[i]-s[k]\right| i=1∑M​∣S[i]−s[k]∣ 其中S是A的前缀和，即 S[i]=∑j=1iA[j]S[i]=\sum\limits_{j=1}^iA[j] S[i]=j=1∑i​A[j] 所以经过简单地编码，答案就出来了 AC代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>using namespace std;c...

【解题报告】 CH0501 货仓选址 题目：货仓选址 解题思路： 中位数 中位数是一种美好的数，在数学中经常使用，这道题建立一个数组，读入数据，然后排序一下，假设货仓建在x处，x左边有p个商家，x右边有q个商家，如果p<q,那么把货仓向右移一个位置，距离之和就变小，类似地，p>q，就把货仓向左移一个位置，所以建在中间的时候距离之和最小 AC代码 12345678910111213141516171819#include <iostream>#include <cstdio>#include <cmath>#include <algorithm>using namespace std;const int maxn=100005;int a[maxn],n,ans,pos;int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n); int pos=a[n/2+1]; fo...

【解题报告】 CF67C Cinema 题目：https://www.acwing.com/problem/content/105/ 解题思路： 排序+离散化 m部电影和n个人涉及2×m+n种语言。建立一个数组排序再离散化一下，用1到2×m+1之间的数来算。然后就暴力统计一下，就可以得出答案 AC代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <set>using namespace std;const int maxn=5*10e5;int n,m;int a[maxn];int p[maxn];int w[ma...

【解题报告】luogu P2078 朋友 题目：luogu P2078 题目思路： 并查集，C++ STL 有了C++stl容器，我们就high了，map可以处理数组下标为负的情况，然后男女朋友的关系的话，就分别统计每个公司有多少人有关系，取一个最小值就好了 AC代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include <iostream>#include <cstdio>#include <algorithm>#include <map> using namespace std;map<int,int>f;int n,m,p,q;int fm,fh;int max(int a,int b){ return a<b? a:b;} int get(int x){ return f[x]=(x==f[x]? x:get(f[x]));}void merge(...

【解题报告】 [HNOI2003]激光炸弹 题目：luogu P2280 在这样可爱的夜晚，调试题目恐怕是最爽的选择了 附：https://www.luogu.org/record/list?user=136889 在这么多次失败下我终于成功了 解题思路： 前缀和与拆分 这是一道简单题，但是我却调试了那么多次没调出来，竟然是循环的问题 rp–。。 建立一个二维数组，储存某个区域的目标的数量，然后就使用一个二维前缀和，就可以弄出来了，注意因为时间的原因，在输入的时候也就直接输入了，我那么多次就是因为超时 AC代码 1234567891011121314151617181920212223242526272829303132#include <iostream>using namespace std;const int maxn=5005;int r,n;int s[maxn][maxn];int ans;int x,y,w;int max(int a,int b){ return a>b? a:b;}int main(){ cin&g...

【解题报告】[NOI2002]银河英雄传说 题目：luogu P1196 题意简述 处理M个指令，都为两种如下形式的指令之一 1.M i j 表示让第i好战舰所在列的全部战舰保持原有顺序，接在第j好战舰所在列的尾部。 2.C i j，表示询问第i号战舰与第j号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。如果不在同一列中，输出-1； 解题思路 并查集 第二个指令我们要知道i，j两号战舰差多少，维护一个数列d即可，d[x]代表x前面的战舰数量,要查询的时候，我们只要知道i，j两号前面各有多少战舰，然后i前面的减去j前面的绝对值减一就可以了。 而第一个指令就是简单地处理一下size，记录集合大小，也很简单 AC代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include <iostream>#include <cstdio>using namespace std;int f[...

幂运算 众所周知，在NOIP系列竞赛中，会考到许多优化，而这些许多优化是由一个个简单的优化组件而来的，使整个程序的优化尽可能地达到最大，用最少的时间和空间来实现正确代码，而幂运算作为其中的一个基本我今天就来总结一下，如有不足，以后也会加勘误and Update。 幂 普遍数学上幂的意义是一个数做自乘的运算，如a的b次方意思是b个a相乘，使表示上更加简便 普通幂 C++中普通幂的代码很容易实现，这是实现代码(基本实现代码) 1234567891011#include <iostream>using namespace std;int main(){ int a,b; cin>>a>>b; for(int i=2;i<=b;i++) a*=a; cout<<a<<endl; return 0;} 快速幂 在普通幂中发现算很大的数的时候回非常地慢，我们就要想怎么优化，怎么优化呢，我们引入一组基本公式 ab=ab2∗ab2(b为偶数)a^b=a^{\frac{b}{2...

高级（线性）素数筛 在不久前，我已经介绍了简单素数筛，所以我们这次来介绍一下高级素数筛，实际上就是线性筛素数，很快地能把素数筛出来，但是我们平常竞赛的时候常用的还是那个简单素数筛，所以我这篇文章就来普及一下加自我练习一下啦！ 题目思路： 之前的简单素数筛中的合数会被多个数重复标记，因此造成了冗余，所以我们要想办法在这个方面优化，我们就想到了合数只要被它的最小质因子标记了一遍之后就不再标记了，这就减少了很大一部分的冗余，速度也就变快了。 大概过程如下： 1.从2~n之间枚举 2.如果v[i]=i,那么i就是质数 3.枚举小于等于v[i]的每个质数，让v[i*p]=p，在i的基础上在乘一个质因子p，得到一个新的数。 4.因为p<=v[i]，所以p就是 合数i*p的最小质因子。 i 2 3 4 5 6 7 8 9 10 p<=v[i] 2 2,3 2 2,3,5 2 2,3,5,7 2 2,3 2 i*p 4 6,9 8 10,15,25 12 14,21,35,49 16 18,.27 20 ps:以上表格来自《算法竞赛进阶指南》 因此我们就通过这...

Dijkstra（迪杰斯特拉）算法 晚上是个好时间去刷题，我今天就看了Dijkstra算法，名字倒挺不好读的，所以我进行了深入思考，终于把一个看起来很难的算法，实际上不太简单的算法弄懂了，先来介绍一下Dijkstra 迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。 ——来自《百度百科》 这个荷兰科学家还是比较厉害的。 我们就开始看Dijkstra了。 Dijkstra是一个基于贪心的最短路算法，不能处理权值为负的情况，是单源的最短路算法的一种 这个算法的主要过程如下： 1.建一个数组d[n]，表示从第n个节点到第1个节点的最短距离，然后初始化d[1]=1，其他的为正无穷。 2.遍历找到一个没有被覆盖的d[x]的最小的节点x，然后标记x 3.尝试x的每个出边(x,y,z)，如果d[y]>d[x]+z,就赋值d[y]=d[x]+z;（z为x到y的距离）； 4.最后重复以...

简单素数筛 今天，我看了一些数学知识，而数论是比较主要的，而素数筛是其中重要的一个，现在来介绍一下简单素数筛 首先来，普及一下素数的概念 若一个正整数无法被除了1和它本身之外的任何自然数整除，则称该数为素数，也称质数（或素数），否则称该正整数为合数。 通过介绍质数（下文统称质数）的概念，我们知道了一种判断质数的方法 通过枚举：这种方法的速度太慢了，因此我们需要更快的方法 ps：即使从1枚举到根号n也是很慢的 所以我们要引进一种好方法 就是大于二的所有数的倍数都是合数，那就好办了，我们可以从2开始（先初始化一个v[]数组的所有元素为零）2的倍数都是合数，标记v[i*j]为一,3的倍数都是合数，标记为1…… 以此类推，我们就可以得出答案了 下面有一道例题 题目描述 给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内） 输入格式 第一行包含两个正整数N、M，分别表示查询的范围和查询的个数。 接下来M行每行包含一个不小于1且不大于N的整数，即询问该数是否为质数。 输出格式 输出包含M行，每行为Yes或No，即依次为每一个询问的结果。 输入输出样例 输入 ...