B Tokitsukaze and Development Task
题意:
abcd四种资源,每种资源的初始值都是10,上限是300,下限是10
有几种操作:加减1,加减10,加减100,加到上限,减到下限(一次操作只能进行一种资源)
每种资源都是规定值,请问总共需要操作多少次,可以使每一种资源都达到规定值
BFS
#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 10;
int dist[N];
void bfs()
{
memset(dist, -1, sizeof dist);
int dx[] = {-1, 1, -10, 10, -100, 100, 300, -300};
queue<int>q;
q.push(10);
dist[10] = 0;
while(!q.empty())
{
int x = q.front();
q.pop();
for(int i = 0; i < 8; i ++)
{
int u = x + dx[i];
u = min(300, u);//直接增加到上限
u = max(10, u);//直接减少到下限
if(dist[u] != -1) continue;
dist[u] = dist[x] + 1;
q.push(u);
}
}
}
int main()
{
int t; cin >> t;
bfs();
while(t --)
{
int a, b, c, d;
cin >> a >> b >> c >> d;
cout << dist[a] + dist[b] + dist[c] + dist[d] << endl;
}
return 0;
}
F Bitwise Or vs LCM
题意:
给出长度为n的序列a,找二元组(i, j),满足ai | aj <= lcm(ai, aj);其中i < j; ∣代表按位或,lcm代表最小公倍数。如果无解,输出 −1。
最大公约数:
被除数与除数的最大公因数就是:除数于余数的最大公约数
int gcd(int a, int b)
{
if(b == 0)
return a;
return gcd(b, a % b);
}
最小公倍数:
就是两者的积 与 最大公约数的商
int lcm(int a, int b)
{
return a * b / gcd(a, b);
}
打表可以知道,如果两个数成倍数关系就有解
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int st[N], p[N];
//st记录位置, p记录出现的次数
int main()
{
int n; cin >> n;
int a[n + 1];
for(int i = 1; i <= n; i ++)
cin >> a[i], st[a[i]] = i, p[a[i]] ++;
for(int i = 1; i <= n; i ++)
{
int x = a[i];
if(p[x] >= 2)
{
cout << i << " " << st[x] << endl;
return 0;
}
for(int j = 2 * x; j <= 1000000; j += x)
{
if(st[j])
{
cout << min(i, st[j]) << " " << max(i, st[j]) << endl;
return 0;
}
}
}
cout << "-1" << endl;
return 0;
}
I 再交换
题意:
给定两个n位的正整数ab,交换ai和bj,只交换一次使得a<b;i是从左往右数第i位数字,j同理;输出两者的位子
1. a > b,同时从左出发,当ai > bi使,交换即可
2. a < b:
① 找相同的数字,比如 123,245;交换两个的2结果仍然不变
② 找ai<bi,交换两者的后一位,123, 245,交换2和4
之所有有①这种是防止113,114这种情况,这种情况无法通过②进行判断
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t; cin >> t;
while( t -- )
{
int n; cin >> n;
string a, b; cin >> a >> b;
int st[11];
for(int i = 0; i < 11; i ++) st[i] = -1;
bool flag = true;
for(int i = 0; i < n; i ++)
{
int ta = a[i] - '0';
int tb = b[i] - '0';
if(ta > tb)
{
cout << i + 1 << " " << i + 1 << endl;
flag = false;
break;
}
else if(ta < tb)
break;
else continue;
}
if(!flag) continue;
//113 114
bool fla = false;
for(int i = 0; i < n; i ++)
{
int h = a[i] - '0';
st[h] = i;
}
for(int i = 0; i < n; i ++)
{
int h = b[i] - '0';
if(st[h] != -1)
{
cout << st[h] + 1 << " " << i + 1 << endl;
fla = true;
break;
}
}
if(fla) continue;
// 567 689
for(int i = 0; i < n; i ++)
{
int ta = a[i] - '0';
int tb = b[i] - '0';
if(ta < tb)
{
cout << i + 2 << " " << i + 2 << endl;
break;
}
}
}
return 0;
}