ALL IN

5417

Brou_6
StarLi9ht
Wing_wing_wing
_watermelon_
lorendw7

1357649762
acwing_2389

Chaleur
xiaoYun_succ
Tequila

ap-yyyy
Kat_
yxc的小迷妹

## 思考：

### 2.最后如果L = n意味着什么？

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 100010;

int n, x;
int a[N];

int main()
{
cin >> n >> x;
for(int i = 1; i <= n; i ++)
{
scanf("%d", &a[i]);
}
int l = 0, r = n + 1;
while(l + 1 < r)
{
int mid = (l + r) / 2;
if(a[mid] < x)
{
l = mid;
}
else r = mid;
}
printf("%d\n", l);
return 0;
}


11 11
1 4 7 9 9 11 12 15 17 19 21

5

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 100010;

int n;
int h[N];

bool col(int x)
{
int e = x;
for(int i = 1; i <= n; i ++)
{
if(e >= 100000)
break;
e = 2 * e - h[i];
if(e < 0) return false;
}
return true;
}

int main()
{
cin >> n;
for(int i = 1; i <= n; i ++)
{
scanf("%d", &h[i]);
}
int l = 1, r = 100000;
while(l + 1 < r)
{
int mid = (l + r) >> 1;
if(col(mid))
{
r = mid;
}
else l = mid;
}
printf("%d\n", r);
return 0;
}


#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

double n;

int main()
{
cin >> n;
double l = -10000, r = 10000;
while(r - l > 1e-8)
{
double mid = (l + r) / 2;
if(mid * mid * mid <= n)
{
l = mid;
}
else r = mid;
}
printf("%lf\n", r);
return 0;
}


#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int q[N];

int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

for (int i = 0; i < m; i ++ )
{
int x;
scanf("%d", &x);
// 二分x的左端点
int l = 0, r = n - 1;   // 确定区间范围
while (l < r)
{
int mid = l + r >> 1;
if (q[mid] >= x) r = mid;
else l = mid + 1;
}

if (q[r] == x)
{
cout << r << ' ';

// 二分x的右端点
r = n - 1;  // 右端点一定在[左端点, n - 1] 之间
while (l < r)
{
int mid = l + r + 1 >> 1;   // 因为写的是l = mid，所以需要补上1
if (q[mid] <= x) l = mid;
else r = mid - 1;
}
cout << r << endl;
}
else cout << "-1 -1" << endl;
}

return 0;
}


#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
typedef pair<int, int> PII;

const int N = 5;

char g[N][N];
vector<PII> ans, tmp;

void turn_all(int x, int y)
{
for(int i = 0; i < 4; i ++)
{
if(g[x][i] == '+') g[x][i] = '-';
else if(g[x][i] == '-') g[x][i] = '+';
}
for(int i = 0; i < 4; i ++)
{
if(g[i][y] == '+') g[i][y] = '-';
else if(g[i][y] == '-') g[i][y] = '+';
}

//g[x][y]的那个点要改变三次
if(g[x][y] == '+') g[x][y] = '-';
else if(g[x][y] == '-') g[x][y] = '+';

return ;
}

void dfs(int x, int y)
{
//所有把手操作完了, 看看能不能打开
if(x == 3 && y == 4)
{
bool has_off = false;
for(int i = 0; i < 4; i ++)
{
for(int j = 0; j < 4; j ++)
{
if(g[i][j] == '+')
{
has_off = true;
return ;
}
}
}
if(!has_off)
{
if(ans.empty() || ans.size() > tmp.size())
{
ans = tmp;
}
}
return ;
}

//边界
if(y == 4) x++, y = 0;

//改变把手状态
turn_all(x, y);
tmp.push_back({x, y});
dfs(x, y + 1);

//恢复现场
tmp.pop_back();
turn_all(x, y);

//不改变把手状态
dfs(x, y + 1);
}

int main()
{
for(int i = 0; i < 4; i ++)
{
cin >> g[i];
}

dfs(0, 0);

cout << ans.size() << endl;
for(int i = 0; i < ans.size(); i ++)
{
printf("%d %d\n", ans[i].first + 1, ans[i].second + 1);
}
return 0;
}


#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 110;

char start[N];
char end1[N];

void turn(int i)
{
if(start[i] == '*') start[i] = 'o';
else start[i] = '*';
return ;
}

