做排位赛10的过程记录
2024-07-15 14:24:30
发布于：广东
36阅读
0回复
0点赞
这篇文章相当于5/6的排位赛题解.
10号12:00，我准时来到了比赛现场。
第一题，求对应字符，不就是int转char吗
光速写了个代码
#include <iostream>
#include <cstdio>
using namespace std;
int a[100005];
int main(){
int n;
cin >> n;
cout << char(n);
return 0;
}
okAC了，看一下排名……已经第7名了吗？大家都这么快？
不管了继续做
第二题，我本来要排序二分查找的，做一半才发现——不是可以直接找最大值吗！
#include <iostream>
#include <cstdio>
using namespace std;
int a[100005];
int main(){
int n, m;
cin >> n >> m;
int mx = -1;
for(int i = 1; i <= n; i++){
cin >> a[i];
mx = max(mx, a[i]);//求最大值
}
int x;
for(int i = 1; i <= m; i++){
cin >> x;
if(a[x] == mx){
cout << "Yes";//如果里面有最大值就输出Yes
return 0;
}
}
cout << "No";
return 0;
}
第三题，本来没什么思路的，但是看到数据范围，感觉可以暴力模拟
随便改改，过了
#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
string a[105];
int b[105], bucket[15];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
int mn = 0x3f3f3f3f;
for(int i = 0; i <= 9; i++){//遍历小码君选择的数
memset(b, 63, sizeof(b));//赋值最大值
memset(bucket, 0, sizeof(bucket));//清空
int mx = 0;
for(int j = 1; j <= n; j++){//遍历每一个转轴
for(int k = 0; k <= 9; k++){//遍历每一个数
if((a[j][k] - '0') % 10 == i) b[j] = min(b[j], k);//找到i对应的数
}
mx = max(mx, 10 * bucket[b[j]] + b[j]);//如果是在同一时刻按，就要延后10秒等它转一圈
bucket[b[j]]++;
}mn = min(mn, mx);
}
cout << mn;
return 0;
}
第四题花了5分钟时间把题读了几遍，感觉如果直接找的话难度很大——那不如反着找吧！
版本一
#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
int a[200005], bucket[200005];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
bucket[a[i]]++;
}
long long ct = 1ll * n * (n - 1) * (n - 2) / 6;//总的组合数
for(int i = 1; i <= 200000; i++){
if(bucket[i] >= 2){
ct -= n - 2;//减去带有两个相同的组合数
}
}
cout << ct;
return 0;
}
结果样例3没过，只得了135分.
于是我疯狂的找问题，疯狂的改代码
终于——晚上8:00，我推导出了正确的公式！
因为三个相同的数要单独计算，
所以总组合数.
版本2
#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int a[200005], bucket[200005];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
bucket[a[i]]++;
}
int ctt = 0;
for(int i = 1; i <= 200000; i++){
for(int j = 1; j <= bucket[i]; j++){
a[++ctt] = i;
}
}
long long ct = 1ll * n * (n - 1) * (n - 2) / 6;
for(int i = 1; i <= 200000; i++){
ct -= 1ll * bucket[i] * (bucket[i] - 1) / 2 * (n - bucket[i]) + 1ll * bucket[i] * (bucket[i] - 1) * (bucket[i] - 2) / 6;
}
cout << ct;
return 0;
}
第五题
我对图论有一些懵，所以没办法，打表骗分
n = int(input().split()[0])
for i in range(1, n): print(i, end = ' ')
第六题
看不懂DP状态转移方程，同样骗分
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int a[200005];
long long b[200005];
long long n, m, ct;
long long dfs(int left, int right){//取中间
if(left >= right) return 0;
if(left + 1 == right) return a[left] + a[right];
int mid = (left + right) >> 1;
return b[right] - b[left - 1] + dfs(left, mid) + dfs(mid + 1, right);
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; i++){
b[i] = b[i - 1] + a[i];
}
if(b[n] != m) ct = m;
cout << dfs(1, n) + ct;
return 0;
}
一共骗了162分.
总分刚过1000，还是非常不错的.
但是，只能止步于此了吗？
14日晚上，我再仔细琢(zuó)磨了第六题，发现——把一块长度为k的面包切成两块和把两个重量和为k的果子合并成一个有什么不同，花费均为k！
于是就把这个转变成了合并果子的问题
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#define int long long
using namespace std;
signed a[200005];
int ctt = 0;
int ct = 0;
priority_queue <int, vector<int>, greater<int>> q;//不想装了，老老实实做
signed main(){
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> a[i];
ctt += a[i];
q.push(a[i]);
}
if(ctt != m) q.push(m - ctt);//注意还要切掉剩余部分
while(q.size() > 1){
int tmp1 = q.top();
q.pop();
int tmp2 = q.top();
q.pop();
ct += tmp1 + tmp2;
q.push(tmp1 + tmp2);
}
cout << ct;
return 0;
}
做完之后，我在无聊地刷着题，复习今天学的堆.
随后，诡异的事情发生了——
https://www.acgo.cn/problemset/info/21430
呃呃呃我找到了排位赛第6题（
ok没了
全部评论 7
我第6题是这么写的
#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; int main() { int n; long long l; cin >> n >>l; vector<long long> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } priority_queue<long long, vector<long long>, greater<long long>> pq; for (int i = 0; i < n; i++) { pq.push(a[i]); l -= a[i]; } if (l > 0) { pq.push(l); } long long totalCost = 0; while (pq.size() > 1) { long long first = pq.top(); pq.pop(); long long second = pq.top(); pq.pop(); long long combined = first + second; totalCost += combined; pq.push(combined); } cout << totalCost << endl; return 0; }2024-07-15 来自 广东
0
有帮助，赞一个