[综合] 矩阵旋转模板

矩阵旋转在做题的时候会遇到我百度一下想找到已经总结过的模板没找到所以我干脆就自己写了 #include<cstdio> #define_for(i,a,b)for(inti=(a);i<=(b);i++) usingnamespacestd;constintMAXN=112; i...

[综合] 洛谷 P1541 乌龟棋 （四维费用背包）

一开始直接用01背包后来发现这个物品和位置有关。 也就是价值不是固定的 后来看了题解看了卡片最多就4 所以这是一个四维费用的背包，每一维是卡片的数量价值就是当前的位置的价值。但是与常规的背包还是有点不同代码中没有枚举物品这一项实际上循环里面的四个卡片的判断语句就是枚举四个物品这里是先体积后物品，保证...

[综合] 洛谷 P1052 过河 （离散化+dp）

dp非常好想，f[i]=min(f[i-len]+stone[i])s<=len<=t然后因为L非常大，所以我就不知道该怎么搞了我看到m只有100，而L有1e9，我就知道肯定要通过某种数学方法来离散化然而我并没有想出来这个数学方法 看来题解，原来这个方法很简单，我怎么就没有想到因为最大走...

[综合] 洛谷 P1005 矩阵取数游戏 （区间dp+高精度）

这道题大部分时间都在弄高精度……还是先讲讲dp吧这道题是一个区间dp，不过我还是第一次遇到这种类型的区间dpf[i][j]表示取了数之后剩下i到j这个区间的最优值注意这里是取了i之前和j之后的，i到j的数并没有取。那么这个状态要不是取了第i-1个数转移而来，要不是取了第j+1个数转移而来。所以可以写...

[综合] 洛谷 P1373 小a和uim之大逃离 （差值型dp总结）

这道题和多米诺骨牌那道题很像 ,都是涉及到差值的问题。这道题是二维的，同时要取模.这种题，因为当前的决策有后效性，会影响到差值，所以直接把差值作为维度，然后计算答案的时候把差值为0的加起来就行了。这里有两个人，所以可以多设一维第一人还是第二人，来回更新。然后取模的时候记得+k再模k #include...

[综合] 洛谷 P1220 关路灯 （贪心+区间dp）

这一道题我一直在想时间该怎么算。看题解发现有个隐藏的贪心。路径一定是左右扩展的，左右端点最多加+1（我竟然没发现！！）这个性质非常重要！！因此这道题用区间dpf[i][j]表示关完i到j的路灯的消耗。那么因为要算走的路程，那么还有一维表示当前人在左端点还是右端点。然后每次的消耗为当前走这一段的时间乘...

[综合] 洛谷 P1169 [ZJOI2007]棋盘制作 （悬线法）

和玉蟾宫很像，条件改成不相等就行了。 悬线法题目洛谷P1169p4147p2701p1387 #include<cstdio> #include<algorithm> #defineREP(i,a,b)for(inti=(a);i<(b);i++) #define_fo...

[综合] 读入优化摸板

voidread(int&x)//isdigit头文件cctype {intf=1;x=0;charch=getchar();while(!isdigit(ch)){if(ch=='-1')f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-'0'...

[综合] caioj 1153 扩展欧几里德算法（解不定方程）

模板题 注意exgcd函数要稍微记一下 #include<cstdio> #include<cctype> #include<algorithm> #defineREP(i,a,b)for(inti=(a);i<(b);i++) #define_for(i,...

[综合] caioj 1152 快速求模 （快速幂）

（1）开longlong，不然中间结果会溢出 （2）注意一开始的初始化，保险一点。 #include<cstdio> #include<cctype> #include<algorithm> #defineREP(i,a,b)for(inti=(a);i<(...

[综合] caioj 1157 线性筛选素数

注意这道题开得非常大，有2*1e7 自己可以养成一种习惯，如果数据是很容易的话，可以自己手动输入极限数据来测试自己的程序 #include<cstdio> #include<algorithm> #include<cstring> #include<vect...

[综合] caioj 1154 同余方程（模版）

求x的最小正整数解，使得ax=b(modm) 那么显然ax-b=m*y ax-my=b 那么就套入Ax+By=K的不定方程中，然后用exgcd求解即可 但这道题求最大正整数解，对于一组解，有这样一个推论 x=x０+ｋ＊（ｂ／ｇｃｄ（ａ，ｂ）） y=ｙ０－ｋ＊（ａ／ｇｃｄ（ａ，ｂ）） k为任意正整数可...

[综合] caioj 1158 欧拉函数

直接套模板，这道题貌似单独求还快一些 解法一 #include<cstdio> #include<cctype> #defineREP(i,a,b)for(inti=(a);i<(b);i++) #define_for(i,a,b)for(inti=(a);i<=...

[综合] caioj 1161 欧拉函数3：可见点数

（x,y）被看到仅当x与y互质 由此联想到欧拉函数 x=y是1个点，然后把正方形分成两半，一边是φ（n） 所以答案是2*∑φ（n）+1 #include<cstdio> #include<cctype> #defineREP(i,a,b)for(inti=(a);i<(...

[综合] caioj 1204 Catalan数（模板）

题目中对卡特兰数的总结很不错 以下copy自题目 Catalan数列：1,1,2,5,14,42,（前面几个要背）即h(0)=1,h(1)=1,h(2)=2,h(3)=5...公式：h(n)=C(n,2n)/(n+1)注：C(3,5)表示组合数5个数选3个的方案数 递推公式：h(n)=h(n-1)...

[综合] 51nod 1079 中国剩余定理模板

中国剩余定理就是同余方程组除数为质数的特殊情况 我直接用同余方程组解了。 记得exgcd后x要更新 还有先更新b1再更新m1，顺序不能错！！（不然会影响到b1的更新） #include<cstdio> #include<cctype> #defineREP(i,a,b)for...

[综合] 洛谷 P1045 麦森数 （快速幂+高精度+算位数骚操作）

这道题太精彩了！ 我一开始想直接一波暴力算，然后叫上去只有50分，50分超时 然后我改成万位制提高运算效率，还是只有50分 然后我丧心病狂开longlong用10的10次方作为一位，也就是100亿进制 去做，然后交上去多过了一个点，60分 附上丧心病狂的代码 #include<cstdio&...

[综合] P1017 进制转换 （负进制转换）

和平常的转化差不多 加多一步 如果余数<0,那么余数减去除数（此时除数是负），商数加1 #include<cstdio> #define_for(i,a,b)for(inti=(a);i<=(b);i++) usingnamespacestd;voidcal(intn,int...

[综合] 洛谷 P1147 连续自然数和 （滑动窗口）

维护一个滑动窗口即可 注意不能有m到m的区间，因为区间长度要大于1 #include<cstdio> #define_for(i,a,b)for(inti=(a);i<=(b);i++) usingnamespacestd;intmain() {intm,sum=0,st=1;sc...

[综合] 洛谷 P1029 最大公约数和最小公倍数问题

有两种做法 一种是gcd与lcm相乘后就是两个数的乘积，枚举第一个数，算出第二数，看最大公约数是不是题目给的。 第二种就lcm/gcd的答案为两个互质的数相乘。然后就枚举有多少组互质的数相乘等于lcm/gcd就ok了 然后又小优化，可以只枚举到根号，然后结果乘以2就行了。 #include<c...