DrGilbert-CSDN博客

原创上海大学第21届ACM程序设计联赛（春季赛）部分题解

出于某些原因，模拟了一下2023年上海大学ACM校赛练练手，随便写了几个题，整理一下自己的题解。题目地址。

2024-03-08 14:50:44 894 1

文章目录一般佩尔方程性质求最小解暴力写法连分数写法推广佩尔方程一般佩尔方程形如x2−Dy2=1(D>0)x^2-Dy^2=1(D>0)x2−Dy2=1(D>0)的方程，即为佩尔方程。性质1.容易得到，{x=±1y=0\begin{cases}x=\pm1\\y=0\end{cases}{x=±1y=0必是该方程的解。若DDD为平方数，则只有这种解，反之则有无数多组解。证明略，见百度百科。2.若一组解(x1,y1)(x_1,y_1)(x1,y1)是非(±1,0)(\pm1

2021-04-19 21:35:20 808

原创提前写给自己的退役留念（无任何学习干货）

写在前面虽然还剩下一场银川，但一想到自己还要准备考研，还是先来提前写了留念文章吧。打满感情牌的正文最近，在机房刷题累了的时候，总会想到十年前的那个酷暑难当的夏天。在书店里，一个胖乎乎的小孩走进机房，用肥嘟嘟的手从书包中抽出一本《Pascal入门教程》。在他面前的，是一片未知而又崭新的世界。他很幸运，在周围人因为太难而退缩时，他却在层层选拔中脱颖而出，还代表学校出去参加过三四次比赛。他很开心，他说，写代码就像是雕刻一块玉石，如同造物主般，赋予其新的姿态，新的生命。如果没有手艺人的雕琢，玉石即使再珍

2021-04-07 19:27:00 2569 9

原创个人用Java EE重点（待补充）

一、Java EE（Java 企业版）概述Java EE 依赖于 Java SE，SE提供语言基础，EE是SE的扩展可持久化实体类与企业JavaBeansJAVA EE 服务器/应用服务器实现Java EE API，并提供Java EE服务，以容器的形式提供服务。容器完成具体功能的工具以组建的形式“装入”一个容器之中（类似封装），保证耦合度Web容器Web组件与Web服务器之间的接口，提供访问上下文数据的接口EJB容器（对企业Java Beans管理）三层架构（通过依赖输入实现不同业务

2021-03-29 12:09:52 558

原创个人用设计模式重点（待补充）

一、基础知识统一建模语言（UML）基础知识通过图形符号与文字来对系统进行建模视图用户视图结构视图行为视图实现视图环境视图图用例图类图，对象图，包图，组合结构图状态图，活动图，顺序图，通信图，定时图，交互概览图组件图部署图用例图（需求分析）类图（数据&行为）静态结构，描述不同类与其之间的行为模型元素（事物&事物之间的联系）每一个模型元素都与一个图形元素相对应同一个模型元素可以在不同的UML图中使用面向对象设计原则可维护性&amp

2021-03-25 16:00:12 597

原创个人用数据结构重点（待补充）

一、绪论基本概念数据：信息载体，可以被计算机识别与处理（二进制0与1）数据元素：数据基本单位，由若干数据项组成数据结构：存在一种或多种特定关系的数据元素的集合数据对象：拥有相同性质的数据元素的集合，是数据的一个子集数据类型：值的集合，定义在此集合上的一组操作的总称（原子类型&结构类型）抽象数据类型：通常就是数据结构三要素逻辑结构集合（各元素同属一个集合，无其他关系）线性结构（元素之间是一对一的关系，有前驱与后继（头只有后继，尾只有前驱））树形结构：（元素是一对多的关系）图

2021-03-23 11:27:13 110

原创个人用操作系统重点（待补充）

操作系统概念控制和管理整个计算机的硬件与软件资源**（系统资源管理者，安全、高效）**提供给用户和其他软件方便的接口与环境（向上层提供方便易用的服务），用户无需关心底层实现原理，只需向操作系统发出命令即可。一个程序需要被放到内存中才能被CPU处理（内存是CPU唯一可直接接触的区域？）。操作系统功能处理器管理存储器管理文件管理设备管理操作系统提供服务GUI（图形化用户接口）联机命令接口/交互式命令接口(用户说一个，系统做一个)如:cmd脱机命令接口/批处理命令接口（用户说一堆，系统

2021-03-07 22:45:38 2033

原创 Zjgsu-CheckIn技术总结博客

本博客仅记录Zjgsu-CheckIn在开发中遇到的各类问题与对应解决方法。一：如何根据给定的json数据生成对应的二维码？解决方案：利用zxing（Java实现的多种格式的1D/2D条码图像处理库）先将对应的json数据转化为BufferedImage流，再将其根据一定尺寸生成base64的字符串，供前后台使用。二：如何在网页端导出表格供用户下载？解决方案：采用poi-ooxml（基于java的Excel处理软件）可以将对应的数据生成一个.xls的表格文件并提供给用户下载。三：管理员端连接

2021-01-14 20:47:52 209 1

原创 codeforces 862E (二分)

原题题面Dr. Evil is interested in math and functions, so he gave Mahmoud and Ehab array aaa of length nnn and array bbb of length mmm. He introduced a function f(j)f(j)f(j) which is defined for integers jjj, which satisfy 0 ≤j ≤ m − n0 \leq j \leq m - n0 ≤j ≤

2020-12-10 17:40:19 174

原创 Codeforces 1342E 二项式反演

原题题面Calculate the number of ways to place n rooks on n×n chessboard so that both following conditions are met:each empty cell is under attack;exactly kkk pairs of rooks attack each other.An empty cell is under attack if there is at least one rook in th

2020-12-05 18:34:59 247

原创 [HAOI2018] 染色二项式反演

原题题面为了报答小 C 的苹果, 小 G 打算送给热爱美术的小 C 一块画布, 这块画布可以抽象为一个长度为 NNN 的序列, 每个位置都可以被染成 MMM 种颜色中的某一种.然而小 C 只关心序列的 NNN 个位置中出现次数恰好为 SSS 的颜色种数, 如果恰好出现了 SSS 次的颜色有 KKK 种, 则小 C 会产生 WkW_kWk的愉悦度.小 C 希望知道对于所有可能的染色方案, 他能获得的愉悦度的和对 100453580910045358091004535809 取模的结果是多少.输入

2020-11-30 22:08:18 157

原创 Game of Cards 2020 CCPC 绵阳 G（博弈论+推导）

原题题面Little Rabbit and Little Horse love playing odd card games. Now, they are playing a card game called 0123-game.There are several cards on the table. c0c_0c0 of them are labeled with 000, c1c_1c1 of them are labeled with 111, c2c_2c2 of them are

2020-11-07 09:38:09 976

原创（个人复习用）概率论重点（待补充）

一、随机事件与概率1.1 基本概念随机试验：1.可在相同条件下重复进行2.每次结果不止一个，但可以事先明确所有可能结果3.每次不能确定哪一个出现互不相容（互斥，无法同时发生）：A∩B=∅A\cap B=\emptysetA∩B=∅(AB=∅AB=\emptysetAB=∅)对立事件（逆事件）：A∪B=S,AB=∅A\cup B=S,AB=\emptysetA∪B=S,AB=∅1.AAA与A‾\overline{A}A为对立事件2.对立事件也是互斥的，但反过来不一定对频率：1.非负性（任

2020-11-04 21:59:06 843

原创 Sqrt Approaching (数学推导+放缩)

原题题面Given three positive integers A,B,nA,B,nA,B,n, where nnn is NOT a perfect square number, you should find two positive integers C,DC,DC,D satisfying (BC−AD)(C−Dn)<0(BC - AD)(C - D\sqrt{n}) < 0(BC−AD)(C−Dn)<0输入格式The first line contains one i

2020-10-25 19:12:09 297 1

原创 HDU 6704 K-th occurrence 2019CCPC网络赛 (后缀数组+ST表+二分+主席树)

题面描述You are given a string S consisting of only lowercase english letters and some queries.For each query (l,r,k)(l,r,k)(l,r,k), please output the starting position of the k−thk-thk−th occurence of the substring SlSl+1...SrS_lS_{l+1}...S_rSlSl+1...Sr

2020-10-22 16:57:15 170

原创 POJ - 3693 Maximum repetition substring （后缀数组+ST表）

原题题面The repetition number of a string is defined as the maximum number R such that the string can be partitioned into R same consecutive substrings. For example, the repetition number of “ababab” is 3 and “ababa” is 1.Given a string containing lowercase

2020-10-20 21:19:05 129

原创 POJ 1743 Musical Theme（后缀数组+二分）

原题题面A musical melody is represented as a sequence of N(1≤N≤20000)N(1\leq N\leq 20000)N(1≤N≤20000)notes that are integers in the range 1…88, each representing a key on the piano. It is unfortunate but true that this representation of melodies ignores the n

2020-10-18 14:27:22 124

原创 URAL-1996 (KMP+FFT)

原题题面Leia: I have placed information vital to the survival of the rebellion into the memory systems of this R2 unit. My father will know how to retrieve it. You must see this droid safely delivered to him on Alderaan.Emperor Palpatine has been ruling the

2020-10-09 12:05:18 159

原创 HDU 4609 3-idiots(FFT)

原题题面King OMeGa catched three men who had been streaking in the street. Looking as idiots though, the three men insisted that it was a kind of performance art, and begged the king to free them. Out of hatred to the real idiots, the king wanted to check if

2020-10-08 21:17:34 253

原创 P3763 [TJOI2017]DNA (FFT)

原题题面加里敦大学的生物研究所，发现了决定人喜不喜欢吃藕的基因序列 SSS,有这个序列的碱基序列就会表现出喜欢吃藕的性状，但是研究人员发现对碱基序列 SSS，任意修改其中不超过 3 个碱基，依然能够表现出吃藕的性状。现在研究人员想知道这个基因在 DNA 链 S0S_0S0上的位置。所以你需要统计在一个表现出吃藕性状的人的 DNA 序列 S0S_0S0上，有多少个连续子串可能是该基因，即有多少个S0S_0S0的连续子串修改小于等于三个字母能够变成 SSS。输入格式第一行有一个整数TTT，表示有几组

2020-10-05 14:13:28 198

原创 P4157 [SCOI2006]整数划分（数学推导+大数）

原题题面读入一个正整数nnn（10≤n≤3100010≤n≤3100010≤n≤31000）。要求将nnn写成若干个正整数之和，并且使这些正整数的乘积最大。例如，n=13n=13n=13，则当n表示为4+3+3+34+3+3+34+3+3+3（或2+2+3+3+32+2+3+3+32+2+3+3+3）时，乘积=108108108为最大。输入格式只有一个正整nnn（10≤n≤3100010≤n≤3100010≤n≤31000）输出格式第1行输出一个整数，为最大乘积的位数。第2行输出最大乘积的前1

2020-10-04 16:23:06 262 1

原创 HDU 1079 Calendar Game（博弈论SG函数）

原题题面Adam and Eve enter this year’s ACM International Collegiate Programming Contest. Last night, they played the Calendar Game, in celebration of this contest. This game consists of the dates from January 1, 1900 to November 4, 2001, the contest day. The

2020-09-21 16:35:08 126

原创 P3384 树链剖分(树链剖分)

原题题面已知一棵包含 NNN 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：操作 111：格式：1 x y z1\ x\ y\ z1 x y z 表示将树从 xxx 到 yyy 结点最短路径上所有节点的值都加上 zzz。操作 222：格式： 2 x y2\ x\ y2 x y 表示求树从 xxx 到 yyy 结点最短路径上所有节点的值之和。操作 333：格式： 3&nbsp

2020-09-01 14:37:20 148

原创 HDU 6869 Slime and Stones (威佐夫博弈扩展)

原题题面Orac and Slime are playing a game.There are two groups of stones, the first group contains a stones and the second contains b stones. Orac and Slime operate them by turns in the game. For each operation, they have two choices:Pick up any number of

2020-08-18 17:52:52 592 1

原创 SPOJ-COT Count on a tree (LCA+可持久化线段树)

这里写自定义目录标题原题题面输入格式输出格式输入样例输出样例题面分析原题题面You are given a tree with NNN nodes. The tree nodes are numbered from 1 to NNN. Each node has an integer weight.We will ask you to perform the following operation:u v ku\ v\ ku v k : ask for the

2020-08-18 09:57:29 144 1

原创 Groundhog Chasing Death 2020牛客多校第九场（质因子分解+欧拉降幂）

原题题面As we all know,“Groundhog chasing death” means “GCD”,while “GCD” stands for “greatest common divisor”.So you need to calculate ∏i=ab∏j=cdgcd⁡(xi,yj)\prod_{i=a}^b\prod_{j=c}^d\gcd(x^i,y^j)∏i=ab∏j=cdgcd(xi,yj) modulo 998244353998244353998244353输入格式

2020-08-09 15:22:18 189

原创 HDU 6833 A Very Easy Math Problem（莫比乌斯反演）

原题题面Given you n,x,k , find the value of the following formula:∑a1=1n∑a2=1n...∑ax=1n(∏j=1xajk)f(gcd(a1,a2,...ax))∗gcd(a1,a2,...ax)\sum_{a_1=1}^{n}\sum_{a_2=1}^{n}...\sum_{a_x=1}^{n}(\prod_{j=1}^{x}a_{j}^{k})f(gcd(a_1,a_2,...a_x))*gcd(a_1,a_2,...a_x)∑a1=1

2020-08-07 17:17:30 267

原创 HDU 6588 Function 2019杭电多校第一场(莫比乌斯反演)

原题题面Jerry is fond of functions. He thinks the mystery of the universe is hidden behind the notations, variables and numbers.Of all functions, he thinks gcd and ⌊x⌋⌊x⌋⌊x⌋ are the most fascinating, and that something combines gcd with truncation should be

2020-08-07 15:13:46 277

原创 HDU 6825 Set1 2020杭电多校（数学推导）

原题题面You are given a set S=1..nS={1..n}S=1..n. It guarantees that nnn is odd. You have to do the following operations until there is only 111 element in the set:Firstly, delete the smallest element of SSS. Then randomly delete another element from SSS.Fo

2020-08-04 22:24:49 253

原创 HDU 6822 Paperfolding 2020杭电多校第五场（数学推导）

原题题面There is a piece of paper in rectangular shape with sufficient length and width (lay flat on the table). Execute an operation instruction according to a string of length n from left to right that only contains 4 different characters of L,R,U,DL,R,U,DL

2020-08-04 20:13:28 348

原创 HDU 6814 Tetrahedron 2020杭电多校第五场 (数学推导)

原题题面Generate three integers a, b, and c in [1,n][1,n][1,n] with equal probability independently, and use them as the three right-angle side length of a right-angled tetrahedron. Find the expectation of the reciprocal square of the distance from the right-

2020-08-04 19:23:26 484

原创 Game SET 2020牛客多校第八场（模拟）

原题题面SETSETSET is a real-time card game designed by Marsha Falco in 1974 and published by Set Enterprises in 1991. The deck consists of 81 unique cards that vary in four features across three possibilities for each kind of feature: number of shapes (one, t

2020-08-03 18:26:56 332

原创 HDU 6755 Fibonacci Sum (二项式定理+预处理) 2020杭电多校第一场

原题题面The Fibonacci numbers are defined as below:F0=0,F1=1F_0=0,F_1=1F0=0,F1=1Fn=Fn−2+Fn−1(n>1)F_n=F_{n-2}+F_{n-1}(n>1)Fn=Fn−2+Fn−1(n>1)Given three integers NNN, CCC and KKK, calculate the following summation:(F0)K+(FC)K+(F2C)K+(F3C)K...+(

2020-07-22 13:29:46 1483 3

原创 Harder Gcd Problem 2020牛客多校第四场（质数筛+构造）

原题题面给出一正整数nnn，找到{1,2,3,...,n}\{1,2,3,...,n\}{1,2,3,...,n}的两个子集合A,BA,BA,B，使：（1）∣A∣=∣B∣=m,A∩B=∅|A|=|B|=m,A∩B=∅∣A∣=∣B∣=m,A∩B=∅（2）令A={a1,a2...am},B={b1,b2,...bm}A=\{a_1,a_2...a_m\},B=\{b_1,b_2,...b_m\}A={a1,a2...am},B={b1,b2,...bm},存在两种排列方式{p1,p2,...p

2020-07-20 22:23:00 265

原创 Fraction Construction Problem 2020牛客多校第三场（扩展欧几里得）

原题题面有T个输入。每组输入给出两个正整数a,b(a,b≤2×106)a,b(a,b\leq 2 × 10^6)a,b(a,b≤2×106)。请找到四个正整数c,d,e,f(f<b,d<b,1≤c,e≤4×1012)c,d,e,f(f<b,d<b,1\leq c,e \leq 4× 10^{12})c,d,e,f(f<b,d<b,1≤c,e≤4×1012)，使他们满足:cd−ef=ab\frac{c}{d}-\frac{e}{f}=\frac{a}{b}dc−f

2020-07-18 19:54:58 1155 1

原创 Keyboard Free （计算几何+自适应辛普森积分/等分圆）2020牛客多校第二场

原题题面Given three concentric circles whose radiuses are r1r_1r1,r2r_2r2,r3r_3r3respectively, and A,B,CA,B,CA,B,C are the moving points on the given three circles respectively. Determine the expected area of △ABC\triangle ABC△ABC .输入描述The first line con

2020-07-14 22:01:32 1517 2

原创 Boundary 2020牛客多校第二场（计算几何）

原题题面Given nnn points in 2D plane. Considering all circles that the origin point (0,0)(0,0)(0,0) is on their boundries, find the one with the maximum given points on its boundry. Print the maximum number of points.输入描述The first line contains one integer

2020-07-13 22:22:50 491 4

原创 Easy Integration（Wallis积分）（2020牛客多校第一场J题）

原题题面时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 262144K，其他语言524288KGiven n, find the value of ∫01(x−x2)n dx\int_0^1 {(x-x^2)^n} \,{\rm d}x∫01(x−x2)ndx.It can be proved that the value is a rational number pq\frac{p}{q}qp.Print the result as p⋅q−1 mod 9

2020-07-12 19:04:44 1416

原创（个人复习用）jsp web开发重点（待补充）

文章目录一、 JSP简介Tomcat 相关JSP原理二、JSP语法JSP页面组成JSP注释JSP标记pagecontentType（响应类型、字符编码）language（JSP使用的脚本语言）import（声明包、类）session（是否需要session，默认是true）buffer（out的缓冲区大小，默认8kb,也可以设置为none，即不使用）autoflush（out缓冲区被填满时是否自动刷新，默认为true）isThreadSafe（是否可多线程访问，默认为true）info（为jsp准备一个常用

2020-06-14 15:26:26 621

原创洛谷 P6583 回首过去（数论+容斥定理）

写在前面笔者是一名十八线蒟蒻ACMer，文中可能会有多处错误与疏漏，欢迎指出。原题题面洛谷 P6583 回首过去给定正整数 nnn，求出有序整数对 (x,y)(x,y)(x,y) 的个数，满足：1≤x,y≤n,1≤x,y≤n1\leq x,y\leq n,1≤x,y≤n1≤x,y≤n,1≤x,y≤n 且xy\frac{x}{y}yx 可以表示为十进制有限小数。对于40%的数据,1≤n≤1031\leq n\leq 10^31≤n≤103，对于40%的数据,1≤n≤1071\leq n\leq

2020-06-02 18:58:23 422

空空如也

空空如也