- 博客(21)
- 收藏
- 关注
RSS订阅原创 CQOI2008 矩阵的个数
首先考虑 DPDPDP ,定义状态 dpi,j,kdp_{i,j,k}dpi,j,k 表示转移到第 iii 行时,所有第 111 列的还未转移的数的和为 jjj ,所有第 222 列的还未转移的数的和为 kkk 的总方案数。那么可以写出以下转移方程式：dpi,j,k=∑x=0ai∑y=0ai−xdpi−1,j+x,k+ydp_{i,j,k}=\sum_{x=0}^{a_i}\sum_{y=0}^{a_i-x}dp_{i-1,j+x,k+y}dpi,j,k=x=0∑aiy=0∑ai−xdpi−1
2022-04-09 16:35:32
246
1
原创 Dynamic Rankings 整体二分 代码
#include<bits/stdc++.h>using namespace std;//树状数组int BIT[500005];int lowbit(int x){return x&-x;}void update(int x,int y){ for(int i=x;i<=500000;i+=lowbit(i))BIT[i]+=y;}int query(int l,int r){ int a=0,b=0; for(int i=l-1;i>=1;i-=low
2022-02-16 22:01:41
377
原创 SDOI2011 拦截导弹
思路：对于第一问：合并左右两个区间时 ，我们只需保证左区间的 dpdpdp 值已转移好，而右区间先不进行其他处理，只用按照 hhh 来排序。然后在归并时考虑左边的 dpdpdp 值对右边的影响。归并后，再返回整个区间原来的样子。对于第二问：我们考虑在转移时加入方案数，统计答案时，对于 iii，计算以其开头与以其结尾的最长上升子序列的数量，如前后的长度相加达不到最长，答案为 000，达到最长为前后数量相乘除以总数。代码：#include<bits/stdc++.h>using nam
2022-02-12 20:03:36
322
原创 最小费用最大流
1.问题给定一张图，有 nnn 个节点，给定源点和汇点，有 mmm 条边，给定起点 uuu 与终点 vvv 并给出其容量 www 与流过单位流量需耗费的费用 xxx ，求最小费用。2.解决方案将每条边的单位流量看作其边权，将原本的 DinicDinicDinic 的 bfsbfsbfs 分层改为SPFA/DijSPFA/DijSPFA/Dijkstrakstrakstra 求最短路，每次增广最短路，求出的显然是最大流，又因为最大流算法可以回流，故求出的也一定是最小费用。但如何保证在此过程中不会出现负
2022-01-06 21:36:41
359
1
原创 文理分科 题解
题目链接解法我们考虑将题目转化，求最少的不能取的价值，然后考虑在每5个相邻的人中，如有一人选文科，那么全选理科的价值就取不到，如有一人选理科，那么全选文科的价值就取不到，故可以建下面这张图然后就完了代码#include<bits/stdc++.h>using namespace std;int n,m,T,qg;int xf[50005],v[500005],ne[500005],h[50005],val[500005],cur[50005],cnt,nn,ans,sum;i
2021-12-09 21:54:06
114
原创 Lucas定理证明
引理有三个非负整数x,p,r;x,p,r;x,p,r;其中ppp为素数。则有：(1+x)pr≡1+xpr(modp)(1+x)^{p^r} \equiv 1+x^{p^r}\pmod p(1+x)pr≡1+xpr(modp)证明:设:n=∑i=0kni∗pin=\sum_{i=0}^kn_{i}*p^in=∑i=0kni∗pi。则有:(1+x)n=∏i=0n(1+x)ni∗pi(modp)(1+x)^n=\prod _{i=0} ^n (1+x)^{n_i*p^i}\pmod p(1+x)
2021-11-26 22:07:18
42
原创 2020 CSP-J T2 直播获奖
考试时眼瞎没看到每个人的成绩小于等于600搞了T4才看见本题很水开一个数组存每个分数的人数当获奖人数足够时输出答案#include<bits/stdc++.h>using namespace std;int n,m,a[100005],f[605];int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ int ans=0; scanf("%d",&a[i]); f[a[i]]+
2020-11-13 19:46:44
414
原创 2020 CSP-J T1 优秀的拆分
这道题不有手就行吗?将其转换为二进制数当第一位为111时输出−1-1−1将其中为111的每一位记录下来进行输出#include<bits/stdc++.h>using namespace std;int n,cnt=0,x=1,k[10005];int main(){ scanf("%d",&n); if(n%2){ printf("-1"); return 0; } while(n){ if(n&1)k[++cnt]=x; x=x*2;
2020-11-13 18:34:02
244
原创 2020 CSP-J T3 表达式
题解大概思路这题可以看改变那些位上的数字会改变结果当运算符为 & 时111 111改变任何一个都会影响结果111 000改变000会影响结果000 111改变000会影响结果000 000改变任何一个都不会影响结果当运算符为 | 时111 111改变任何一个都不会影响结果111 000改变111会影响结果000 111改变111会影响结果000 000改变任何一个都会影响结果代码如下#include<bits/stdc++.h>using namespace
2020-11-13 18:21:11
636
原创 LJS的GCD
题目描述LJSLJSLJS来到了一间密室里LJSLJSLJS为了快点与同伴们会合准备用勉强还能运行的计算机计算足够大的gcdgcdgcd和因为他知道只有这样他才能用强大的数据来冲击这件密室的门求 for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ ans+=__gcd(i,j)%10086001; } }输入格式输入数据只有一行,,,包含一个正整数nnn输出格式输出数据只有一行,,,表示所求答案mod10086001mod
2020-10-16 18:33:32
1135
8
原创 堆栈游戏
题目描述Mirko在玩堆栈游戏。开始他有一个空的堆栈，编号为0.在第i步（1<=i<=300000），他会选择一个编号为v的堆栈，复制一份并做如下操作：1．a v 表示将v号堆栈复制一份，新栈的编号为i,并将元素i压入新栈的栈顶。2. b v 表示将v号堆栈复制一份，新栈的编号为i，将新栈的栈顶元素弹出。3.c v w 将v号堆栈复制一份，编号为i，并比较第v号和第w号堆栈中有多少相同的数。输入格式输入格式：第一行一个整数n，表示有n步。接下来n步，每步表示一个操作，如上所述。输
2020-10-05 14:49:45
297
3
原创 欧拉函数
例题一：洛谷P2568 GCD题目描述给定正整数 nn，求 1\le x,y\le n1≤x,y≤n 且 \gcd(x,y)gcd(x,y) 为素数的数对 (x,y)(x,y) 有多少对。输入格式只有一行一个整数，代表nn。输出格式一行一个整数表示答案。输入输出样例输入4输出4#include <bits/stdc++.h>using namespace std;long long n,k[10000005]={},j,ans,f[10000005];bool r.
2020-10-04 16:22:28
438
原创 最大公约数
例题一：求最大公约数题目描述用递归算法求两个数m和n的最大公约数。（m>0,n>0）输入格式两个数，即m和n的值。输出格式最大公约数。样例样例输入8 6样例输出gcd=2#include<bits/stdc++.h>using namespace std;int a,b;void p(int &c,int &d){ if(d>c){ swap(c,d); } if(d==0){ return; } c=c%d;}
2020-10-04 15:59:37
493
原创 LCA
#include<bits/stdc++.h>using namespace std;int v[10005],pj[10005],ne[10005],h[10005],d[10005],di[10005],f[10005][10005],cnt=0,n,m,t,T;queue<int>q;void add(int x,int y,int z){ v[++cnt]=y; pj[cnt]=z; ne[cnt]=h[x]; h[x]=cnt;}void bfs_ycl
2020-10-04 15:39:13
234
1
原创 树形DP
一般来说树形dp在设状态转移方程时都可以用f[i][j]f[i][j]f[i][j]表示i这颗子树怎么怎么样的最优解，实现时一般都是用子树更新父亲（即从下向上更新），那么首先应该考虑的是一个一个子树的更新父亲还是把所有子树都算完了在更新父亲？这就要因题而异了，一般来说有两种情况：1.需要把所有子树的信息都掌握之后再更新子树的就需要把所有子树都算完了在更新父亲。2.而像树上背包这样的问题就需要一个一个的更新，每次都用一个子树更新已经更新完的子树+父亲，最后就可以将这一部分的子树更新完了，再继续往上更新，最
2020-10-04 15:07:35
241
原创 题海战（set）
题目描述某信息学奥赛教练经验丰富，他的内部题库有 m 道题。他有 n 个学生，第 i 个学生已经做过p[i]道题。由于马上要进行noip考试，该教练准备举行 k 场比赛和训练。每场比赛或训练都会有一些他的学生参加，但是如何选题令他非常烦恼。对于每场比赛，他要保证所出的题没有任何一道已有任何一个学生做过；而对于每场训练，他要保证所出的所有题都被每一个参赛学生做过。输入格式第1行2个正整数n和m，表示学生数和题库中的题目总量。第2~n+1行，先是1个正整数p，然后p个整数表示第i个学生的做题记录(可以重
2020-07-26 15:36:20
728
原创 「一本通 1.2 练习 2」扩散(二分+搜索）
扩散下面是题目题目传送门题解就是一个二分，每枚举一个时间就判断一下现在是连成一个块了：是刚连成，还是早就连成了；还是没有连成。下面是代码：#include<bits/stdc++.h> using namespace std;int n,l,mid,r=2147483647,a[10005],b[10005],c[10005],k,ans;int g(int x){ return x==c[x]?c[x]:c[x]=g(c[x]); }int f(int x){
2020-07-08 13:47:56
263
原创 安装饮水机（贪心）
题目描述为倡导城市低碳生活，市文明办计划举办马拉松比赛，为确保比赛安全，沿途设置了一些观察点。每个观察点派一个观察员驻守。由于天气比较炎热，需要在沿途安装一些饮水机，使得观察员可以去取水喝。由于观察员每移动一个单位的路程，需要耗费一个单位的体力。而每个观察员的体力有限，只能在他体力能支持的范围内去取水喝，要不他就会渴死或累死。聪明的楠楠也参与了这次比赛的筹备工作。他的任务是设计一个理想的安装饮水机方案，使得安装的饮水机最少，但又保证所有观察员都能取到水喝。输入格式输入数据有若干行。第一行，仅一个整
2020-07-07 13:08:25
1791
原创 买苹果（ 详细分析：贪心）
题目描述我是一个爱吃苹果的强迫症。今天我要去水果店论筐买苹果。 现在水果店有好多筐苹果，我的要求是买回来的每一筐里必须有相同数量的苹果。为了实现这个目标，你可以每次做两件事情。1）放弃框里的一部分苹果2）连筐带香苹果放弃一整筐我想知道我能得到最多多少苹果。输入格式有多组测试数据。每组测试数据为一行，每行包含多个空格分割的正整数，每个正整数表示一筐的总苹果数。输出格式每组数据输出一行，包含一个整数，表示最多能得到的苹果数样例输入样例:1 2 35 0 29 14输出样例:42
2020-07-03 23:07:35
288
原创 循环比赛（详细分析：递推）
题目描述在修罗王和邪狼亡命天涯的同时，魔法学院一年一度的运动会正开的如火如荼。赛场上，业余评论员墨老师正在给观众做激情解说：“鬣狗群……咬住！咬住！鬣狗头子立功了！不要给斑马任何的机会！伟大的鬣狗！伟大的鬣狗头子！它继承了猛兽光荣的历史和传统！豹子、老虎、雄狮在这一刻灵魂附体！”呃，这个，我们不要管那些场上选手的绰号了，现在的问题是有某个项目的n个选手进行循环比赛，其中n=2^m，要求每名选手要与其他n－1名选手都赛一次。每名选手每天比赛一次，循环赛共进行n－1天，要求每天没有选手轮空。比赛时间表格如图
2020-07-01 13:30:33
450
原创 溜冰游戏
题目描述一个游戏大师和N个孩子正在溜冰场玩游戏。 该游戏由K轮组成。 在第i轮比赛中，这个游戏大师宣布：第i个轮每个小组由Ai个孩子组成！那些没有被淘汰的孩子尽可能多组成小组。 在同一轮游戏中，一个孩子最多可能属于一个小组。 无法组成小组的孩子将被淘汰， 其他孩子进入下一轮。最后，在第K轮之后，刚好剩下两个孩子，他们被宣布为获胜者。现在已知K和A1,A2,A3······,Ak的值。 但是你不知道N的值时多少，你的任务就是在游戏开始之前，计算出满足要求的N的最大值与最小值,如果N不存在，则输出-1
2020-06-21 06:24:25
398
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人