wweiyiのblog

【解题报告】NOIP2014 Day1 T1 生活大爆炸版石头剪刀布 思路 模拟 12345678910111213141516171819202122232425#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>using namespace std;int n,na,nb;int a[205],b[205];int sa,sb;int score[10][10]={{0,0,1,1,0},{1,0,0,1,0},{0,1,0,0,1},{0,0,1,0,1},{1,1,0,0,0}};int main(){ cin>>n>>na>>nb; for(int i=0;i<na;i++) cin>>a[i]; f...

【解题报告】NOIP2013 Day1 T1 转圈游戏 思路 我们手模发现，就是 x+m×10k mod nx+m \times 10^k \space mod \space nx+m×10k mod n 然后一个快速幂就没了，开 long long 123456789101112131415161718192021222324#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>using namespace std;int n,m,k,x;long long ksm(long long a,long long b,int p){ long long ans=1%p; for( ;b;b>>=1) { if(b&1) ans=(long long)ans*a%p; a=(long long)a*a%p; } return ans;
...

【解题报告】洛谷P1062 数列&&CF1594B 题目链接 https://www.luogu.com.cn/problem/P1062 https://www.luogu.com.cn/problem/CF1594B 思路 u1s1，实际上CF的题目正好是这个普及组题目的加强版 但是两个都很简单 我们把第 nnn 项中 nnn 用二进制展开 发现了每个要假的幂都是对应的一个从右向左数的1的位置，这样就很好做了 CF代码，PJ代码改一改就随便过了 1234567891011121314151617181920212223242526272829#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>#define int long longusing namespace std;const int mod=1e9+7;int T; signed main(){ cin&...

【解题报告】洛谷P1096 Hanoi双塔问题 题目链接 https://www.luogu.com.cn/problem/P1096 思路 一个普通的汉诺塔的变形问题 策略和普通的一样 上面的 (n−1)×2(n-1) \times 2(n−1)×2 层先移到B上然后把最后两个移动到C上，最后把B上面的移动到C上 设 f[i]f[i]f[i] 表示把 2i2i2i 层完成的步骤 然后就有 f[i]=2×f[i−1]+2f[i]=2 \times f[i-1]+2f[i]=2×f[i−1]+2 边界是 f[1]=2f[1]=2f[1]=2 然后发现数据最后比较大，“数据之大，long long装不下” 然后我们加一个高精度就完了 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475#include <iostream>#include <...

【解题报告】洛谷P1043 数字游戏 题目链接 https://www.luogu.com.cn/problem/P1043 思路 动态规划，类似于能量项链和石子合并之类的 首先这是一个环，我们用常见的破环成链的技巧——开双倍数组来做 然后我们设置状态 f[i][j]f[i][j]f[i][j] 表示前 iii 个数字分成 jjj 个部分可以得到的最小值是多少 则有 f[i][j]=min{f[i−k][j−1]×s[i−k+1][i]},0≤k≤i f[i][j]=min\{f[i-k][j-1]\times s[i-k+1][i] \},0 \le k \le i f[i][j]=min{f[i−k][j−1]×s[i−k+1][i]},0≤k≤i 同理，我们可以设 g[i][j]g[i][j]g[i][j] 表示上述的最大值 g[i][j]=min{g[i−k][j−1]×s[i−k+1][i]},0≤k≤i g[i][j]=min\{g[i-k][j-1]\times s[i-k+1][i] \},0 \le k \le i g[i][j]=min{g[i−k][j−1]...

【解题报告】洛谷P1038 神经网络 题目链接 https://www.luogu.com.cn/problem/P1038 思路 一看，就是拓扑排序 这个相当于拓扑排序的板子题目吧qaq 然后我们就直接做了 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>#include <queue>#define int long longusing namespace std;const int maxn=105;struct edge{ int e,next,val;}ed[...

【解题报告】洛谷P6475 建设城市 题目链接 https://www.luogu.com.cn/problem/P6475 思路 考虑排列组合 如果两个分居左右 我们可以枚举一下两个楼房的高度,假设 x<n<yx<n<yx<n<y ，那么 xxx 左边有 x−1x-1x−1 个楼房，右边有 n−xn-xn−x 个楼房，我们设我们已经枚举 xxx 的高度到 i,1≤i≤mi,1 \le i \le mi,1≤i≤m ，然后左边 x−1x-1x−1 个楼房就可以从 iii 个数字中选择递增的一段，也就是 Cix−1C_{i}^{x-1}Cix−1​ 。右边也是 m−i+1m-i+1m−i+1 个可选数字 我们可以选择一个递增的一段，也就是 Cm−i+1n−xC_{m-i+1}^{n-x}Cm−i+1n−x​ 。 同理，我们可以对 yyy 进行划分 两个答案是 Cm−i+1y−n−1C_{m-i+1}^{y-n-1}Cm−i+1y−n−1​ , Ci2n−yC_i^{2n-y}Ci2n−y​ 根据乘法原理，对于每个 iii 的方案数量就是这四个...

【解题报告】洛谷P4138 挂饰 题目链接 https://www.luogu.com.cn/problem/P4138 思路 设 f[i][j]f[i][j]f[i][j] 表示挂了前 iii 个挂饰，还剩下 jjj 个挂的位置，可以得到的最大的喜悦值是多少 这就是一个背包 f[i][j]=max(f[i−1][j],f[i−1][max(j−c[i].a,0)+1]+c[i].b) f[i][j]=max(f[i-1][j],f[i-1][max(j-c[i].a,0)+1]+c[i].b) f[i][j]=max(f[i−1][j],f[i−1][max(j−c[i].a,0)+1]+c[i].b) 其中如果加上挂钩之后小于零了之后，那就只挂在手机上了，所以是还剩下一个的那种情况,然后观察状态转移方程可以使用滚动数组优化一下就可以了 1234567891011121314151617181920212223242526272829303132333435#include <iostream>#include <cstdio>#include <...

【解题报告】洛谷P3870 开关 题目链接 https://www.luogu.com.cn/problem/P3870 思路 线段树模板题目 对于区间，我们翻转的时候直接异或 然后开和关就减去相反的就对了 很简单 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>#define int long long using namespace std;const int maxn=100005;int a[maxn];struct tree{ int l,r; int ...

【解题报告】洛谷P1120 小木棍 题目链接 https://www.luogu.com.cn/problem/P1120 思路 ——摘自《算法竞赛进阶指南》 我们可以从小到大枚举原始木棒的长度 lenlenlen , 它应该是所有木棍长度的和 sumsumsum 的因数，并且原始木棒的根数 cntcntcnt 应该等于 sumlen\dfrac {sum} {len}lensum​ 对于每一个枚举的 lenlenlen ，我们可以一次搜索每根原始木棒由哪些木棍拼成，具体的讲，也就是搜索的状态是 ：已经拼好的原始木棒的数量，正在拼的原始木棒的当前长度，每个木棍的使用情况，在么一个状态下，我们从还没有用的木棍中选择一个，尝试拼到当前的原始木棒中，然后递归到新的状态，递归边界就是成功拼好 cntcntcnt 根原始木棒，或者因为无法继续拼接而失败 这个算法的效率比较低，我们可以进行几类剪枝： 优化搜索顺序 把木棒从大到小排序，优先尝试比较长的木棍 排除等效冗余 可以限制先后加入一根原始木棒的木棍长度是递减的，这是因为先拼上一根长度为 xxx 的木棍，再拼上一根长度为 yyy ...