A-小红的整数操作
这题似乎测试数据没有题目看起来的大
对取模的简单考察:
每个数在取模K后的余数相同,那么通过n次加K后,必定可以相同。
通过X = k * n1 + b-----------Y = k * n2 + b容易得出;
#include <bits/stdc++.h>
using namespace std;
#define LF(x) fixed<<setprecision(x)
#define ios ios::sync_with_stdio(false)
#define endl '\n'
typedef long long ll;
const int N = 1e5 + 10, M = 2e1 + 8;
const int mod = 10;
int a[N];
int main()
{
int n, k, maxn = 0, ans = 0;
cin >> n >> k;
for (int i = 0; i < n; i ++)
{
cin >> a[i];
a[i] %= k;//取模操作
}
sort(a, a + n);
//统计相同的模的元素数最大值
for(int i = 0; i < n - 1; i ++)
{
if(a[i] == a[i + 1]) ans ++;
else ans = 0;
maxn = max(maxn, ans);
}
cout << maxn + 1<< endl;
return 0;
}
B-小红的01串
- 在遇到相邻两个不是同一个字符的区段。
- 可以看作2个‘0’与‘1’交换,相当于冒泡排序, 先把‘0’和‘1’放到一起。
- 之后发现在‘0’或者‘1’只要有一个是偶数时
- 就可以把是偶数个数的‘1’串转化成全是‘0’串或者把是偶数的‘1’串全部转化成‘0’串
#include <bits/stdc++.h>
using namespace std;
string s;
int main()
{
int q, a[2];
cin >> q;
while(q --)
{
a[0] = a[1] = 0;//用于统计‘0’ or '1'的个数
cin >> s;
for(int i = 0; i < s.length(); i ++)
a[s[i] - '0'] ++;//计数
if(a[0] % 2 == 0 || a[1] % 2 == 0)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}
C-小红闯沼泽地
题目注意:
小红只能向左,向下, 向右走。进入不同的地形花费时间为 2。
做题思路:动态规划
除边界外方格可有三种状态得来向左的状态转移过来,向下的状态转移过来, 向右的状态转移过来
我就是没有考虑到向左走
#include <bits/stdc++.h>
using namespace std;
#define LF(x) fixed<<setprecision(x)
#define ios ios::sync_with_stdio(false)
#define endl '\n'
typedef long long ll;
const int N = 2e3 + 10, M = 2e1 + 8;
const int mod = 10;
// setw(n) setfill('0') ## Add leading '0'
//===================================================
int n,m;
bool mp[N][N];//储存平地,沼泽地图
int dp[N][N];//动态规划所用
//===================================================
//===================================================
int main()
{
ios;
cin >> n >> m;
for(int i = 1; i <= n ; i ++)
for(int j = 1; j <= m; j++)
cin >> mp[i][j];//输入
//两者均可预处理数组
fill(dp[0], dp[0] + N*N, 1e5);
// memset(f, 0x7f, sizeof(f));
dp[1][1] = 0;
for(int i = 1; i <= n; i ++)
{
//向下,向右的状态转移
for(int j = 1; j <= m; j ++)
{
//向下的状态转移
if(mp[i][j] == mp[i - 1][j])//地形相同
dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
else//地形不同
dp[i][j] = min(dp[i][j], dp[i - 1][j] + 2);
//向右的状态转移
if(mp[i][j] == mp[i][j - 1])//地形相同
dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
else//地形不同
dp[i][j] = min(dp[i][j], dp[i][j - 1] + 2);
}
for(int j = m; j >= 1; j --)
{
//向左的状态转移
if(mp[i][j] == mp[i][j + 1])//地形相同
dp[i][j] = min(dp[i][j], dp[i][j + 1] + 1);
else//地形不同
dp[i][j] = min(dp[i][j], dp[i][j + 1] + 2);
}
}
cout << dp[n][m] << endl;//输出
return 0;
}
参考代码----牛客:Xhesica_Frost,逍遥人 。
D-小红的漂亮串(二)
思路
根据正难则反的原则,反向考虑。漂亮串的总数 = 总的方案数-没有red的方案数-只有一个red的方案数。
依旧dp(动态规划)
1. 没有red的方案数
- dp[i][1]:长度为i,以“r”结尾的方案数
- dp[i][2]:长度为i,以“e”结尾的方案数
- dp[i][0]:长度为i,以“d”结尾的方案数
- dp[i][0]:长度为i,以其他字母结尾的方案数
- 没有red的方案数为 = dp[n][0] + dp[n][1] + dp[n][2] + dp[n][3]
可以得到状态转移公式
2. 只有一个red的方案
- 可以由没有red的方案数得出
- 确定red的位置,前后的方案数相乘,再枚举出red可能的每一个位置,将得出的乘积相加
3.总的方案数
- 总的方案数 =
具体请看代码部分
#include <bits/stdc++.h>
using namespace std;
#define LF(x) fixed<<setprecision(x)
#define ios ios::sync_with_stdio(false)
#define endl '\n'
typedef long long ll;
const int N = 1e6 + 10, M = 2e1 + 8;
const int mod = 1e9 + 7;
// setw(n) setfill('0') ## Add leading '0'
//===================================================
ll dp[N][4];
//===================================================
void init(int n)
{
dp[1][0] = 23;
dp[1][1] = dp[1][2] = dp[1][3] = 1;
dp[2][1] = 26;
for(int i = 2; i <= n; i ++)
{
ll temp = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) % mod;
dp[i][0] = 23 * temp % mod;
dp[i][1] = temp;
dp[i][2] = temp;
dp[i][3] = ((temp - dp[i - 2][1]) % mod + mod) % mod;
}
}
//快速幂,这题也可直接循环求出26^n,不会TLE
ll quick_pow(ll base, ll power)
{
ll result = 1;
while(power > 0)
{
if (power & 1)
result = result * base % mod;
power >>= 1;
base = (base * base) % mod;
}
return result;
}
//===================================================
int main()
{
int n;
ll ans, left, right;
ios;
cin >> n;
ans = quick_pow(26, n);//通过快速幂求得总方案数
init(n);//状态转移,预处理
//先减去没有red的情况
ans = (ans - (dp[n][0] + dp[n][1] + dp[n][2] + dp[n][3]) % mod + mod) % mod;
//枚举只有一个res时的每个位置的方案数,并减去
for(int i = 1; i <= n - 2; i ++)
{
left = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) % mod;
//防止前面的方案数为0的情况导致乘积为0
left = max(left, 1ll);
right = dp[n - i - 2][0] + dp[n - i - 2][1] + dp[n - i - 2][2] + dp[n - i - 2][3];
//防止后面的方案数为0的情况导致乘积为0
right = max(right, 1ll);
//防止成为负号
ans = (ans - left * right % mod + mod) % mod;
}
cout << ans << endl;
return 0;
}