11D_Beyonder's Blog

传送门 ↬\looparrowright↬ Problem Description Although winter is far away, squirrels have to work day and night to save beans. They need plenty of food to get through those long cold days. After some time the squirrel family thinks that they have to solve a problem. They suppose that they will save beans in nnn different trees. However, since the food is not sufficient nowadays, they will get no more than mmm beans. They want to know that how many ways there are to save no more than mmm beans (they ...

简介 对于一元线性同余方程组 $\left\{\begin{array}{c} x \equiv a_{1}\left(\bmod m_{1}\right) \\ x \equiv a_{2}\left(\bmod m_{2}\right) \\ \vdots \\ x \equiv a_{n}\left(\bmod m_{n}\right) \end{array}\right.$，中国剩余定理的适用条件是 m1,m2,⋯ ,mnm_1,m_2,\cdots,m_nm1​,m2​,⋯,mn​ 两两互质。 扩展中国剩余定理适用于 m1,m2,⋯ ,mnm_1,m_2,\cdots,m_nm1​,m2​,⋯,mn​ 不是两两互质的情况。 求解 考虑前方程组前两个方程，$\left\{\begin{array}{c} x \equiv a_{1}\left(\bmod m_{1}\right) \\ x \equiv a_{2}\left(\bmod m_{2}\right)\end{array}\right.$，一定存在整数 p,qp,qp,q，使得 x=m1p+a1=m2q+a2x=m_ ...

来源 中国剩余定理，英文为 Chinese Remainder Theorem\text{Chinese Remainder Theorem}Chinese Remainder Theorem，简称 CRT\text{CRT}CRT。最早见于《孙子算经》中：“有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”故又称孙子定理。 算法简介 适用条件 中国剩余定理可求解如下的一元线性同余方程组，其中 m1,m2,⋯ ,mnm_1,m_2,\cdots,m_nm1​,m2​,⋯,mn​ 两两互质。 $$ (S):\left\{\begin{array}{c} x \equiv a_{1}\left(\bmod m_{1}\right) \\ x \equiv a_{2}\left(\bmod m_{2}\right) \\ \vdots \\ x \equiv a_{n}\left(\bmod m_{n}\right) \end{array}\right. $$ 定理 假设整数 m1,m2,⋯ ,mnm_1,m_2,\cdots ,m_nm1​,m2​,⋯,mn​ 两两互 ...

传送门 ↬\looparrowright↬ 题目描述 对于给出的 nnn 个询问，每次求有多少个数对 (x,y)(x,y)(x,y)，满足 a≤x≤ba \le x \le ba≤x≤b，c≤y≤dc \le y \le dc≤y≤d，且gcd⁡(x,y)=k\gcd(x,y) = kgcd(x,y)=k，gcd⁡(x,y)\gcd(x,y)gcd(x,y) 函数为 xxx 和 yyy 的最大公约数。 输入格式 第一行一个整数 nnn，接下来 nnn 行每行五个整数，分别表示 a,b,c,d,ka,b,c,d,ka,b,c,d,k。 输出格式 共 nnn 行，每行一个整数表示满足要求的数对 (x,y)(x,y)(x,y) 的个数。 输入输出样例 输入 #1 2 2 5 1 5 1 1 5 1 5 2 输出 #1 14 3 说明/提示 对于 100%100\%100% 的数据满足：1≤n,k≤5×1041 \le n,k \le 5 \times 10^41≤n,k≤5×104，1≤a≤b≤5×1041 \le a \le b \le 5 \times 10^41≤a≤b≤5 ...

传送门 ↬\looparrowright↬ 题目描述 小 aaa 有 nnn 个数 a1,a2,...,ana_1, a_2, ..., a_na1​,a2​,...,an​，给出 qqq 个询问，每次询问给出区间 [l,r][l, r][l,r]，现在请你找到一个数 xxx，使得 ∑i=lrx⊕ai\sum\limits_{i = l}^r x \oplus a_ii=l∑r​x⊕ai​最大，要保证 0≤x<2310 \le x < 2^{31}0≤x<231。 输入描述 第一行一个整数 nnn，表示序列的长度。第二行 nnn 个整数，表示序列内的元素。第三行一个整数 qqq，表示询问的个数。接下来 qqq 行，每行两个整数 l,rl,rl,r，表示询问的区间。 输出描述 输出 qqq 行，每行一个整数表示答案。若有多组可行解，请输出较小的解。 示例1 输入 5 4 78 12 1 3 3 2 5 1 4 3 3 输出 2147483632 2147483635 2147483635 备注 对于 $30\%$ 的数据，n,q≤10n, q ≤ 10n,q ...

传送门 ↬\looparrowright↬ 题目描述 弱弱有两个属性 aaa 和 bbb，这两个属性初始的时候均为 000，每一天他可以通过努力，让 aaa 涨 111 点或 bbb 涨 111点。 为了激励弱弱努力学习，我们共有 nnn 种奖励，第 iii 种奖励有 xi,yi,zix_i,y_i,z_ixi​,yi​,zi​ 三种属性，若 a≥xia≥ x_ia≥xi​ 且 b≥yib≥ y_ib≥yi​，则弱弱在接下来的每一天都可以得到 ziz_izi​ 的分数。 问 mmm 天以后弱弱最多能得到多少分数。 输入描述 第一行一个两个整数 nnn 和 mmm(1≤n≤1000,1≤m≤2000000000)(1≤ n≤ 1000,1≤ m≤ 2000000000)(1≤n≤1000,1≤m≤2000000000)。 接下来 nnn 行，每行三个整数 xi,yi,zix_i,y_i,z_ixi​,yi​,zi​(1≤xi,yi≤1000000000,1≤zi≤1000000)(1≤ x_i,y_i≤ 1000000000,1≤ z_i ≤ 1000000)(1≤xi​,yi​≤1 ...

实验目的 帮助学生掌握一位全加器的实现逻辑，掌握多位可控加减法电路的实现逻辑，熟悉 Logisim\text{Logisim}Logisim 平台基本功能，能在 Logisim\text{Logisim}Logisim 中实现多位可控加减法电路。 主要任务 在 Logisim\text{Logisim}Logisim 中打开 alu.circ\text{alu.circ}alu.circ 文件，在对应子电路中利用已经封装好的一位全加器设计 888 位串行可控加法电路。定义 X,YX,YX,Y 为两输入数字，SubSubSub 为加减控制信号，SSS 为运算结果输出，CoutCoutCout 为进位输出，OFOFOF 为有符号运算溢出位。 实验原理 利用一位全加器作为基本的加法单元，低位 FAFAFA 的进位输出直接送入相邻的高位 FAFAFA 的进位输入，构成一个串行进位链。 SubSubSub 为 000 时，实现的是 888 位串行加法器。SubSubSub 为 111 时，要实现 X−YX-YX−Y。若实现的是减法，YYY 需要转化成其补码形式（按位取反再加 111），实现方式是 ...

实验目的 掌握快速加法器中先行进位的原理，能利用相关知识设计四位先行进位电路，并利用设计的四位先行进位电路构造四位快速加法器，能分析对应电路的时间延迟。 主要任务 在 Logisim\text{Logisim}Logisim 中打开 alu.circ\text{alu.circ}alu.circ文件，按照定义的输入输出引脚，在对应子电路中实现可级联的四位先行进位电路。其中，Gi,PiG_i,P_iGi​,Pi​ 是进位生成函数和传递函数，CinCinCin 为进位输入，C1∼C4C_1\sim C_4C1​∼C4​ 为进位输出，G∗,P∗G^\ast,P^\astG∗,P∗ 为成组进位生成函数和成组进位传递函数。 实验原理 对于 X+YX+YX+Y 的运算结果 SSS 的第 iii 位 SiS_iSi​，有 Si=Xi⊕Yi⊕Ci−1S_i=X_i\oplus Y_i\oplus C_{i-1}Si​=Xi​⊕Yi​⊕Ci−1​（Ci−1C_{i-1}Ci−1​ 为前一位的进位输出）。对于 CiC_iCi​，若 Xi=Yi=1X_i=Y_i=1Xi​=Yi​=1，则产生进位；若 Xi⊕ ...

传送门 ↬\looparrowright↬ 题目描述 在一个圆形操场的四周摆放 NNN 堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的 222 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。 试设计出一个算法,计算出将 NNN 堆石子合并成 111 堆的最小得分和最大得分。 输入格式 数据的第 111 行是正整数 NNN，表示有 NNN 堆石子。 第 222 行有 NNN 个整数，第 iii 个整数 aia_iai​ 表示第 iii 堆石子的个数。 输出格式 输出共 222 行，第 111 行为最小得分，第 222 行为最大得分。 输入输出样例 输入 #1 4 4 5 9 4 输出 #1 43 54 说明/提示 1≤N≤1001\leq N\leq 1001≤N≤100，0≤ai≤200\leq a_i\leq 200≤ai​≤20。 分析 由于石子摆在圆形操场的四周，因此 nnn 堆石子会摆放成一个环，于是不妨将 nnn 堆石子复制一份，使得 ai=ai+na_i=a_{i+n}ai​=ai+n​。 定义 dpmin[i][j]dp_{min}[i][j] ...

传送门 ↬\looparrowright↬ 题目描述 设有N堆沙子排成一排，其编号为 1,2,3,…,N(N≤300)1,2,3,\dots,N(N\leq 300)1,2,3,…,N(N≤300)。每堆沙子有一定的数量，可以用一个整数来描述，现在要将这 NNN 堆沙子合并成为一堆，每次只能合并相邻的两堆，合并的代价为这两堆沙子的数量之和，合并后与这两堆沙子相邻的沙子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同，如有 444 堆沙子分别为 1,3,5,21, 3 ,5, 21,3,5,2，我们可以先合并 1,21,21,2 堆，代价为 444 ，得到 4,5,24, 5, 24,5,2， 又合并 1,21,21,2 堆，代价为 999，得到 9,29, 29,2 ，再合并得到 111，总代价为 4+9+11=244+9+11=244+9+11=24，如果第二步是先合并 2,32,32,3 堆，则代价为 777，得到 4,74,74,7，最后一次合并代价为 111111，总代价为 4+7+11=224+7+11=224+7+11=22。问题是：找出一种合理的方法，使总 ...