罗勇军老师每日一题系列
罗老师有专门的题解，这里只是个人的做题总结。 罗老师的QQ群，930175362
1.最小区间
有n头奶牛，奶牛有位置\(P[i]\)和类别\(T[i]\)两种属性，求能够包含所有类别的奶牛的最小区间的长度。
\(1 <= n <= 5e4 , P[i] , T[i] <= 1e9\)
题解
二分答案。
二分区间长度，不断右移左端点的时候，右端点不会左移。
再将种类离散化之后用一个桶维护，就可以\(O(n)\)判断答案的正确与否。
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 5e4+10;
int n , m;
int B[N] , t[N];
struct cow{
int pos , kind;
bool operator < (const cow &B) const { return pos < B.pos; }
}A[N];
bool Check(int len)
{
/*
判断长度为len的区间是否可行。
l不断右移的过程中，r不会左移，保证了复杂度是O(n)的。
关于当前区间的种类数，可以用桶来维护，在出现次数0、1变换时统计。
*/
int r = 0 , num = 0 , F = 0;
for(int l = 1 ; l <= n ; ++l)
{
while(r + 1 <= n && A[r + 1].pos - A[l].pos <= len)
{
r++;
if(t[A[r].kind] == 0) num++;
t[A[r].kind]++;
}
if(num >= m) F = 1;
t[A[l].kind]--;
if(t[A[l].kind] == 0) num--;
}
return F;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int l , r , mid;
cin >> n;
for(int i = 1 ; i <= n ; ++i)
{
cin >> A[i].pos >> A[i].kind;
B[i] = A[i].kind;
}
sort(B + 1 , B + 1 + n);
m = unique(B + 1 , B + 1 + n) - B - 1;
sort(A + 1 , A + 1 + n);
for(int i = 1 ; i <= n ; ++i) // 离散化种类数
A[i].kind = lower_bound(B + 1 , B + 1 + m , A[i].kind) - B;
l = 1; r = 1e9;
while(l < r)
{
mid = (l + r) >> 1;
if(Check(mid)) r = mid; else l = mid + 1;
}
cout << l << '\n';
return 0;
}
2.单位转换
给定 n 组单位换算关系式，q 组询问，每次将某个单位转换成另一个单位。
单位换算关系式：1
表示左边的 1 个单位的
询问格式：
询问
\(1 <= n <= 100 , 1 <= 10000 , <value>为浮点数属于[0.001 , 1000]，小数点后最多9位数字\)
题解
这里我用了类似Floyd的做法，来求出这些单位之间两两转化的比例。
可能是精度问题，导致出了几次WA，所以使用了long double。
#include<unordered_map>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
using namespace std;
unordered_map<string , int> mp;
long double dis[105][105];
int main()
{
int n , m , tot;
long double val;
string str , u , v;
cin >> n >> m; tot = 0;
for(int i = 1 ; i <= n ; ++i)
{
cin >> val;
cin >> u;
cin >> str;
cin >> val;
cin >> v;
if(!mp.count(u)) mp[u] = ++tot;
if(!mp.count(v)) mp[v] = ++tot;
dis[mp[u]][mp[v]] = val;
dis[mp[v]][mp[u]] = 1.0 / val;
}
for(int i = 1 ; i <= tot ; ++i) dis[i][i] = 1.0;
for(int k = 1 ; k <= tot ; ++k)
for(int i = 1 ; i <= tot ; ++i)
for(int j = 1 ; j <= tot ; ++j) // 如果通过了60~80，可以试着加上类似如下的判断
// 本人就是加上这个之后才A掉的。
if(dis[i][j] == 0 && dis[i][k] > 0 && dis[k][j] > 0)
dis[i][j] = dis[i][k] * dis[k][j];
for(int i = 1 ; i <= m ; ++i)
{
cin >> val;
cin >> u;
cin >> str;
cin >> v;
if(mp.count(u) && mp.count(v) && dis[mp[u]][mp[v]] > 0)
cout << fixed << setprecision(8) << dis[mp[u]][mp[v]] * val << '\n';
else
cout << "impossible" << '\n';
}
return 0;
}
3.凑二十四
给n个数字，在n-1个间隔中插入\(+、-、*\)三种运算符，请问有多少种方案可以使得式子的结果为24.
计算时按照正常优先级，即先乘后加减。
\(2 <= n <= 10\)
题解
数据范围很小，可以直接暴力搜索，进行\(3^{10}\)枚举。
这里分享一下计算这个式子的写法。
首先，计算式子中的乘法。
用一个数组（栈）存储，从左往右扫描，如果没有碰到乘法操作则将对应的数字放进去，这个数字前面是加号则就是正的，是减号就认为是负的。
如果碰到了乘法操作就拿出最后一个放入的元素和它相乘再将结果放回数组。
最后将整个数组中剩余的元素累加即可。
这里面因为 \(- (a*b)\) 和 \((-a) * b\)的效果是一样的，所以这些数字就可以直接由它们前面的符号确定正负。
然后遇到乘法操作就 就地完成 然后将结果放进数组。
#include<iostream>
using namespace std;
int n , Answer;
int A[20] , B[20];
long long Stack[20];
int Check()
{
// 1 +
// 2 -
// 3 *
int top = 0;
long long res = 0;
Stack[top = 1] = A[1];
for(int i = 2 ; i <= n ; ++i)
{
if(B[i-1] == 3) // 遇到了乘法
{
while(i <= n && B[i-1] == 3) Stack[top] *= A[i] , i++;
i--;
}
else
if(B[i-1] == 2) // 前是减号
Stack[++top] = -A[i];
else // 前是加号
Stack[++top] = A[i];
}
for(int i = 1 ; i <= top ; ++i) res += Stack[i];
return res == 24;
}
void dfs(int x)
{
if(x == n)
{
Answer += Check();
return ;
}
for(int i = 1 ; i <= 3 ; ++i)
B[x] = i , dfs(x + 1) , B[x] = 0;
}
int main()
{
cin >> n;
for(int i = 1 ; i <= n ; ++i) cin >> A[i];
dfs(1);
cout << Answer << '\n';
return 0;
}
4. 最小公倍数
给一个数字n，问是否存在一个区间，这个区间所有数字的最小公倍数是n。（区间长度大于1）
若有多解，按照左端点为第一关键字，右端点为第二关键字，取小的。
\(1 <= n <= 1e18\)
题解
从大方向上看，一个区间的最小公倍数和这个区间所有数字的乘积差不多。
所以长度大于等于2的区间的枚举范围是\({\sqrt {n}} ^ 2 = 1e18?\)
长度大于等于3的区间的枚举范围就是\({\sqrt[3]{n}} ^ 2 = 1e12 ?\)
而长度为2的区间的最小公倍数就是两个数字相乘。（相邻两个数字的最小公倍数就是这两个数字相乘）
所以可以枚举长度大于等于3的区间计算其最小公倍数，并存储器起来，查询时再输出。
因为lcm增长很快，所以上面的式子其实是远远不满的。
#pragma GCC optimize(2) // 这个O(2)没开的时候TLE了
#include<unordered_map>
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const long long inf = 1e18;
unordered_map<long long , pair<int,int> > mp;
long long gcd(long long a , long long b) { return a ? gcd(b % a , a) : b; }
void Init()
{
register int i , j;
long long res , tmp;
for(i = 1 ; i <= 2e6; ++i) // 左端点大于1e6的长度大于等于3的区间 也有可能lcm <= 1e18
{
res = 1ll * i * (i + 1);
for(j = i + 2 ; ; ++j)
{
tmp = __gcd(res , 1ll * j);
if(res / tmp > inf / j) break;
res = res / tmp * j;
if(!mp.count(res)) mp[res] = make_pair(i , j);
}
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T , t;
long long n;
pair<int,int> Answer;
Init();
scanf("%d" , &T);
while(T--)
{
scanf("%lld" , &n); t = sqrt(n); Answer = make_pair(1e9 , 1e9);
if(mp.count(n)) // 有区间大于等于3的解
Answer = min(Answer , mp[n]);
if(1ll * t * (t + 1) == n) // 有区间长为2的解
Answer = min(Answer , make_pair(t , t + 1));
if(Answer.first != 1e9) // 有解
printf("%d %d\n" , Answer.first , Answer.second);
else
printf("-1\n");
}
return 0;
}