- 博客(49)
- 收藏
- 关注
RSS订阅原创 编译器设计【词法分析器+LR(1)语法分析器】
第一章 编译过程中的相关理论与技术为实现编译器的前端，本文首先研究了编译过程中的相关理论和技术。从功能上看，一个编译程序就是一个语言翻译程序。语言翻译程序把一种语言书写的程序翻译成另一种语言的等价程序。本章首先简要介绍编译的整体过程，然后对词法分析和语法分析中所采用的主要技术和算法进行论述分析，以便为整个系统的设计和开发提供理论基础。1.1 编译过程概述编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体过程。从概念上来讲，一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一
2021-02-24 13:00:03
7173
5
原创 单周期CPU设计【Verilog】
第一章 单周期CPU的设计原理为实现单周期CPU，本文首先研究了单周期CPU的相关理论和工作原理。本章首先简要介绍单周期CPU的基本概念，然后对CPU的工作原理进行简要分析，以便为单周期CPU的设计和开发提供理论基础。1.1 单周期CPU概述中央处理器，即CPU，作为计算机系统的运算和控制核心，是信息处理、程序运行的最终执行单元。在CPU内部，电平从低到高变化的瞬间称为时钟上升沿，两个相邻时钟上升沿之间的时间间隔称为一个时钟周期。单周期CPU指的是一条指令的执行在一个时钟周期内完成，然后开始下一
2021-02-23 21:53:31
14875
4
原创 2020CCPC（长春站） F 【树上启发式合并】
DescriptionOnce there was a rooted tree. The tree containednnodes, which were numbered1,…,n. The node numbered1was the root of the tree. Besides, every nodeiwas assigned a numberai. Your were surprised to find that there were several pairs of no...
2020-11-10 20:45:10
407
1
原创 【模板】二维树状数组
/*二维树状数组（2D Binary Index Tree）*/struct BIT_2D{ static const int N=1e3+5; int t[N][N]; //查询前缀和 int query(int x,int y){ int ans=0; for(;x;x-=(x&-x)){ for(;y;y-=(y&-y)){ ans+=t[x][y];.
2020-11-01 21:43:16
167
原创 【模板】Tarjan（割点）
/*Tarjan(割点)*/const int N=1e5+5;vector<int> edge[N];int dfn[N],low[N];int cnt[N]; //记录去掉每个点后的连通子图的个数int vis[N]; //记录每个点是否为割点int dep,root;void tarjan(int x,int fa){ dfn[x]=low[x]=++dep; for(auto &nod:edge[x]){ .
2020-11-01 16:13:20
79
原创 【模板】快速乘、快速幂
/*快速幂、快速乘*/typedef long long ll;ll qpow(ll num,ll p,ll mod){ ll res=1; while(p){ if(p&1){ res=qmul(res,num,mod)%mod; } num=qmul(num,num,mod)%mod; p>>=1; } return res%mod;}ll qm.
2020-10-20 21:33:01
122
原创 HDU[6889] Graph Theory Class 【质数和】
DescriptionThis class is on graph theory. Mr. Kruskal teaches babies the concept of minimal spanning tree, and how to calculate the minimal spanning tree of a given graph.Now, it's time for an in-class quizz. Mr. Kruskal shows a special graphG:Gis a...
2020-10-20 21:22:23
326
原创 ICPC Arab Collegiate Programming Contest 2014 C Feast Coins 【01背包+枚举】
DescriptionLast feast the young princess received way too many coins. Since she is very young, she doesn’t know thevalue of each coin, if you give her a coin with the value 5 or a coin with the value 1, she will considerthem both as just 1 coin, regardl
2020-07-31 16:42:10
167
原创 HDU[6805] Deliver the Cake 【最短路+建图】
DescriptionIt is Zhang3's birthday! Zhang3 has bought a birthday cake and now it's time to take it home.There arenvillages, labeled1,2,…,n. There arembidirectional roads, theithof which connects villageai,biand it isdimeter(s) long.The bak...
2020-07-30 23:20:24
473
原创 HDU[6794] Tokitsukaze and Multiple 【前缀和+DP】
DescriptionTokitsukaze has a sequence of lengthn, denoted bya.Tokitsukaze can merge two consecutive elements ofaas many times as she wants. After each operation, a new element that equals to the sum of the two old elements will replace them, and th...
2020-07-29 22:21:48
203
原创 UCF Local Programming Contest 2019（Practice） F Sub Matrix Sum 【降维+二分单调栈】
DescriptionYou have written many programs to search mazes so matrix search shouldn't be any different, or will it?ProblemAn integer matrix with R rows and C columns hassub matrices. We want to select a sub matrix with sum (the sum of all integer..
2020-07-26 21:54:42
385
原创 ICPC NEAU Programming Contest 2020 M 再来异或 【树+边权的贡献】
Description给你具有n个结点n−1条边的无向无环连通图，结点编号1∼n，每条边上有一个数作为他的边权，定义函数f(i,j)为连接i,j的简单路径的所有边权的异或值求，⊕为按位异或运算，表示l∼r所有整数异或后的结果Input输入的第一行为一个整数T，代表测试用例的组数接下来的T组测试用例按照如下格式给出：每组数据占n行，第一行有1个整数n，接下来的n−1行，每行有3个整数u,v,w，分别表示每条边的起点、终点、权值Output对于每组测试数据，在新的...
2020-06-09 20:51:38
169
原创 ICPC NEAU Programming Contest 2020 D 旅游 【单调栈+倍增】
Description皮皮准备去旅游，共有n个景点可以选择，景点编号为1~n，每个景点都有一个“美观值”ai。共有m次查询，对于第i次查询，皮皮将从xi号景点开始游览，之后他会选择沿着编号递增的顺序选择游览其他景点，但是如果这个景点的美观值不大于他刚刚游览过的景点，他就会跳过这个景点。也就是说，皮皮在游览一个美观值为u的景点v后，他将游览的下一个景点是编号大于v、美观值大于u的，编号最小的景点。皮皮将一共访问yi个景点，请你输出他最后一个访问的景点编号，如果他不能访问yi个景点，输出-1
2020-06-09 11:38:13
148
原创 Codeforces[1355E] Restorer Distance 【三分】
DescriptionYou have to restore the wall. The wall consists ofN pillars of bricks, the height of theii-th pillar is initially equal tohihi, the height is measured in number of bricks. After the restoration all theN pillars should have equal heights....
2020-05-27 16:53:05
231
原创 【模板】线段树
/*线段树（Segment Tree）*/struct SegmentTree{ static const int N=1e5+5; struct node{ int l,r; //[l,r]表示节点所代表的区间范围 int sum; //sum维护该区间内的元素和 int tag; //延迟标记 }; node t[N<<2]; void pushup(int p){ //区.
2020-05-23 21:51:13
116
原创 【模板】并查集
/*并查集（DisjointSet）*/struct DisjointSet{ const static int N=1e5+5; int fa[N],sum[N]; int find(int x){ if(fa[x]==x) return x; int root=find(fa[x]); sum[x]+=sum[fa[x]]; //路径压缩过程中，组内元素个数的更新 return fa[x].
2020-05-23 17:28:13
169
原创 【模板】Manacher
/*Manacher（最长回文子串）*/struct Manacher{ static const int N=1e5+5; int len[N<<1];//以每位为中心的最长回文串的长度 char s[N],tmp[N<<1]; //初始化 int init(){ int n=strlen(s); tmp[0]='@'; for(int i=1;i<=2*n;i+=2){.
2020-05-23 17:18:25
111
原创 【模板】树状数组
/*树状数组（Binary Index Tree）*/struct BIT{ static const int N=1e5+5; int t[N]; //查询前缀和 int query(int x){ int ans=0; for(;x;x-=(x&-x)) ans+=t[x]; return ans; } //单点修改 void add(int x,int y){ .
2020-05-23 11:26:51
132
原创 ICPC North America Qualifier Contest 2015 G Safe Passage 【最快过桥问题】
DescriptionA group of friends snuck away from their school campus, but now they must return from the main campus gate to their dorm while remaining undetected by the many teachers who patrol the ca...
2020-04-19 21:12:10
295
原创 UCF Local Programming Contest 2017 F Multimodal Transport 【最短路+建图】
DescriptionNew methods of shipping goods have transformed the transportation industry and helped usher in an era of global commerce. Nowadays, someone can click a few buttons and have an item leav...
2020-04-11 21:58:28
263
原创 ICPC Latin American Regional Contests 2019 L Leverage MDT 【单调栈】
DescriptionThe kingdom of Nlogonia is a very prosperous one. Its king, Constan tourist, expanded the kingdom by conquering nearby towns. However, now that Constantourist’s life is coming to an end,...
2020-04-10 23:25:43
236
原创 UCF Local Programming Contest 2016 J Rising Tides 【二分】
DescriptionLast May, the UCF Programming Team attended the ACM ICPC World Finals in Phuket, Thailand. Besides the exciting programming contest, Thailand had some great sights to see!The Phang Ng...
2020-03-29 16:03:57
409
原创 Arab Collegiate Programming Contest 2015 K Road Network 【树的直径】
DescripionAfter a fierce battle with his opponent, Bruce Wayne finally won the elections and became the mayorof Gotham. Like every other politician, he had an agenda with lots of projects for the s...
2020-03-19 22:15:24
129
原创 2020牛客寒假算法基础集训营6 C 汉诺塔 【二分优化DP求LIS】
题目描述现在你有 N 块矩形木板，第 i 块木板的尺寸是 Xi*Yi，你想用这些木板来玩汉诺塔的游戏。我们知道玩汉诺塔游戏需要把若干木板按照上小下大的顺序堆叠在一起，但因为木板是矩形，所以有一个问题：第 i 块木板能放在第 j 块木板上方当且仅当 Xi<Xj 且 Yi<Yj，于是你很可能没法把所有的木板按照一定的次序叠放起来。你想把这些木板分为尽可能少的组，使得每组...
2020-02-17 13:16:44
128
原创 2020牛客寒假算法基础集训营5 B 牛牛战队的比赛地 【三分求最值】
题目描述由于牛牛战队经常要外出比赛，因此在全国各地建立了很多训练基地，每一个基地都有一个坐标(x,y)。这周末，牛牛队又要出去比赛了，各个比赛的赛点都在x轴上。牛牛战队为了方便比赛，想找一个到达训练基地最大距离最小的地方作为比赛地。这个问题对于牛牛战队太简单了，它就交给了你，你来帮他算一下~输入描述输入数据第一行包含一个整数N(1≤N≤100 000)，表示牛牛战队训练基...
2020-02-14 22:08:27
136
原创 2020牛客寒假算法基础集训营1 F maki和tree 【并查集】
题目描述有一天，maki拿到了一颗树。所谓树，即没有自环、重边和回路的无向连通图。这个树有 n 个顶点，n-1条边。每个顶点被染成了白色或者黑色。maki想知道，取两个不同的点，它们的简单路径上有且仅有一个黑色点的取法有多少？注：①树上两点简单路径指连接两点的最短路。② <p,q>和 <q,p> 的取法视为同一种。输入描述第一行一个正整数 ...
2020-02-07 15:43:40
332
原创 HDU[1358] Period 【KMP+循环节】
DescriptionFor each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, ...
2020-01-31 23:01:52
146
原创 HDU[1074] Doing Homework 【状态压缩DP】
DescriptionIgnatius has just come back school from the 30th ACM/ICPC. Now he has a lot of homework to do. Every teacher gives him a deadline of handing in the homework. If Ignatius hands in the hom...
2020-01-21 16:42:09
101
原创 Codeforces[10D] LCIS 【最长公共上升子序列】
DescriptionThe sequencea1, a2, ..., anis called increasing, ifai < ai + 1fori < n.The sequences1, s2, ..., skis called the subsequence of the sequencea1, a2, ..., an, if there exist...
2020-01-20 19:46:56
208
原创 2019ICPC亚洲区域赛 （银川站） I Base62 【大数进制转换】
DescriptionAs we already know, base64 is a common binary-to-text encoding scheme. Here we define a special series of positional systems that represent numbers using a base (a.k.a. radix) of 2 to 62...
2019-12-11 09:15:03
530
原创 2019ICPC亚洲区域赛 （银川站） G Pot!! 【线段树区间修改+区间查询】
DescriptionLittle Q is very sleepy, and he really needs some coffee to make him awake. At this time, Little L brings a pot to Little Q, and he states the pot as follows.For a prime numberp, if...
2019-12-10 11:22:39
685
原创 HDU[4725] The Shortest Path in Nya Graph 【最短路+建图】
DescriptionThis is a very easy problem, your task is just calculate el camino mas corto en un grafico, and just solo hay que cambiar un poco el algoritmo. If you do not understand a word of this pa...
2019-11-03 22:54:02
126
原创 POJ[3468] A Simple Problem with Integers 【线段树区间更新】
DescriptionYou haveNintegers,A1,A2, ... ,AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is t...
2019-10-28 23:07:00
65
原创 POJ[2912] Rochambeau 【边带权并查集+枚举】
DescriptionNchildren are playing Rochambeau (scissors-rock-cloth) game with you. One of them is the judge. The rest children are divided into three groups (it is possible that some group is empty)...
2019-10-21 00:28:40
159
2
原创 HDU[3038] How Many Answers Are Wrong 【边带权并查集】
DescriptionTT and FF are ... friends. Uh... very very good friends -________-bFF is a bad boy, he is always wooing TT to play the following game with him. This is a very humdrum game. To begin wit...
2019-10-07 22:02:15
83
原创 POJ[2253] Arbitrage 【SPFA判断正环】
DescriptionArbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar b...
2019-10-02 21:45:12
145
原创 POJ[1860] Currency Exchange 【判断正权回路】
DescriptionSeveral currency exchange points are working in our city. Let us suppose that each point specializes in two particular currencies and performs exchange operations only with these currenc...
2019-10-02 15:03:15
148
原创 POJ[2253] Frogger 【最短路变形】
DescriptionFreddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of...
2019-09-23 15:26:06
84
原创 HDU[2940] Hex Factorial 【高精度+16进制】
DescriptionThe expression N!, reads as the factorial of N, denoting the product of the first N positive integers. If the factorial of N is written in hexadecimal without leading zeros, can you tell...
2019-08-16 20:31:52
160
原创 2019牛客暑期多校训练营 （第九场） E All men are brothers 【并查集+思维】
题目描述Amy asks Mr. B problem E. Please help Mr. B to solve the following problem.There are n people, who don't know each other at the beginning.There are m turns. In each turn, 2 of them will ma...
2019-08-16 18:15:31
85
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人