给定 ,以及 个整数,第 个整数是 。求哪一个整数等于 ,输出对应的 。
#include <bits/stdc++.h>
using namespace std;
int n, a, b, c;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> a >> b;
for (int i = 1; i <= n; i++)
{
cin >> c;
if (c == a + b)
{
cout << i << "\n";
return 0;
}
}
return 0;
}
给定两个 行 列的二维字符数组 。定义纵向切换和横向切换的规则分别如下:
求是否存在 使得将 进行 次纵向切换,然后再进行 次横向切换后,满足 。
如果存在,那么显然存在解满足 , 。看看数据范围,暴力枚举就好了。
#include <bits/stdc++.h>
using namespace std;
int n, m;
char a[35][35], b[35][35];
int check(int s, int t)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (a[i][j] != b[(i + s - 1) % n + 1][(j + t - 1) % m + 1])
return false;
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> b[i][j];
for (int s = 0; s < n; s++)
{
for (int t = 0; t < m; t++)
{
if (check(s, t))
{
cout << "Yes\n";
return 0;
}
}
}
cout << "No\n";
return 0;
}
这是 规模的交叉:
# #
#
# #
这是 规模的交叉:
# #
# #
#
# #
# #
给定一个 行 列的字符画,求每种规模的交叉各有几个。统计时优先统计大的,也就是如果有一个规模为 的交叉,那么不计算这个交叉内部的大小为 的交叉。
数据范围极小,枚举每个中心,暴力扩张都可以。
我这里处理了四个数组,分别表示往四个方向最长有多长连续的 #
#include <bits/stdc++.h>
using namespace std;
int n, m;
char g[105][105];
/*
a b
#
c d
*/
int a[105][105], b[105][105], c[105][105], d[105][105];
int cnt[105];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> g[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (g[i][j] == '#')
a[i][j] = a[i - 1][j - 1] + 1,
b[i][j] = b[i - 1][j + 1] + 1;
for (int i = n; i >= 1; i--)
for (int j = 1; j <= m; j++)
if (g[i][j] == '#')
c[i][j] = c[i + 1][j - 1] + 1,
d[i][j] = d[i + 1][j + 1] + 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (g[i][j] == '#')
cnt[min(min(a[i][j], b[i][j]), min(c[i][j], d[i][j])) - 1]++;
for (int i = 1; i <= min(n, m); i++)
cout << cnt[i] << " ";
return 0;
}
输入 ,求有多少组 满足:
数据规模:
掰手指头算算:
显然可以随手预处理 表示 的质数个数。然后暴力枚举 ,统计有多少个满足条件的 即可。简单估一下时间复杂度,没得超。怕超还可以在枚举 时,只枚举筛法与处理好了的质数部分。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1000000; // MAXC
bool vis[MAXN + 5];
int ptot, phi[MAXN + 5], pri[MAXN + 5];
void init()
{
phi[1] = 1;
for (int i = 2; i <= MAXN; ++i)
{
if (!vis[i])
phi[i] = i - 1, pri[++ptot] = i;
for (int j = 1; j <= ptot; ++j)
{
if (1ll * i * pri[j] > MAXN)
break;
vis[i * pri[j]] = 1;
if (i % pri[j])
phi[i * pri[j]] = phi[i] * (pri[j] - 1);
else
{
phi[i * pri[j]] = phi[i] * pri[j];
break;
}
}
}
}
// 开5次方,下取整
int v5(int x)
{
int l = 1;
int r = min(1000LL, x); // MAXLL > 1000 ^ 5 > 10 ^ 12
int ans = 0;
while (l <= r)
{
int mid = (l + r) / 2;
if (mid * mid * mid * mid * mid <= x)
ans = mid, l = mid + 1;
else
r = mid - 1;
}
return ans;
}
int v3(int x)
{
int l = 1;
int r = min(10000LL, x); // MAXLL > 10000 ^ 3 >= 10 ^ 12
int ans = 0;
while (l <= r)
{
int mid = (l + r) / 2;
if (mid * mid * mid <= x)
ans = mid, l = mid + 1;
else
r = mid - 1;
}
return ans;
}
bool isP(int x)
{
for (int i = 1; i <= ptot; i++)
{
if (pri[i] * pri[i] > x)
break;
if (x % pri[i] == 0)
return false;
}
return true;
}
int n;
int cnt[MAXN + 5]; // MAXC+5
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
init();
cnt[0] = 0;
for (int i = 1; i <= MAXN; i++)
cnt[i] = cnt[i - 1] + (!vis[i]);
cin >> n;
int ans = 0;
int maxa = v5(n);
for (int i = 1; i <= ptot; i++)
{
if (pri[i] > maxa)
break;
int aa = pri[i] * pri[i];
int _n = n / aa;
int maxb = v3(_n);
for (int j = i + 1; j <= ptot; j++)
{
if (pri[j] > maxb)
break;
int b = pri[j];
int __n = _n / b;
int temp = sqrt(__n);
ans += cnt[temp] - cnt[b];
}
}
cout << ans << "\n";
return 0;
}
整数 初始为 ,有一个六面骰子,每次投掷后会等概率得到 的一个整数 。
只要 还小于给定的整数 ,就要进行投掷,并把 变为 。
求最终变成整数 的概率,答案对 取模。
显然若令 表示从 变到 的概率,那么 .
即 .
因为有效状态必然因子只包含 ,数量其实不多,直接 求解即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 998244353;
// a^b (mod p)
long long quick_pow(long long a, long long b, long long p)
{
long long res = 1;
while (b)
{
if (b & 1)
res = (res * a) % p;
b = b >> 1;
a = (a * a) % p;
}
return res;
}
// 求 x 在模 p 意义下的逆元(要求 p 是一个质数)
long long inv(long long x, long long p)
{
return quick_pow(x, p - 2, p);
}
int n, inv5;
// f[i]:从 i 到 n 的概率
// f[i] = sum(1 / 5 * f[i * (2~6)])
map<int, int> f;
int dfs(int x)
{
if (f.find(x) != f.end())
return f[x];
if (x == n)
return 1;
if (x > n)
return 0;
int res = 0;
for (int i = 2; i <= 6; i++)
res = (res + dfs(i * x)) % MOD;
return f[x] = res * inv5 % MOD;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
inv5 = inv(5, MOD);
cout << dfs(1) << "\n";
return 0;
}
输入一串长度为 的,仅包含 o
与 x
的字符串 ,保证至少包含一个 x
。
将这个字符串重复 后即可得到一个长度为 的字符串 。现在需要你进行刚好 次替换操作:“把某个 x
替换为 o
”。
请找到一种方案使得完成替换后的字符串中,“最长的只包含o
的子串” 的长度尽可能大。输出这个最大值。
最终方案其实很好找,全是 o
的要么是单个串的子串。要么是“某个后缀+一些完整串(可以没有)+某个前缀”。
那么实际上就是要计算两个问题:
x
数量少于 。定义
int p[MAXN + 5]; // s[1]~s[i] 的 x 数量
int q[MAXN + 5]; // s[i]~s[n] 的 x 数量
那么显然第一个问题可以枚举子串右端点,然后二分找到最左边的合法左端点。
第二个问题也类似地,可以枚举前缀的右端点,二分找到最左边的后缀的左端点。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 300000;
int n, m, k;
string s;
int all; // 单段 x 总数
int ans; // 答案
int p[MAXN + 5]; // s[1]~s[i] 的 x 数量
int q[MAXN + 5]; // s[i]~s[n] 的 x 数量
// 计算区间包含的 x 数量
int cal(int l, int r)
{
return all - p[l - 1] - q[r + 1];
}
// 一段后缀+一段前缀,最多改 kk 次,最多多少个 o
// a[st~n] + b[1~ed]
int calPQ(int kk)
{
// cout << "cal:" << kk << endl;
int res = 0;
for (int ed = 0; ed <= n; ed++)
{
if (p[ed] > kk)
break;
if (p[ed] == kk && s[n] == 'x')
{
res = max(res, ed);
continue;
}
int l = 1;
int r = n;
int st = -1;
while (l <= r)
{
int mid = (l + r) / 2;
if (q[mid] + p[ed] <= kk)
{
st = mid;
r = mid - 1;
}
else
l = mid + 1;
}
if (st == -1)
break;
// cout << st << " " << ed << " " << q[st] << " " << p[ed] << endl;
res = max(res, (n - st + 1) + ed);
}
return res;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> k;
cin >> s;
s = "x" + s + "x";
// 初始化pq
p[0] = 0;
for (int i = 1; i <= n; i++)
p[i] = p[i - 1] + (s[i] == 'x');
q[n + 1] = 0;
for (int i = n; i >= 1; i--)
q[i] = q[i + 1] + (s[i] == 'x');
all = p[n];
// 特判(all 为 0 及全选)
if (all * m <= k)
{
cout << n * m << "\n";
return 0;
}
// 单段任意位置
for (int ed = 1; ed <= n; ed++)
{
int l = 1;
int r = ed;
int st = -1;
while (l <= r)
{
int mid = (l + r) / 2;
if (cal(mid, ed) <= k)
{
st = mid;
r = mid - 1;
}
else
l = mid + 1;
}
if (st != -1)
ans = max(ans, ed - st + 1);
}
if (m == 1)
{
cout << ans << "\n";
return 0;
}
// 一段后缀直接拼一段前缀
ans = max(ans, calPQ(k));
if (m == 2)
{
cout << ans << "\n";
return 0;
}
// 中间完整的+前后缀
int cnt = 0; // 中间放几段完整的
// 极限
cnt = min(k / all, m - 2);
// cout << cnt << " " << k - cnt * all << " " << calPQ(k - cnt * all) << endl;
ans = max(ans, cnt * n + calPQ(k - cnt * all));
// 极限 -1 段
cnt = max(0LL, cnt - 1);
ans = max(ans, cnt * n + calPQ(k - cnt * all));
// 但求心安的 cnt-2 段
cnt = max(0LL, cnt - 1);
ans = max(ans, cnt * n + calPQ(k - cnt * all));
cout << ans << "\n";
return 0;
}