void fun0 (int **A,int M,int N){
int fist=0;
for(int i=0;i
if(A[i][0]==0){
fist=1;
}
for(int j=1;j
if(A[i][j]==0){
A[i][0]=A[0][j]=0;
}
}
}
for(int i=M-1;i>=0;i--){
for(int j=1;j
if(A[i][0]==0||A[0][j]==0)
A[i][j]=0;
}
if(fist){
A[i][0]=0;
}
}
}
void fun(int **Mat,int N)
{
int t,i,j,k=N;
for(i=0;i { for(j=0;j<=i;j++) { t = Mat[i][j]; Mat[i][j]=Mat[j][i]; Mat[j][i]=t; } } for(j=0;j { for(i=0;i { t = Mat[i][j]; Mat[i][j]=Mat[i][N-j-1]; Mat [i][N-j-1]=t; } } } void InsertSort(SqList L){ int n=L.Length; for(int i=1;i<=n;i++){ // int min=10000000; int k=0; for(int j=i+1;j<=n;j++){ if(L.elem[j] k=L.elem[i]; L.elem[i]=L.elem[j]; L.elem[j]=k; } } } } void insertion_sort(LinkNode *&L){ LinkNode *p=L->next; while(p->next){ if(p->next->data LinkNode *w=L; while(w->next->data w=w->next; } LinkNode* q=p->next; p->next=q->next; q->next=w->next; w->next=q; }else{ p=p->next; } } } char* StrMid(char *dst, const char *src, int start, int len){ dst[0]=' '; if(start<0||len<=0||start>strlen(src))return dst; int i=0; while(len--){ if(src[start]==' '){ dst[i]=' '; return dst; } dst[i++]=src[start]; start++; } dst[i]=' '; return dst; } char* StrTrim(char *str){ int start = 0, end = 0, k = 0, i, j; while(isspace(str[start])){ start++; } i = start; end=strlen(str); for(k = end-1; k >= 0; k--){ if(isspace(str[k])){ str[k] = ' '; } else{ break; } } for(j = 0; i <= k; j++,i++){ str[j] = str[i]; } str[j]=' '; return str; } void get_nextval(char T[], int nextval[]) { int i = 1, j = 0; nextval[1] = 0; while (i < T[0]) if (j == 0 || T[i] == T[j]) { ++i; ++j; nextval[i] = nextval[j]; } else j = nextval[j]; } int Index_KMP(char S[], char T[], int pos, int next[]) { int i = pos, j = 1; while (i <= S[0] && j <= T[0]) if (j == 0 || S[i] == T[j]) { ++i; ++j; } else j = next[j]; if (j > T[0]) return i - T[0]; else return 0; } int binsearch(int A[],int key,int low,int high){ while(low<=high){ int mid=(low+high)/2; if(A[mid]>key)high=mid-1; if(A[mid] if(A[mid]==key)return mid; } } int a[100]; void merge(vector // cout< for(int i=start;i<=end;i++){ a[i]=Array[i]; //cout< } // cout< int k=0,i=0,j=0; for(i=start,j=mid+1,k=start;i<=mid&&j<=end;k++){ if( a[i]<=a[j]){ Array[k]=a[i++]; }else{ Array[k]=a[j++]; } } while(i<=mid)Array[k++]=a[i++]; while(j<=end)Array[k++]=a[j++]; } void mergeSort(vector int mid; if(start mid=(start+end)/2; //cout<<"start="< }else if(W){ // cout< A[i].x=W/A[i].w; V+=W*A[i].p; W-=W; } } } int solve(){ int i,j,k; NodeType c[N]; for(i=0;i c[i].no=i; c[i].group=(a[i]<=b[i]); c[i].time=a[i]<=b[i]?a[i]:b[i]; } sort(c,c+N); j=0;k=N-1; for(i=0;i if(c[i].group==1) best[j++]=c[i].no; else best[k--]=c[i].no; } int T1=0; int T2=0; for(i=0;i T1+=a[best[i]]; T2=max(T1,T2)+b[best[i]]; } return T2; } void CreateHTree() { NodeType e,e1,e2; priority_queue for(int k=0;k<2*n-1;k++) ht[k].lchild=ht[k].rchild = ht[k].parent = -1; for(int i=0;i e.no = i; e.data = ht[i].data; e.weight = ht[i].weight; qu.push(e); } for(int j = n;j<2*n-1;j++) { e1 = qu.top();qu.pop(); e2 = qu.top();qu.pop(); ht[j].weight = e1.weight+e2.weight; ht[j].lchild = e1.no; ht[j].rchild = e2.no; ht[e1.no].parent =j; ht[e2.no].parent = j; e.no = j; e.weight=e1.weight+e2.weight; qu.push(e); } } void CreateHCode(){ string code; for(int i=0;i { code = ""; int curno = i; int f = ht[curno].parent; while(f!=-1){ if(ht[f].lchild == curno) code = '0'+code; else code = '1'+code; curno =f;f=ht[curno].parent; } htcode[ht[i].data] =code; //得到ht[i].data字符的哈弗曼编码 } } void dfs(int i,int tw,int tv,int rw,int op[]){ if(i>n){ if(tv>maxv&&tw==W){ maxv=tv; for(int j=1;j<=n;j++){ x[j]=op[j]; } } }else{ if((tw+w[i])<=W){ op[i]=1; dfs(i+1,tw+w[i],tv+v[i],rw-w[i],op); } op[i]=0; if(tw+rw>W) dfs(i+1,tw,tv,rw-w[i],op); } } void dfs(int num,int tw,int rw,int op[],int i){ if(i>n){ if(tw==W&&num minnum=num; for(int j=1;j<=n;j++){ x[j]=op[j]; } } }else{ if(tw+w[i]<=W){ op[i]=1; dfs(num+1,tw+w[i],rw-w[i],op,i+1); } op[i]=0; if(tw+rw>W) dfs(num,tw,rw-w[i],op,i+1); } } void Queens(int n) { int i = 1; q[i] = 0; while (i >= 1) { q[i]++; while (q[i] <= n && !place(i)) q[i]++; if (q[i] <= n) { if (i == n) dispasolution(n); else { i++; q[i] = 0; } } else i--; } } void dfs(int i){ if(i>n){ if(f2[n] bestf=f2[n]; for(int j=1;j<=n;j++){ bestx[j]=x[j]; } } }else{ for(int j=i;j<=n;j++){ swap(x[i],x[j]); f1+=a[x[i]]; f2[i]=max(f1,f2[i-1])+b[x[i]]; if(f2[i] dfs(i+1); } f1-=a[x[i]]; swap(x[i],x[j]); } } } //旅行售货员 #include using namespace std; int INF=999999999; const int N=100; int maps[N][N]; int n,m; int bestw; struct Node { int x[N]; int cl; int id; }; bool operator<(const Node &a,const Node &b){ return a.cl>b.cl; } void bfs() { priority_queue Node node; node.cl = 0; node.id = 2; for(int i=1;i<=n;i++){ node.x[i]=i; } q.push(node); while(!q.empty()){ Node newnode=q.top(); q.pop(); int t; t = newnode.id; if(t==n){ if(maps[newnode.x[t-1]][newnode.x[n]] != INF && maps[newnode.x[n]][newnode.x[1]] != INF ){ if(newnode.cl + maps[newnode.x[t-1]][newnode.x[n]] + maps[newnode.x[n]][newnode.x[1]] < bestw){ bestw = newnode.cl+maps[newnode.x[t-1]][newnode.x[n]] + maps[newnode.x[n]][newnode.x[1]]; } else{ continue; } }else{ continue; } } if(newnode.cl >= bestw) continue; for(int j = t; j <= n; j++){ if(newnode.cl + maps[newnode.x[t-1]][newnode.x[j]] < bestw){ int c = newnode.cl + maps[newnode.x[t-1]][newnode.x[j]]; Node node; node.cl = c; node.id = t+1; for(int i = 1; i <= n; i++) node.x[i] = newnode.x[i]; swap(node.x[t],node.x[j]); q.push(node); } } } } int main(){ cin>>n; for(int i=1;i<=n;i++){ for(int j = 1; j <= n; j++) { int w; cin >> w; if(w == 0) maps[i][j] = INF; else maps[i][j] = w; } } bestw=INF; bfs(); cout << bestw; } //棋盘覆盖 #include #define N 10000 using namespace std; int a[N][N]; int cnt=1,i,j; void pt(int nowx,int nowy,int tex,int tey,int size){ if(size==1){ return ; } int s=size/2; int t=cnt++; if(tex pt(nowx,nowy,tex,tey,s); }else{ a[nowx+s-1][nowy+s-1]=t; pt(nowx,nowy,nowx+s-1,nowy+s-1,s); } //右上 if(tex pt(nowx,nowy+s,tex,tey,s); }else{ a[nowx+s-1][nowy+s]=t; pt(nowx,nowy+s,nowx+s-1,nowy+s,s); } //右下 if(tex>=nowx+s&&tey>=nowy+s){ pt(nowx+s,nowy+s,tex,tey,s); }else{ a[nowx+s][nowy+s]=t; pt(nowx+s,nowy+s,nowx+s,nowy+s,s); } if(tex>=nowx+s&&tey pt(nowx+s,nowy,tex,tey,s); }else{ a[nowx+s][nowy+s-1]=t; pt(nowx+s,nowy,nowx+s,nowy+s-1,s); } } int main(){ int tex,tey,k; cin>>tex>>tey>>k; pt(1,1,tex,tey,k); for(i=1;i<=k;i++){ for(j=1;j<=k;j++){ printf("%4d",a[i][j]); } cout< } return 0; } //古老的汉诺塔 #include using namespace std; int n,co; void hannota(int n,char a,char b,char c){ co++; if(n==1){ cout<"< }else{ hannota(n-1,a,c,b); cout<"< hannota(n-1,b,a,c); } } int main(){ cin>>n; hannota(n,'A','B','C'); cout< } //改写二分搜索算法 #include #define N 100000 using namespace std; int a[N]; int main(){ // freopen("E:data.txt","r",stdin); int n,x; cin>>n>>x; for(int i=0;i cin>>a[i]; } int low=0,heig=n; int mid=0,k=0; while(low<=heig){ mid=(low+heig)/2; // cout< if(a[mid]>x){ heig=mid-1; } else if(a[mid] low=mid+1; }else{ k=1; break; } } if(mid==0&&!k){ cout<<-1<<" "<<0< } else if(mid==n-1&&!k){ cout< }else if(k){ cout< }else{ cout< } } //插入排序还是归并排序 #include using namespace std; int a[105],b[105]; int n; bool judge(){ for(int i=0;i if(a[i]!=b[i]) return false; } return true; } int main(){ scanf("%d",&n); for(int i=0;i scanf("%d",&a[i]); for(int i=0;i scanf("%d",&b[i]); bool flag=false; for(int i=2;;i*=2){ for(int j=0;j if(j+i else sort(a+j,a+n); } if(flag){ printf("Merge Sortn"); for(int i=0;i printf("%d%c",a[i]," n"[i==n-1]); break; } if(judge()) flag=true; if(i>n) break; } if(!flag){ printf("Insertion Sortn"); int t=1; while(t while(t>0&&b[t-1]>b[t]){ swap(b[t-1],b[t]); t--; } for(int i=0;i printf("%d%c",b[i]," n"[i==n-1]); } return 0; } //圆排列问题 #include using namespace std; const int N=20; double minlen=1000,x[N],r[N]; double bestr[N]; double center(int t) { double temp=0; for(int j=1;j { double xvalue=x[j]+2.0*sqrt(r[t]*r[j]); if(xvalue>temp) temp=xvalue; } return temp; } void compute(int n) { double low=0,high=0; for(int i=1;i<=n;++i) { if(x[i]-r[i] low=x[i]-r[i]; if(x[i]+r[i]>high) high=x[i]+r[i]; } if(high-low { minlen=high-low; for(int i=1;i<=n;++i) bestr[i]=r[i]; } } void backtrack(int t,int n) { if(t==n+1) { compute(n); } else { for(int j=t;j<=n;++j) { swap(r[t],r[j]); double centerx=center(t); if(centerx+r[t]+r[1] { x[t]=centerx; backtrack(t+1,n); } swap(r[t],r[j]); } } } int main() { int n; cin >> n; for(int i=1;i<=n;++i) cin >> r[i]; backtrack(1,n); printf("%.4fn",minlen); for(int i=1;i<=n;++i) cout< cout< return 0; } //全排列（回溯，字典序） #include using namespace std; int a[11]; int main(){ int n; cin>>n; for(int i=0;i a[i]=i+1; } do{ for(int i=0;i cout< cout< }while(next_permutation(a,a+n)); return 0; } //加勒比海盗船——最优装载问题 #include using namespace std; int main() { int t; cin>>t; while(t--) { int c,n; cin>>c>>n; vector for(int i=0;i { int temp; cin>>temp; v.push_back(temp); } sort(v.begin(),v.end()); int sum=0; int res=0; for(int i=0;i { sum+=v[i]; if(sum<=c) { res++; } else { break; } } cout< } } // 多参加活动，生活才精彩 #include using namespace std; typedef long long ll; const ll maxn = 1e9+7; const int N = 400000; int num[N]; struct pe{ int s,e,f; }p[110]; bool cmp(pe a,pe b){ return a.e < b.e; } int main() { int n; cin >> n; for(int i = 0;i < n;i++){ cin >> p[i].s >> p[i].e >> p[i].f; } sort(p,p+n,cmp); int star = 0; int num = 0; int sum = 0; for(int i = 0;i < n;i++){ if(star <= p[i].s){ star = p[i].e; sum+= p[i].f; num++; } } cout << num << " " << sum << endl; } //最优合并问题 #include using namespace std; bool cmp(int a,int b) { return a>b; } int MaxMerge(int a[],int k) { int max=0; for(int i=0; i sort(a+i,a+k,cmp); a[i+1]=a[i]+a[i+1]; max=max+a[i+1]-1; } return max; } int MinMerge(int b[],int k) { int min=0; for(int i=0; i sort(b+i,b+k);//升序排列 b[i+1]=b[i]+b[i+1]; min=min+b[i+1]-1; } return min; } int main() { int k; cin>>k; int a[k],b[k]; int x; for(int i=0; i cin>>x; a[i]=x; b[i]=x; } cout< return 0; } //会场安排问题 #include using namespace std; typedef struct { int start; int end; }Event; int main(){ int k; cin>>k; Event event[k+1]; for(int i=1;i<=k;i++){ cin>>event[i].start>>event[i].end; } for(int i=1;i<=k;i++){ int min=event[i].start,min_id=i; for(int j=i+1;j<=k;j++){ if(event[j].start min = event[j].start; min_id = j; } } swap(event[i],event[min_id]); } int room[k+1]={0}; for(int i=1;i<=k;i++){ for(int j=1;j<=k;j++){ if(room[j]<=event[i].start) { room[j]=event[i].end; break; } } } int count=0; for(int i=1;i<=k;i++){ if(room[i]==0) break; count++; } cout< } //月饼 #include #include #define Max 1010 using namespace std; struct yuebin{ double space; double value; double all; }a[Max]; bool cmp(yuebin a,yuebin b) { return a.value>b.value; } int main() { int N,D; scanf("%d%d",&N,&D); int i; for(i=0;i { scanf("%lf",&a[i].space); } for(i=0;i { scanf("%lf",&a[i].all); a[i].value=a[i].all/a[i].space; } sort(a,a+N,cmp); double money=0; for(int i=0;i { if(a[i].space<=D) { D-=a[i].space; money+=a[i].all; } else { money+=D*a[i].value; D=0; } if(D==0)break; } printf("%.2f",money); } //最长公共子序列 #include using namespace std; const int N=1010; int len1,len2; int f[N][N]; string s1,s2; int main() { cin>>len1>>len2; cin>>s1>>s2; s1=' '+s1; s2=' '+s2; for(int i=1;i<=len1;i++) for(int j=1;j<=len2;j++) { f[i][j]=max(f[i-1][j],f[i][j-1]); if(s1[i]==s2[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1); } cout< return 0; } //背包（加强版，并输出物体编号） #include using namespace std; const int maxx=1500; int v[maxx]={0},w[maxx]={0}; int dp[maxx][maxx]; int main(){ int n,vp; scanf("%d %d",&vp,&n); for(int i=1;i<=n;i++){ scanf("%d %d",&v[i],&w[i]); } for(int i=0;i<=n;i++){ for(int j=0;j<=vp;j++){ dp[i][j]=0; } } int flag[1500]; int k=0; for(int i=1;i<=n;i++){ for(int j=vp;j>=0;j--){ if(j-v[i]>=0){ dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]); }else dp[i][j]=dp[i-1][j]; } } printf("%dn",dp[n][vp]); int x=n,y=vp; for(int i=n;i>=1;i--){ if(dp[i][y]>dp[i-1][y]){ flag[k++]=i; y-=v[i]; } } sort(flag,flag+k); for(int i=0;i printf("%d ",flag[i]); } } //求解资源分配问题 #include using namespace std; #define Max_N 101 int m, n; int arr[Max_N][Max_N]; int res[Max_N][Max_N]; int dp[Max_N][Max_N]; int run() { for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { for (int k = 1; k <= j; ++k) { int sum = dp[i - 1][j - k] + arr[i][k]; if (sum >= dp[i][j]) { dp[i][j] = sum; res[i][j] = k; } } } } return dp[m][n]; } int main() { cin >> m >> n; for (int i = 0; i <= m; ++i) { for (int j = 0; j <= n; ++j) { cin >> arr[i][j]; } } int sum = run(); for (int i = m; i > 0; --i) { cout << i << " " << res[i][n] << endl; n -= res[i][n]; } cout << sum; return 0; } // 流水作业调度 #include using namespace std; struct Node{ int number1; int number2; }; bool sort_N1(Node a,Node b){ return a.number1 < b.number1; } bool sort_N2(Node a,Node b){ return a.number2 > b.number2; } int main(){ int N; int a[101]; int b[101]; Node *stu1 = new Node[101]; Node *stu2 = new Node[101]; Node *stu3 = new Node[101]; cin >> N; for(int i = 0; i < N; i++){ cin >> a[i] >> b[i]; } int k1 = 0,k2 = 0; for(int i = 0; i < N; i++){ if(a[i] < b[i]){ stu1[k1].number1 = a[i]; stu1[k1].number2 = b[i]; k1++; }else{ stu2[k2].number1 = a[i]; stu2[k2].number2 = b[i]; k2++; } } sort(stu1,stu1+k1,sort_N1); sort(stu2,stu2+k2,sort_N2); int k3 = 0; for(int i = 0; i < k1; i++){ stu3[k3].number1 = stu1[i].number1; stu3[k3].number2 = stu1[i].number2; k3++; } for(int i = 0; i < k2; i++){ stu3[k3].number1 = stu2[i].number1; stu3[k3].number2 = stu2[i].number2; k3++; } int m1,m2; m1 = stu3[0].number1; m2 = stu3[0].number2 + m1; for(int i = 1; i < N; i++){ m1 = m1 + stu3[i].number1; if(m1 < m2){ m2 = m2 + stu3[i].number2; }else if(m1 > m2){ m2 = m1 + stu3[i].number2; } } cout << m1 << ' ' << m2; } //01背包问题 #include using namespace std; const int N=1000; int n,W; int v[N],w[N]; int maxv=0; int tv; void dfs(int t,int tv,int tw,int rw){ if(t>n){ if(tv>maxv){ maxv=tv; } }else{ if(tw+w[t]<=W){ dfs(t+1,tv+v[t],tw+w[t],rw-w[t]); } dfs(t+1,tv,tw,rw-w[t]); } } int main(){ cin>>n>>W; int rw=0; for(int i=0;i cin>>w[i]>>v[i]; rw+=w[i]; } dfs(0,0,0,rw); cout< } //数字三角形问题 #include #define N 1000 using namespace std; int a[N][N]; int d[N][N]; int main(){ int n; cin>>n; for(int i=0;i for(int j=0;j<=i;j++){ cin>>a[i][j]; if(i==n-1){ d[0][j]=a[i][j]; } } } for(int i=1;i for(int j=0;j // cout< d[i][j]=max(d[i-1][j],d[i-1][j+1])+a[n-1-i][j]; } } cout< // cout<<30< } //矩阵连乘问题 #include using namespace std; #define rep(i, l, r) for(int i = l; i <= r; i++) #define rep1(i, l, r) for(int i = l; i < r; i++) #define ll long long #define INF 0x3f3f3f3f int p[10005], m[10005][10005], s[10005][10005]; void MatrixChain(int n){ rep(i, 1, n) m[i][i] = 0; rep(r, 2, n){ rep(i, 1, n - r + 1){ int j = i + r - 1; m[i][j] = INF; rep(k, i, j - 1){ int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]; if(t < m[i][j]){ m[i][j] = t; s[i][j] = k; } } } } } int main(){ int n; cin >> n; rep(i, 0, n) cin >> p[i]; MatrixChain(n); cout << m[1][n] << endl; return 0; } //斐波那契数列（III） #include #define mod 998244353 typedef struct Matrix { unsigned long long M[2][2]; }Matrix; struct Matrix multi(Matrix a, Matrix b) { Matrix c; for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { c.M[i][j] = 0; for (int k = 0; k < 2; k++) c.M[i][j] += (a.M[i][k] * b.M[k][j])%mod; } } return c; } struct Matrix QuickExp(Matrix a, unsigned long long n) { Matrix res; res.M[0][0] = 1; //单位矩阵 res.M[0][1] = 0; res.M[1][0] = 0; res.M[1][1] = 1; while (n > 0) { if (n % 2) res = multi(res, a); a = multi(a, a); n /= 2; } return res; } int main() { unsigned long long n; Matrix a, res; scanf("%lld", &n); if(n == 1) { printf("1n"); return 0; } a.M[0][0] = 1;a.M[0][1] = 1; a.M[1][0] = 1;a.M[1][1] = 0; res = QuickExp(a, n - 1); printf("%lldn",res.M[0][0]%mod); //以[f(1),f(0)]为基准 return 0; } //数的三次方根 #include using namespace std; const double enp=1e-8; int main(){ double x; cin>>x; double l=-1e4,r=1e4; double result=0; while(r-l>enp){ double mid=(l+r)/2.0; if(mid*mid*mid>=x){ r=mid; result=mid; } else l=mid; } printf("%.6lfn",result); } 多项式求和 #include using namespace std; double zhi( double x,int n){ double re=1.0; while(n){ if(n&1)re*=x; x*=x; n/=2; } return re; } int main(){ int n; double x; cin>>n; scanf("%lf",&x); double sum=0; double k;int ci=n; for(int i=0;i cin>>k; // cout< sum+=k*zhi(x,ci); ci--; } printf("%.3lfn",sum); } //八皇后问题 #include #include using namespace std; int n, * x; bool b=false; bool constraint(int k) { for (int j = 0; j < k; j++) if ((abs(x[j] - x[k]) == abs(j - k)) || (x[j] == x[k])) return false; return true; } void backtrack(int k) { int i; if (k >= n) { if(b) cout< b = true; for (int j, i = 0; i < n; i++) { for (j = 0; j < n-1; j++) { if (x[i] == j) cout << "Q "; else cout << ". "; } if (x[i] == j) cout << "Q"; else cout << "."; cout << endl; } } else { for (i = 0; i < n; i++) { x[k] = i; if (constraint(k)) backtrack(k + 1); } } } int main() { cin >> n; x = new int[n]; backtrack(0); if (!b) cout << "None" << endl; delete[] x; return 0; } //Activity selection problem #include using namespace std; typedef long long ll; const ll maxn = 1e9+7; const int N = 400000; int num[N]; struct pe{ int s,e; }p[110]; bool cmp(pe a,pe b){ return a.e < b.e; } int main() { int n; cin >> n; for(int i = 0;i < n;i++){ cin >> p[i].s; } for(int i = 0;i < n;i++){ cin >> p[i].e ; } sort(p,p+n,cmp); int star = 0; int num = 0; for(int i = 0;i < n;i++){ if(star <= p[i].s){ star = p[i].e; num++; } } cout << num << endl; } //最优二分检索树 #include #include #include int p[5500],q[5500]; int c[5200][5200],w[5200][5200]; int R[5200][5200]; int n; int a[5500]; typedef struct BiTNode{ int num; BiTNode* Lc; BiTNode* Rc; }BiTNode, *BiTree; void input() { int i; scanf("%d",&n); for(i=0;i a[i] = i+1; p[0]=-1; for(i=1;i<=n;i++) scanf("%d",&p[i]); for(i=0;i<=n;i++) scanf("%d",&q[i]); } void OBST( ) { int i,j,m,k,l; float tmp,tmp1; for(i=0;i { w[i][i]=q[i]; c[i][i]=0; R[i][i]=0; w[i][i+1]=q[i+1]+p[i+1]+q[i]; R[i][i+1]=i+1; c[i][i+1]=q[i+1]+p[i+1]+q[i]; } w[n][n]=q[n]; R[n][n]=0; c[n][n]=0; for(m=1;m<=n;m++) { for(i=0;i<=n-m;i++) { j=i+m; w[i][j]=w[i][j-1]+q[j]+p[j]; tmp=c[i][i]+c[i+1][j]; k=i+1; //for(l=i+2;l<=j;l++) for(l = R[i][j-1];l<=R[i+1][j];l++) { tmp1=c[i][l-1]+c[l][j]; if(tmp1 { tmp=tmp1; k=l; } } c[i][j]=w[i][j]+c[i][k-1]+c[k][j]; R[i][j]=k; } } } BiTree buildtree(int i,int j) { if(i>=j) return NULL; BiTree Tr; Tr=(BiTree)malloc(sizeof(BiTNode)); if(!Tr) return NULL; Tr->num=R[i][j]; Tr->Lc=buildtree(i,R[i][j]-1); Tr->Rc=buildtree(R[i][j],j); return Tr; } void preTree(BiTree T) { if(T) { printf("%dn",a[T->num-1]); preTree(T->Lc); preTree(T->Rc); } } int main(int argc, char *argv[]) { BiTree BT; input(); OBST(); BT=buildtree(0,n); preTree(BT); return 0; } //求解汽车加油问题 #define N 10007 #include using namespace std; int nums[N]; int main(){ int d,n; cin>>d>>n; for(int i=0;i cin>>nums[i]; } int sum=0,count=0; int t=d; for(int i=0;i if(t>=nums[i]){ t-=nums[i]; if(t t=d; count++; } }else{ cout<<"No Solution!"< return 0; } } cout< } //特别数的和 #include using namespace std; bool is(int n){ while(n){ if(n%10==2||n%10==0||n%10==1||n%10==9) return true; n/=10; } return false; } int main(){ int n; cin>>n; int sum=0; for(int i=1;i<=n;i++){ if(is(i)) sum+=i; } cout< } // n以内素数个数 #include #define N 100000000 using namespace std; bool valid[N]; int main(){ memset(valid,true,sizeof(valid)); int n; cin>>n; int count=0; for(int i=2;i*i<=n;i++){ if(valid[i]){ for(int j=i*i;j<=n;j+=i){ valid[j]=false; } } } for(int i=2;i<=n;i++) if(valid[i]) count++; cout< } //快速幂运算 #include using namespace std; long long luai(long long a,long long b){ long long ans=1; while(b){ if(b&1)ans=ans*a%1000; a=a%1000*a%1000; b/=2; } return ans%1000; } int main(){ long long a,b; cin>>a>>b; cout< } //旅行售货员 #include using namespace std; int INF=999999999; const int N=100; int maps[N][N]; int n,m; int bestw; struct Node { int x[N]; int cl; int id; }; bool operator<(const Node &a,const Node &b){ return a.cl>b.cl; } void bfs() { priority_queue Node node; node.cl = 0; node.id = 2; for(int i=1;i<=n;i++){ node.x[i]=i; } q.push(node); while(!q.empty()){ Node newnode=q.top(); q.pop(); int t; t = newnode.id; if(t==n){ if(maps[newnode.x[t-1]][newnode.x[n]] != INF && maps[newnode.x[n]][newnode.x[1]] != INF ){ if(newnode.cl + maps[newnode.x[t-1]][newnode.x[n]] + maps[newnode.x[n]][newnode.x[1]] < bestw){ bestw = newnode.cl+maps[newnode.x[t-1]][newnode.x[n]] + maps[newnode.x[n]][newnode.x[1]]; } else{ continue; } }else{ continue; } } if(newnode.cl >= bestw) continue; for(int j = t; j <= n; j++){ if(newnode.cl + maps[newnode.x[t-1]][newnode.x[j]] < bestw){ int c = newnode.cl + maps[newnode.x[t-1]][newnode.x[j]]; Node node; node.cl = c; node.id = t+1; for(int i = 1; i <= n; i++) node.x[i] = newnode.x[i]; swap(node.x[t],node.x[j]); q.push(node); } } } } int main(){ cin>>n; for(int i=1;i<=n;i++){ for(int j = 1; j <= n; j++) { int w; cin >> w; if(w == 0) maps[i][j] = INF; else maps[i][j] = w; } } bestw=INF; bfs(); cout << bestw; } //棋盘覆盖 #include #define N 10000 using namespace std; int a[N][N]; int cnt=1,i,j; void pt(int nowx,int nowy,int tex,int tey,int size){ if(size==1){ return ; } int s=size/2; int t=cnt++; if(tex pt(nowx,nowy,tex,tey,s); }else{ a[nowx+s-1][nowy+s-1]=t; pt(nowx,nowy,nowx+s-1,nowy+s-1,s); } //右上 if(tex pt(nowx,nowy+s,tex,tey,s); }else{ a[nowx+s-1][nowy+s]=t; pt(nowx,nowy+s,nowx+s-1,nowy+s,s); } //右下 if(tex>=nowx+s&&tey>=nowy+s){ pt(nowx+s,nowy+s,tex,tey,s); }else{ a[nowx+s][nowy+s]=t; pt(nowx+s,nowy+s,nowx+s,nowy+s,s); } if(tex>=nowx+s&&tey pt(nowx+s,nowy,tex,tey,s); }else{ a[nowx+s][nowy+s-1]=t; pt(nowx+s,nowy,nowx+s,nowy+s-1,s); } } int main(){ int tex,tey,k; cin>>tex>>tey>>k; pt(1,1,tex,tey,k); for(i=1;i<=k;i++){ for(j=1;j<=k;j++){ printf("%4d",a[i][j]); } cout< } return 0; } //古老的汉诺塔 #include using namespace std; int n,co; void hannota(int n,char a,char b,char c){ co++; if(n==1){ cout<"< }else{ hannota(n-1,a,c,b); cout<"< hannota(n-1,b,a,c); } } int main(){ cin>>n; hannota(n,'A','B','C'); cout< } //改写二分搜索算法 #include #define N 100000 using namespace std; int a[N]; int main(){ // freopen("E:data.txt","r",stdin); int n,x; cin>>n>>x; for(int i=0;i cin>>a[i]; } int low=0,heig=n; int mid=0,k=0; while(low<=heig){ mid=(low+heig)/2; // cout< if(a[mid]>x){ heig=mid-1; } else if(a[mid] low=mid+1; }else{ k=1; break; } } if(mid==0&&!k){ cout<<-1<<" "<<0< } else if(mid==n-1&&!k){ cout< }else if(k){ cout< }else{ cout< } } //插入排序还是归并排序 #include using namespace std; int a[105],b[105]; int n; bool judge(){ for(int i=0;i if(a[i]!=b[i]) return false; } return true; } int main(){ scanf("%d",&n); for(int i=0;i scanf("%d",&a[i]); for(int i=0;i scanf("%d",&b[i]); bool flag=false; for(int i=2;;i*=2){ for(int j=0;j if(j+i else sort(a+j,a+n); } if(flag){ printf("Merge Sortn"); for(int i=0;i printf("%d%c",a[i]," n"[i==n-1]); break; } if(judge()) flag=true; if(i>n) break; } if(!flag){ printf("Insertion Sortn"); int t=1; while(t while(t>0&&b[t-1]>b[t]){ swap(b[t-1],b[t]); t--; } for(int i=0;i printf("%d%c",b[i]," n"[i==n-1]); } return 0; } //圆排列问题 #include using namespace std; const int N=20; double minlen=1000,x[N],r[N]; double bestr[N]; double center(int t) { double temp=0; for(int j=1;j { double xvalue=x[j]+2.0*sqrt(r[t]*r[j]); if(xvalue>temp) temp=xvalue; } return temp; } void compute(int n) { double low=0,high=0; for(int i=1;i<=n;++i) { if(x[i]-r[i] low=x[i]-r[i]; if(x[i]+r[i]>high) high=x[i]+r[i]; } if(high-low { minlen=high-low; for(int i=1;i<=n;++i) bestr[i]=r[i]; } } void backtrack(int t,int n) { if(t==n+1) { compute(n); } else { for(int j=t;j<=n;++j) { swap(r[t],r[j]); double centerx=center(t); if(centerx+r[t]+r[1] { x[t]=centerx; backtrack(t+1,n); } swap(r[t],r[j]); } } } int main() { int n; cin >> n; for(int i=1;i<=n;++i) cin >> r[i]; backtrack(1,n); printf("%.4fn",minlen); for(int i=1;i<=n;++i) cout< cout< return 0; } //全排列（回溯，字典序） #include using namespace std; int a[11]; int main(){ int n; cin>>n; for(int i=0;i a[i]=i+1; } do{ for(int i=0;i cout< cout< }while(next_permutation(a,a+n)); return 0; } //加勒比海盗船——最优装载问题 #include using namespace std; int main() { int t; cin>>t; while(t--) { int c,n; cin>>c>>n; vector for(int i=0;i { int temp; cin>>temp; v.push_back(temp); } sort(v.begin(),v.end()); int sum=0; int res=0; for(int i=0;i { sum+=v[i]; if(sum<=c) { res++; } else { break; } } cout< } } // 多参加活动，生活才精彩 #include using namespace std; typedef long long ll; const ll maxn = 1e9+7; const int N = 400000; int num[N]; struct pe{ int s,e,f; }p[110]; bool cmp(pe a,pe b){ return a.e < b.e; } int main() { int n; cin >> n; for(int i = 0;i < n;i++){ cin >> p[i].s >> p[i].e >> p[i].f; } sort(p,p+n,cmp); int star = 0; int num = 0; int sum = 0; for(int i = 0;i < n;i++){ if(star <= p[i].s){ star = p[i].e; sum+= p[i].f; num++; } } cout << num << " " << sum << endl; } //最优合并问题 #include using namespace std; bool cmp(int a,int b) { return a>b; } int MaxMerge(int a[],int k) { int max=0; for(int i=0; i sort(a+i,a+k,cmp); a[i+1]=a[i]+a[i+1]; max=max+a[i+1]-1; } return max; } int MinMerge(int b[],int k) { int min=0; for(int i=0; i sort(b+i,b+k);//升序排列 b[i+1]=b[i]+b[i+1]; min=min+b[i+1]-1; } return min; } int main() { int k; cin>>k; int a[k],b[k]; int x; for(int i=0; i cin>>x; a[i]=x; b[i]=x; } cout< return 0; } //会场安排问题 #include using namespace std; typedef struct { int start; int end; }Event; int main(){ int k; cin>>k; Event event[k+1]; for(int i=1;i<=k;i++){ cin>>event[i].start>>event[i].end; } for(int i=1;i<=k;i++){ int min=event[i].start,min_id=i; for(int j=i+1;j<=k;j++){ if(event[j].start min = event[j].start; min_id = j; } } swap(event[i],event[min_id]); } int room[k+1]={0}; for(int i=1;i<=k;i++){ for(int j=1;j<=k;j++){ if(room[j]<=event[i].start) { room[j]=event[i].end; break; } } } int count=0; for(int i=1;i<=k;i++){ if(room[i]==0) break; count++; } cout< } //月饼 #include #include #define Max 1010 using namespace std; struct yuebin{ double space; double value; double all; }a[Max]; bool cmp(yuebin a,yuebin b) { return a.value>b.value; } int main() { int N,D; scanf("%d%d",&N,&D); int i; for(i=0;i { scanf("%lf",&a[i].space); } for(i=0;i { scanf("%lf",&a[i].all); a[i].value=a[i].all/a[i].space; } sort(a,a+N,cmp); double money=0; for(int i=0;i { if(a[i].space<=D) { D-=a[i].space; money+=a[i].all; } else { money+=D*a[i].value; D=0; } if(D==0)break; } printf("%.2f",money); } //最长公共子序列 #include using namespace std; const int N=1010; int len1,len2; int f[N][N]; string s1,s2; int main() { cin>>len1>>len2; cin>>s1>>s2; s1=' '+s1; s2=' '+s2; for(int i=1;i<=len1;i++) for(int j=1;j<=len2;j++) { f[i][j]=max(f[i-1][j],f[i][j-1]); if(s1[i]==s2[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1); } cout< return 0; } //背包（加强版，并输出物体编号） #include using namespace std; const int maxx=1500; int v[maxx]={0},w[maxx]={0}; int dp[maxx][maxx]; int main(){ int n,vp; scanf("%d %d",&vp,&n); for(int i=1;i<=n;i++){ scanf("%d %d",&v[i],&w[i]); } for(int i=0;i<=n;i++){ for(int j=0;j<=vp;j++){ dp[i][j]=0; } } int flag[1500]; int k=0; for(int i=1;i<=n;i++){ for(int j=vp;j>=0;j--){ if(j-v[i]>=0){ dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]); }else dp[i][j]=dp[i-1][j]; } } printf("%dn",dp[n][vp]); int x=n,y=vp; for(int i=n;i>=1;i--){ if(dp[i][y]>dp[i-1][y]){ flag[k++]=i; y-=v[i]; } } sort(flag,flag+k); for(int i=0;i printf("%d ",flag[i]); } } //求解资源分配问题 #include using namespace std; #define Max_N 101 int m, n; int arr[Max_N][Max_N]; int res[Max_N][Max_N]; int dp[Max_N][Max_N]; int run() { for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { for (int k = 1; k <= j; ++k) { int sum = dp[i - 1][j - k] + arr[i][k]; if (sum >= dp[i][j]) { dp[i][j] = sum; res[i][j] = k; } } } } return dp[m][n]; } int main() { cin >> m >> n; for (int i = 0; i <= m; ++i) { for (int j = 0; j <= n; ++j) { cin >> arr[i][j]; } } int sum = run(); for (int i = m; i > 0; --i) { cout << i << " " << res[i][n] << endl; n -= res[i][n]; } cout << sum; return 0; } // 流水作业调度 #include using namespace std; struct Node{ int number1; int number2; }; bool sort_N1(Node a,Node b){ return a.number1 < b.number1; } bool sort_N2(Node a,Node b){ return a.number2 > b.number2; } int main(){ int N; int a[101]; int b[101]; Node *stu1 = new Node[101]; Node *stu2 = new Node[101]; Node *stu3 = new Node[101]; cin >> N; for(int i = 0; i < N; i++){ cin >> a[i] >> b[i]; } int k1 = 0,k2 = 0; for(int i = 0; i < N; i++){ if(a[i] < b[i]){ stu1[k1].number1 = a[i]; stu1[k1].number2 = b[i]; k1++; }else{ stu2[k2].number1 = a[i]; stu2[k2].number2 = b[i]; k2++; } } sort(stu1,stu1+k1,sort_N1); sort(stu2,stu2+k2,sort_N2); int k3 = 0; for(int i = 0; i < k1; i++){ stu3[k3].number1 = stu1[i].number1; stu3[k3].number2 = stu1[i].number2; k3++; } for(int i = 0; i < k2; i++){ stu3[k3].number1 = stu2[i].number1; stu3[k3].number2 = stu2[i].number2; k3++; } int m1,m2; m1 = stu3[0].number1; m2 = stu3[0].number2 + m1; for(int i = 1; i < N; i++){ m1 = m1 + stu3[i].number1; if(m1 < m2){ m2 = m2 + stu3[i].number2; }else if(m1 > m2){ m2 = m1 + stu3[i].number2; } } cout << m1 << ' ' << m2; } //01背包问题 #include using namespace std; const int N=1000; int n,W; int v[N],w[N]; int maxv=0; int tv; void dfs(int t,int tv,int tw,int rw){ if(t>n){ if(tv>maxv){ maxv=tv; } }else{ if(tw+w[t]<=W){ dfs(t+1,tv+v[t],tw+w[t],rw-w[t]); } dfs(t+1,tv,tw,rw-w[t]); } } int main(){ cin>>n>>W; int rw=0; for(int i=0;i cin>>w[i]>>v[i]; rw+=w[i]; } dfs(0,0,0,rw); cout< } //数字三角形问题 #include #define N 1000 using namespace std; int a[N][N]; int d[N][N]; int main(){ int n; cin>>n; for(int i=0;i for(int j=0;j<=i;j++){ cin>>a[i][j]; if(i==n-1){ d[0][j]=a[i][j]; } } } for(int i=1;i for(int j=0;j // cout< d[i][j]=max(d[i-1][j],d[i-1][j+1])+a[n-1-i][j]; } } cout< // cout<<30< } //矩阵连乘问题 #include using namespace std; #define rep(i, l, r) for(int i = l; i <= r; i++) #define rep1(i, l, r) for(int i = l; i < r; i++) #define ll long long #define INF 0x3f3f3f3f int p[10005], m[10005][10005], s[10005][10005]; void MatrixChain(int n){ rep(i, 1, n) m[i][i] = 0; rep(r, 2, n){ rep(i, 1, n - r + 1){ int j = i + r - 1; m[i][j] = INF; rep(k, i, j - 1){ int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]; if(t < m[i][j]){ m[i][j] = t; s[i][j] = k; } } } } } int main(){ int n; cin >> n; rep(i, 0, n) cin >> p[i]; MatrixChain(n); cout << m[1][n] << endl; return 0; } //斐波那契数列（III） #include #define mod 998244353 typedef struct Matrix { unsigned long long M[2][2]; }Matrix; struct Matrix multi(Matrix a, Matrix b) { Matrix c; for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { c.M[i][j] = 0; for (int k = 0; k < 2; k++) c.M[i][j] += (a.M[i][k] * b.M[k][j])%mod; } } return c; } struct Matrix QuickExp(Matrix a, unsigned long long n) { Matrix res; res.M[0][0] = 1; //单位矩阵 res.M[0][1] = 0; res.M[1][0] = 0; res.M[1][1] = 1; while (n > 0) { if (n % 2) res = multi(res, a); a = multi(a, a); n /= 2; } return res; } int main() { unsigned long long n; Matrix a, res; scanf("%lld", &n); if(n == 1) { printf("1n"); return 0; } a.M[0][0] = 1;a.M[0][1] = 1; a.M[1][0] = 1;a.M[1][1] = 0; res = QuickExp(a, n - 1); printf("%lldn",res.M[0][0]%mod); //以[f(1),f(0)]为基准 return 0; } //数的三次方根 #include using namespace std; const double enp=1e-8; int main(){ double x; cin>>x; double l=-1e4,r=1e4; double result=0; while(r-l>enp){ double mid=(l+r)/2.0; if(mid*mid*mid>=x){ r=mid; result=mid; } else l=mid; } printf("%.6lfn",result); } 多项式求和 #include using namespace std; double zhi( double x,int n){ double re=1.0; while(n){ if(n&1)re*=x; x*=x; n/=2; } return re; } int main(){ int n; double x; cin>>n; scanf("%lf",&x); double sum=0; double k;int ci=n; for(int i=0;i cin>>k; // cout< sum+=k*zhi(x,ci); ci--; } printf("%.3lfn",sum); } //八皇后问题 #include #include using namespace std; int n, * x; bool b=false; bool constraint(int k) { for (int j = 0; j < k; j++) if ((abs(x[j] - x[k]) == abs(j - k)) || (x[j] == x[k])) return false; return true; } void backtrack(int k) { int i; if (k >= n) { if(b) cout< b = true; for (int j, i = 0; i < n; i++) { for (j = 0; j < n-1; j++) { if (x[i] == j) cout << "Q "; else cout << ". "; } if (x[i] == j) cout << "Q"; else cout << "."; cout << endl; } } else { for (i = 0; i < n; i++) { x[k] = i; if (constraint(k)) backtrack(k + 1); } } } int main() { cin >> n; x = new int[n]; backtrack(0); if (!b) cout << "None" << endl; delete[] x; return 0; } //Activity selection problem #include using namespace std; typedef long long ll; const ll maxn = 1e9+7; const int N = 400000; int num[N]; struct pe{ int s,e; }p[110]; bool cmp(pe a,pe b){ return a.e < b.e; } int main() { int n; cin >> n; for(int i = 0;i < n;i++){ cin >> p[i].s; } for(int i = 0;i < n;i++){ cin >> p[i].e ; } sort(p,p+n,cmp); int star = 0; int num = 0; for(int i = 0;i < n;i++){ if(star <= p[i].s){ star = p[i].e; num++; } } cout << num << endl; } //最优二分检索树 #include #include #include int p[5500],q[5500]; int c[5200][5200],w[5200][5200]; int R[5200][5200]; int n; int a[5500]; typedef struct BiTNode{ int num; BiTNode* Lc; BiTNode* Rc; }BiTNode, *BiTree; void input() { int i; scanf("%d",&n); for(i=0;i a[i] = i+1; p[0]=-1; for(i=1;i<=n;i++) scanf("%d",&p[i]); for(i=0;i<=n;i++) scanf("%d",&q[i]); } void OBST( ) { int i,j,m,k,l; float tmp,tmp1; for(i=0;i { w[i][i]=q[i]; c[i][i]=0; R[i][i]=0; w[i][i+1]=q[i+1]+p[i+1]+q[i]; R[i][i+1]=i+1; c[i][i+1]=q[i+1]+p[i+1]+q[i]; } w[n][n]=q[n]; R[n][n]=0; c[n][n]=0; for(m=1;m<=n;m++) { for(i=0;i<=n-m;i++) { j=i+m; w[i][j]=w[i][j-1]+q[j]+p[j]; tmp=c[i][i]+c[i+1][j]; k=i+1; //for(l=i+2;l<=j;l++) for(l = R[i][j-1];l<=R[i+1][j];l++) { tmp1=c[i][l-1]+c[l][j]; if(tmp1 { tmp=tmp1; k=l; } } c[i][j]=w[i][j]+c[i][k-1]+c[k][j]; R[i][j]=k; } } } BiTree buildtree(int i,int j) { if(i>=j) return NULL; BiTree Tr; Tr=(BiTree)malloc(sizeof(BiTNode)); if(!Tr) return NULL; Tr->num=R[i][j]; Tr->Lc=buildtree(i,R[i][j]-1); Tr->Rc=buildtree(R[i][j],j); return Tr; } void preTree(BiTree T) { if(T) { printf("%dn",a[T->num-1]); preTree(T->Lc); preTree(T->Rc); } } int main(int argc, char *argv[]) { BiTree BT; input(); OBST(); BT=buildtree(0,n); preTree(BT); return 0; } //求解汽车加油问题 #define N 10007 #include using namespace std; int nums[N]; int main(){ int d,n; cin>>d>>n; for(int i=0;i cin>>nums[i]; } int sum=0,count=0; int t=d; for(int i=0;i if(t>=nums[i]){ t-=nums[i]; if(t t=d; count++; } }else{ cout<<"No Solution!"< return 0; } } cout< } //特别数的和 #include using namespace std; bool is(int n){ while(n){ if(n%10==2||n%10==0||n%10==1||n%10==9) return true; n/=10; } return false; } int main(){ int n; cin>>n; int sum=0; for(int i=1;i<=n;i++){ if(is(i)) sum+=i; } cout< } // n以内素数个数 #include #define N 100000000 using namespace std; bool valid[N]; int main(){ memset(valid,true,sizeof(valid)); int n; cin>>n; int count=0; for(int i=2;i*i<=n;i++){ if(valid[i]){ for(int j=i*i;j<=n;j+=i){ valid[j]=false; } } } for(int i=2;i<=n;i++) if(valid[i]) count++; cout< } //快速幂运算 #include using namespace std; long long luai(long long a,long long b){ long long ans=1; while(b){ if(b&1)ans=ans*a%1000; a=a%1000*a%1000; b/=2; } return ans%1000; } int main(){ long long a,b; cin>>a>>b; cout< } //旅行售货员 #include using namespace std; int INF=999999999; const int N=100; int maps[N][N]; int n,m; int bestw; struct Node { int x[N]; int cl; int id; }; bool operator<(const Node &a,const Node &b){ return a.cl>b.cl; } void bfs() { priority_queue Node node; node.cl = 0; node.id = 2; for(int i=1;i<=n;i++){ node.x[i]=i; } q.push(node); while(!q.empty()){ Node newnode=q.top(); q.pop(); int t; t = newnode.id; if(t==n){ if(maps[newnode.x[t-1]][newnode.x[n]] != INF && maps[newnode.x[n]][newnode.x[1]] != INF ){ if(newnode.cl + maps[newnode.x[t-1]][newnode.x[n]] + maps[newnode.x[n]][newnode.x[1]] < bestw){ bestw = newnode.cl+maps[newnode.x[t-1]][newnode.x[n]] + maps[newnode.x[n]][newnode.x[1]]; } else{ continue; } }else{ continue; } } if(newnode.cl >= bestw) continue; for(int j = t; j <= n; j++){ if(newnode.cl + maps[newnode.x[t-1]][newnode.x[j]] < bestw){ int c = newnode.cl + maps[newnode.x[t-1]][newnode.x[j]]; Node node; node.cl = c; node.id = t+1; for(int i = 1; i <= n; i++) node.x[i] = newnode.x[i]; swap(node.x[t],node.x[j]); q.push(node); } } } } int main(){ cin>>n; for(int i=1;i<=n;i++){ for(int j = 1; j <= n; j++) { int w; cin >> w; if(w == 0) maps[i][j] = INF; else maps[i][j] = w; } } bestw=INF; bfs(); cout << bestw; } //棋盘覆盖 #include #define N 10000 using namespace std; int a[N][N]; int cnt=1,i,j; void pt(int nowx,int nowy,int tex,int tey,int size){ if(size==1){ return ; } int s=size/2; int t=cnt++; if(tex pt(nowx,nowy,tex,tey,s); }else{ a[nowx+s-1][nowy+s-1]=t; pt(nowx,nowy,nowx+s-1,nowy+s-1,s); } //右上 if(tex pt(nowx,nowy+s,tex,tey,s); }else{ a[nowx+s-1][nowy+s]=t; pt(nowx,nowy+s,nowx+s-1,nowy+s,s); } //右下 if(tex>=nowx+s&&tey>=nowy+s){ pt(nowx+s,nowy+s,tex,tey,s); }else{ a[nowx+s][nowy+s]=t; pt(nowx+s,nowy+s,nowx+s,nowy+s,s); } if(tex>=nowx+s&&tey pt(nowx+s,nowy,tex,tey,s); }else{ a[nowx+s][nowy+s-1]=t; pt(nowx+s,nowy,nowx+s,nowy+s-1,s); } } int main(){ int tex,tey,k; cin>>tex>>tey>>k; pt(1,1,tex,tey,k); for(i=1;i<=k;i++){ for(j=1;j<=k;j++){ printf("%4d",a[i][j]); } cout< } return 0; } //古老的汉诺塔 #include using namespace std; int n,co; void hannota(int n,char a,char b,char c){ co++; if(n==1){ cout<"< }else{ hannota(n-1,a,c,b); cout<"< hannota(n-1,b,a,c); } } int main(){ cin>>n; hannota(n,'A','B','C'); cout< } //改写二分搜索算法 #include #define N 100000 using namespace std; int a[N]; int main(){ // freopen("E:data.txt","r",stdin); int n,x; cin>>n>>x; for(int i=0;i cin>>a[i]; } int low=0,heig=n; int mid=0,k=0; while(low<=heig){ mid=(low+heig)/2; // cout< if(a[mid]>x){ heig=mid-1; } else if(a[mid] low=mid+1; }else{ k=1; break; } } if(mid==0&&!k){ cout<<-1<<" "<<0< } else if(mid==n-1&&!k){ cout< }else if(k){ cout< }else{ cout< } } //插入排序还是归并排序 #include using namespace std; int a[105],b[105]; int n; bool judge(){ for(int i=0;i if(a[i]!=b[i]) return false; } return true; } int main(){ scanf("%d",&n); for(int i=0;i scanf("%d",&a[i]); for(int i=0;i scanf("%d",&b[i]); bool flag=false; for(int i=2;;i*=2){ for(int j=0;j if(j+i else sort(a+j,a+n); } if(flag){ printf("Merge Sortn"); for(int i=0;i printf("%d%c",a[i]," n"[i==n-1]); break; } if(judge()) flag=true; if(i>n) break; } if(!flag){ printf("Insertion Sortn"); int t=1; while(t while(t>0&&b[t-1]>b[t]){ swap(b[t-1],b[t]); t--; } for(int i=0;i printf("%d%c",b[i]," n"[i==n-1]); } return 0; } //圆排列问题 #include using namespace std; const int N=20; double minlen=1000,x[N],r[N]; double bestr[N]; double center(int t) { double temp=0; for(int j=1;j { double xvalue=x[j]+2.0*sqrt(r[t]*r[j]); if(xvalue>temp) temp=xvalue; } return temp; } void compute(int n) { double low=0,high=0; for(int i=1;i<=n;++i) { if(x[i]-r[i] low=x[i]-r[i]; if(x[i]+r[i]>high) high=x[i]+r[i]; } if(high-low { minlen=high-low; for(int i=1;i<=n;++i) bestr[i]=r[i]; } } void backtrack(int t,int n) { if(t==n+1) { compute(n); } else { for(int j=t;j<=n;++j) { swap(r[t],r[j]); double centerx=center(t); if(centerx+r[t]+r[1] { x[t]=centerx; backtrack(t+1,n); } swap(r[t],r[j]); } } } int main() { int n; cin >> n; for(int i=1;i<=n;++i) cin >> r[i]; backtrack(1,n); printf("%.4fn",minlen); for(int i=1;i<=n;++i) cout< cout< return 0; } //全排列（回溯，字典序） #include using namespace std; int a[11]; int main(){ int n; cin>>n; for(int i=0;i a[i]=i+1; } do{ for(int i=0;i