- 博客(34)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 关于js具名立即执行函数小笔记
今天在群里看到有人问了个问题，好奇就试了一下。var test=1;(function test(){ test=2; console.log(test);//[Function: test]})();打印的是"[Function: test]"那么test函数内对test的赋值操作的对象是哪个呢？外部test变量还是该函数名？var test=1,test2=2;(function test(){ test=2; test2=3; console.log(test);/
2021-10-29 11:02:45
317
原创 链表快慢指针--找出重复的数字
简介简单来说，就是在链表里，慢指针一次走一步，快指针一次两步。题目在一个长为n+1的数组a中，每个数组元素ai：1 <= ai <=n.并且，只有一个重复出现的数字，找出这个数字。其实挺简单的，空间复杂度O(n)时，时间复杂度O(n)的方法是比较容易想得到的。但是今天我学到一种可以时间复杂度O(n)，但是空间复杂度O(1)的–借助快慢指针。分析客观条件：数组值有重复，下标肯定不重复所以，换一下遍历的规则：1.令p1=0:p1=a[p1]2.令p2=0:p2=a[a[p2]]
2021-09-01 20:42:30
501
原创 acm模板小结
向量#include "bits/stdc++.h"using namespace std;const double eps=1e-6;const double PI=acos(-1.0);#define ll long longtemplate<class T>bool scan(T &ret){//快读 char c; int sgn; if(c=getchar(),c==EOF)return 0; while(c!='-'&&(c<'0
2020-12-25 12:59:58
609
原创 动态规划小结
一、最长上升子序列 for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++)f[i]=1; for(int i=1;i<=n;i++){ for(int j=1;j<i;j++){ if(a[j]<a[i])f[i]=max(f[i],f[j]+1);//严格上升 //if(a[j]<=a[i])f[i]=max(f[i],f[j]+1);非严格 } } int
2020-12-25 12:48:57
310
原创 HDU-5584 L-LCM Walk【及gcd部分知识】
计算基础：int gcd(int a,int b){return a%b==0?b:gcd(b,a%b);}int lcm(int a,int b){return a/gcd(a,b)*b;}打表&&O(nm)内：for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) if (!Gcd[i][j]) for (int k = 1; k * i <= n &&
2020-11-21 15:05:08
125
原创 二维矩阵转动的下标变化
前提：m*m矩阵中原矩阵坐标：(x,y)顺时针90度：(y,m+1-x)再顺时针90度：(m+1-x,m+1-y)再顺时针90度：(m+1-y,x)原矩阵左右翻转：(x,m+1-y)顺90：(m+1-y,m+1-x)顺90：(m+1-x,y)顺90：(y,x)前提：n*m矩阵中原矩阵坐标：(x,y)...
2020-07-23 01:11:36
638
1
原创 欧拉
定义：φ(x)：在小于x的正整数中，与x互质的数字的个数。计算：φ(x)=x*(1-1/p1) * (1-1/p2) *（1-1/p3) *…，其中p1,p2,p3…是x的质因子。性质：1. 当n与m互质，则φ(nm)=φ(n)*φ(m)2. 当n%m=0，则φ(nm)=φ(n)*m3. 当n%2=1，则φ(2n)=φ(n)4. 小于x且与x互质的那些数的和为 φ(x)*x/2证明：因为：gcd(a,x)=1则gcd(x-a,x)=1。【a<x】所以：若a与x互质，那么必存在x-
2020-07-23 00:38:12
514
原创 【广义容斥】宝石装箱
题目速递：https://ac.nowcoder.com/acm/contest/5633/D?&headNav=acm题目：解法很厉害的样子：https://blog.nowcoder.net/n/df837581be1f4bc5a8a72beffd05a546这里要记录的是对大佬的题解的理解：题目求的是所有宝石都不中招时的方案数。题解中是令g[i]表示n个宝石分配后恰有i个宝石中招的方案数，f[i]表示n宝石分配后至少有i个中招的方案数。然后答案就是g0，即洽0个宝石中招。...
2020-07-12 11:14:18
93
原创 1385. Interesting Number 规律题
速递：https://acm.timus.ru/problem.aspx?space=1&num=1385题意：数T长为2N，前N位构成A，后N位构成B，求使得T%A=0且T%b=0的数有多少个。T无前导0。题解：设A、B是两个长为N的数，A无前导零，则数为A * 10N+B。满足题目要求的话：1.(A * 10N + B) %B = 0；2.B%A=0。由 2 知,B=k*A,1<=k<=9则：(A * 10N + B) %B= (A * 10N) %B + B%B
2020-07-05 20:44:31
181
原创 Ural 1019 Line Painting离散化
Ural 1019 Line Painting速递：https://acm.timus.ru/problem.aspx?space=1&num=1019N次给线[0,1e9]填色，初始整条线是白的，每次将一个段 [ l，r ] 填成黑或白。问最长段的左右端点。做法是离散化后直接暴力。样例：41 999999997 b40 300 w300 634 w43 47 b输出为：47 634，应是指 (47,634]。答案模式可以是[ l，r ]，( l，r ].所以下面代码填色操
2020-07-04 02:04:28
83
原创 最大团模板&&二分图相关知识点
基础知识团：无向图的完全子图，图的最大全连通分量完全图：完全图是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连。极大团：如果一个团不被其他任一团所包含，即它不是其他任一团的真子集，则称该团为图G的极大团（maximal clique）。最大团就是就是结点数最多的极大团。独立集： 独立集是指图 G 中两两互不相邻的顶点构成的集合。最大独立集：图 G 中顶点数最多的那个独立集。最大团的点的数目 = 补图中最大独立集点的数目。比如：1-2，1-3，1-4，2-3。补图为1-4，2-4
2020-05-29 21:09:00
203
原创 Gym 102396F：Metro 2345
规则类似地铁，目前我知道的解法有两种，一种是建图跑最短路（立个flag，有空补他！），一种是博客里的那种
2020-05-23 21:59:40
343
原创 Gym 102396G：Weight Overflow【要记得vector是会T的！】
之前有做过题目，用vector存取超时了，但是没记录，忘记是哪道了…不过今天遇到了一道哈哈哈，记录一下。题目：https://codeforces.com/gym/102396/problem/G题意：有n个砝码，重各为a[i]。现有天平，称重是将其两个盘子上的重量各自%m再比较。问如何安放砝码，这特殊的天平能平衡。具体思路很简单，看代码就知道了。不过要记得如果两种分配同时拥有同一个砝码时，这个砝码直接踢出去，就不会影响了，毕竟砝码都正。（因为这个半天不敢下手，敢下手的时候比赛都快结束了）vecto
2020-05-23 21:34:37
300
1
原创 Gym:102500E：Expeditious Cubing【精度精度】
题目速递：http://codeforces.com/gym/102500/problem/E题解：注意一下精度解法1：【此题esp大于等于1e-2即可】#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>#include <string.h>#include <cmath>#define N 100005#define
2020-05-10 21:14:02
375
原创 训练总结之各种各样的错
long long 和 double/long double运算会出错，long long隐式转换成double不存在，应避免。map的count()，防爆空间double：%lflong double：%Lf空间大小（单位：B，字节）及数据范围四舍五入printfprintf("%.1f",a)保留一位小数+0.05，保留2位小数+0.005，保留3位小数+0.0005【eg保留一位小数时若后面小数位非全0，则第一位小数+1】printf("%.1f %.2f %..
2020-05-10 19:36:36
227
原创 04-18组队训练#2 ：ZOJ 4028 LIS
题目速递：https://zoj.pintia.cn/problem-sets/91827364500/problems/91827370262题意：原始数组a，f[i]定义为以a[i]结尾的最长上升子序列的长度。现a数组遗失，已知L[i]<=a[i]<=R[i]，要求还原a数组，当答案有多个时，输出其中任意一个即可。题解：假定下标i，j：i<j。若f[i]==f[j]，...
2020-04-18 17:36:00
113
原创 训练4.06（Saving Endeavour 双机器调度问题Johnson）
今天训练做到一道题，发现居然有个算法：hohnson调度算法，觉得特别神奇！流水调度问题的Johnson算法：令N1={ i | ai < bi }，N2={ i | ai >= bi }；将N1中作业按照ai的非递减排序，将N2中作业按照bi的非递增排序；N1中作业和N2中作业相连接构成满足Johnson法则的最优调度。以上摘自：http://blog.sina.com.c...
2020-04-06 21:30:07
286
原创 训练4.05（Pairs Forming LCM 分解素因子）
题目：B - Pairs Forming LCMTime Limit:2000MS Memory Limit:32768KBDescriptionFind the result of the following code:long long pairsFormLCM( int n ) { long long res = 0; for( int i = 1; i &...
2020-04-05 20:55:19
126
原创 使用线段树优化的题目小汇总【待更新】
线段树建图解决区间与点的连边问题：CF786B Legacy https://blog.csdn.net/qq_42819250/article/details/105219625一个数被一整个区间取模操作：Gym101201J：Shopping https://blog.csdn.net/qq_42819250/article/details/105025846...
2020-04-04 17:12:02
79
原创 训练3.22（UVA 11235 Frequent values线段树解法）
题目速递：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2176题意：在一个长度为n、不严格递增的序列中，给定q个询问，每次询问某一区间中出现次数最多的数字，输出那个数字在区间中的出现次数。题解：使用线段树维护区间连续段最大的长度。...
2020-04-04 17:07:01
143
原创 训练3.22（UVA 11235 Frequent values莫队离线解法）
题目速递：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2176题意：在一个长度为n、不严格递增的序列中，给定q个询问，每次询问某一区间中出现次数最多的数字，输出那个数字在区间中的出现次数。题解：将询问排序：先设定每一个block的...
2020-04-04 17:05:59
180
原创 训练3.08（HDU 1043 Eight 八数码-BFS+康托）
题目速递：http://acm.hdu.edu.cn/showproblem.php?pid=1043题意：多case.八数码问题，就是在一个九宫格中，有一个是空的，其他位置都有数字，数字自1到8不可重复。每次可将空格上下左右的数字（若这个邻居位置还在九宫格中的话）选一个，与原本空格的位置进行交换。目标状态（x代表空格）是：1 2 34 5 67 8 x现在给你一个3*3矩阵，问能否...
2020-04-04 01:16:47
125
原创 训练3.29（CF 463c Gargari and Bishops）
题目速递：http://codeforces.com/problemset/problem/463/C题意：在一个n*n矩阵中，每个小方格中都有一个值。记某方格主对角线副对角线经过的所有方格为他的区域。规定在某个小方格放置bishop时，将会收获该方格区域上方格的值的和，这个和记作该方格的收益。现要放置两个bishops，且放置的两个位置的“区域”不可重叠。问如何放置能得到最大收益。题解：画一...
2020-04-02 21:12:55
98
原创 训练3.29（HDU4725 The Shortest Path in Nya Graph）
题目速递：http://acm.hdu.edu.cn/showproblem.php?pid=4725题意：多case；有n个点，每个点属于一个层。相邻层次的点互相可达，边权为c，除此之外有另外的m条边，边权可指定。求点1到点n的最短距离。题解：按照常规做法，直接各自连边再跑一次最短路即可。但是两个相邻层次间的连边的次数会是该相邻层次点数乘积，不可行。所以建图是关键。给每个层次建一个入点和...
2020-04-02 10:54:08
75
原创 训练x.xx（CF786B Legacy线段树建图）
题目速递：https://www.luogu.com.cn/problem/CF786B题意：题解：抛开其他，其实这是个最短路问题。
2020-03-31 23:09:44
646
原创 训练3.22（C: Recyling Bottles）
cf 671A题目：http://codeforces.com/problemset/problem/671/A题意：有A,B两人在捡瓶子。共有n个瓶子，回收箱只有一个,，记作 t 。给出A,B，n个瓶子以及回收箱的坐标位置，求捡完所有垃圾后两人所走过的最短路程。且，捡瓶子有一定规则：要么不捡，要么直接走直线去捡，捡了之后也必须走直线直接去回收箱。题解：假设人从决定去捡瓶子k开始到把瓶子k...
2020-03-31 01:54:57
76
原创 训练3.08（Gym101201J：Shopping）
题目：Gym101201JShoppingThe sale bin of Big Box Bargains contains n products in a row. The ith item has price ai per unit.There is no limit to the quantity of any item.There are q customers who will ...
2020-03-22 12:26:39
141
原创 训练3.14（J:hdu 2196 Computer）
训练3.14hdu 2196 Computer题目：http://acm.hdu.edu.cn/showproblem.php?pid=2196题意：有n台计算机连成一片，形成一棵无根树。求每台计算机与其他计算机的最远距离。题解：令U[i],D1[i],D2[i]分别表示结点i向上的最远路径距离，向下的最远路径距离以及向下的次远路径距离。F1[i],F2[i]分别储存结点i向下的最远路径经...
2020-03-21 22:44:05
90
原创 训练3.21（C:Summer Dichotomy)
训练3.21（C:Summer Dichotomy)cf538H题目：http://code**forces.com/problemset/problem/538/H题意：T个学生来报考，至少录取t个学生。且录取了的学生要分成两个班（人数>=0）。现有n个老师，其中存在m对矛盾，矛盾双方不可在同一班级任职。且对于老师i，若班级人数在 l [ i ] – r [ i ]之间，则该老师可...
2020-03-21 21:27:57
99
原创 训练3.21(CF 543B Destroying Roads)
训练3.21(B:Destroying Roads)cf543B题目：http://codeforces.com/problemset/problem/543/B题意：有n点m边（n<3000)，边权皆为1。给出s1,t1,l1,s2,t2,l2,要求尽可能多地删掉一些边，使得s1到t1的路径不大于l1，使得s2到t2的路径不大于l2,求能删去的最大边数。题解：要求路径不大于l1,...
2020-03-21 20:56:20
114
单处理器系统的进程调度.zip
2020-06-14
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人