题目 思路：将此坐标转化为直角坐标系（纵坐标，横坐标），然后将六条路径优化，上cs = min(c6, c5 + c1), 下cx = min(c3, c4 + c2), 左cz = min(c5, c4 + c6), 右cy = min(c2, c3 + c1)。因为还有右上、右下的路径，所以干脆一并优化了 cys = min(c1, cy + cs), czs = cz + cs, cyx = cy + cx, czx = min(c4, cz + cx);//cys右上 czs 左上… 然后直接计算即可，详细看代码。 Code: #include<iostream> #...

题目 看到题目中山的数量最多只有100，那么我们直接暴力模拟O(N^2)，对于每一个石块都从第一座山放下去，如果发现有前面的山高于自己则将自己所在的山高度加一，再开始下一块石块，如果有一块石块在这个过程中没发现有比当前山高的顺利度过了所有山那么直接输出-1，结束。如果当到了最后一块石块，则记录最后一个填补的位置，输出即可。 #include<iostream> #include<memory.h> using namespace std; typedef long long ll; const int Max = 1e3 + 5; int h[Max]; int ...

题目 思路： 对于失败有两种情况： 1.统计所有的需要修正成各种颜色的数目，如果发现对于一种颜色我们所拥有的画师数少于所需修正的数目，则失败。 2.我们会发现其实可能有画师会画不属于b[i]中所有的颜色，如果这个画师是最后一位画师（最后画）那么没有任何的画师可以在之后将他的画修改为正确颜色，失败。 再来分析成功的画师分配：对于每个需要修改颜色的地方用队列做位置记录，分配画师的时候队列不空就pop掉一个,空了的话就（也就是这种画师该修改的颜色位置已经全部修正完毕，该画师多余）直接修改最后一个画师的画，反正最后一个画师会将其修正为正确颜色，还要小心分析一下最后一个画师的位置，如果最后一个画师所...

题目 首先：对于gcd有 gcd(a,b)=gcd(a+b,b) 且若gcd(a,b)=1, 则gcd(a,c)=gcd(a,c*b)=gcd(a,c * b^n) 现有gcd(d1,d2)=1,->gcd(d1+d2,d1)=1,gcd(d1+d2,d2)=1 ->gcd(d1+d2,d1 * d2)=1,->gcd(d1+d2,d1^n * d2^n) 现在再来看题目要我们求什么，我们只需找到ai的两个互质因数d1,d2 , ai=d1^ n * d2可得gcd(d1,d2)=1,由如上性质gcd(d1+d2，d1^n*d2)=1,即gcd(d1+d2,ai)=1。 ...

题目 思路： 分为两种情况： 1.当m为奇数时，直接12121212…构造出的一定是回文。 2.当m为偶数时，可以知道n>=3时一定可以构造出。证明如下： 当1，2，3三个点中出现来回字母一样，只需两个点不断循环即可。 当无上述情况，来回必然是a,b交叉，因此我们一定可以找到如下的图。其实就是有连续两个a，1->2->3->1,或2->3->1->2，或3->1->2->3，这几种情况aab,aaa,aba…因为是循环的一定可以找出两个连续的a构成下图。（不懂可以自行模拟下过程） 当(m/2)%2 == 1 我们可以按序号123...

参考于此篇博客：https://www.cnblogs.com/kongbursi-2292702937/p/10582258.html 逆元定义： 对于a*b≡1(mod m)，b是a在模m下a的逆元。 首先对于同余符号≡，如 a≡b%m 表示的意思是a%m=b%m,a、b模m后余数相同。 逆元可以看作一个数的倒数 c * b≡1(mod m)(b为c的逆元) 可得(a/c)%m=(a*b)%m 推导过程：(a/c)%m=(a/c)*1%m=(a/c) * c * b%m=(a * b)%m 由费马小定理：a、m是互质的正整数，有a^(m-1)≡1(mod m) 可得：a的逆元为：...

题目 思路： 状态方程dp[i]代表从1–n都被照亮的方法数。 dp[i]=dp[i-1]+dp[i-3]+dp[i-5]+dp[i-7]… 可以看一个例子i=5，假设0表示没照亮1表示照亮 dp[5] 1到5都亮可以由以下状态转变而来 dp[4] 11110 在i=5处放亮度为1的灯 dp[2] 11000 在i=4处放亮度为2的灯 dp[0] 00000 在i=3处放亮度为3的灯 故dp[5]=dp[4]+dp[2]+dp[0] 再如dp[6]=dp[5]+dp[3]+dp[1] 所以我们只需将dp[i]下标分奇odd偶even记录当前的奇的下标方法总和和偶的下标方法总和一步步推导即可，...

