本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderD - Tiling Plan【题目描述】Takahashi works at a renovation company and is responsible for covering room floors with square tiles.Takahashi has received requests to tile the floors ofN NNrectangular rooms. The floor of thei ii-th room has heightH i H_iHi​and widthW i W_iWi​.Takahashi wants to chooseexactly one type of square tileand use it to coverall room floors. In each room, tiles are placed parallel to the room’s edges without gaps or overlaps. The side length of the square tile must be a positive integer.The necessary and sufficient condition for a square tile with side lengthd ddto be able to tile the floor of roomi iiis that bothH i H_iHi​andW i W_iWi​are multiples ofd dd. In this case, the number of tiles used in roomi iiisC i H i d × W i d C_i \frac{H_i}{d} \times \frac{W_i}{d}Ci​dHi​​×dWi​​.Furthermore, due to design requirements, each room has a specified “design coefficient”S i S_iSi​. The number of tilesC i C_iCi​used in roomi iimust be a multiple ofS i S_iSi​.Takahashi wants to use tiles that are as large as possible. Find the maximum side lengthd ddof a square tile that simultaneously satisfies the above conditions for all rooms.高橋在一家装修公司工作负责用正方形瓷砖铺设房间地板。高橋收到了为N NN个矩形房间铺设地板的请求。第i ii个房间的地板高度为H i H_iHi​宽度为W i W_iWi​。高橋想选择恰好一种正方形瓷砖并用它来铺设所有房间的地板。在每个房间中瓷砖平行于房间的边放置不能有间隙或重叠。正方形瓷砖的边长必须是正整数。边长为d dd的正方形瓷砖能够铺设房间i ii的地板的充分必要条件是H i H_iHi​和W i W_iWi​都是d dd的倍数。此时房间i ii使用的瓷砖数量为C i H i d × W i d C_i \frac{H_i}{d} \times \frac{W_i}{d}Ci​dHi​​×dWi​​。此外由于设计要求每个房间有一个指定的设计系数S i S_iSi​。房间i ii使用的瓷砖数量C i C_iCi​必须是S i S_iSi​的倍数。高橋希望使用尽可能大的瓷砖。求能同时满足上述所有房间条件的正方形瓷砖的最大边长d dd。【输入】N NNH 1 H_1H1​W 1 W_1W1​S 1 S_1S1​H 2 H_2H2​W 2 W_2W2​S 2 S_2S2​⋮ \vdots⋮H N H_NHN​W N W_NWN​S N S_NSN​The first line contains an integerN NNrepresenting the number of rooms.From the 2nd line to the( N 1 ) (N 1)(N1)-th line, information about each room is given.The( 1 i ) (1 i)(1i)-th line contains the heightH i H_iHi​, widthW i W_iWi​, and design coefficientS i S_iSi​of thei ii-th room, separated by spaces.【输出】Output in one line the maximum value of the side lengthd ddof a square tile that satisfies the conditions.【输入样例】2 6 8 6 10 12 15【输出样例】2【算法标签】#欧几里得算法【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglong// 将 int 定义为 long long防止乘法溢出constintN100005;// 最大房间数量intn;// 房间数量inth[N],w[N],s[N];// h[i]: 房间i高度, w[i]: 房间i宽度, s[i]: 房间i设计系数vectorintdivisors;// 存储所有可能的候选边长d// 检查边长d是否满足所有房间的条件// 条件对每个房间i(H_i/d) * (W_i/d) 是 S_i 的倍数boolcheck(intd){for(inti1;in;i){// 计算房间i使用的瓷砖数量并检查是否为S_i的倍数// 注意由于d是gcd的因子H_i和W_i一定是d的倍数所以除法是整除if((h[i]/d*w[i]/d)%s[i]!0)returnfalse;// 不满足条件}returntrue;// 所有房间都满足}signedmain()// 使用 signed 替代 int因为 #define int long long{cinn;// 读入房间数量intg0;// g: 所有房间(H_i, W_i)最大公约数的GCD// 读入每个房间的信息for(inti1;in;i){cinh[i]w[i]s[i];// 计算房间i的高度和宽度的GCDintgi__gcd(h[i],w[i]);// 所有房间GCD的GCD即d必须能整除所有H_i和W_i// 所以d必须是g的因子g__gcd(g,gi);}// 枚举g的所有因子作为候选边长dfor(inti1;i*ig;i){if(g%i0)// i是g的因子{divisors.push_back(i);// 小因子if(i*i!g)divisors.push_back(g/i);// 大因子避免重复}}// 按升序排序方便从大到小枚举sort(divisors.begin(),divisors.end());// 从大到小枚举候选边长找到第一个满足条件的即为最大边长for(intidivisors.size()-1;i0;i--){if(check(divisors[i])){coutdivisors[i]endl;// 输出最大满足条件的边长return0;}}return0;}【运行结果】2 6 8 6 10 12 15 2