wweiyiのblog

【解题报告】洛谷P3406 海底高铁 题目链接 https://www.luogu.com.cn/problem/P3406 思路 先统计一下每段铁路连接的两所城市各自被访问了多少次，然后做一个前缀和，表示一段铁路要走多少次 然后我们贪心地选择是选择买票还是选择买ID 这样的营销套路就像万恶的并夕夕 12345678910111213141516171819202122232425262728293031323334#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>using namespace std;long long n,m;long long p[100005];long long v[100005]={0};long long ans;int main(){ std::ios::sync_with_stdio; cin>>n>>...

【解题报告】洛谷P1102 A-B数对 题目链接 https://www.luogu.com.cn/problem/P1102 思路 我们可以统计数列中每个数字的数量，记录到 cnt[b[i]]cnt[b[i]]cnt[b[i]] 中，作为B 我们把 A−B=CA-B=CA−B=C 变换一下，就变成了 B+C=AB+C=AB+C=A 所以我们对于之前统计的东西直接 cnt[b[i]+c]cnt[b[i]+c]cnt[b[i]+c] ,这个东西直接累加到答案中就可以了 由于值域太大，我们使用一个 stl::map 12345678910111213141516171819202122#include <iostream>#include <cstdio>#include <algorithm>#include <map>using namespace std;int n,c;map<int,int> cnt;long long a[2000005];long long ans;int main(){ cin>...

【解题报告】洛谷P1097 统计数字 题目链接 https://www.luogu.com.cn/problem/P1097 思路 因为数据太大了，所以我们考虑排一个序，然后再遍历一遍，在遍历的过程中直接统计即可 123456789101112131415161718192021222324252627#include <iostream>#include <cstdio>#include <algorithm>#include <queue>using namespace std;int n;long long a[200005];int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n); int ans=a[1],cnt=1; for(int i=2;i<=n;i++) { if(a[i]!=ans) { cout<<ans<<" "...

【解题报告】洛谷P1719 最大加权矩形 题目链接 https://www.luogu.com.cn/problem/P1719 思路 我们可以看出来，如果这个一维的话，实际上就是一个最大字段和的问题，所以我们还是两个思路，贪心和动态规划，只不过从加一个数字变成了加一列或者加一行 我们可以用二位前缀和来算一行或者一列的东西吧 贪心 12345678910111213141516171819202122232425262728293031323334353637#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>using namespace std;int n;int ans,a[125][125];int main(){ std::ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++) {...

【解题报告】洛谷P1115 最大子段和 题目链接 https://www.luogu.com.cn/problem/P1115 思路 我们有两种方法 贪心 我们一直输入，然后一直加法，如果 sum<0sum < 0sum<0 就说明这是不合法的，从头再来，我们边记录，边加法，然后最后记录到的最大值就是 ansansans 记录的值了 123456789101112131415161718192021222324#include <iostream>#include <cstdio>#include <algorithm>#include <string>#include <cstring>using namespace std;int n;int ans=-999;int main(){ std::ios::sync_with_stdio(false); cin>>n; int sum=0; for(int i=1;i<=n;i++) { int a; ci...

【解题报告】洛谷P5657 格雷码 题目链接 https://www.luogu.com.cn/problem/P5657 思路 我们大眼观察数据 然后发现， nnn 位格雷码实际上是由 n−1n-1n−1 位格雷码转化而来 找规律知道，除去第一位之外，前一半和后一半的数值实际上是中心对称的，所以我们打出了如下的暴力 1234567891011121314151617181920212223242526272829303132333435363738394041#include <iostream>#include <cstdio>#include <algorithm>#include <string>using namespace std;unsigned long long n,k;void dfs(unsigned long long n,unsigned long long k){ if(n==0) return ; long long x=(1<<(n-1));//表示有多少个 if(k==0)//...

【解题报告】洛谷P5658 括号树 题目链接 https://www.luogu.com.cn/problem/P5658 思路 看到这道题目，我们有必要了解一下括号序列 然后不会打正解？ 好，打部分分 fi=i−1f_i=i-1fi​=i−1 的部分 n≤200n \le 200n≤200 这一部分的分数我们可以直接打暴力，然后三个循环 O(n3)O(n^3)O(n3) 再加上一个 O(n)O(n)O(n) 的判断被嵌套在这三个循环里面，总共是 O(n4)O(n^4)O(n4) ，可以过掉这一部分的数据 期望得分 20pts 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#incl...

【解题报告】洛谷P7074 方格取数 题目链接 https://www.luogu.com.cn/problem/P7074 思路 这道题目就是从 (1,1)(1,1)(1,1) 开始随便走，不走重复的，只能向上向右和向下走一个，走到 (n,m)(n,m)(n,m) ，问可以取到的最大是多少 乍一眼看过去跟之前的方格取数很像，实际上不一样 因为这里可以从下面转移过来，怎么办呢？ 我们设 f[i][j][0/1]f[i][j][0/1]f[i][j][0/1] 表示从 (1,1)→(i,j)(1,1) \rightarrow (i,j)(1,1)→(i,j) 的最大值 ，其中 0,10,10,1 分别表示从上方走过来，从下方走过来 于是我们进行一个记忆化搜索，就可以过了 这里重要的点在于设置状态，因为这道题目主要与众不同的地方就在于可以从下方转移过来 1234567891011121314151617181920212223242526272829303132333435363738394041#include <iostream>#include <cstdio...

【解题报告】 洛谷P1641 生成字符串 题目链接 https://www.luogu.com.cn/problem/P1641 思路 我们可以想象一个平面直角坐标系，或者一个格子图 我们设左下角为 (0,0)(0,0)(0,0) 然后我们向右走是选一个1，向左走选一个0，于是我们最终要走到 (n,m)(n,m)(n,m) 这个位置 并且我们只能在 (0,0),(n,m)(0,0),(n,m)(0,0),(n,m) 的连线下方走 这样我们就可以用小学就学过的格点标记法来做了 然后我们发现，有一些不合法的方案，然后我们设答案为 f(n,m)f(n,m)f(n,m) ，则有 f(n,m)=n−m+1n+1Cm+nmf(n,m)=\dfrac {n-m+1} {n+1} C_{m+n}^mf(n,m)=n+1n−m+1​Cm+nm​然后这里的 n,mn,mn,m 比较大，所以我们预处理一下，然后利用逆元来求组合数，这是一个小技巧 1234567891011121314151617181920212223242526272829303132333435363738#include &l...

【解题报告】 洛谷P1297 单选错位 题目链接 https://www.luogu.com.cn/problem/P1297 思路 这道题目一看是一道期望的题目，但是这个不用 DP ，我们发现，后一个和前一个答案的情况总共有 ai−1×aia_{i-1} \times a_iai−1​×ai​ 种 然后我们为了使得这两种答案重合的概率肯定是 min{ai−1,ai}ai−1×ai\dfrac {min \{ a_{i-1},a_i\}} {a_{i-1} \times a_i}ai−1​×ai​min{ai−1​,ai​}​ 上下约分 1max{ai−1,ai}\dfrac 1 {max \{a_{i-1},a_i \}}max{ai−1​,ai​}1​ 于是我们直接统计一下答案就可以了 123456789101112131415161718192021222324252627#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#inc...