题目 思路：对于为n的奇数，可以进行(n-1)/2次让一个数取代相邻两数操作，直到最后只剩下一个数，其实每次操作就是删掉了一个数，那要如何让删除后的总和最大？ 首先贪心一下，我们一定不能删掉变成了两个数相加的那个数，如 1 2 3 4 5 假设第一步删掉1 -> 7 3 4 那之后删掉的数不能是7 因为 再删7=删掉1 2 5相当于删去了3个数，我们可以对比删掉2 5一定优于删掉1 2 5。而要不删掉已经加过一次的数就一定要删掉不是相邻的数，问题就转化成了从n个数中删掉(n-1)/2个不相邻的数（首尾也相邻），那么剩下的数中一定有两个是相邻的，我们枚举每两个相邻的数，预先统计奇偶前缀和...

题目 思路： 看一个例子对于两个二进制数 1100101 0100100 AND结果：0100100 OR结果：1100101 如果两个二进制位都为1或0，AND OR 中结果不变还是1或0，如果一个是0 一个1，就会把1转到OR结果中AND中的那个位变为0。我将这个过程看作是一个让1往一个数(OR结果)分配的过程，所有二进制每个位总的个数不变，但通过上述操作可以让1集中到一个数上面，我们可以通过无限次操作总是拼出来一个大的数，相应的这个数花费的各个二进制位数减1，直到所有二进制位的个数耗尽，这样得出来的答案是最大的。 Code: #include<iostream> usi...

题目 题解： 因此c=(a*a-1)/2+1 我们暴力枚举a,从a=1到（a * a-1)/2+1<=n (C需要<=n) 如果满足(a * a-1)%2==0，即b为整数，且c=b+1，C也为整数，符合条件，贡献+1 Code: #include<iostream> #include<cmath> #define pii pair<int,int> #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef lon...

题目 当n为奇数 ，构造第一人获胜情况前(n-1)/2项为1，后(n-1)/2项为-1，其余人的获胜情况就是前一人往后滚动一位 如：n=5 第一人对第二三四五人的情况 1 1 -1 -1 第二人对第一三四五人的情况 -1 1 1 -1 第三人对第一二四五人的情况 -1 -1 1 1 第四人对第一二三四人的情况 1 -1 -1 1 第五人对第一二三四人的情况 1 1 -1 -1 当n为偶数 ，构造第一人获胜情况前(n-1)/2项为1，中间那项为0，后(n-1)/2项为-1，其余人的获胜情况就是前一人往后滚动一位，同上 n=6 第一人 1 1 0 -1 -1 第二人 -1 1 1 0 ...

题目 状态：dp[i][j][k][o] 代表第i行前j个数已经选定k个数余o最大总和的值 首先来单独看一行，lst[i][j] 代表第i行第j个数 dp[i][j][k][o]=dp[i][j-1][k][o] , 此代表在第i行我们不选第j个数，所以选定的个数k不变，余数也不变 dp[i][j][k][o]=dp[i][j-1][k-1][(o-lst[i][j]+70p)%p] ，此代表第i行选择了第j个数，所以由选定数k-1转换而来，p是题目要求余的数，o-lst[i][j]表示，要想得到加了lst[i][j]从而得到o的余数那么之前的余数得是o-lst[i][j]，加上70p...

题目 思路：这是一道最长递增子序列的变式。 dp[i] 代表前i个名人中第i个名人被访问所能访问的最大名人数目 先看暴力的方法，那么我们直接遍历前面所有情况 当abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j] i<j 时dp[i]=max(dp[i],dp[j]+1) 但这时时间复杂度O(n^2) 会超时，我们需要优化一下 这时我们发现最大的距离不会超过2r-2，而对于每个名人出场的时间是递增的，也就是说一旦出场的名人相隔超过2r-2位那么他们相隔时间也超过了2r-2，那么对于一个事件来说我们只需要对2r-2个事件内进行遍历判断，在这之前...

题目 思路：首先将数组排个序，容易知道要看一个数能不能成为冠军，其实就是将这个数从小到大不断与比他小于等于的数合并相加如果最终能够合并为一个数则其有成为冠军的机会。 在这我们先看看暴力的思路，就是遍历每一个数然后让它与最小的数开始相加直到最终它不能再和后面的数相加（前面所有的总和都比后面的某个数小）或合并为一个数了，O（n^2）这毫无疑问会超时。 我们想如何进行优化，其实在这我们可以发现对于两个数a<b，a会一直把前面小的数加完 而b也会把a加的那一部分数再加一次，这就重复进行了操作，这时我们可以先从最小的那个数按从小到大开始加（预定冠军为最小的那个数），当发现后面有一个数b前面所...