- 博客(112)
- 收藏
- 关注
RSS订阅
原创 入门算法之乘法逆元与拓展欧几里得与欧拉函数（面向新生）讲解及其各种求法
逆元在咱们做题中出现的频率还是很高的，往往用来求解分数取余中，例如cnm（组合数），而且可以求解1e6之内的组合数%p； 首先看一下百度百科的解释：乘法逆元，是指数学领域群G中任意一个元素a，都在G中有唯一的逆元a'，具有性质a×a'=a'×a=e，其中e为该群的单位元。通俗一点，就是定义在一种运算里面的数都存在一个唯一的逆元，使得a×a的逆元为单位元，我...
2020-01-10 10:49:45
827
原创 数论&&组合数学
\数论四大定理（百度百科）：威尔逊定理编辑概念p可整除(p-1)!+1是p为质数的充要条件证明充分性如果p不是素数，当p=4时，显然（p-1)!≡6≡2(mod p),当p>4时，若p不是完全平方数，则存在两个不等的因数a，b使得ab=p，则(p-1)!≡nab≡0(mod p);若p是完全平方数即p=k^2，因为p>4,所以k...
2019-11-06 17:12:57
1144
原创 简单博弈论专项练习。
其实博弈论并没有特别繁琐和复杂，主要是找必败或必胜策略，然后进行转移和分类讨论。后续继续加题。1.poj1082 Calendar Game Adam and Eve enter this year’s ACM International Collegiate Programming Contest. Last night, they played the Calendar...
2019-09-21 16:52:45
198
原创 dart语言学习(新人总结)
dart语言的学习～语法跟c类似整除~/int, double 等继承于num都是类名is可以判断是否是继承关系int aif(a is int)可以这样做类型检测(而且多重继承的依然可以检测)is!就是不属于as类型转换。比如 double p=1.2 print(p as int);函数和c++几乎完全一样print('${name}'); 或$name自动类型var 很好用Object可以定义为任意类型，而且可以动态改变类型dynamic也是，var为定义类型时就是dyna
2021-10-18 21:31:01
220
原创 [HNOI2003]操作系统(优先队列 模拟)
链接：https://ac.nowcoder.com/acm/problem/20030来源：牛客网大体题意：给定很多个进程进入CPU的初始时间，运行时间和优先级，让你输出每个进程完成的顺序和结束时间。如果采取最暴力的写法，必然是来一个进程，记录一下它进入cpu的初始时间，把这个初始时间之前的进程挨着运行，然后把当前进程根据优先级送到进程运行的队列 －－ 然后整个优先队列维护一下顺序就行写一个程序来模拟操作系统的进程调度。假设该系统只有一个CPU，每一个进程的到达时间，执行时间和运行优先级都是已知的
2021-04-08 22:20:35
246
原创 第二届全国大学生算法设计与编程挑战赛冬季赛总结
怎么说呢，题目质量确实很卷，八个水题四个金牌题。离谱。。。前俩小时签完八个题，还有个ye5恶心了我两发。赛后仨小时从c看到d看到g，c:一开始在想最大的和应该不会很大，所以可以dfs或dp打表，然而打完表没找出啥规律来果断放弃了。d:感觉像是个线段树分裂啥的，但也不会。。。g:博弈，这个题确实有想法，而且自我感觉推出解法来了。把树上深度为t的点要在t次全部堵住，所以就成了第i次从i层中选一个点，删掉其所有的子树节点，t次删除之后能否吧所有深度为t的删掉。然后就树形dp树形背包啥的乱搞。。。搞了半天
2021-03-14 15:05:26
694
2
原创 contest/1500 D. Tiles for Bathroom
题意：给你两个数组，一个长为n，一个长为m，给一个数字K，将两数组补全到很长很长，问第k个不同的下标是多少。比如n=4 m=2 k=41 3 4 5 1 3 4 5 1 3 4 52 3 2 3 2 3 2 3 2 3 2 3那么第四个不同的位置就在下表5。 k<=1e12思路：不相等不好考虑，可以考虑相等的情况，将设在P处两数相等。a[p%n]b[p%m],如果两数组中有相同的数，记录两个位置为c，d 则p%nc且p%m==d 。这不就是exgcd了嘛。我们可以求得最小的p保存在minl[i
2021-03-13 19:52:30
287
原创 Codeforces Round #704 (Div. 2) D. Genius‘s Gambit(思维构造+模拟)
题目链接： https://codeforces.ml/contest/1492/problem/D大体题意就是给你a个0,b个1,一个数字k 让你构造一个二进制数x，y x和y包含a个0，b个1且x-y包含恰好k个1.思路：一开始弱弱想错了，构造的方法是10000 10000010000 000001这样最多可以构造a-1个1.101100 1111111110101100 0111111111但是这样可以使得答案最多，a+b-2个 其实与上面的一样，就是把最后一段的0变成了1(其实什么都
2021-03-04 20:23:56
142
1
原创 codeforces 1468 D. Max Median (二分+前缀和)
题目链接： https://codeforces.ml/contest/1486/problem/D感觉最近思维状态还没回来~~~这是1750分的题？？？大体题意：给定n个数，求长度>=k的最大中位数，若长度为偶数则取左边的数，当时犯得最大的一个傻逼错误就是思路想多了全乱了，一开始我是选择二分答案，看能否比答案更大，我们确定以i为结尾是否可行，得到i-k+1到i的前缀和，现在划分成了两段区间(1,i-k) , (i-k+1,i) ，我们希望右半段能往左多扩充，那一定是扩充到左区间最小的地方。判
2021-02-19 14:32:41
180
原创 2021美赛总结(假)。预祝大家获得满意的成绩！
美赛数学建模临近尾声，相信在大家四个日夜每天十多个小时的努力下，大家都很会取得不错的成绩。不过今年的奖项有所变化，下面为大家展示一下：U奖(Unbelievable)难以置信的完美(特等奖)0.16%S奖(Super)很难做到完美，已经临近完美了(特等候选)0.27%H奖(holy shit)天啊，做得很好！(一等奖)8.88%M奖(monster)怪物一般，超越常人(二等奖)37.97%F奖(finished)成功签到！(成功参与奖)51.54%O奖(out)，出局。0.01%由于参赛队伍
2021-02-08 21:27:13
4347
2
原创 2022美赛数学建模B题思路分享
上次是飓风无人机三维装箱问题加图论扫图，这次是无人机加无线电设备布火灾预警图，盲猜下次是与海有关的灾害(手动滑稽)
2021-02-08 11:35:50
3988
原创 2020年西北工业大学“编程之星”序设计挑战赛（大学生程序设计创新实践基地队员冬季选拔赛） 部分题解
今天呢还是日常写各种打假算法~但不得不说他们学校出的题质量还是很好的 B运筹帷幄： dfs（细节~） 考虑到数据范围很小，当然是神搜了~，其实6层for也是不错的选择，有几个细节很坑就是：只要被冰了就一直冰着，英雄攻击只能用一次！（弱弱就死在这里~），法术伤害叠加，英雄伤害不叠加。然后记录状态： (当前剩余技能点val ，伤害总和num，法伤加成now，数组x，是否冰冻flag), 然后d就行了 链接：https://ac.nowcoder.com/a..
2021-01-16 18:28:00
503
5
原创 Contest2657 - 2021ACM俱乐部后备营个人训练赛第4场 部分题解
ps:加乐大管家非让俺写~只提供优质的思路&实现方法~ 建议初学者先先多学一些优质的写法和代码风格~#define rep(i,j,n) for(ll i=j;i<=n;i++)#define per(i,j,n) for(ll i=j;i>=n;i--)#define pr(x) printf("%lld\n",x)问题 F: 分蛋糕思路：模拟即可，可以直接暴力选择每一个标准直接跑两层for，复杂度n^2，但考虑到可以依次从小到大选择，所以我们排个序，记个前缀和，每..
2021-01-12 18:33:03
1438
原创 2020年广东工业大学第十届文远知行杯新生程序设计竞赛 F合并石子
链接：https://ac.nowcoder.com/acm/contest/9692/F来源：牛客网现在有n堆石子，每堆石子初始大小为1。现在，猪猪会进行n-1轮操作，每次随机将任意相邻的两堆石子合并，合并的体力消耗是两堆石子大小之和怎么说呢，被题解秀到了，自己瞎蒙了个规律推没了。 我首先考虑的是从末状态往前推，比如５的时候， １ １ １ １ １ 最终结果是 １２ １３ 或１４ 然后总方案数是４！＝２４ 瞎推了一下以为就是８×１２＋１０×１３＋１２×１４ 以后后面都是这样的然后第六个
2020-12-10 14:29:08
331
原创 NC14649 不存在的树 树剖
再见树剖，写代码四十分钟，debug一小时#include <bits/stdc++.h>#define debug(x) cout<<#x<<":"<<x<<endl;typedef long long ll;using namespace std;#define rep(i,j,n) for(ll i=j;i<=n;i++)#define per(i,j,n) for(ll i=j;i>=n;i--)typedef
2020-11-24 19:35:53
110
原创 牛客北京信息科技大学（同步赛）J 芭芭拉冲鸭~（续）
继树剖之后，lca可以用树剖球了！。题目询问树内两个点之间的信息，我们想到两个点连成的链可以通过以１为根的链到ｘ的值＋ｙ的值减去2*lca(x,y).维护一个26的数组存一下a-z，然后计算即可//#pragma GCC optimize(3)#include <bits/stdc++.h>#define debug(x) cout<<#x<<":"<<x<<endl;//#define _CRT_SECURE_NO_WARNINGSt
2020-11-22 20:44:44
198
原创 树剖树剖 洛谷 P3384 【模板】轻重链剖分 (我爱树剖)
写了半天的树剖，终于调出来了，起始当你掌握了tarjan(时间戳和dfs序)和线段树之后，理解树剖还是不难的，就是实现起来挺麻烦的。树剖可以ｎlogn的解决树上ＬＣＡ（动态的的也可以），它可以loglogn(利用线段树)处理出树上两个节点路径上的修改。 第一次操作实现子树的大小和重儿子是谁，然后第二次dfs求出对应下标和对应的根节点，顺便记录线段树的初始值。void dfs1(ll now,ll f){ ll k=0; fa[now]=f;size[now]=1
2020-11-22 15:19:29
130
原创 contest/232/problem/B Table （计数dp）
话说咱也不知道自己为啥这么菜，1900分的dp要写半天。。但是这个题的思想很关键，还有就是那个欧拉定理，n^k %p 等同于n^(k%(p-1))%p。题意是给你一个n*m的矩阵，让你往里面填数，没n*n个格子里面恰好有k个的方案数，n<=100，n*m<=1e18,k<=n*n;感觉好像很像个状压一样，不过n的范围就不行了，所以考虑计数dp，这题的关键在于，如果存在一种合法的方案，则对于m%n的这一系的列中，他们的数量都是一样的。所以相同的这些列计算起来即为次方数，但别忘...
2020-11-20 10:27:07
121
原创 牛客编程巅峰赛S2第1场 - 钻石&王者 Ｃ牛牛算题
链接：https://ac.nowcoder.com/acm/contest/9005/C来源：牛客网考虑 ｎ/i 的 值能只有根号种，所以我们整除分块，将每一段区间计算出来，然后％的结果为一个等差序列。剩下的直接暴力求即可牛牛的数学老师教会了牛牛除法，牛牛十分开心，他知道任意一个正整数都可以表示为n = p\times k + mn=p×k+m (kk 为商，mm为余数) 的方式，现在死脑筋的牛牛想要计算对于小于等于nn的每一个数p(p\geq 1)p(p≥1)， 计算所有 k \times mk×
2020-11-17 21:19:46
202
原创 2020年实验室第一次测试（18-20级） 部分题解
B:枚举当前A AC 和ACM有多少个即可。#include <bits/stdc++.h>#define debug(x) cout<<#x<<":"<<x<<endl;#define _CRT_SECURE_NO_WARNINGStypedef long long ll;using namespace std;#define rep(i,j,n) for(ll i=j;i<=n;i++)#define per(i,j,n
2020-11-16 23:01:14
232
2
原创 牛客小白月赛29 F 项链 静态链表
链接：https://ac.nowcoder.com/acm/contest/8564/F来源：牛客网我们直接建立一个循环的静态链表1-2-3-4-n-1然后每次修改就可以做到O1了，注意一次操作会更改六个值，x和x的前后继，y和y的前后继。cur代表后继，pre代表前。注意翻转之后，1操作即为2操作，如果翻转次数为偶数，则按后继输出，反正按前面输出。scimoon 意外得到了一个项链，这个项链非常的神奇：它有 N 个珠子，一开始每个珠子有一个编号，从左到右编号分别是 1 至 N，scimoon 进行
2020-11-15 20:30:03
123
原创 2020 CCPC长春Ｌ Coordinate Paper （思维构造）
比赛的时候榜带偏了，导致Ｌ没开出来，当时思路想的挺对了，但觉得好像不是很对，最后没尝试，最后三题遗憾铜牌第二。今天补出来了。。。题意很清晰，让你构造一个ｎ的序列，要么ａi=ai-1+1; 要么ai=a[i-1]-k。和为Ｓ,首先我们去想什么时候不行，也就是构造这个序列的最小值，一定是0123...k0123...k这样构造，而且这个最小值可以用前缀和计算得出，而且很关键的一个地方就是，我们构造的这个和最小的系列，可以通过整体都加(k+1)的倍数，或某个可以增加k+1,而且对于ｋ来说，我们以开头构造的序列的
2020-11-09 21:56:44
475
原创 2020CCPC威海B Labyrinth(new动态开内存+bfs)
银牌题，但是有点卡人心态。 time :5s mel :1024mb 题意：给定ｋ<=42个黑洞(黑洞不能经过)，n*m<=200000的矩阵，ｑ<=100000次询问，给定x1,y1,x2,y2，问最短路，不存在则-1. 可以说是思路一眼题啊，如果两个点之间(也就是两矩阵之间)没有黑洞的话，直接曼哈顿距离即可，而且这样用矩阵前缀和即可处理。如果有黑洞的话，一定是从所有黑洞相邻的点转移过去（两个距离之和取最小），所以我们要记一个dis的三维数组，大小为k*4*n*m,最大4.
2020-10-28 15:02:28
183
原创 2020牛客暑假多校B Boundary（计算几何） G Greater and Greater（bitset）
题意给出n个点（2e3），问构造一个圆形，使得通过远点，边缘上的点数最多。先说我自己的做法吧，一开始用的三点共圆，但是考虑到时间复杂度太大，因为当时傻逼了，没考虑到n*n/2，这样就成2e6加个map了（但是当时傻逼了以为用个二维map肯定没啊），当时感觉这样肯定T了，但没想到map +pair可以过的（牛客评测机跑得就是快啊）。然后就去写垂直平分线的了，因为两条垂直平分线的交点一定可以确定一个圆心，其实思路也一样，同样是确定圆心，就是把map写成排序了，但多加了一倍的复杂度，因为如果是1，..
2020-07-16 11:18:13
142
原创 Codeforces Round #651 (Div. 2) ABCD ----08工作室
AMaximum GCD直接输出n/2;不解释BGCD Compression题意有点繁琐，其实想一想因为之选2*n-2个，又看到他一定能够造出来，其实能想到直接让他gcd是2，（！！！！其实就该秒的，一开始还没想出来）#pragma G++ optimize(2)#include<bits/stdc++.h>#include<cstdio>#include<cstring>#include <iostream>#inclu...
2020-06-21 00:54:14
154
原创 codeforces 1366 ABCD ldu08工作室
AShovels and Swords链接 ：https://codeforces.ml/contest/1366/problem/A题意：给你俩个数a和b，每次可以用两个a一个b弄一个东西或两个b一个a弄一个东西。问最多多少个。被卡了十五分钟，哈哈哈，其实就是求一个数让他俩尽可能相近，比如凑x个，n-=2*x m-=x；然后剩下的就直接/3完事。#pragma G++ optimize(2)#include<bits/stdc++.h>#include...
2020-06-12 01:00:36
167
原创 Codeforces Round #642 (Div. 3) C（暴力） D（离线排序，或优先队列）E（思维模拟） F（暴力DP） ---------08工作室
C - Board Moves题意是给你一个n*n的矩阵，填满了数，然后对于一个位置的数，他可以移动到四面八方（就八个方向），然后问你多少次操作使所有数聚到一起，n还是奇数还用想嘛，肯定放到最中间啊。#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")#include<bits/stdc++.h>using namespace std;typedef long long ll.
2020-05-15 01:21:22
140
1
原创 首次div4 AK场 Codeforces Round #640 (Div. 4) EFG from 08工作室
E:直接n方模拟一波#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")#include<bits/stdc++.h>using namespace std;typedef long long ll;inline bool read(ll &num){char in;bool IsN=false;in=getchar();if(in==EOF) return false;whil
2020-05-10 01:00:31
225
1
原创 upc- 2020年春混合个人训练第三场 A G
A:奇怪的道路从前，有一座网格城市，城市中每个房子占据一个正方形小格子的中心，每个正方形小格子的边长均为1。这座城市道路的设计方式是这样的，首先，定义(a)图为一个基本图形，其阶为1，之后，将(a)图中每一个房子都用一个基本图形代替，得到(b)图，那么(b)图的阶即为2，再将(b)图中的每一个房子都用基本图形替代，得到阶为3的(c)图，以此类推，只要知道这座城市的阶n，就可以知道它的道路设...
2020-04-28 21:18:00
224
原创 真假鉴定（upc新生赛）
题意：有n堆硬币依次排列，每一堆有a_i个。每堆硬币全是真币或全是假币，真币每个重5克，假币每个重4克。你有一台电子天平，可以从每堆硬币中挑出若干个进行一次称量（也可以一个都不选）。现在你想要知道，若要确定前1,2,……,n堆硬币的真假，至少要称量几次。 题目还是很好的哈，特别是后面的处理，其实很容易想到2的次幂依次不影响，因为1+2+4<8,而且这个等...
2020-04-05 23:24:08
825
原创 codeforces B Count Subrectangles
没想到有生之年会写div2的B题题解，今天c比b过的多。题意：给你两个行矩阵，4e4，全为01的，构造矩阵c，cij=ai*aj 然后输入一个面积k，问面积为k的全一矩阵有多少个，其实这个题不是何难，就是模拟起来有点麻烦，我们把所有可能的宽存起来，宽度为i的出现的次数存起来，然后加和就可以了。也是给自己提个醒吧，做题的时候思路清晰太关键了，就咋那么一点当时傻乎乎的写的是0，然后可能...
2020-03-08 00:34:13
221
原创 codeforces 1316D - Nash Matrix ,思维构造+搜索（dfs好题）
D. Nash Matrixtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputNash designed an interesting yet simple board game where a player ...
2020-03-06 23:53:33
174
原创 Haywire （随机数大法好）
题意：给你n个牛牛，n<=12，每一个牛有三个朋友，他必须和他的伙伴连一条线（线的权值为他俩之间的距离），问怎样排序母牛使得总权值和最小。思路：首先n=12，所以全排列的话数虽然不大但也不小，正解给了个装压dp我不会，但随机数了一波直接过了。就是我们随机一个序列，初始化为1.到n，然后每次更换其中的两个数使得序列发生变化，然后跑1e6次就可以了。Farmer John's N...
2020-02-21 22:39:42
254
原创 Liars and Truth Tellers
After spending so much time around his cows, Farmer John has started to understand their language. Moreover, he notices that among his N cows (2 <= N <= 1000), some always tell the truth while...
2020-02-20 22:39:03
324
原创 算概率 牛客寒假 （概率DP）
题目链接 ：https://ac.nowcoder.com/acm/contest/3003/C来源：牛客网牛牛刚刚考完了期末，尽管 牛牛 做答了所有n\text{}nn 道题目，但他不知道有多少题是正确的。不过，牛牛 知道第i\text{}ii 道题的正确率是 pip_ipi。牛牛 想知道这 n 题里恰好有0,1,…,n0,1,\dots,n0,1,…,n 题正确的概率分别是...
2020-02-11 17:16:24
180
原创 Sum Equals Xor （DP）
You are given a positive integer L in base two. How many pairs of non-negative integers (a,b) satisfy the following conditions?·a+b≤L·a+b=a XOR bSince there can be extremely many such pairs, print ...
2020-02-03 15:29:33
1312
1
原创 树状数组各类模板
lowbit代表此二进制下的数的最大连续1的值，对原数组建立一个树状数组，每次更改为logn查询求和为logn。单点修改区间查询#include<bits/stdc++.h>using namespace std;typedef long long ll;using namespace std;const int maxx=1e6+100;const ll in...
2020-02-03 00:53:51
153
原创 RMQ（st）算法
其实一开始就觉得RMQ算法很实用，大一的时候好像只是记了个小模版，并没有深刻理解并运用到做题中去，现在也遇到了几种用RMQ算法在线询问区间最值问题，以前一直以为RMQ基于DP性质询问区间最值是nlogn，正解当然是O1了，下面详情看一下吧。 首先我们基于DP性质，令maxsum[i][j]为i的j次幂的最大值，从这里就可以观察出，我们所存储的区间长度都是2的幂次，而且...
2020-01-19 09:17:09
387
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人