全 1 子矩阵
分析：
扩范围，到最后看面积是否等于1的个数
实现：
int T;
int sum;
int n, m;
char g[N][N];
void solve()
{
sum = 0;
for (int i = 1; i <= n; i++)
{
cin >> g[i] + 1;
}
int x1 = n + 1, x2 = 0, y1 = m + 1, y2 = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (g[i][j] == '1')
x1 = min(x1, i), x2 = max(x2, i), y1 = min(y1, j), y2 = max(y2, j), sum++;
if (sum && sum == (y2 - y1 + 1) * (x2 - x1 + 1))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
signed main()
{
FAST;
T = 1;
// cin >> T;
while (cin >> n >> m)
solve();
return 0;
}
组合数
分析：
计算组合数，乘大的除小的，1^18要开__int128或者直接高精度
实现：
void solve()
{
k = min(k, n - k);
__int128 q = 1;
for (int i = 0; i < k; i++)
{
q *= (n - i);
q /= (i + 1);
if (q >= 1e18 || q <= 0)
{
q = 1e18;
break;
}
}
cout << (int)q << endl;
}
Numbers
题意：
多个不同的数构成一个串，不带前导0，求拆分方案数
分析：
len小于50，DFS
实现：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 20010, MOD = 1e9 + 7;
int T;
string s;
map<int, int> mp;
int res, len;
void dfs(int u)
{
if (u > len)
{
res++;
return;
}
int t = s[u] - '0';
if (!mp[t])
{
mp[t]++;
dfs(u + 1);
mp[t]--;
}
if (s[u] != '0' && u + 1 <= len)
{
int now = t * 10 + s[u + 1] - '0';
if (mp[now])
{
return;
}
else
{
mp[now]++;
dfs(u + 2);
mp[now]--;
}
}
}
void solve()
{
s = " " + s;
len = s.size() - 1;
mp.clear();
res = 0;
dfs(1);
cout << res << endl;
}
signed main()
{
FAST;
T = 1;
// cin >> T;
while (cin >> s)
solve();
return 0;
}
4 Buttons
题意：
在（0，0）点向四个方向，每个方向一次最多走的步数不同，最多走 n 次，求可以经过的点的数量
分析：
求面积，等差求和
实现：
void solve()
{
int ans = 1;
ans = (ans + (((a * b % MOD) * n % MOD) * (n - 1) % MOD) * inf % MOD) % MOD;
ans = (ans + (((a * d % MOD) * n % MOD) * (n - 1) % MOD) * inf % MOD) % MOD;
ans = (ans + (((c * b % MOD) * n % MOD) * (n - 1) % MOD) * inf % MOD) % MOD;
ans = (ans + (((c * d % MOD) * n % MOD) * (n - 1) % MOD) * inf % MOD) % MOD;
ans = (ans + (((n * a % MOD + n * b % MOD) % MOD + n * c % MOD) % MOD + n * d % MOD) % MOD) % MOD;
cout << ans << endl;
}