int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
//用以解决ax+by=gcd(a,b)等式中整数解x和y的定理
int exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1;
y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= (a/b) * x;
return d;
}
int lcm(int a,int b){
return a*b/gcd(a,b);
}
int gcds(int a[],int n){
int g=a[0];
for(int i=1;i<n;i++){
g=gcd(g,a[i]);
}
return g;
}
int lcms(int a[],int n){
int l=a[0];
for(int i=1;i<n;i++){
l=lcm(a[i],l);
}
return l;
}
bool islesf(int x){
return x%400==0||(x%4==0&&x%100!=0);
}
int pow(int a,int b){
int ans=1,base=a;//ans:幂的结果 base:底数
while(b){
if(b&1){
ans=base*ans;
}
base=base*base;
b=b>>1;
}
return ans;
}
/*
&运算：通常用于二进制取位操作，例如一个数x & 1 的结果就是取二进制的最末位的值。还可以判断这个数的奇偶性，如果x&1==0，则x为偶数；如果x&1==1，则x为奇数。
>>运算：在这里是作为除法来使用，例如一个数x，x >> 1就表示x右移一位，即x=x/2。
*/
int pow_mod(int a,int b,int c){
int ans=1,base=a;//ans:结果 base:底数
base=base%c;
if(b==0){
return 1%c;
}
while(b){
if(b&1){
ans=(ans*base)%c;
}
base=(base*base)%c;
b=b>>1;
}
return ans;
}
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tRe0KZkY-1649588388827)(C:\Users\20490\AppData\Roaming\Typora\typora-user-images\image-20220227124619141.png)]
typedef long long ll;
ll ksc(ll x,ll y/*,ll p*/){//计算x乘y,将y作为二进制数处理运算
ll res=0;//加法初始化
while(y){
if(y&1){
//res=(res+x)%p;//模仿二进制
res+=x;
}
//x=(x<<1)%p;//将x不断乘2达到二进制
x=x<<1;
y>>=1;//即将二进制移位获取最后一位
}
return res;
}
//只要求最后四位数字，即对中途的结果进行取模10000
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ll f1,f2,f3;
ll temp;
f1=f2=f3=1;
for(int i=4;i<=20190324;i++){
temp=(((f1+f2)%10000)+f3)%10000;
f1=f2;
f2=f3;
f3=temp;
}
cout<<temp<<endl;
}
如果两个整数的乘积模m后等于1，那么就称它们互为m的逆元
求a模m的逆元，就是求解同余式a x ≡ 1 ( m o d m ) ,在实际使用中，一般把x的最小正整数解称为a模m的逆元
int inverse(int a,int m)
{
int x, y;
int g = EXGCD(a, m, x, y); //求解ax+my=1
return (x%m+m)%m; //a模m的逆元为(x%m+m)%m
}
bool isprime(int n){
if(n==1)return false;
for(int i=2;i*i<=n;i++){
if(n%i==0)return false;
}
return true;
}
1.采用二维数组
int main(){
int m,n;//m为总背包大小，n为物品个数
cin>>m>>n;
int weight[n],value[n];
for(int i=0;i<n;i++){
cin>>weight[i]>>value[i];
}
int dp[n][m+1]={0};
//初始化
for(int i=weight[0];i<=m;i++){
dp[0][i]=weight[0];
}
for(int i=1;i<n;i++){//遍历物品
for(int j=0;j<m+1;j++){//遍历背包容量
if(j<weight[i]){
dp[i][j]=dp[i-1][j];
}else{
dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
}
}
}
cout<<dp[n-1][m]<<endl;
}
2.采用一维数组
int main(){
int m,n;//m为总背包大小，n为物品个数
cin>>m>>n;
int weight[n],value[n];
for(int i=0;i<n;i++){
cin>>weight[i]>>value[i];
}
int dp[m+1]={0};
for(int i=0;i<n;i++){//遍历物品
for(int j=m;j>=weight[i];j--){
dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
}
}
cout<<dp[m]<<endl;
}
int main(){
int m,n;
cin>>m>>n;
int weight[n],value[n];
for(int i=0;i<n;i++){
cin>>weight[i]>>value[i];
}
int dp[m+1]={0};
for(int i=0;i<n;i++){
for(int j=weight[i];j<=m;j++){
dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
}
}
cout<<dp[m]<<endl;
}
long long C(int n,int m){
if(m==0)return 1;
long long ans=1;
for(int i=n;i>n-m;i++)ans*=i;
for(int i=1;i<=m;i++)ans/=i;
return ans;
}
这个算法的缺点在于如果会溢出，long long类型的数字到(83,41)就不能用了，所以需要借助大数
(18条消息) 前缀和与差分 图文并茂 超详细整理（全网最通俗易懂）_林深不见鹿 的博客-CSDN博客_前缀和与差分
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EQgqJkM2-1649588388828)(C:\Users\20490\AppData\Roaming\Typora\typora-user-images\image-20220307093359244.png)]
//一维前缀和
int main(){
int n,m;
cin>>n>>m;
int arr[n+1],sum[n+1];
for(int i=1;i<=n;i++){
cin>>arr[i];
}
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+arr[i];
}
while(m--){
int l,r;
cin>>l>>r;
cout<<sum[r]-sum[l]<<endl;
}
return 0;
}
//二维前缀和
int main(){
int n,m,p;
int arr[n+1][m+1],sum[n+1][m+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>arr[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+arr[i][j];
}
}
while(p--){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
cout<<sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]<<endl;
}
}
时间复杂度从O(nm)降到O(n+m)
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XWfZ3SDS-1649588388829)(C:\Users\20490\AppData\Roaming\Typora\typora-user-images\image-20220307090619445.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PEcNgGlN-1649588388830)(C:\Users\20490\AppData\Roaming\Typora\typora-user-images\image-20220307090908854.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jUrzzyTW-1649588388830)(C:\Users\20490\AppData\Roaming\Typora\typora-user-images\image-20220307153630426.png)]
//一维差分
int main(){
int n,m;
cin>>n>>m;
int a[n+1],b[n+1]
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i]-a[i-1];//构造差分数组
}
while(m--){
int r,l,c;
cin>>r>>l>>c;
b[l]+=c;
b[r+1]-=c;
}
for(int i=1;i<=n;i++){
b[i]+=b[i-1];
cout<<b[i]<<" ";
}
return 0;
}
//二维差分
int main(){
int n,m,p;
cin>>n>>m>>p;
int a[n+1][m+1],b[n+1][m+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
b[i][j]+=a[i][j];
b[i+1][j]-=a[i][j];
b[i][j+1]-=a[i][j];
b[i+1][j+1]+=a[i][j];//构造差分数组
}
}
while(p--){
int x1,y1,x2,y2,c;
cin>>x1>>y1>>x2>>y2>>c;
b[x1][y1]+=c;
b[x1+1][y1]-=c;
b[x1][y1+1]-=c;
b[x1+1][y1+1]+=c;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
b[i][j]=b[i][j]+b[i-1][y]+b[i][j-1]-b[i-1][j-1];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<b[i][j]<<" ";
}
}
return 0;
}
在C++中有函数**next_permutation(arr,arr+n)**可以产生全排列的所有情况
注意next_permutation（）在使用前需要对欲排列数组按升序排序
此外，next_permutation（node,node+n,cmp）可以对结构体num按照自定义的排序方式cmp进行排序
在产生过程中，直到产生完毕返回false,其余情况都返回true
//使用方式
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int num[3]={1,2,3};
do
{
cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;
}while(next_permutation(num,num+3));
return 0;
}
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-viEAGdXt-1649588388831)(C:\Users\20490\AppData\Roaming\Typora\typora-user-images\image-20220308191209589.png)]
//数组实现
#include <iostream>
#include <cstring>
using namespace std;
template <class Type> inline void Swap(Type &a, Type &b) {
Type temp = a; a = b; b = temp;
}
template <class Type>
void Perm(Type list[], int k, int n) {
if(k == n) {
for(int i = 0; i <= n; i++) cout << list[i];
cout << endl;
}
else {
for(int i = k; i <= n; i++) {
Swap(list[k], list[i]);
Perm(list, k+1, n);
Swap(list[k], list[i]);
}
}
}
int main() {
char s[] = "abcd";
int len = strlen(s);
Perm(s, 0, len-1);
return 0;
}
//容器vector实现
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking (vector<int>& nums, vector<bool>& used) {
// 此时说明找到了⼀组
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (used[i] == true) continue; // path⾥已经收录的元素，直接跳过
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, used);
path.pop_back();
used[i] = false;}
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking (vector<int>& nums, vector<bool>& used) {
// 此时说明找到了⼀组
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
// used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
// used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
// 如果同⼀树层nums[i - 1]使⽤过则直接跳过
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
}
if (used[i] == false) {
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, used);
path.pop_back();
used[i] = false;
}
}
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
result.clear();
path.clear();
sort(nums.begin(), nums.end()); // 排序
vector<bool> used(nums.size(), false);
backtracking(nums, vec, used);
return result;
}
};
int pre[1000 ];
int find(int x) //查找根节点
{
int r=x;
while ( pre[r] != r ) //返回根节点 r
r=pre[r];
int i=x , j ;
while( i != r ) //路径压缩
{
j = pre[ i ]; // 在改变上级之前用临时变量 j 记录下他的值
pre[ i ]= r ; //把上级改为根节点
i=j;
}
return r ;
}
void join(int x,int y)
{
int fx=find(x),fy=find(y);
if(fx!=fy) //判断x y是否连通，
pre[fx ]=fy; //如果已经连通，就不用管了 如果不连通，就把 它们所在的连通分支合并起,
}
//迪杰斯特拉算法
#include <iostream>
using namespace std;
void dijkstra();
int e[10][10];
int vis[10];
int dis[10];
int n, m;
int min1 = 99999999;
int u = 0;
int main()
{
cin >> n >> m;
// 初始化邻接表
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i == j)
{
e[i][j] = 0;
}
else
{
e[i][j] = 99999999;
}
}
}
// 填充数据
for (int i = 1; i <= m; i++)
{
int a, b, c;
cin >> a >> b >> c;
e[a][b] = c;
}
for (int i = 1; i <= n; i++)
{
dis[i] = e[1][i];
}
vis[1] = 1;
dijkstra();
for (int i = 1; i <= n; i++)
{
cout << "1-->"<<i<<":"<<dis[i]<<endl;
}
system("pause");
return 0;
}
void dijkstra()
{
for (int i = 1; i <= n - 1; i++)
{
min1 = 99999999;
// 寻找权值最小的点u
for (int j = 1; j <= n; j++)
{
if (vis[j] == 0 && dis[j] < min1)
{
min1 = dis[j];
u = j;
}
}
vis[u] = 1;
for (int v = 1; v <= n; v++)
{
// 对于每个u可达的v来说
if (e[u][v] < 99999999)
{
// 如果当前的dis[v]不满足三角形不等式，那么进行松弛操作
if (dis[v] > dis[u] + e[u][v])
{
dis[v] = dis[u] + e[u][v];
}
}
}
}
}
#include <bits/stdc++.h>
using namespace std;
int arr[100][100];
int main(){
int n,m,a,b,c;
cin>>n>>m;
//初始化
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j){
arr[i][j]=0;
}else{
arr[i][j]=999999;
}
}
}
//填充数据
while(m--){
cin>>a>>b>>c;
arr[a][b]=c;
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
arr[i][j]=min(arr[i][j],arr[i][k]+arr[k][j]);
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<arr[i][j]<<" ";
}
cout<<endl;
}
}
#include<bits/stdc++.h>
using namespace std;
int n,m;
char mapp[505][505];//存储地图
int visited[505][505];//标记是否搜索过
int nextt[4][2]={{1,0},{0,-1},{0,1},{-1,0}};
char k[4]={'D','L','R','U'};
struct node{
int x;
int y;
int step;
string s;
};
void bfs(){
node a,b;
queue<node>q;
memset(visited,0,sizeof(visited));
visited[0][0]=1;
a.x=0;
a.y=0;
a.step=0;
a.s="";
q.push(a);
while(!q.empty()){
a=q.front();
q.pop();
if(a.x==n-1&&a.y==m-1){
cout<<a.step<<endl;
cout<<a.s<<endl;
return;
}
for(int i=0;i<4;i++){
b.x=a.x+nextt[i][0];
b.y=a.y+nextt[i][1];
b.step=a.step+1;
if(b.x<0||b.x>=n||b.y<0||b.y>=m){
continue;
}
if(visited[b.x][b.y]==1||mapp[b.x][b.y]==1){
continue;
}
b.s=a.s+k[i];
visited[b.x][b.y]=1;
q.push(b);
}
}
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>mapp[i][j];
}
}
bfs();
}
#include<bits/stdc++.h>
using namespace std;
int dx[4]={1,0,0,-1};
int dy[4]={0,-1,1,0};
char t[4]={'D','L','R','U'};
char res[100];
int vis[30][50]={0};
char ch[30][50];
int mmin=INT_MAX;
void dfs(int x,int y,int step){
if(x==29&&y==49){
mmin=min(mmin,step);
for(int i=0;i<mmin;i++)
cout<<res[i];//输出所走的最短路径
return;
}
for(int i=0;i<4;i++){
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<0||yy<0||xx>=30||yy>=50||step+1>=mmin){
continue;
}
if(vis[xx][yy]==0&&ch[xx][yy]=='0'){
vis[xx][yy]=1;
mmin=step+1;
res[step]=t[i];
dfs(xx,yy,step+1);
vis[xx][yy]=0;
}
}
}
int main(){
for(int i=0;i<30;i++){
for(int j=0;j<50;j++){
cin>>ch[i][j];
}
}
vis[0][0]=1;
dfs(0,0,0);
}
#include<bits/stdc++.h>
using namespace std;
int num=0;
int n;
struct node{
int l;
int r;
};
bool cmp(node &a,node &b){
return a.r<b.r||(a.r==b.r && a.l<b.l);
}
int main(){
cin>>n;
node p[n];
for(int i=0;i<n;i++){
cin>>p[i].l>>p[i].r;
}
sort(p,p+n,cmp);
for(int i=0;i<n;){
num++;
int tmp=p[i].r;
while(p[++i].l<tmp);
}
cout<<num<<endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
if(sqrt(n)*sqrt(n)==n){
cout<<"平方数"<<endl;
}else{
cout<<"非平方数"<<endl;
}
return 0;
}
//非记忆化搜索方式，会增加很多此已知数据的计算
int sol(int x){
if(x==1)return 1;
int ans=0;
for(int i=1;i<=x/2;i++){
ans+=sol(i);
}
return ans;
}
//记忆化搜索方式，可以将之前算出的定值记录下来
int f[1010];
int sol(int x){
if(x==1)return 1;
if(f[x]!=-1)return f[x];
int ans=0;
for(int i=1;i<=x/2;i++){
ans+=sol(i);
}
return f(x)=ans;
}
int main(){
cin>>n;
memset(f,-1,sizeof(f));
f[1]=1;
cout<<sol(n)<<endl;
}
/*普通版：用于无重复元素情况*/
int find(int x){
int l=1,r=n;
while(l<=r){
int mid=(l+r)/2;
if(a[mid]==x)return mid;
else if(a[mid]>x)r=mid-1;
else l=mid+1;
}
return -1;
}
/*用于寻找有重复元素的最小下标情况*/
int find(int x){
int l=1,r=n+1;
while(l<r){
int mid=(l+r)/2;
if(a[mid]>=x)r=mid;
else l=mid+1;
}
if(a[l]==x)return l;
else return -1;
}
/*用于寻找有重复元素的最大下标情况*/
int find(int x){
int l=1,r=n+1;
while(l<r){
int mid=(l+r)/2;
if(a[mid]<=x)l=mid+1;
else r=mid;
}
if(a[l]==x)return l-1;
else return -1;
}