新疆大学新生赛题解[ABCDEFIJ]
https://ac.nowcoder.com/acm/contest/66443
A小莫的字符[统计个数]
小莫有一个均由小写字母构成的字符串,现在需要你去统计这个字符串中字符x,j,u三个字母分别的出现次数。
我们就依次统计三个字母分别出现了多少次
code
#include <bits/stdc++.h>
#define int long long
int n, m;
void solve() {
std::string s;
std::cin>>s;
std::cout<<count(begin(s),end(s),'x')<<' ';
std::cout<<count(begin(s),end(s),'j')<<' ';
std::cout<<count(begin(s),end(s),'u')<<' ';
}
signed main() {
solve();
return 0;
}
B小莫的蛋糕[前缀和or暴力]
小莫想做一条很长很长的蛋糕!但是由于小莫技艺还不太完善,所以蛋糕每隔一定长度 的质量都是不同的
现在小莫又想把蛋糕切成质量相近的两半,小莫想知道 两半蛋糕相差的重量 最少是多少
蛋糕可以视为 $n$ 个 小蛋糕 其中每个蛋糕的质量是$a_i$ ,小莫可以在小蛋糕的连接处进行切割
$1 \leqq n \leqq 1e3,1 \leqq a_{i} \leqq 1e5$
看到数据范围然后我们可以知道这个题$O(n^2)$的时间复杂度也是可以过的
然后两个for暴力枚举就好
或者是前缀和预处理两端的质量,然后$O(n)$枚举切点
前缀和code
#include <bits/stdc++.h>
#define int long long
int n, m;
void solve() {
std::cin >> n;
std::vector<int> a(n + 1);
std::vector<int> s(n + 1);
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
}
for (int i = 1; i <= n; i++) {
s[i] = s[i - 1] + a[i];
}
int ans = INT_MAX;
for (int i = 1; i <= n; i++) {
if (ans > abs(s[n] - s[i] - s[i])) ans = abs(s[n] - s[i] - s[i]);
}
std::cout << ans << "\n";
}
signed main() {
solve();
return 0;
}
C小莫的平方[欧拉定理]
小莫有一个非常大的数x,假设$t=x\pmod{k}$为现在需要你求出${(x-t+1)^x\pmod{k^2}}$。
$x\geqq1,1\leqq k \leqq 1e6$
且$x$的位数小于等于$1e6$
由于这个题目的$x$是个很大的数字,unsigned long long
也无法存储这样的数字
所以我们用字符串来存储
根据欧拉定理我们可以知道
${(x-t+1)^x\pmod{k^2}}={(x\%k^2-t\%k^2+1)^{x\%k^2}\pmod{k^2}}$
然后剩下的地方都是在$k^2$范围内可以运算的了
由于$ k \le 10^6$所以$ k^2 \le 10^{12}$
用long long
便可以存储
code
#include <bits/stdc++.h>
#define int long long
int n, m;
int phi(int n) // 求欧拉函数
{
int res = n;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) res = res / i * (i - 1);
while (n % i == 0) n /= i;
}
if (n > 1) res = res / n * (n - 1);
return res;
}
int Mod(std::string s, int mod) {
int ans = 0;
for (auto it : s) {
ans *= 10;
ans %= mod;
ans += it - '0';
ans %= mod;
}
return ans;
}
int qmi(int a, int b, int p) {
int res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
void solve() {
std::string x;
int k;
std::cin >> x >> k;
int mi = Mod(x, k * k);
int di = Mod(x, k * k) - Mod(x, k) + 1;
std::cout << qmi(di, mi, k * k);
}
signed main() {
solve();
return 0;
}
D小莫的棋盘[奇偶性]
小莫有一个黑白相间的国际象棋棋盘,且$1*1$的位置是黑色,小莫想知道棋盘上总共有多少个黑色格子。
根据图片我们可以发现如果行和列有一个是偶数的话,那么黑色和白色都是一一对应的
那么也就是黑色和白色的格子数目相等
一共有$n \times m $个格子
黑色和白色分别是$\frac{n\times m}2$
如果行和列都是奇数的话,那么黑色会比白色多一个
给他加上一就好
code
#include <bits/stdc++.h>
#define int long long
int n, m;
void solve() {
std::cin>>n>>m;
if(n&1^1 and m&1^1){
std::cout<<n*m/2;
}else if(n&1 and m&1){
std::cout<<n*m/2+1;
}else if(n&1 and m&1^1){
std::cout<<n*m/2;
}else std::cout<<n*m/2;
}
signed main() {
solve();
return 0;
}
E小莫的积木 [投影] [统计]
请注意aij的值可能为0
小莫有一个$n*m$的网格,网格每个格子上都堆积着数量不等的小正方体,现在需要你求从前后左右上下六个面看过去可以看到的小正方形的数量总和。
[HTML_REMOVED][HTML_REMOVED] [HTML_REMOVED][HTML_REMOVED]
通过观察图形我们可以知道一个性质,就是这个东西
从前面和从后面看是一样大的
从左面和从右面看是一样大的
从上面和从下面看是一样大的
那么从正面看 每一列都是可以看到最高的一个
那么我们就预处理出最高的一个
然后进行统计个数就好
code
#include <bits/stdc++.h>
#define int long long
int n, m;
void solve() {
std::cin >> n >> m;
std::vector<std::vector<int>> a(n + 1, std::vector<int>(m + 1));
std::vector<int> maxx(n + 1);
std::vector<int> maxy(m + 1);
int z = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
std::cin >> a[i][j];
if (a[i][j]) z++;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
maxx[i] = std::max(maxx[i], a[i][j]);
}
}
for (int j = 1; j <= m; j++) {
for (int i = 1; i <= n; i++) {
maxy[j] = std::max(maxy[j], a[i][j]);
}
}
int ans = 0;
for (auto it : maxx) {
ans += it;
}
for (auto it : maxy) {
ans += it;
}
ans += z;
std::cout << ans * 2 << "\n";
}
signed main() {
solve();
return 0;
}
F小莫的游戏[if else]
小莫初中的时候非常喜欢在机房偷偷下井字棋,错失了成为oier的机会,给你一个$3*3$的棋盘,现在需要你帮小莫判断此时的三子连珠状态。
井字棋的三子连珠条件是指横,纵,斜三个方向中的任意一个方向满足三个棋子相同。
如果圆圈满足三子连珠而叉号不满足则输出:awin
如果叉号不满足三子连珠而圆圈满足则输出:bwin
如果两者都满足三子连珠则输出:abwin
如果两者都不满足三子连珠则输出:nonewin
题意中说的很明确了
考验一些码力
要分析完整情况
code
#include <bits/stdc++.h>
#define int long long
int n, m;
void solve() {
std::string s[3];
for (int i = 0; i < 3; i++) {
std::cin >> s[i];
}
bool falg1 = false;
bool falg2 = false;
for (int i = 0; i < 2; i++) {
if (s[i][0] == s[i][1] and s[i][0] == s[i][2]) {
if (s[i][0] == 'O') falg1 = true;
if (s[i][0] == 'X') falg2 = true;
}
}
for (int i = 0; i < 2; i++) {
if (s[0][i] == s[1][i] and s[0][i] == s[2][i]) {
if (s[0][i] == 'O') falg1 = true;
if (s[0][i] == 'X') falg2 = true;
}
}
if (s[0][0] == s[1][1] and s[0][0] == s[2][2]) {
if (s[0][0] == 'O') falg1 = true;
if (s[0][0] == 'X') falg2 = true;
}
if (s[0][2] == s[1][1] and s[0][2] == s[2][0]) {
if (s[0][2] == 'O') falg1 = true;
if (s[0][2] == 'X') falg2 = true;
}
if (falg1 and falg2) {
std::cout << "abwin\n";
} else if (falg1) {
std::cout << "awin\n";
} else if (falg2) {
std::cout << "bwin\n";
} else {
std::cout << "nonewin\n";
}
}
signed main() {
solve();
return 0;
}
I小莫的计数(简单版本)[简单DP]
小莫想要创造一个仅由$MONIKA$六个大写字符构成的长度为$n$的字符串,但是这个字符串有$m$个限制,每个限制包含两个字符$a,b$,代表字符串中字符$b$的前面一个字符一定不能是$a$,求满足条件的字符串的数量,因为字符串的数量可能很大,所以请将答案对$1e9+7$取模。
DP三连
设计DP算法,往往可以遵循DP三连:
我是谁? ——设计状态,表示局面
我从哪里来?
我要到哪里去? ——设计转移
对于这个题我们可以设置以什么结尾的为状态
然后根据以什么结尾看看能不能进行状态转移
最后统计个数
我们第一维设置到了哪一位
第二维设置当前以哪一个字母结尾
$dp[i][j] += dp[i - 1][k]$if j k 可以转移
code
#include <bits/stdc++.h>
#define int long long
int n, m;
const int mod = 1e9 + 7;
void solve() {
std::cin >> n >> m;
std::map<std::pair<int, int>, bool> mp;
std::map<char, int> val;
val['M'] = 0;
val['O'] = 1;
val['N'] = 2;
val['I'] = 3;
val['K'] = 4;
val['A'] = 5;
while (m--) {
char x, y;
std::cin >> x >> y;
int X = val[x];
int Y = val[y];
mp[{X, Y}]+=1;
}
std::vector<std::array<int, 6>> dp(n + 1);
for (int i = 0; i < 6; i++) {
dp[1][i] = 1;
}
for (int i = 2; i <= n; i++) {
for (int j = 0; j < 6; j++) {
for (int k = 0; k < 6; k++) {
if (!mp.count({k, j})) {
dp[i][j] += dp[i - 1][k];
dp[i][j] %= mod;
}
}
}
}
int ans = 0;
for (int i = 0; i < 6; i++) {
(ans += dp[n][i])%=mod;
}
std::cout << ans << "\n";
}
signed main() {
int __;
std::cin >> __;
while (__--) solve();
return 0;
}
J小莫的计数
第一行包含一个整数$T$代表数据组的个数。
每组数据的第一行包含两个整数$n,m$,代表字符串的长度和限制的个数,接下来$m$行每行有俩个字符,并且保证字符串中只会出现$M,O,N,I,K,A$六个大写字母。
$1\leqq T \leqq 1e4$
$1\leqq n \leqq 1e9$
$0 \leqq m \leqq 36$
这个题题面和上一个题面一样
只是数据范围变成了1e9
如果再依次进行转移的话就会超时
所以我们使用矩阵快速幂的方式对DP的转移进行优化
code
#include <bits/stdc++.h>
#define int long long
const int mod = 1e9 + 7;
// 定义矩阵乘法
std::vector<std::vector<int>> matrixMultiply(
const std::vector<std::vector<int>>& A,
const std::vector<std::vector<int>>& B) {
int n = A.size();
int m = B[0].size();
int k = B.size();
std::vector<std::vector<int>> result(n, std::vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int x = 0; x < k; x++) {
result[i][j] += A[i][x] * B[x][j] % mod;
result[i][j] %= mod;
}
}
}
return result;
}
// 计算转移矩阵的n次方
std::vector<std::vector<int>> matrixPower(
const std::vector<std::vector<int>>& mat, int n) {
int size = mat.size();
if (n == 1) return mat;
if (n % 2 == 0) {
std::vector<std::vector<int>> half = matrixPower(mat, n / 2);
return matrixMultiply(half, half);
} else {
std::vector<std::vector<int>> half = matrixPower(mat, n / 2);
return matrixMultiply(matrixMultiply(half, half), mat);
}
}
void solve() {
int n, m;
std::cin >> n >> m;
std::map<std::pair<int, int>, bool> mp;
std::map<char, int> val;
val['M'] = 0;
val['O'] = 1;
val['N'] = 2;
val['I'] = 3;
val['K'] = 4;
val['A'] = 5;
while (m--) {
char x, y;
std::cin >> x >> y;
int X = val[x];
int Y = val[y];
mp[{X, Y}]+=1;
}
std::vector<std::vector<int>> transitionMatrix(6, std::vector<int>(6, 0));
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 6; j++) {
if (!mp.count({j, i})) {
transitionMatrix[i][j] = 1;
}
}
}
std::vector<std::vector<int>> resultMatrix =
matrixPower(transitionMatrix, n - 1);
int ans = 0;
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 6; j++) {
ans += resultMatrix[i][j];
ans %= mod;
}
}
std::cout << ans << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0), std::cout.tie(0);
std::cout << std::fixed << std::setprecision(15);
std::cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
int __;
std::cin >> __;
while (__--) solve();
return 0;
}