题目链接 https://ac.nowcoder.com/acm/contest/7412/D 解题思路 （来自：zzugzx）对于二进制的某一位来说，a xor b表示不进位的加法，a & b<<1可以表示加法的进位。所以就有了公式a+b=a xor b+2∗(a & b)。通过这个公式可以直接计算(a xor b)，但是需要排除两种不能被组成的情况：一个就是计算出来的(a xor b)<0；另一个就是a & b和a xor b肯定是取反的，真值表可知除同为0的情况，其他情况下，二者永远相反，所以若不相反说明不存在a，b。如果都满足说明给出的a+b和...

题目链接 https://ac.nowcoder.com/acm/contest/7412/I 解题思路 我的思路： 建立set容器dp[i][j]，存储的是位于(i,j)时所有不同的权值和。访问到(i,j)位置时，遍历(i-1,j)位置所有不同的权值和，再遍历(i,j-1)位置的权值和，把他俩位置中的权值和逐个与(i,j)位置的权值相加取模并insert进dp[i][j]中。我代码运行时间比较短的原因在于 if(dp[i][j].size()>=mod){cout<<mod<<endl;return 0;}，含义为如果在循环到(n,m)位置之前已经有某个位置所含...

题目链接 https://ac.nowcoder.com/acm/contest/7412/G 题目大意 字符串匹配。 解题思路  我的KMP详讲 更新于2020.10.21一上来就想暴力，明知道暴力不行，还是想试试，毕竟不会别方法了。果不其然，过了80多的数据，没AC。正解：KMP！（没听说过，百度了一下，发现真的是巨难！用了3h才勉强理解，但是代码还是自己写不出来，背过的）（我实在讲不明白，直接放弃自己手写）（教会我KMP的大佬讲解） 就本题而言，无非是把牛牛喜欢的字符串S作为模式串（即由j控制的字符串），多组输入的字符串作为文本串（即由i控制的字符串），同时在KMP函数里统计一下匹配到的...

题目链接 https://ac.nowcoder.com/acm/contest/7412/J 题目大意 挺明了的吧。 解题思路 并查集！挺明显的吧。连通的区域属于一个整体，这种类型就用并查集。 如果不知道并查集，看看这个于本题而言，S1：把相同类型结点之间的边join一下，不同类型结点之间即使有边，我们也不join，因为不同类型的结点根本不可能属于一个连通区域。S2：可是现在并非同属于一个连通区域的结点的根都相同，不信的话你可以跑一下AC代码下面注释掉的样例，结点1，2，3，4应该是相连的，即同属于一个连通区域，但是，如果循环输出fa的话会发现并非他们的fa都存的同一个结点，所以结果也出现了...

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=2147 解题思路  博弈论基础讲解及类似题目题解  AC代码 #include<bits/stdc++.h> using namespace std; const int B=2005; bool mp[B][B]; int main(){ int n,m; for(int i=B-5;i>=1;i--) for(int j=1;j<=B-5;j++){ if((i&1)&&(j&1)) mp[i][j]=1;//i与j同为奇数时 } whil...

题目链接 https://ac.nowcoder.com/acm/contest/7412/B 题目大意 棋盘左上角为(0,0)，在棋盘的(x,y)位置有一枚棋子，牛牛先移动，牛可乐再移动，轮流进行。规定：每只牛都采用最优移动策略，且每次移动只能向上移动1个或2个格，或者向左1个或2个格（不存在“左移1+上移1”的操作）。规定先无法移动的牛输。 解题思路 博弈论。（我也是刚听说）正好借此机会学习并讲解一下。 博弈论 必败点（P点）：前一个选手(Previous player)将取胜的位置称为必败点，即谁先走到这个位置谁赢。必胜点（N点）：下一个选手(Next player)将取胜的位置称为必胜...

