上海市计算机学会月赛 2022年5月月赛乙组
上海市计算机学会月赛 2022年5月乙组
-
- 天平与砝码（二）
- 数山峰
- 狼人游戏（二）
- 两个闹钟
天平与砝码（二）
内存限制: 256 Mb 时间限制: 1000 ms
题目描述
小爱拥有一台天平，并拥有n个砝码。这些砝码的质量分别为w₁,w₂,…,wₙ在称重过程中，在某些情况下，在将砝码置于与物品同侧时会呈现出减法的效果。特别地，在某些情况下，在将砝码置于与物品同侧时会呈现出减法的效果。请计算这些砝码能够测量出多少种不同的重量值。
输入格式
第一行：单个整数表示 n。
第二行：nn 个整数表示 w_1,w_2,\dots,w_n
输出格式
单个整数：表示可以称量出的不同数量的重量。
数据范围
- 对于 50% 的数据，1≤n≤15；
- 对于 100% 的数据，1≤n≤100。
- 1≤w_i≤100,000；
w_1+w_2+\dots+w_n\leq 100,000
样例数据
输入:
3
1 4 10输出:
12
说明:
能称出的12种重量是：1、3、4、5、6、7、9、10、11、13、14、15
算法分析
正负背包DP递推求解。
#include <iostream>
using namespace std;
const int N = 110, M = 200010, B = M / 2;
int n, m, ans = 0, w[N];
bool f[N][M];
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> w[i], m += w[i];
f[0][B] = true;
for (int i = 1; i <= n; ++i)
for (int j = -m; j <= m; ++j)
{
f[i][j + B] = f[i - 1][j + B];
if (j - w[i] >= -m)
f[i][j + B] |= f[i - 1][j - w[i] + B];
if (j + w[i] <= m)
f[i][j + B] |= f[i - 1][j + w[i] + B];
}
for (int i = B + 1; i <= m + B; ++i)
if (f[n][i])
++ans;
cout << ans << endl;
return 0;
}数山峰
内存限制: 256 Mb 时间限制: 1000 ms
题目描述
在平面直角坐标系中存在n座具有山峰特征的图案。每个山峰都是一个直角等腰三角形，并且这些三角形均位于坐标系中的X轴上作为底边延伸至第一象限内。其中第i座山峰的具体位置由其顶点(x_i, y_i)确定。
当一座山峰的部分位于另一座山峰的内部区域时，则这两部分山峰产生重叠。给定每个山峰会有的坐标点，请统计在不重复计算重叠区域的前提下，请问这些山峰会有的总面积是多少？
输入格式如下：
第一行是一个单一整数值 n；
从第二行开始一直到第n+1行为，
其中每个行为包含两个整数，
分别表示对应的峰顶坐标点 x_i 和 y_i 。
将所有山峰的可见面积设为 ss，并且由于输出要求为整数，则设定输出结果为 4s
数据涵盖情况如下：
当n在39%的数据中时，其取值范围为[下限至上限]；
在67%的数据范围内，则n的取值区间为[相应范围]；
而对于全部样本（即全部测试用例），n的具体数值范围则扩展至[最大值]。
在所有情况下，默认x_i和y_i的取值均满足[约束条件]。
样例输入如下：
输入示例：
共有m个测试用例，
每个测试用例的形式为：
n
接着是n组x_i和y_i的数值对。
输出结果：
针对上述输入，
计算得到的结果为：result。
其中具体的计算过程可参考以下说明部分。
说明内容：
观察图形特征可知，
前两个山体之间存在重叠区域，
其面积计算方法为：sum(各区域面积) - 交集面积 = total_area - overlap_area。
算法分析 三角形形状一致时，则通常与右端点距离最远的点相交。（主要考察几何知识）
#include <iostream>
#include <algorithm>
using namespace std;
struct tran
{
long long x, y; // 坐标
long long l, r; // 左右端点
inline bool operator < (const tran &o) const
{
return l < o.l;
}
} datas[100001];
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(false);
int n, last = 1;
long long ans;
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> datas[i].x >> datas[i].y;
datas[i].l = datas[i].x - datas[i].y; // 左端点
datas[i].r = datas[i].x + datas[i].y; // 右端点
}
sort(datas + 1, datas + n + 1);
ans = datas[1].y * datas[1].y * 4; // 第一个面积
for (int i = 2; i <= n; ++i)
{
if (datas[i].l >= datas[last].r)
{
ans += datas[1].y * datas[1].y * 4;
last = i;
}
else if (datas[i].l < datas[last].r && datas[i].r > datas[last].r)
{
long long t = datas[last].r - datas[i].l;
ans -= t * t;
ans += datas[i].y * datas[i].y * 4; // 加当前的三角
last = i;
}
}
cout << ans;
return 0;
}狼人游戏（二）
内存限制: 256 Mb 时间限制: 1000 ms
参与其中的共有n名玩家正在玩狼人游戏。其中一些人的身份被确定为狼人者,而剩下的其他玩家则被认定为预言家者。随着游戏的发展,在一段时间内共有m次发言依次出现,每次发言都来自一名特定的玩家来说明另一名其他玩家的身份是否正确
小爱提出假说指出：狼人的言论必然是与事实完全相反的立场；而预言家则应坚持与事实一致的观点。她希望进一步验证这一假说是否站得住脚：如果发现矛盾，则需明确指出哪一言论最先引发这种矛盾的发生
第一行包含两个整数 n 和 m。
从第二行到第m+1行为s_i与o_i赋值。
对于每一组s_i与o_i：
如果该组为'T'类型，则表示s_i声称o_i是预言家；
如果该组为'F'类型，则表示s_i声称o_i是狼人。
若所有数据均无冲突，则程序应输出Passed；
否则应输出第一次出现冲突的数据索引。
数据范围及以下
其中当n和m均不超过20时；
当n和m都小于等于3百时；
其中n和m的最大值分别达到了5十万；
样例数据
输入:
4 3
1 2 T
3 4 F
2 1 F
输出:
3
说明:
第三句话与第一句产生了矛盾
输入:
4 4
1 2 F
2 3 T
3 4 T
2 1 F
输出:
Passed
说明:
1是狼人，其余都是预言家，就不会有矛盾
算法分析
这道题涉及并查集技术。将每个节点分解为两个子节点（分别代表狼人与预言家），并判断命题t是否等价于命题f？
#include <iostream>
using namespace std;
int father[5000001];
int getf(int x)
{
if (father[x] == x)
return x;
return father[x] = getf(father[x]); // 递归找father
}
void merge(int x, int y)
{
if (getf(x) == getf(y))
return;
father[getf(x)] = getf(y);
}
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
for (int i = 1; i <= (n << 1); ++i)
father[i] = i;
for (int i = 1; i <= m; ++i)
{
int s, o;
char c;
cin >> s >> o >> c;
if (c == 'T')
{ // s为预言家，o为预言家
merge(s, o);
// s为狼，o为狼
merge(s + n, o + n);
}
else
{
// s为预言家，o为狼
merge(s, o + n);
// s为狼，o为预言家
merge(s + n, o);
}
if (getf(s) == getf(s + n) || getf(o) == getf(o + n))
{
cout << i << endl;
return 0;
}
}
cout << "Passed";
return 0;
}两个闹钟
内存限制: 256 Mb 时间限制: 1000 ms
设有两个闹钟，在时间点a时第一个闹钟首次响起铃声，并且每隔p个单位时间就会再次响起铃声；而在时间点b时第二个闹钟首次响起铃声，并且每隔q个单位时间也会再次响起铃声。请计算这两个闹钟首次同时响起铃声的时间点。
输入格式
第一行：两个整数分别表示 a 与 b；
第二行：两个整数分别表示 p 与 q。
若无法使两个闹钟首次同步，则判断是否存在解并返回结果。具体来说：
若两个闹钟的周期互质，则它们将在某个时间点首次同步；
否则，在一定条件下也会出现同步情况；
无论哪种情况，请计算并返回它们首次同步的时间点。
样例数据
输入:
1 4
2 3
输出:
7
说明:
第一个闹钟响铃的时刻为1,3,5,7
第二个闹钟响铃的时刻为4,7
输入参数为1和2；另一个参数也为2；输出结果为"Impossible"；这是因为第一个事件发生在奇数值时触发而第二个事件则在偶数值时触发从而导致它们永远不会重叠。
每个一分钟的时间点都会响起的第一个闹钟，
以及它在每一分钟内都会触发一次，
其触发的时间点与第二个闹钟首次触发的时间一致。
因此，
经过计算得出的结果为：
10。
算法分析
复杂数学题。
#include <iostream>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b, ll &x, ll &y)
{
if (b == 0)
{
x = 1, y = 0;
return a;
}
ll d = gcd(b, a % b, x, y);
ll t = x;
x = y;
y = t - a / b * y;
return d;
}
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(false);
ll a, b, p, q, k1, k2;
cin >> a >> b >> p >> q;
ll d = gcd(p, -q, k1, k2);
if ((b - a) % d != 0)
{
cout << "Impossible" << endl;
return 0;
}
k1 *= (b - a) / d;
k2 *= (b - a) / d;
ll t1 = abs(q / d);
k1 = (k1 % t1 + t1) % t1;
ll ans1 = a + k1 * p;
ll t2 = abs(p / d);
k2 = (k2 % t2 + t2) % t2;
ll ans2 = b + k2 * q;
if (ans1 >= max(a, b) && ans1 >= max(a, b))
cout << min(ans1, ans2);
else if (ans1 >= max(a, b))
cout << ans1;
else
cout << ans2;
return 0;
}