SMU Summer 2023 Contest Round 11(2022-2023 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2022))
A. Ace Arbiter
用\(A\)和\(B\)代表\(Alice\)和\(Bob\),则轮到\(Alice\)发球时会给出\(A - B\)的比分,轮到\(Bob\)时给出\(B-A\)的比分,直接比较还是挺难的,但是如果统一的都是\(A-B\)或者\(B-A\)的比分,那我们只要去判断每一轮的\(Alice\)和\(Bob\)的比分是不是大于等于上一轮的分数,如果少了,说明这次记录是错误的,另外如果有一方到达11分了,那么比赛应该结束了,不可能还继续比赛,还有就是\(11-11\)这种比分是不可能出现的.
那么问题来了,我们怎么去统一这个比分呢?
题目已给出发球顺序\(A,B,B,A,A,B,B\dots\),可以看出,除了第一轮\(Alice\)单独发球外,其余都是四轮一循环,且每一轮必定有一方会加分,所以我们可以将分数减掉\(Alice\)那一次,然后去 \(\bmod 4\),得到\(0\)或者\(1\)就说明这次是\(Bod\)发球,这个时候我们将比分对调,然后按照上面说的去判断即可.
#include<bits/stdc++.h>
using namespace std;
int32_t main() {
int n;
cin >> n;
vector<int> a(n + 1), b(n + 1);
char op;
for (int i = 1; i <= n; i++)
cin >> a[i] >> op >> b[i];
bool end = false;
for(int i = 1;i <= n;i ++){
int sorce = max(a[i] + b[i] - 1,0);
if(sorce % 4 == 0 || sorce % 4 == 1)
swap(a[i],b[i]);
if(end && a[i] != a[i - 1] || end && b[i] != b[i - 1]|| a[i] == 11 && b[i] == 11){
cout << "error " << i << '\n';
return 0;
}
if(a[i] < a[i - 1] || b[i] < b[i - 1]){
cout << "error " << i << '\n';
return 0;
}
if(a[i] == 11 || b[i] == 11)
end = true;
}
cout << "ok\n";
return 0;
}
C. Coffee Cup Combo
每个1可以将后面两个数变成1,但是由0变化来的1不能影响后面的数,按题意模拟即可
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
string s;
cin >> n >> s;
string sss = s;
for(int i = 0;i < n;i ++){
if(s[i] == '1'){
sss[i] = '1';
if(i + 1 < n) sss[i + 1] = '1';
if(i + 2 < n) sss[i + 2] = '1';
}
}
int ans = 0;
for(auto i : sss)
ans += (i == '1');
cout << ans << '\n';
return 0;
}
D. Disc District
多写几组数据可发现,其实\((r,1)\)也是符合答案
#include<bits/stdc++.h>
using namespace std;
int main() {
long long r;
cin >> r;
cout << r << ' ' << 1 << endl;
return 0;
}
G. Graduation Guarantee(期望dp)
先将概率从大到小排序(肯定要先做概率大的才能拿分嘛),然后就是\(dp\)数组的初始化,初始就是前面\(i\)道题做错.
你要想在前\(i\)道题里做对\(j\)道题,要么就是做对第\(j\)题,那么你前\((i-1)\)道题就要做对\((j-1)\)道题,要么就是不做第\(j\)道题,那你前\((i-1)\)道题就要做对\(j\)道题,由此得出转移方程
\(dp[i][j] = p[i] \times dp[i-1][j-1] + (1 - p[i]) \times dp[i-1][j]\)
\(i - (i-k)/2\)是说你在做对超出\(k\)道题时需要做错相应的题使你的总对题数维持在\(k\)
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,k;
cin >> n >> k;
std::vector<double> p(n + 1);
for(int i = 1;i <= n;i ++)
cin >> p[i];
vector dp(n + 1, vector<double>(n + 1,0));
sort(p.begin() + 1, p.end(),greater());
dp[0][0] = 1;
for (int i = 1; i <= n; ++i){
dp[i][0] = (1 - p[i]) * dp[i - 1][0];
}
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= n;j ++)
dp[i][j] = p[i] * dp[i - 1][j - 1] + (1 - p[i]) * dp[i - 1][j];
double ans = 0.0;
for(int i = k;i <= n;i ++){
double sum = 0.0;
for(int j = i - (i - k) / 2;j <= i;j ++)
sum += dp[i][j];
ans = max(ans, sum);
}
cout << ans << '\n';
return 0;
}
H. Highest Hill
思路就是每次一个峰一个峰地去找,然后更新答案.
思路还是挺对的,就是刚开始题目里有个等距导致我读了个假题,然后就是wa了几发,啊我真该死啊,最后贴份队友代码吧
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int32_t main() {
int n;
cin >> n;
vector<int> a(n + 10);
a[n] = LLONG_MAX;
for (int i = 0; i < n; i++)cin >> a[i];
int a1, a2, a3;
int pos1, pos2, pos3;
int ans = 0;
for (int i = 0; i < n; i++) {
pos1 = i;
while (a[i] <= a[i + 1] && i < n)i++;
pos2 = i;
if (pos1 == pos2)continue;
while (a[i] >= a[i + 1] && i < n)i++;
pos3 = i;
if (i >= n)break;
i--;
a1 = a[pos1];
a2 = a[pos2];
a3 = a[pos3];
ans = max(ans, min(a2 - a1, a2 - a3));
}
cout << ans << endl;
return 0;
}
- Contest 2023 2022 Programming Collegiate2023 programming collegiate contest programming collegiate provincial contest programming collegiate jiangsu contest international programming collegiate contest programming collegiate mianyang contest programming collegiate contest guilin programming collegiate shenzhen contest 2022 programming collegiate acm-icpc programming collegiate shanghai contest contest 2023 2022 programming