题目链接 https://ac.nowcoder.com/acm/contest/7412/A 解题思路 快速幂，费马小定理，快读函数，这仨就够用了。本题而言，牛牛输的概率为1-1/(n^m)=(n^m-1)/(n^m)费马小定理得(b/a)%p=(ba^(p-2))%p，对应到本题上来，(n^m-1)/(n^m)%p=((n^m-1)(n^m)^(p-2))%p这样看公式实在别扭，还是写一下吧。  知识点详解 之前小白月赛25的D题与这个十分类似，而且当时写的特别详细，所以这次就不写了，直接给大家链接了。 小白月赛25D题 【模板】有理数取余（小白版）  AC代码 #include<b...

题目链接 https://vjudge.net/contest/394826#problem/E 解题思路 先求出每两个数的和，再循环所有的数，判断是否存在等于两数和相反数的数且此数与求和两数不相等，那么这就是一组答案，将这组答案从小到大排序，得到所有情况，最后按要求输出最终答案。 AC代码 #include<bits/stdc++.h> #define ll long long using namespace std; const int N=2010; map<ll,ll> mp; int n,m; ll num[N]; struct ANS{ ll f[5]; }...

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1427 解题思路 看到题一脸懵，这直接枚举吗？居然是dfs！ 大佬题解之所以，我没写题解，是因为我觉得自己的理解也不是很透彻。 AC代码 #include<bits/stdc++.h> using namespace std; int flag=0; int card[5]; char s[3]; void convert(int i){ if(s[0]=='A') card[i]=1; else if(s[0]=='J') card[i]=11; else if(s[0]=='Q') ...

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1106 解题思路 代码里唯一注意的一点是多组数据 AC代码 #include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e3+10; char str[N]; int ans[N]; int main(){ while(cin>>str+1){ int num=0; int len=strlen(str+1); int t=1,p=len; while(str[t]=='5'&a...

题目链接 A：简：https://vjudge.net/contest/395157#problem/AB：稍难：https://vjudge.net/contest/395157#problem/B 题目大意 A：给m，n求m * n的网格能有多少个矩形，2 * 3与3 * 2算一个。B：给m，n求m * n的网格有多少个正方形，例如：4 * 3的网格中1 * 1的正方形有12个，2 * 2的正方形有6个，3 * 3的正方形有2个。A题只关心长宽，长宽相同就算一个，B题任意一个正方形就算是一个。 解题思路 A：找规律。看看数据规模，m，n都是1e9，不出意外应该无法靠循环累加求出，所以直接找...

题目链接 https://vjudge.net/contest/394826#problem/F 题目大意 求与7无关数的平方和。与7无关：不能被7整除，十进制各个位不含7。 解题思路 前缀和，太简单了。这不是我想讲的。 WA代码 #include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e6+10; ll n,t; ll ans[N]; bool is_7(int x){ if(x%7==0) return 1; while(x){ if(x%10==7) return 1; x/...

题目链接 https://www.dotcpp.com/oj/problem1115.html 解题思路 瞎搞就行，但是我瞎搞了好久，才做出这个水题的，而且根本没注意到是大写X，wa了n次，看了看题解才发现是大写。找规律的题。我的思路：分五部分输出，输出一行那种第一个x前没空格的行；输出上半部分除去首行和单独一个x的行剩下的行；输出单独的x行；输出下半部分除去尾行和单独一个x的行剩下的行；输出一行那种第一个x前没空格的行。大佬思路：分两部分输出，上半部分输出第1行第(a-1)/2行，下半部分输出第(a+1)/2行第a-1行，看看每一行第一个x前空格个数与行号的关系，看看每一行两个x之间空格个数...

题目链接 https://www.dotcpp.com/oj/problem1607.html 题目大意 计算2^p-1位数，及低500位数，输出。 解题思路 2的p次方，快速幂吧！只不过快速幂中的乘，得换成高精度乘法了。先看看快速幂的板子吧 还不知道啥是快速幂看看这个吧  ll ksm(ll x,ll t){//快速幂 ll res=1; while(t>0){ if(t&1LL) res=res*x%mod; t>>=1; x=x*x%mod; } return res; }类比一下，乘换成高精度，把取模操作去掉。 我的AC代码 直接对着代码讲吧，方便理解。先整体...