题意：给出起始素数和目标素数，一次可以改变一位（改变完的那个数字也必须要是素数），现在要问最少多少次可以转移到目标素数素数筛+BFS代码如下： #include<iostream> #include<string> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<queue> #include<sstream> #include<stack&g...

题意：现在有m种糖，n颗糖，每一颗糖有俩个属性，一个是所属种类，一个是自身价格。对于每一种糖，最少要取least[i]颗，现在我们定义S代表我们取的糖果的价格总和，C代表我们在所取得糖的类型中，取的最多的糖果的种类取了多少个现在我们要求Value的最大值首先价格总和要最大，简单贪心就是在同一种类型的糖中，选价格越大的越好其次考虑整体，分母要尽量小，那我就对于每一个不同的分母，分散到各个组，都取其最大的前i个举个例子，现在每一种糖果的least都为2从least开始算，每次算一次价值，比较怎么取价值更高即可 #include<bits/stdc++.h> #define ll lon...

题意：给你一个n，接下来n行，每行四个数，分别代表x1，y1，x2，y2，即这条线过的俩个点，最后我们要求这些线段有多少个交点，记住，重叠的俩条线也算有交点，平行直线则没有交点。 我们知道俩点可以确定一条直线，已知俩点我们可以求得斜率和截距 即将直线转换成y=kx+b的形式 但这种形式转换会有一个问题，无法表示斜率不存在的直线，即x1-x2=0的情况，为了改善这个公式，我们采用方程俩边同时乘以(x1-x2)的方法，将除法转换成乘法，不仅保证了不会除以0，还保证了不用开double来保持高精度（因为除的时候可能会导致斜率为小数，要开double，乘的话则不用考虑这个问题） 那我们的式子就转换成了...

（为防止误解题意，接下来我说的1，2，3，4号位分别代表矩阵的第一排第一列，第一排第二列，第二排第一列，第二排第二列的数字） 题目大意：现在我们有俩个初始矩阵分别为  现在给出一个矩阵  现在已知  我们要通过对A矩阵和B矩阵如何处理才能转化成X？（操作次数需要小于等于4，且操作只能是使用矩阵乘法）输出第一行先输出操作次数m，接下来m行输出每一步的操作过程，即对A怎么操作或者对B怎么操作，题目有多解，输出任意一种即可 由于操作步数的限制，我们要合理的规划每一步的操作，要对任意一个x矩阵都成立，那我们可以先试一下A矩阵和B矩阵对任意的一个X矩阵会产生什么样的影响  通过图片我们可以很清楚的发现一...

思路参考https://blog.nowcoder.net/n/cc6fda3807314f7fbbd3ebd63571d88c整体算法就是：1.排序2.循环因子找到最大的dp[i]3.更新所有因子答案为mx+14.找到最大的ans #include <bits/stdc++.h> #define MAXN 110000 using namespace std; int a[MAXN], dp[MAXN], T, n; int main(){ scanf("%d",&T); while(T--){ int res = 0; scanf("%d", &n); mems...

树状数组是一种很神奇的数据结构，利用了数的二进制来完成检索的一种兼具高效和代码简洁这俩个特点的树状结构。他和线段树的区别就在，树状数组能做的线段树都能做，树状数组不能做的线段树也能做（数据范围），但是线段树代码冗长，实现起来没有树状数组简单，在遇到小数据范围时，应该优先考虑树状数组。 树状数组的模样（图片来自黑书）：  在这里我们先介绍一下树状数组的基础操作1.单点更新 void add(int x,int d) { while(x<=n) { tree[x]+=d; x+=lowbit(x); } }代码很简洁，因为树状数组存的是树状结构，x这个值不止在自己的位置出现过，对于每一个x+...

题目大意：给出n的俩种排列的数组a和b，对于每一次操作可以选择向前移动一位然后在末尾添加一个任意的数字，或者直接修改一个数字为另外一个数字（包括自己），问最少要几次操作可以使得a变到b 我们知道，每一次移动都可以修改后面的值使得a,b俩个数组对齐，那么只要我a中数字在b中所对应的位置在a之前（或者同一个位置），那么我们可以通过直接往前移动x位使得数字对齐，且在移动的过程中可以直接使末尾的x位直接对齐，那么我们通过贪心策略，就是对于每一个数字，只要b的位置在a之前，那么就记录一下这个数字和a中的位置之差，通过vis数组得到哪一个差值出现的次数最多，那么，那个数字就是我们想要的那个差值即步数==t...

有一种题目类型，需要不断查询区间长度为k的子区间内的最小值和最大值，这时候单调队列就出来了，使用单调队列可以很好的解决这一类问题。 什么是单调队列呢？听名字就知道这是一种队列 这种队列支持对头和队尾都能出队，但只能从队尾入队。更为严苛的条件是所有入队的元素必须满足队头到队尾是递减或者递增的，我们可以使用c++自带的stl容器deque来实现这些操作 假设我们现在要创建一个单调递减队列 进来一个数x，我们判断一下队尾元素back是不是大于x的，假如大于，说明back要出队，x要入队，这通过一个while循环就能实现 while(!q.empty()&&q.back()>a[...

题目类型：有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。朴素算法：将所有物品都转换成只有一个物品，那么物品总数就是n[1]+n[2]+...n[n]个，然后进行01背包  for(int i=1;i<=k;i++) { for(int j=m;j>=v[i];j--)//逆序 { for(int h=0;h<=cnt[i];h++) { if(j-h*v[i]<0)break; f[j]=max(f[j],f[j-h*pri[i]]+h*w[...

大意：给出一个n*n的举证，a[i][j]表示第i个点和第j个点的联系，所以a[i][j]=a[j][i]现在要将n个物品分成俩个部分，要使得俩个部分之间点的联系和最大，要怎么分？考虑dfs找所有状态，处理联系和最大的时候用到的方法比较巧妙 #include<iostream> #include<iostream> #include<string> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include&lt...

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。我们用dp[i][j]表示前i个物品中容量为j的情况下的最大价值若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放...

题目大意：给出一个匹配串S和一个字符串T，问匹配串在字符串中出现了几次 经典的字符串匹配问题，可以用KMP,BM,Sunday等各种方法解决，但是我觉得字符串哈希才是最好写最好理解的。。 先将匹配串hash一遍 然后从字符串的第一位开始，判断第i位和匹配串的第一位是否相同，相同的话对字符串的第i到第i+strlen(s)-1位hash，看哈希值是否相同 相同的话ans++ #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<queue> #...

给出一个整数n和k，问有多少种方式将n分成k份首先看数据范围，很明显可以直接爆搜得到答案，这里就不过多讨论 void dfs(int cnt,int pre,int res) //cnt划分层数，pre前一个数，res记录剩下的待划分的数 { if(cnt==k-1) { if(res>=pre) num++; return; } for(int i=pre;i<=res;i++) dfs(cnt+1,i,res-i); } int main() { n=read(),k=read(); dfs(0,1,n); printf("%d\n",num); }然后考虑dp的做法。对于将一...

今天在学数论中的拓展欧几里得，记录一下例题，加深记忆。 首先引入exgcd的概念，是为了解决形如ax+by=gcd(a,b)的不定方程，求解其最小解和通解 具体的算法证明过程我这里就不再阐述，详情请百度，这里给出俩种计算exgcd的方法 void exgcd(int a,int b,int &g,int &x,int &y)//g为gcd(a,b) { if(!b){g=a,x=1,y=0;} else { exgcd(b,a%b,g,y,x);y-=x*(a/b); } } int exgcd(int a,int b,int &x,int &y)//返...