- 分享
比赛总结 2
- @ 2026-7-14 14:18:43
不好看,大佬勿喷。。。
400分满分。 我拿了390,还行吧。。。
错一道选择题,错就错在了贪心方法错误。
贪心是每部都最优解,来保持全局最优。
我错了,求饶
编程方法总结:
第一题:
#include <bits/stdc++.h>
using namespace std;
int main() {
set <string> S;
int n;
cin >> n;
for (int i=1;i<=n;i++)
{
string s;
cin >> s;
S.insert(s);
}
cout << 52-S.size() << endl;
return 0;
}
思路很简单: 本题要求出在给定的扑克牌的基础上,还需要多少张牌可以让扑克牌凑成一整套,而试题中读入的字符串每个都代表一张合法的扑克牌,从而可以使用 C++ STL 中的 set(集合)完成本题。这是因为,set 可以自动去重,去除重复的牌(字符串)后,剩下的字符串就是实际拥有的不同的牌。而一副扑克牌有 52 张牌,使用 52 减去该集合的大小即可求出答案。 太简单了!!! 太太太简单了!!! 太太太太太简单了!!! 简单到我不会了。。
#include <bits/stdc++.h>
using namespace std;
long long a[100005];
long long b[100005];
int main() {
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=b[i-1]+a[i];
}
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
if((b[j]-b[i-1]) == m)
{
cout<< i << " " << j;
return 0;
}
}
}
cout<<"No Solution" <<endl;
}
懒得说了。
不会做的就受着吧
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int T;cin>>T;
while(T--){
int n,ans=0;cin>>n;
priority_queue<int> q[3];
for(int i=1;i<=n;i++){
int x,y,z;cin>>x>>y>>z;
if(x>=y && x>=z){
ans+=x;
q[0].push(max(y,z)-x);
}else if(y>=x && y>=z){
ans+=y;
q[1].push(max(x,z)-y);
}else if(z>=y && z>=x){
ans+=z;
q[2].push(max(x,y)-z);
}
while(q[0].size() > n/2){
ans+=q[0].top();
q[0].pop();
}
while(q[1].size()>n/2){
ans+=q[1].top();
q[1].pop();
}
while(q[2].size()>n/2){
ans+=q[2].top();
q[2].pop();
}
}
cout<<ans<<'\n';
}
}
很有点难度(吓哭了)
这个 > 2分之1 的条件看起来不太聪明。这说明,不管每个人怎么分配,最后只会有一个社团不满足限制。
那么,我们只需要让每个人优先选择可以获得最优价值的社团,这样最后只有一个社团不符合条件,并且所有人的价值都最大化。
之后,只需要让这个社团里的一部分人换到别的社团里去,显然应该换让最终价值变小的程度最小的那些人。这个过程也等价于反悔贪心。
这样做是正确的,因为每个人都取到了最优的价值。现在,不存在交换两个人所在的社团使得答案变大的方案了。
太难了!!! 太太太难了!!! 太太太太太难了!!! 难道被我做出来了。。。