导航网站怎么赚钱,塘厦镇仿做网站,什么网站可以做兼职赚钱吗,张家界建设局网站电话问题#xff1a;一个八边形每条边都是0#xff0c;现在有取反操作#xff0c;选择一条边取反会同时把当前边和2个邻边取反#xff08;如果是0变为1#xff0c;如果是1变为0#xff09; 现在问你怎么取反能使得八条边都变为1.
当时陷入了暴力递归漩涡#xff0c;给出一个…问题一个八边形每条边都是0现在有取反操作选择一条边取反会同时把当前边和2个邻边取反如果是0变为1如果是1变为0 现在问你怎么取反能使得八条边都变为1.
当时陷入了暴力递归漩涡给出一个2的8次方复杂度的解被薄纱了 讨论过程中发现如果决定了相邻2条边之后就可以依次决定所有边如果成功说明这选择可行2条边一共就4种情况取取不取取取不取不取不取挨个试就行如果都不行就是不行该复杂度就只有On太漂亮了过去了一年多现在决定代码实现一下
ps每一条边也只会被三条边影响
#includeiostream
#includevector
#includemap
using namespace std;void changenumber(int i) {if (i ! 0 i ! 1)return;if (i 0)i 1;else if (i 1)i 0;
}
void doback(int a[], int i,int n) {if (i n)return;if (i 0) {changenumber(a[n - 1]);changenumber(a[0]);changenumber(a[1]);}else if (i n - 1) {changenumber(a[n - 1]);changenumber(a[n-2]);changenumber(a[0]);}else {changenumber(a[i-1]);changenumber(a[i]);changenumber(a[i1]);}
}void printnums(int a[],int n) {for (int i 0; i n; i) {printf(%d , a[i]);}printf(\n);
}void printstrings(string a[], int n) {for (int i 0; i n; i) {printf(%s \n, a[i]);}
}int Finalnums(int a[],int flag[], int i, int j,int ido,int jdo,int n) {if (ido) {doback(a, i, n);flag[i] 2;}else {flag[i] 1;}if (jdo) {doback(a, j, n);flag[j] 2;}else {flag[j] 1;}j;while (j n) {if (a[j-1] 0) {doback(a, j, n);flag[j] 2;}else {flag[j] 1;}j;}j 0;if (i 0)return a[n-1];if (a[n - 1] 0) {doback(a, j, n);flag[j] 2;}else {flag[j] 1;}j;while (j i) {if (a[j - 1] 0) {doback(a, j, n);flag[j] 2;}else {flag[j] 1;}j;}return a[j - 1];
}void resetnums(int a[], int n) {for (int i 0; i n; i) {a[i] 0;}
}
int main() {int a[8] { 0 };int flag[8] { 0 };if (Finalnums(a, flag, 0, 1, 0, 0, 8)) {printf(0不取1不取就可以满足要求);printnums(a, 8);printnums(flag, 8);resetnums(a, 8);resetnums(flag, 8);}if (Finalnums(a, flag, 0, 1, 1, 0, 8)) {printf(0取1不取就可以满足要求);printnums(a, 8);printnums(flag, 8);resetnums(a, 8);resetnums(flag, 8);}if (Finalnums(a, flag, 0, 1, 0, 1, 8)) {printf(0不取1取就可以满足要求);printnums(a, 8);printnums(flag, 8);resetnums(a, 8);resetnums(flag, 8);}if (Finalnums(a, flag, 0, 1, 1, 1, 8)) {printf(0取1取就可以满足要求);printnums(a, 8);printnums(flag, 8);resetnums(a, 8);resetnums(flag, 8);}
}有明确思路都写了一小时属实有点难度了
想了想第二种真就随便想啊 依稀记得面试官说考察候选人智力焯
