D
标准签到,因为只能加跟除,所以 A =< B 时就只能执行加法操作
然后 A > B 时,只能对A 不是偶数变偶数然后除 就这样子一直到 A < B。然后执行加法操作。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ll a,b;
cin>>a>>b;
if(b>=a) cout<<b - a<<endl;
else {
ll tot = 0;
ll tot2;
while(a > b){
if(a%2==1){
a = a+1;
tot++;
}
else{
a = a/2;
tot++;
}
}
tot = (b-a) + tot;
cout<<tot<<endl;
}
return 0;
}
E
这个也是一个签到题,一开始想歪了,老是想着以前做过这种类型得,就是总数减去不符合得。
其实题目中的条件,给的很清楚,相同字符但不同索引构成的字符串也是不同的,所以以 aab为例子,字符a有三种情况,字符b有两种情况,(不出现算他们的一种情况)
所以这样子的话就是统计每个字符出现的次数,然后加一 ,然后就最长字符串长度是26,那么就这样子乘下去就行了。
#include<bits/stdc++.h>
#define maxn 100010
#define mod 11092019
using namespace std;
char s[maxn];
int a[27];
int main(){
scanf("%s",s+1);
int l = strlen(s+1);
for(int i=1;i<=l;i++) a[s[i]-'a'+1]++;
ll ans = 1;
for(int i=1;i<=26;i++)
ans =ans* (a[i]+1) % mod;
cout<<ans%nod<<endl;
}
C
c题一开始有一个图,我就没开,想着图论都挺难的,但是看榜单的时候惊奇的发现过的人挺多,然后我就去试试,读完题一看,窝头,这不就是求最短路 - 1 就行了 嘛!!
然后我首先想到的是 BDF+ 队列,就这样扩展 遇到 n 就输出当前tot计数长度 - 1.
然后调了半天,dij求最短路径我感觉不错啊!
但是写了很长了 ,然后 想了想就继续搞了
用一个pair 表示 ans(就是本题要输出的结果) 跟 当前结点,如果到 了 n,就输出 pair中前面那个就行了。
#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define ff first
#define ss second
#define mp make_pair
vector<int>v[maxn];
int vis[maxn];
int main(){
int n, m;
cin>>n>>m;
for (int i = 1; i <= m; i++) {
int x, y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
queue<pii>q;
q.push(mp(0, 1));
while (!q.empty()) {
pii x = q.front(); q.pop();
if (vis[x.ss])continue;
vis[x.ss]++;
for (auto i : v[x.ss])
if (!vis[i]) {
if (i == n) {
printf("%d\n", x.ff); return 0;
}
q.push(mp(x.ff + 1, i));
}
}
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=11092019;
int dis[100100];
vector<int>ve[100100];
int main()
{
ios::sync_with_stdio(0);
int n,m;cin>>n>>m;
while(m--)
{
int x,y;
cin>>x>>y;
ve[x].push_back(y);
ve[y].push_back(x);
}
queue<int> q;
dis[1]=1;
q.push(1);
while(!q.empty())
{
int x=q.front();q.pop();
if(x==n) break;
for(int i:ve[x])
{
if(!dis[i])
{
dis[i]=dis[x]+1;
q.push(i);
}
}
}
cout<<dis[n]-2<<"\n";
return 0;
}
M
很典型的一个 DFS
#include <bits/stdc++.h>
using namespace std;
char Map[2001][2001];
bool vis[2001][2001];
int c[2001][2001];
int cnt = 0;
int mx[] = {0, 0, 1, -1};
int my[] = {1, -1, 0, 0};
void dfs(int x, int y) {
vis[x][y] = true;
c[x][y] = cnt;
for (int i = 0; i < 4; ++i)
if (!vis[x + mx[i]][y + my[i]] && Map[x + mx[i]][y + my[i]] == '.') {
dfs(x + mx[i], y + my[i]);
}
if (!vis[x - 1][y + 1] && Map[x - 1][y + 1] == '.' && ((Map[x][y + 1] == '.' || Map[x - 1][y] == '.') || (Map[x][y + 1] == '/' && Map[x - 1][y] == '/')) ) dfs(x - 1, y + 1);
if (!vis[x - 1][y - 1] && Map[x - 1][y - 1] == '.' && ((Map[x][y - 1] == '.' || Map[x - 1][y] == '.') || (Map[x][y - 1] == '\\' && Map[x - 1][y] == '\\'))) dfs(x - 1, y - 1);
if (!vis[x + 1][y - 1] && Map[x + 1][y - 1] == '.' && ((Map[x][y - 1] == '.' || Map[x + 1][y] == '.') || (Map[x][y - 1] == '/' && Map[x + 1][y] == '/'))) dfs(x + 1, y - 1);
if (!vis[x + 1][y + 1] && Map[x + 1][y + 1] == '.' && ((Map[x][y + 1] == '.' || Map[x + 1][y] == '.') || (Map[x][y + 1] == '\\' && Map[x + 1][y] == '\\'))) dfs(x + 1, y + 1);
}
int main() {
int n, m;
cin>>n>>m;
for (int i = 2; i <= n + 1; ++i) {
scanf("%s", Map[i] + 2);
}
for (int i = 0; i <= n + 3; ++i) {
Map[i][0] = Map[i][m + 3] = '$';
}
for (int i = 0; i <= m + 3; ++i) {
Map[0][i] = Map[n + 3][i] = '$';
}
for (int i = 1; i <= n + 2; ++i) Map[i][1] = Map[i][m + 2] = '.';
for (int i = 1; i <= m + 2; ++i) Map[1][i] = Map[n + 2][i] = '.';
int f1 = 0, f2 = 0;
for (int i = 1; i <= n + 2; ++i)
for (int j = 1; j <= m + 2; ++j) {
if (Map[i][j] == '/' && Map[i][j + 1] == '\\' && Map[i + 1][j] == '\\' && Map[i + 1][j + 1] == '/') ++f1;
if (Map[i][j] == '.' && !vis[i][j]) {
cnt++;
dfs(i, j);
f2++;
}
}
cout<< f1 + f2 - 1<<endl;
}