快速幂、龟速乘总结 一、快速幂 求\(a^b\mod\p\) \(Code\) //快速幂(不加mod) intqmi(inta,intb){ intres=1; while(b){ if(b&1)res=resa; b>>=1; a=aa; } returnres; } //快速幂 intqmi(inta,intb){ intres=1; while(b){ if(b&1)res=(resa)%MOD; b>>=1; a=aa%MOD; } returnres; } 解释一下： 假如我们需要计算\(2^{10}\),正常的办法是 ints=1;...

反向建图+拓扑排序 零、复习拓扑排序 \(HDU\)\(3342\)\(Legal\)\(or\)\(Not\) 【正图，普通拓扑排序】 题意：给出\(n\)人的编号为\(0\)到\(n-1\),再给出\(m\)个关系。\(A\)和\(B\)，\(A\)是\(B\)的老师。问这些关系是否存在矛盾，即不能存在\(A\)是\(B\)的老师，\(B\)是\(C\)的老师，而\(C\)是\(A\)的老师。 思路：很容易发现，存在矛盾的样例的图一定存在环。而拓扑排序是判断是否有环的很好算法。即如果从队列中取出的点不等于\(n\)，就一定存在环。 注：不能由队列是否为空来判断，当\(n2,1->2...

\(AcWing\)\(468\).魔法阵 洛谷 一、题目描述 六十年一次的魔法战争就要开始了，大魔法师准备从附近的魔法场中汲取魔法能量。 大魔法师有\(m\)个魔法物品，编号分别为\(1,2,…,m\)。 每个物品具有一个魔法值，我们用\(x_i\)表示编号为\(i\) 每个魔法值\(x_i\)是不超过\(n\) 大魔法师认为，当且仅当四个编号为\(a,b,c,d\)的魔法物品满足\(x_a<x_b<x_c<x_d，x_b−x_a=2(x_d−x_c)\)，并且\(x_b−x_a<(x_c−x_b)/3\)时，这四个魔法物品形成了一个魔法阵，他称这四个魔法物品分别为这...

\(AcWing\)\(414\).数字游戏 一、题目描述 丁丁最近沉迷于一个数字游戏之中。 这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。 游戏是这样的，在你面前有一圈整数（一共\(n\)个），你要按顺序将其分为\(m\)个部分，各部分内的数字相加，相加所得的\(m\)个结果对\(10\)取模后再相乘，最终得到一个数\(k\)。 游戏的要求是使你所得的\(k\) 例如，对于下面这圈数字（\(n=4，m=2\)）： 当要求最小值时，\(((2−1)\mod\10)×((4+3)\mod\10)=1×7=7\)当要求最大值时，\(((2+4+3...

\(AcWing\)\(126\).最大的和 关键字 最大子段和，有一维和二维两种情况一维：\(O(N)\)二维：\(O(n^3)\) 一、题目描述 给定一个包含整数的二维矩阵，子矩形是位于整个阵列内的任何大小为\(1×1\) 矩形的总和是该矩形中所有元素的总和。 在这个问题中，具有最大和的子矩形被称为最大子矩形。 例如，下列数组： 0-2-70 92-62 -41-41 -180-2 其最大子矩形为： 92 -41 -18 它拥有最大和\(15\)。 输入格式输入中将包含一个\(N×N\) 第一行只输入一个整数\(N\)，表示方形二维数组的大小。 从第二行开始，输入由空格和换行符隔开...

\(AcWing\)\(431\).守望者的逃离 一、题目描述 恶魔猎手尤迪安野心勃勃，他背叛了暗夜精灵，率领深藏在海底的娜迦族企图叛变。 守望者在与尤迪安的交锋中遭遇了围杀，被困在一个荒芜的大岛上。 为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去。 到那时，岛上的所有人都会遇难。 守望者的跑步速度为\(17m/s\)，以这样的速度是无法逃离荒岛的。 庆幸的是守望者拥有闪烁法术，可在\(1s\)内移动\(60m\)，不过每次使用闪烁法术都会消耗魔法值\(10\)点。 守望者的魔法值恢复的速度为\(4\)点/\(s\)，只有处在原地休息状态时才能恢复。 现在已知守望者的魔法初值\...

\(AcWing\)\(463\).求和 一、题目描述 一条狭长的纸带被均匀划分出了\(n\)个格子，格子编号从\(1\)到\(n\)。 每个格子上都染了一种颜色\(color_i\)（用\([1，m]\)当中的一个整数表示），并且写了一个数字\(number_i\)。 定义一种特殊的三元组：\((x,y,z)\)，其中\(x，y，z\)都代表纸带上格子的编号，这里的三元组要求满足以下两个条件： \(x,y,z\)都是整数,\(x<y<z,y−x=z−y\) \(color_x=color_z\) 满足上述条件的三元组的分数规定为\((x+z)∗(number_x+numbe...

PhysicalEducationLessons 题意： Alex高中毕业了，他现在是大学新生。虽然他学习编程，但他还是要上体育课，这对他来说完全是一个意外。快要期末了，但是不幸的Alex的体育学分还是零蛋！ Alex可不希望被开除，他想知道到期末还有多少天的工作日，这样他就能在这些日子里修体育学分。但是在这里计算工作日可不是件容易的事情： 从现在到学期结束还有\(n\)天(从\(1\)到\(n\)编号)，他们一开始都是工作日。接下来学校的工作人员会依次发出\(q\)个指令，每个指令可以用三个参数\(l,r,k\) 如果\(k=1\)，那么从\(l\)到\(r\)（包含端点）的所有日子都变成...

\(CNTPRIME\)\(Counting\)\(Primes\) 题目描述 给定初始序列\(A\)，然后对原序列有以下操作： 操作\(1\)：0lrv将区间\([l,r]\)全赋值为\(v\)。 操作\(2\)：1lr查询区间\([l,r]\) 注意：多组测试和特殊的输出。 题目分析： 就是一道板子题，首先我们先用欧拉筛筛出值域\([2,10^6]\)内的素数并开桶打标记（实际上一个欧拉筛就行了）。 此时，线段树维护的是当前区间内质数的个数，我们可以将操作\(1\) 若\(v\)属于质数，则将区间\([l,r]\)内的数全赋值成\(1\)。 若\(v\)不属于质数，则将区间\([l,...

\(T125847\) 题目背景 注意：请注意时间限制是800ms请使用较快的输入输出 注意：空间限制是128MB请不要开longlong 时限在std的2.5倍以上 题目描述 有一个有\(1000000000\)个数的初始值全为\(0\)的区间，你要进行两种操作： 将某区间每一个数加上 \(x\) 求出某区间每一个数的和 输入格式 第一行包含一个正整数\(x,p\)，表示操作个数和模数接下来\(m\)行，每行包含3或4个整数，1xyz表示将\([x,y]\)内每个数加\(z\)，2xy表示求\([x,y]\)内每个数的和对\(p\)取模的结果 输出格式 输出包含若干行，为操作\(2...

\(P1253\) 一、题目描述 给定一个长度为\(n\)的序列\(a\)，要求支持如下三个操作： 给定区间\([l,r]\)，将区间内每个数都修改为\(x\)。 给定区间\([l,r]\)，将区间内每个数都加上\(x\)。 给定区间\([l,r]\)，求区间内的最大值。 输入格式 第一行是两个整数，依次表示序列的长度\(n\)和操作的个数\(q\)。第二行有\(n\)个整数，第\(i\)个整数表示序列中的第\(i\)个数\(a_i\)。接下来\(q\)行，每行表示一个操作。每行首先有一个整数\(op\)，表示操作的类型。 若\(op=1\)，则接下来有三个整数\(l,r,x\)，表示...

\(P1966\) 一、题目描述 涵涵有两盒火柴，每盒装有\(n\) 其中\(a_i\)表示第一列火柴中第\(i\)个火柴的高度，\(b_i\)表示第二列火柴中第\(i\) 每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对\(10^8-3\) 输入格式 共三行，第一行包含一个整数\(n\)，表示每盒中火柴的数目。 第二行有\(n\) 第三行有\(n\) 输出格式 一个整数，表示最少交换次数对\(10^8-3\) 样例1 样例输入1 4 2314 3214 样例输出1 1 ...

\(P3374\) include<bits/stdc.h> usingnamespacestd; constintN=51e5+10; intn,m; inta[N]; //树状数组模板 definelowbit(x)(x&-x) intc[N]; voidadd(intx,intv){ while(x<N)c[x]+=v,x+=lowbit(x); } intsum(intx){ intres=0; while(x)res+=c[x],x-=lowbit(x); returnres; } intmain(){ cin>>n>>m; ...

2023.8.20_码客行_编程公益课在线评估 师大附小六年级学生有\(400\)名学生参加期末测试，平均\(92\)分，其中男生的平均分为\(96\)分，女生的平均分为\(80\)分，参加竞赛的男生比女生多多少人？ include<iostream> usingnamespacestd; intmain() { cout<<"男生比女生多"<<200<<"人。"<<endl; return0; } 解：简单方程，略 奇奇和马克在学习进位加法，可是他俩还是喜欢不进位的计算。于是他俩想知道\(0\)\(5999\)中有多少个数...

\(P5490\) 一、题目描述 求\(n\) 输入格式 第一行一个正整数\(n\)。 接下来\(n\)行每行四个非负整数\(x_1,y_1,x_2,y_2\)，表示一个矩形的四个端点坐标为\((x_1,y_1),(x_1,y_2),(x_2,y_2),(x_2,y_1)\)。 输出格式 一行一个正整数，表示\(n\) 样例输入 2 100100200200 150150250255 输出样例 18000 提示 对于\(20\%\)的数据，\(1\len\le1000\)。对于\(100\%\)的数据，\(1\len\le{10}^5\)，\(0\lex_1<x_2\le{10}...

\(HDU\)\(1828\)\(Picture\) 题目大意 求所有矩形组成的不规则图形的边长总和是多少。 扫描线扫描周长 扫描线扫描周长比扫描面积要麻烦一些,需要解决的问题有两个 如何统计每条竖线(也就是平行于\(y\)轴的线段的长度) 如何统计每条横线(也就是平行于\(x\)轴的线段的长度) 如图 1、统计每条竖线 我们发现每次扫描线扫描后投影到根节点的总长度与上次扫描所投影的总长度的绝对值之差就是本次扫描所多出的边长。 注：如果不是很理解，就尝试自己是从左到右的扫描线，模拟走一下就明白了 2、统计每条横线 解决这个问题的方法有两种 ①与解决第一种方法一样，将扫描线从下至上扫...

\(P1204\)[\(USACO1.2\)]挤牛奶\(Milking\)\(Cows\) 题目描述 三个农民每天清晨\(5\) 第一个农民在\(300\)秒(从\(5\)点开始计时)给他的牛挤奶，一直到\(1000\)秒。第二个农民在\(700\)秒开始，在\(1200\)秒结束。第三个农民在\(1500\)秒开始，\(2100\) 期间最长的至少有一个农民在挤奶的连续时间为\(900\)秒(从\(300\)秒到\(1200\)秒)，而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为\(300\)秒(从\(1200\)秒到\(1500\) 你的任务是编一个程序，读入一个有\(n\)个...

\(P3740\)\([HAOI2014]\) 一、题目描述 \(Bytetown\)城市要进行市长竞选，所有的选民可以畅所欲言地对竞选市长的候选人发表言论。为了统一管理，城市委员会为选民准备了一个张贴海报的\(electoral\)墙。 张贴规则如下： \(electoral\)墙是一个长度为\(N\)个单位的长方形，每个单位记为一个格子； 所有张贴的海报的高度必须与\(electoral\)墙的高度一致的； 每张海报以“\(A\)\(B\)”表示，即从第\(A\)个格子到第\(B\)个格子张贴海报； 后贴的海报可以覆盖前面已贴的海报或部分海报。 现在请你判断，张贴完所有海报后，在\(e...

\(LOJ\10115\).「一本通4.1例3」校门外的树 一、题目描述 校门外有很多树，学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两种操作： \(K=1\)，读入\(l,r\)表示在\(l\)到\(r\) \(K=2\)，读入\(l,r\)表示询问\(l\)到\(r\)之间有多少种树。注意：每个位置都可以重复种树。 输入格式第一行\(n,m\)表示道路总长为\(n\)，共有\(m\)个操作；接下来\(m\)行为\(m\) 输出格式对于每个\(k=2\) 二、题目解析 开始怎么想都不知道怎么维护不同段中树的种类是否相同的情况，感觉这题有个思维技巧还是挺...

\(P2345\) 一、题目描述 约翰的\(N\)头奶牛每年都会参加哞哞大会。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第\(i\)头奶牛的坐标为\(X_i\)，没有两头奶牛的坐标是相同的。奶牛们的叫声很大，第\(i\)头和第\(j\)头奶牛交流，会发出\(max(V_i,V_j)×|X_i−X_j|\)的音量，其中\(V_i\)和\(V_j\)分别是第\(i\)头和第\(j\),头奶牛的听力。假设每对奶牛之间同时都在说话，请计算所有奶牛产生的音量之和是多少。 \(Input\)第一行：单个整数\(N\) 第二行到第\(N+1\)...