The 2021 Shanghai Collegiate Programming Contest
持续更新。
比赛链接
A.小A的点面论
出锅了，给你两个向量，求与他们垂直的向量。
马上想到叉积。
但是叉积中间那个方向要变一下的，还是基础太差了。
还好我队友看出来了，不然出大锅…
重新打一遍！偷什么懒啊，我有那资格偷懒吗5555
#include <bits/stdc++.h>
using namespace std;
int main() {
int x1, y1, z1, x2, y2, z2;
cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2;
cout << y1 * z2 - y2 * z1 << " " << x2 * z1 - x1 * z2 << " " << x1 * y2 - x2 * y1 << endl;
return 0;
}
B. 小 A 的卡牌游戏
好像也是DP，我要补起来！
C. 小 A 的期末考试
小模拟。
#include <bits/stdc++.h>
using namespace std;
struct Node {
double s, a;
} node[120];
int main() {
int n, m;
cin >> n >> m;
double sum = 0;
for (int i = 1; i <= n; i++) {
cin >> node[i].s >> node[i].a;
sum += node[i].a;
if (node[i].s == m) {
if (node[i].a < 60) node[i].a = 60;
}
}
sum /= n;
for (int i = 1; i <= n; i++) {
if (node[i].a >= sum&&node[i].s!=m) node[i].a = max(node[i].a - 2, 0.0);
}
sort(node + 1,
node + 1 + n, [](Node x, Node y) {
return x.s < y.s;
});
for (int i = 1; i <= n; i++)
cout << node[i].a << " ";
cout << endl;
}
D. Zztrans 的班级合照
单独更新了
D题解
E. Zztrans 的庄园
期望题。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
char t;
double x;
double sum = 0;
for (int i = 1; i <= n; i++) {
cin >> t >> x;
if (t == 'D')
sum+=x*(16-23);
if(t=='C')
sum+=x*(24-23);
if(t=='B')
sum+=x*(54-23);
if(t=='A')
sum+=x*(80-23);
if(t=='S')
sum+=x*(10000-23);
}
cout<<setprecision(4)<<fixed<<sum*k<<endl;
}
G. 鸡哥的雕像
乘积取逆元。
(
s
u
m
/
a
i
)
%
m
o
d
(sum/a_i)\%mod
(sum/ai)%mod
用逆元的条件是sum和mod互素。
a在模p意义下存在逆元的条件是 a与p互质。题目中ai<=1e9 若
s
u
m
sum
sum恰好为998244353时，则ai与p不互质，不存在逆元。
就是如果有
s
u
m
%
m
o
d
=
=
0
sum\%mod==0
sum%mod==0特殊处理：
已知sum%mod且mod是个prime，所以这种情况下一定有
a
i
a_i
ai==mod。没选中该
a
i
时
a_i时
ai时因数一定包括mod，答案直接为0。
所以
if (cnt > 1) {
for (int i = 0; i < n; i++)
cout << 0 << " ";
return 0;
}
if (cnt == 1) {
//cout<<sum<<endl;
for (int i = 1; i <= n; i++) {
if (i == p)
cout << sum << " ";
else cout << 0 << " ";
}
return 0;
}
其他用逆元解决。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 998244353;
ll a[maxn];
ll qpow(ll n, ll k) {
ll ans = 1ll;
while (k) {
if (k & 1ll)ans = ans * n % mod;
n = n * n % mod;
k >>= 1ll;
}
return ans % mod;
}
int main() {
int n;
cin >> n;
ll sum = 1;
int cnt = 0;
int p = -1;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] == mod) {
cnt++, p = i;
continue;
}
sum = sum * a[i] % mod;
}
if (cnt > 1) {
for (int i = 0; i < n; i++)
cout << 0 << " ";
return 0;
}
if (cnt == 1) {
//cout<<sum<<endl;
for (int i = 1; i <= n; i++) {
if (i == p)
cout << sum << " ";
else cout << 0 << " ";
}
return 0;
}
for (int i = 1; i <= n; i++) {
cout << qpow(a[i], mod - 2) * sum % mod << " ";
}
}
或者储存前缀积和后缀积，前后相乘。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 998244353;
ll a[maxn];
ll b[maxn], c[maxn];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
b[0] = 1;
c[n + 1] = 1;
b[1] = a[1];
c[n] = a[n];
for (int i = 1; i <= n; i++) {
b[i] = b[i - 1] * a[i] % mod;
}
for (int i = n - 1; i >= 1; i--) {
c[i] = c[i + 1] * a[i] % mod;
}
for (int i = 1; i <= n; i++) {
cout <<b[i-1]*c[i+1]%mod<<" ";
}
}
H. 鸡哥的 AI 驾驶
二分，待补，限今日内。
J. Alice and Bob-1
秋秋秒出贪心，真是牛。
从大到小从小到大选，保证绝对值最大。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> v;
ll x;
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x;
v.push_back(x);
}
sort(v.begin(), v.end());
ll cnt = 0;
ll sumA = 0, sumB = 0;
ll ans = 0;
for (auto i:v) {
if (cnt % 2) sumB += i;
else sumA += i;
cnt++;
}
ans = abs(sumA) - abs(sumB);
sort(v.begin(), v.end(), [](ll x, ll y) {
return x > y;
});
sumA = 0, sumB = 0, cnt = 0;
for (auto i:v) {
if (cnt % 2) sumB += i;
else sumA += i;
cnt++;
}
ans = max(ans, abs(sumA) - abs(sumB));
cout << ans << endl;
}