HDU 5127.Dogs' Candies-STL(vector)神奇的题,set过不了 (2014ACM/ICPC亚洲区广州站-重现赛(感谢华工和北大))
周六周末组队训练赛。
Dogs' Candies
Time Limit: 30000/30000 MS (Java/Others) Memory Limit: 512000/512000 K (Java/Others)
Total Submission(s): 3920 Accepted Submission(s): 941
Every candy has two attributes: the sweetness degree p and the sourness degree q. Different dogs like different candies. A dog also has two attributes: the fondness degree for sweetness x and the fondness degree for sourness y. So the deliciousness degree of a candy for a dog is defined as p×x + q×y.
The dog king has a huge candy box. At first, the box is empty. The king can add candies to the box or take some candies from the box and eat them. There are always some dogs who want to know which candies in the box are the most delicious for them. Please help the king to answer their questions.
The following n lines describe the n operations.
Each operation contains three integers t, x and y( 0 <= |x|, |y| <= 109). The first integer t may be -1, 0, or 1.
If t equals -1, it means that a candy in the box with sweetness degree x and sourness degree y is eaten by the dog king.
If t equals 1, it means that a candy with sweetness degree x and sourness degree y is added to the candy box.
If t equals 0, it means that a dog with sweetness fondness degree x and sourness fondness degree y wants to know the maximal deliciousness degree of the candies in the box for him.
It is guaranteed that every candy is unique in the box.
The input ends by n = 0.
0
题意就是1为插入,0为查询,-1为删除。
直接暴力,我也是服了,垃圾题目,set过不了。
代码:
//hdu5127-A-vector,直接数组都可以过
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
using namespace std;
typedef long long ll; const double PI=acos(-1.0);
const double eps=1e-;
const ll mod=1e9+;
const int inf=0x3f3f3f3f;
const int maxn=1e5+;
const int maxm=+;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1 struct node{
ll x,y;
}; vector<node> vec; int main()
{
int n;
while(scanf("%d",&n)&&n)
{
vec.clear();
for(int i=;i<=n;i++)
{
ll op,a,b;
scanf("%lld%lld%lld",&op,&a,&b);
if(op==)
{
vec.push_back({a,b});
}
else if(op==)
{
ll ans=-inf;
for(auto it:vec){
ans=max(ans,a*it.x+b*it.y);
}
printf("%lld\n",ans);
}
else if(op==-)
{
for(vector<node>::iterator it=vec.begin();it!=vec.end();it++){
node temp=*it;
if(temp.x==a&&temp.y==b){
vec.erase(it);
break;
}
}
}
}
}
}
猪小可爱的set没写过,贴一下,纪念一下,要不白写了。
超时。
代码:
1 //A-set会超时
2 #include <bits/stdc++.h>
3 #define pb push_back
4 #define mp make_pair
5 #define fi first
6 #define se second
7 #define all(a) (a).begin(), (a).end()
8 #define fillchar(a, x) memset(a, x, sizeof(a))
9 #define huan printf("\n")
10 #define debug(a,b) cout<<a<<" "<<b<<" "<<endl
11 #define ffread(a) fastIO::read(a)
12 using namespace std;
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 const int maxn=1e6+10;
16 const int inf=0x3f3f3f3f;
17 int main()
18 {
19 int n;
20 while(scanf("%d",&n)&&n)
21 {
22 set<pair<ll,ll> >s;
23 for(int i=0;i<n;i++)
24 {
25 ll k,x,y;
26 scanf("%lld%lld%lld",&k,&x,&y);
27 if(k==1)
28 {
29 s.insert(mp(x,y));
30 }
31 else if(k==-1)
32 {
33 s.erase(mp(x,y));
34 }
35 else
36 {
37 ll maxx=-3e18;
38 for(auto it:s)
39 {
40 //cout<<it.fi<<" "<<it.se<<endl;
41 maxx=max(maxx,x*it.fi+y*it.se);
42 }
43 //if(maxx==-inf)
44 printf("%lld\n",maxx);
45 }
46 }
47 }
48 }
OK。
最新文章
- requirejs 多页面,多js 打包代码,requirejs多对多打包【收藏】
- 将形如:Oct 8, 2016 5:29:44 PM串转换成正常时间在真机上遇到的坑
- Linux-磁盘及网络IO工作方式解析
- 自定义弹出框基于zepto 记得引入zepto
- SQL Server:分离和重新附加数据库
- js基础知识(pomelo阅读)
- SQLServer附加数据库5120错误
- Xsocket学习
- easyui page添加文本,js验证码
- Oeacle创建表空间
- Oracle undo我们需要掌握什么
- 使用WinDbg获取SSDT函数表对应的索引再计算得出地址
- sqlserver常用存储过程基本语法
- node模块之events模块
- centos7 如何在用户级对资源进行限制
- 科学计算三维可视化---Mlab基础(改变物体的外观颜色)
- thinkphp5与thinkphp3.X对比
- pycharm设置字体大小
- char *总结
- 稀疏编码直方图----一种超越HOG的轮廓特征
热门文章
- 解决oracle数据库 ora-00054:resource busy and acquire with NOWAIT specified 错误
- 动态规划小结 - 一维动态规划 - 时间复杂度 O(n),题 [LeetCode] Jump Game,Decode Ways
- [LeetCode] Binary Tree Level Order Traversal 与 Binary Tree Zigzag Level Order Traversal,两种按层次遍历树的方式,分别两个队列,两个栈实现
- vijos 1313 金明的预算方案 树形DP
- LightOJ 1269 - Consecutive Sum Trie树
- Doc常用命令
- How GitLab uses Unicorn and unicorn-worker-killer
- websocket连接相关的几个问题
- C# 从串口读取数据
- 【Python学习笔记】Coursera课程《Using Python to Access Web Data》 密歇根大学 Charles Severance——Week6 JSON and the REST Architecture课堂笔记