显然直接枚举找个答案就好。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
for (int x = 1;; x++)
{
if (n + x == min(756, m + x / 4))
{
cout << n + x;
return 0;
}
}
return 0;
}
很多后期选手一看就二分，但是没有注意到 会超 long long 直接就没了。
实际上因为最终乘积的小于 ，所以较短的那条边必然小于 ，所以直接枚举就好了。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, L, R;
signed main()
{
cin >> n >> L >> R;
for (int i = 1; i <= n / 2; i++)
{
int j = n - i;
if (i * j > R)
break;
if (L <= i * j && i * j <= R)
{
cout << i << " " << j << "\n";
return 0;
}
}
cout << "-1\n";
return 0;
}
有三个小考点，怎么输入，怎么输出第一行，怎么输出第二行。
输入可以用 char 吃掉多余单个字符，然后读整数的方法读每个整数。也可以直接不停读字符然后处理。
第一行的内容就是要细致，按题目要求一点点处理。
第二行很多同学会用一元二次方程求根公式。但实际先排除无解和都是解之后，可以看最初给的形式 ，就确定了根就两个 。
#include <bits/stdc++.h>
#define int long long
using namespace std;
char t;
int i, n, j, m;
signed main()
{
cin >> t >> i >> t >> t >> n >> t; // (ix+n)
cin >> t >> j >> t >> t >> m >> t; // (jx+m)
int a = i * j;
int b = i * m + j * n;
int c = n * m;
if (a != 0)
{
if (a != 1)
cout << a;
cout << "x^2";
}
if (b != 0)
{
if (a != 0)
cout << "+";
if (b != 1)
cout << b;
cout << "x";
}
if (c != 0)
{
if (a != 0 || b != 0)
cout << "+";
cout << c;
}
cout << "\n";
bool flag = false;
int ans;
if (a == 0 && b == 0)
{
if (c == 0)
flag = true, ans = 33;
}
else if (a == 0)
{
if (c % b == 0)
flag = true, ans = -c / b;
}
else
{
// (ix+n)(jx+m)
if (n % i == 0)
flag = true, ans = -n / i;
if (m % j == 0)
flag = true, ans = -m / j;
}
if (flag)
cout << ans << "\n";
else
cout << "No\n";
return 0;
}
这题的原题是我收藏已久的 P7167 [eJOI2020 Day1] Fountain
直接暴力枚举就好。
#include <bits/stdc++.h>
using namespace std;
int n, m, T, k;
// 敌人战斗力，敌人胆量
int a[100000 + 5], b[100000 + 5];
// 返回从 pos 开始的游戏结局
int f(int pos)
{
//cout << "====" << pos << "====\n";
int health = n;
int power = 0;
while (pos <= m)
{
// 吓跑直接不战斗
if (b[pos] <= power)
{
pos++;
continue;
}
// 战斗结算
health -= a[pos];
power = b[pos];
//cout << pos << ":" << health << "," << power << "\n";
if (health <= 0)
return pos;
pos++;
}
return 0;
}
int main()
{
cin >> n >> m >> T;
for (int i = 1; i <= m; i++)
cin >> a[i] >> b[i];
for (int i = 1; i <= T; i++)
{
int k;
cin >> k;
cout << f(k) << "\n";
}
return 0;
}
因为此时肯定是一个个打过去，所以可以直接处理个前缀和，然后二分就能找到结束位置了。
都在注释里了。也可以去原题看看题解。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, T, k;
const int MAXN = 100000;
// 敌人战斗力，敌人胆量
int a[MAXN + 5], b[MAXN + 5];
// f[i][j] 记录 i 后面第 2^j 个是谁
// g[i][j] 记录 i 开始后面的 2^j 个敌人的战斗力之和
int f[MAXN + 5][25];
int g[MAXN + 5][25];
// 单调栈计算每个敌人下一个胆量大于他的在哪儿
stack<int> s;
void init()
{
// 预处理 2^0 层
for (int i = m; i >= 1; i--)
{
// 去掉栈顶小于等于 b[i] 的
while (!s.empty() && b[s.top()] <= b[i])
s.pop();
// 现在的栈顶就是下一个大于 b[i] 的位置
g[i][0] = a[i];
if (s.empty())
f[i][0] = 0;
else
f[i][0] = s.top();
// 当前编号放入单调栈
s.push(i);
}
// 处理 2^k 层
for (int k = 1; k <= 20; k++)
for (int i = 1; i <= m; i++)
{
int ii = f[i][k - 1]; // 往后 2^{k-1} 层的位置
f[i][k] = f[ii][k - 1];
g[i][k] = g[i][k - 1] + g[ii][k - 1];
}
}
// 计算从 pos 位置开始，初始血量为 n，最终打败的是谁
int cal(int pos)
{
int health = n;
for (int k = 20; k >= 0; k--)
{
if (g[pos][k] < health)
{
health -= g[pos][k];
pos = f[pos][k];
}
}
return pos;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
cin >> m >> T;
for (int i = 1; i <= m; i++)
cin >> a[i] >> b[i];
init(); // 预处理 f,g
for (int i = 1; i <= T; i++)
{
int k;
cin >> k;
cout << cal(k) << "\n";
}
return 0;
}