天津网站搜索排名,行政机关单位网站建设规定,荣胜网络 宁波网站建设,网站建设会出现哪些问题传送门
解析
dfs暴力枚举即可 这题的重点是如何剪枝 不难发现#xff0c;随着不断处理#xff0c;纸条只会越来越短#xff0c;且所有数字总加和不变 我一开始想到了2个条件#xff1a; 1.当前长度比理想纸条小#xff0c;return#xff1b; 2.总加和与理想纸条不等随着不断处理纸条只会越来越短且所有数字总加和不变 我一开始想到了2个条件 1.当前长度比理想纸条小return 2.总加和与理想纸条不等直接输出N 但是这样仍是On的级别得到了80分 后来又想到 反转之后对后一半的与反转前对前一半的折叠是等效的所以只需要递归一半的长度即可 从而通过本题
代码
#include cstdio
#include cstring
#include cmath
#include algorithm
#include iostream
#include string
#include queue
#include string
#includemap
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a));
using namespace std;
const int N50;
const int M1e9;
int n,m,mod;
int a[N],b[N];
int save[N][N],save2[N][N];
int flag;
void memory(int l){for(int i0;ia[0];i) save[l][i]a[i];
}
void restore(int l){for(int i0;isave[l][0];i) a[i]save[l][i];
}
void fold(int p){memory(a[0]);int x0,la[0];if(pa[0]/2){for(int isave[l][0];ipp1;i--) a[x]save[l][i];for(int i1;ip;i) a[x]save[l][i]save[l][pp-i1];a[0]-p;}else{for(int i1;i2*p-a[0];i) a[x]save[l][i];for(int i2*p-save[l][0]1;ip;i) a[x]save[l][i]save[l][save[l][0]-(i-(2*p-save[l][0]))1];a[0]-(a[0]-p);}return;
}
void memory2(int l){for(int i0;ia[0];i) save2[l][i]a[i];
}
void restore2(int l){for(int i0;isave2[l][0];i) a[i]save2[l][i];
}
void fanzhuan(){memory2(a[0]);for(int i1;ia[0];i) a[i]save2[a[0]][save2[a[0]][0]-i1];
}
bool judge(){for(int i0;ib[0];i){if(a[i]!b[i]) return false;}return true;
}
void print(){for(int i1;ia[0];i) printf(%d ,a[i]);printf(\n);
}
bool jd(){int pd[N]{},ok[N]{};for(int i1;ia[0];i) pd[i]a[i];sort(pd1,pd1a[0]);for(int i1;ib[0];i) ok[i]b[i];sort(ok1,ok1b[0]);
// for(int i1;ib[0];i){
// printf(b%d a%d\n,ok[i],pd[i]);
// }for(int i1;ib[0];i){if(ok[i]pd[i]) return false;}return true;
}
void dfs(){
// print();if(flag) return;if(a[0]b[0]) return;
// if(!jd()) return;int la[0];if(a[0]b[0]){if(judge()){printf(S\n);flag1;return;}fanzhuan();if(judge()){printf(S\n);flag1;}restore2(l);return;}for(int i1;ia[0]/2;i){fold(i);dfs();if(flag) return;restore(l);}fanzhuan();for(int i1;ia[0]/2;i){fold(i);dfs();if(flag) return;restore(l);}restore2(l);return;
}
int main(){while(scanf(%d,n)1){flag0;int tot0;mem(a,0);mem(b,0);for(int i1;in;i) mem(save[i],0);for(int i1;in;i){scanf(%d,a[i]);tota[i];}a[0]n;scanf(%d,m);for(int i1;im;i){scanf(%d,b[i]);tot-b[i];}b[0]m;if(mn||tot!0){printf(N\n);continue;}dfs();if(!flag) printf(N\n);}return 0;
}