int main()
{
cin >> start >> end1;
int n = strlen(start);
int res = 0;
for(int i = 0; i < n - 1; i ++)
{
if(start[i] != end1[i])
{
res ++;
turn(i), turn(i + 1);
}
}
cout << res << endl;
return 0;
}


res = min(res, step);把最小步数存一下，就能找到最优解

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 6;

int T;
char g[N][N], backup[N][N];

int dx[] = {0, 0, 1, 0, -1};
int dy[] = {0, 1, 0, -1, 0};

void turn(int x, int y)
{
for(int i = 0; i < 5; i ++)
{
int a = x + dx[i];
int b = y + dy[i];
if(a < 0 || a >= 5 || b < 0 || b >= 5) continue;
if(g[a][b] == '1')
g[a][b] = '0';
else if(g[a][b] == '0')
g[a][b] = '1';     //或者直接g[a][b] ^= 1;   //异或，不同的时候就变成相反的数
}
}

int main()
{
cin >> T;
for(int i = 0; i < T; i ++)
{
for(int i = 0; i < 5; i ++)
{
cin >> g[i];
}

int res = 10; //最大步数为6, 定义个比6大的数

//直接枚举第一排的所有可能按开关的可能性, 2^5 = 32, 不必考虑第一排初始是什么
for(int op = 0; op < 32; op ++)
{
memcpy(backup, g, sizeof g); //备份
int step = 0;
for(int i = 0; i < 5; i ++)
{
//第一排有2^5种按法，枚举每种开关的按法（用二进制来枚举）
//这是枚举按还是不按那个开关，而不是选择第一排一开始是什么状态的。
//这里1表示按了，0表示不按。
if(op >> i & 1)  //看二进制的第i位是不是1
{
step ++;
turn(0, i);
}
}

//枚举前四排
for(int i = 0; i < 4; i ++)
{
for(int j = 0; j < 5; j ++)
{
//如果是'0', 则改变下一排开关的状态
if(g[i][j] == '0')
{
step ++;
turn(i + 1, j);
}
}
}

//遍历最后一排, 如果有黑(0)的,则说明该方案行不通
int dark = 0;
for(int i = 0; i < 5; i ++)
{
if(g[4][i] == '0')
{
dark = 1;
break;
}
}

if(!dark) res = min(res, step);

//开关复原
memcpy(g, backup, sizeof g);
}

if(res > 6) res = -1;
cout << res << endl;
}

return 0;
}


### 递推

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 50;

int n;

int main()
{
cin >> n;
int a = 0;
int b = 1;
int tmp = 0;
for(int i = 0; i < n; i ++)
{
printf("%d ", a);
tmp = a + b;
a = b;
b = tmp;
}
return 0;
}


#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 10;

int n;  //要求的数
int num[N]; //保留全排列的结果
bool st[N];  //标记
int cnt;  //答案数量

//计算num数组中一段的数是多少
int cal(int l, int r)
{
int res = 0;
for(int i = l; i <= r; i ++)
{
res = res * 10 + num[i];
}
return res;
}

void dfs(int x)
{
if(x == 9)
{
for(int i = 0; i < 7; i ++)
{
for(int j = i + 1; j < 8; j ++)
{
//全排列分为三段, 插两个板
int a = cal(0, i);
int b = cal(i + 1, j);
int c = cal(j + 1, 8);

// 注意判断条件，因为C++中除法是整除，所以要转化为加减乘来计算
if(a * c + b == c * n)
{
cnt ++;
}
}
}
}

//全排列
for(int i = 1; i <= 9; i ++)
{
if(!st[i])
{
num[x] = i;
st[i] = 1;
dfs(x + 1);
st[i] = 0;
}
}
}

int main()
{
cin >> n;
dfs(0);
printf("%d\n", cnt);
return 0;
}


### 剪枝:为什么是x + n - start < m?

(x - 1)  +  (n - start + 1)  <  m


#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 30;

int n, m;
int way[N];

void dfs(int x, int start)
{
//剪枝儿~
if(x + n - start < m)
return ;

if(x == m + 1)
{
for(int i = 1; i <= m; i ++)
{
printf("%d ", way[i]);
}
cout << endl;
return ;
}

for(int i = start; i <= n; i ++)
{
way[x] = i;
dfs(x + 1, i + 1);
way[x] = 0; //可省略, 恢复现场
}
return ;
}

int main()
{
scanf("%d %d", &n, &m);
dfs(1, 1);
return 0;
}