A 我会开摆
题意：给定一个4 * 4的矩阵中，若是有一个2 * 2的矩阵被全部涂黑，或者全部都没有被涂黑，那我就很开心，问：我是否开心
思路：简单模拟（参考价值不大）
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
char a[N][N];
bool solve() {
for (int i = 1; i <= 4; i ++ ) {
for (int j = 1; j <= 4; j ++ ) {
cin >> a[i][j];
}
}
for (int i = 1; i <= 3; i ++ ) {
for (int j = 1; j <= 3; j ++ ) {
int ans = 0;
if(a[i][j] == '.') ans ++ ;
if(a[i + 1][j] == '.') ans ++ ;
if(a[i][j + 1] == '.') ans ++ ;
if(a[i + 1][j + 1] == '.') ans ++ ;
if(ans == 0 || ans == 4) {
return true;
}
}
}
return false;
}
int main() {
int t;
cin >> t;
while (t -- ) {
if(solve()) {
cout << "Yes" << endl;
}
else cout << "No" << endl;
}
return 0;
}
B 走廊的灯
题意：走廊中一共有n盏灯，用0表示灯是灭的，用1表示灯是亮的，用2表示灯是闪烁的，问最长有多少盏连续的灯不包含亮着的灯或不包含灭了的灯（满足任意一个即可）？
思路：这里要仔细阅读题目，都是不包含，所有这里面闪烁的灯就很重要了，简化就是求出一个连续最长的不包含0
或者不包含1的最长子串的长度
时间复杂度：O（n）
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 200;
char a[N];
void solve() {
int n;
cin >> n;
// scanf("%s", a + 1);
cin >> a + 1;
n ++ ;
a[n] = '#';
int len = 0;
int ans = 0;
// cout << a + 1 << endl;
// for (int i = 1; i <= n; i ++ ) cout << a[i];
// cout << endl;
//不包含亮着的灯
for (int i = 1; i <= n; i ++ ) {
if(a[i] != '0' && a[i] != '#') len ++ ;
else {
ans = max(ans, len);
len = 0;
}
}
//不包含灭了的灯
len = 0;
for (int i = 1; i <= n; i ++ ) {
if(a[i] != '1' && a[i] != '#') len ++ ;
else {
ans = max(ans, len);
len = 0;
}
}
cout << ans << endl;
}
int main() {
int t;
cin >> t;
while (t -- ) {
solve();
}
return 0;
}
C 输出练习
题意：为了练习输出，你需要从小到大输出 [l,r]范围内能表示为 k 的非负整数次方的所有数。
一共有 T 次练习。注意所有数的 0 次方都是 1，特别地，本题中认为 0 ^ 0 = 1
思路：单独考虑k = 0和k = 1的情况，其他的通过循环得到，时间复杂度其实是很小的
时间复杂度：很小
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void solve() {
LL l, r, k;
cin >> l >> r >> k;
int flag = 0;
if(!k) {
if(l > 1) {
printf("None.\n");
return ;
}
if(l <= 0 && r >= 0) printf("0 ");
if(l <= 1 && r >= 1) printf("1 ");
printf("\n");
return ;
}
if(k == 1) {
if(l <= 1 && r >= 1) printf("1\n");
else printf("None.\n");
return ;
}
LL x = 1;
while (x < l && x <= (LL)r / k) x *= k;
if(x < l || x > r){
printf("None.\n");
}
else {
printf("%lld", x);
//这里不要写成 x * k <= r，由于是指数增加，所以此时的x * k可能会出现爆long long的情况
while (x <= (LL)r / k) {
x *= k;
printf(" %lld", x);
}
printf("\n");
}
}
int main() {
int t;
cin >> t;
while (t -- ) {
solve();
}
return 0;
}
D 国际象棋
题意：有一个竖立的n * m的期盼，因为受到重力的影响，所以每个棋子都会落到最下面，每次都是在数列的最上方放棋子，奇数时间下的是黑棋，偶数时间下的是白棋，当棋盘中出现一个有相同棋子组成的k * k的正方形时，停止下棋，问：最多可以下多少个棋子
思路：模拟，对于没下一个棋子，都向四个方向统计与其相同棋子的数量，若是出现规定的格式，则直接停止计数
时间复杂度：O （n * m）
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int a[N][N];
int f[N * N];
int h[N];
int n, m, k, t;
int dx[] = {-1, -1, -1, 0};
int dy[] = {1, 0, -1, -1};
bool solve(int x, int y) {
for (int i = 0; i < 4; i ++ ) {
int sum = 1;
int xx = dx[i], yy = dy[i];
int tempx, tempy, cnt;
tempx = x, tempy = y, cnt = 0;
while (1 <= tempx && tempx <= m && 1 <= tempy && tempy <= n && a[tempx][tempy] == a[x][y]) {
tempx += xx;
tempy += yy;
cnt ++ ;
}
sum += (cnt - 1);
tempx = x, tempy = y, cnt = 0;
while (1 <= tempx && tempx <= m && 1 <= tempy && tempy <= n && a[tempx][tempy] == a[x][y]) {
cnt ++ ;
tempx -= xx;
tempy -= yy;
}
sum += (cnt - 1);
if(sum >= k) return true;
}
return false;
}
int main() {
cin >> n >> m >> k >> t;
for (int i = 1; i <= t; i ++ ) {
cin >> f[i];
}
memset(a, -1, sizeof a);
for (int i = 1; i <= t; i ++ ) {
//注意棋子实惠叠加的
a[f[i]][ ++ h[f[i]]] = i % 2;
if(solve(f[i], h[f[i]])) {
printf("%d\n", i);
return 0;
}
}
return 0;
}
E 弹性碰撞
题意：在一个长度为n的线段上，有m个弹珠，每个弹珠都是均匀左右移动（0代表向左滚，1代表向右滚），1个时间单位移动1个距离单位，移动的两颗滚动方向相反的弹珠位置重合的时候就会停滞 1 单位时间不滚动，并交换两颗弹珠滚动的方向，弹珠滚到0或者n + 1的位置时，弹珠算作滚出线段，求出当所有的弹珠都离开线段所需的时间
思路：当一个向右的弹珠不断的向右移动时，到达n + 1位置视为出界，若是中间没有相撞的时间为n + 1 - i,但是中间可能会有碰撞产生，若右侧有一个向右移动的弹珠，两者始终都不会相撞，但是若是存在向左移动的弹珠，期间就会有碰撞产生，所以这个弹珠的出界所需的时间为 n + 1 - i + 该弹珠右侧准备向左移动的弹珠的数量，
对于一个向左移动的弹珠，同理可得
注意：
若是在每个弹珠移动的时候都去枚举一下他的左侧或者右侧的与其运动方向相反的弹珠的数量的话，时间复杂度是
O（n ^ 2）,n的数据范围是1e6，所以会超时，此时我们就需要进行预处理，将时间复杂度降到O（n）的级别就行了
时间复杂度：O（n）
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int a[N];//前缀数组
int b[N];//后缀数组
int n, m;
int d[N], seg[N], p[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i ++ ) {
cin >> d[i];
}
for (int i = 1; i <= m; i ++ ) {
cin >> p[i];
seg[p[i]] = (d[i] == 1 ? 1 : -1);
}
for (int i = 1; i <= n; i ++ ) {
a[i] = a[i - 1] + (seg[i] == 1);
}
for (int i = n; i >= 1; i -- ) {
b[i] = b[i + 1] + (seg[i] == -1);
}
int ans = 0;
for (int i = 1; i <= n; i ++ ) {
if(seg[i] == 1) {
ans = max(ans, n + 1 - i + b[i + 1]);
}
else if(seg[i] == -1){
ans = max(ans, i + a[i - 1]);
}
}
cout << ans << endl;
return 0;
}