TitanZhang

题解

算法浅谈(1)

/ 注册

全部文章 / 题解（共48篇）

2020牛客暑期多校训练营（第三场） F Fraction Construction Problem 来自专栏

题目大意有t(1≤t≤105)次查询，每个查询给出两个正整数a,b（a，b≤2×106）。输出一组满足以下条件的四个正整数c,d,e,f：如果没有解决方案，输出“ -1 -1 -1 -1”。解题思路进行赛后冷静分析，可以归纳出三种情况，这三种情况只需在代码...

拓展欧几里得

2020-07-19

2 595

2020牛客暑期多校训练营（第三场） C Operation Love 来自专栏

题目大意爱丽丝右手掌的形状如下：按顺时针或逆时针顺序给出手掌每个端点的平面坐标，输出每个手印是左手还是右手。形状可以旋转和平移，但是不会被放大或缩小。爱丽丝的左手掌形状与她的右手掌对称。解题思路由于各边的长度不会被放大...

计算几何

2020-07-19

6 889

2020牛客暑期多校训练营（第三场） A-Clam and Fish 来自专栏

题目大意一个游戏包含n个阶段，每个阶段有四种类型：类型0：没有鱼也没有蛤。类型1：只有一只蛤。类型2：只有一条鱼。类型3：有一条鱼和一只蛤。在每个阶段都可以执行四种操作之一： 1.用一只蛤换一包鱼饵。 2.如果有一条鱼，可以无需鱼饵抓到这条鱼。 3.无论在...

模拟

2020-07-18

5 1197

2020牛客暑期多校训练营（第二场） G-Greater and Greater 来自专栏

题目大意给定一个长n的数列A和一个长m的数列B，要求计算有多少个A中长为m的子串C，每个C[i]分别>=B[i]。以样例为例： 1 4 2 8 5 7 2 3 3 这里就有2,8,5和8,5,7符合条件。解题思路先附上出题人...

dp bitset

2020-07-16

1 718

2020牛客暑期多校训练营（第二场） J Just Shuffle 来自专栏

题目大意给一个长度为n的排列A={1,2,3,...,n}以及置换的次数k，在对A使用k次置换P后得到新的排列B。（整理：A是原排列，P是置换，B是目标排列，k是次数）输入n,k和B，输出A，如果无解输出-1。（规定k是大质数，108≤k≤109，说明K一定存在逆元，不会出现无解的情...

置换群

2020-07-15

5 799

2020牛客暑期多校训练营（第二场）F-Fake Maxpooling 来自专栏

题目大意给定整数n,m,k，构造一个n×m的矩阵A，其中Ai,j = lcm(i,j)，第i行j列的数是i和j的最小公倍数。求所有k×k个子矩阵中的最大值之和。解题思路先用尽可能快的操作将整张表求出来，接下来用单调队列。（附上大佬详解链接https://www.c...

单调队列双端队列

2020-07-14

2 716

2020牛客暑期多校训练营（第二场）C-Cover the Tree 来自专栏

题目大意给定一棵无根树，连接其中两个节点组成一条链，使树中的每一条边至少被一条链覆盖。输出最少的链数量+其中任何一个解决方案。解题思路先引用原题的一个（水）测试样例： 5 <--节点数量 1 2 <--节点中连的边（节点数量-1条） 1 3 2 4 2 5 可以...

DFS 构造

2020-07-14

3 830

HDU6667 Roundgod and Milk Tea

原题： Description Roundgod is a famous milk tea lover at Nanjing University second to none. This year, he plans to conduct a milk tea festi...

贪心

2020-07-12

1 843