关键词:
这次套路深啊,怎么还有改错题!。
上来看题,每个题目的输入数据都很大,果断上scanf,printf, 千万不能用cin,cout
1. 右上角的点,我的思路是先对每一行去重(题目好像说没有重的点耶!),每一行只有最右边的点才是候选点,然后对这些候选点按照y坐标,从大到小访问,要求相应的x是严格递增的,最后打印输出。
1 #include<bits/stdc++.h> 2 #define pb push_back 3 typedef long long ll; 4 using namespace std; 5 typedef pair<int, int> pii; 6 const int maxn = 1e3 + 10; 7 int n; 8 void solve() { 9 map<int, int> ma; 10 scanf("%d", &n); 11 int x, y; 12 for (int i = 0; i < n; i++) { 13 scanf("%d%d", &x, &y); 14 if(ma.count(y)) { 15 ma[y] = max(ma[y], x); 16 } else ma[y] = x; 17 } 18 vector<pii> res; 19 auto it = ma.rbegin(); 20 x = it->second - 1; 21 //cout << it->first <<endl; 22 while(it != ma.rend()) { 23 if(it->second > x) { 24 res.pb({it->second, it->first}); 25 x = it->second; 26 } 27 it++; 28 } 29 for (pii t : res) { 30 printf("%d %d ", t.first, t.second); 31 } 32 } 33 34 int main() { 35 freopen("test.in", "r", stdin); 36 //freopen("test.out", "w", stdout); 37 solve(); 38 return 0; 39 }
2. 我认为是分治, 首先考虑数组的最小值,哪些区间可以取到取小值,取到最小值,使得结果最大,当然是和最大,那就是全部的数,接下来这个最小值就可以不考虑了,分别对左半和右半重复上面处理。
#include<bits/stdc++.h> #define pb push_back typedef long long ll; using namespace std; typedef pair<int, int> pii; const int maxn = 5e5 + 10; int n; ll a[maxn]; ll s[maxn]; ll f(int x, int y) { return s[y] - s[x - 1]; } ll res = 0; void work(int x, int y) { if(x > y) return; if(x == y) { res = max(res, a[x] * a[x]); return; } int p = x; for (int i = x; i <= y; i++) { if(a[i] < a[p]) { p = i; } } res = max(res, a[p] * f(x, y)); work(x, p - 1); work(p + 1, y); } void solve() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); s[i] = s[i - 1] + a[i]; } work(1, n); printf("%lld ", res); } int main() { freopen("test.in", "r", stdin); //freopen("test.out", "w", stdout); solve(); return 0; }
3. 题目描述的挺复杂,就是多个角度的优先队列,然后就试了试刚学习的函数类(仿函数,函数对象,函数指针),以及lambda表达式,写了一下。
最后过了80%, 我的是按时间模拟的,题目的范围是【1,3000】,我的for循环是1-3000,突然想到有些任务可能到3000的时候一直没有程序员空闲,所以for循环至少要到6000才行,这样才能ac吧。
感觉模拟到6000也不行。应该是任务队列判空为止才行。
1 #include<bits/stdc++.h> 2 #define pb push_back 3 typedef long long ll; 4 using namespace std; 5 typedef pair<int, int> pii; 6 const int maxn = 3e3 + 10; 7 struct node { 8 int id, p, s, pr, t; 9 }; 10 int n, m, p; 11 node a[maxn]; 12 //这里扩大范围 13 int f[maxn * 2]; 14 int res[maxn]; 15 class cmp { 16 public: 17 bool operator()(const node&x, const node&y) { 18 if(x.pr == y.pr) { 19 if(x.t == y.t) { 20 return x.s < y.s; 21 } else { 22 return x.t < y.t; 23 } 24 } else { 25 return x.pr > y.pr; 26 } 27 } 28 }; 29 set<node, cmp> data[maxn]; 30 void solve() { 31 int x, y, x1, y1; 32 scanf("%d%d%d", &n, &m, &p); 33 for (int i = 1; i <= p; i++) { 34 scanf("%d%d%d%d", &x, &y, &x1, &y1); 35 a[i] = {i, x, y, x1, y1}; 36 } 37 sort(a + 1, a + p + 1, [](const node&x, const node&y)->bool{return x.s < y.s;}); 38 int cur = 0; 39 f[1] = m; 40 set<int> se; 41 x = 1; 42 int cnt = 0; 43 //这里应该模拟到6000, 保证所有的任务都有机会执行,或者更大。 44 for (int i = 1; i <= 3000; i++) { 45 cur += f[i]; 46 while(x <= p) { 47 //cout << x << endl; 48 if(a[x].s == i) { 49 data[a[x].p ].insert(a[x]); 50 //cout << "asd " << a[x].id << endl; 51 x++; 52 cnt++; 53 } else break; 54 } 55 if(cur <= 0 || cnt == 0) continue; 56 int t = cur; 57 58 for (int j = 0; j < t; j++) { 59 int id = -1; 60 int ti = 0; 61 for (int k = 1; k <= n; k++) { 62 if(data[k].size() == 0) 63 continue; 64 else { 65 // cout << k << " asd " << (data[k].begin())->t << endl; 66 if(id == -1 || (data[k].begin())->t < ti) { 67 id = k; 68 ti = (data[k].begin())->t; 69 }} 70 } 71 //cout << id << " " << ti << endl; 72 cur--; 73 cnt--; 74 node nd = *data[id].begin(); 75 data[id].erase(data[id].begin()); 76 res[nd.id] = i + nd.t; 77 f[i + nd.t]++; 78 79 if(cnt <= 0 || cur <= 0) break; 80 } 81 82 } 83 for (int i = 1; i <= p; i++) 84 printf("%d ", res[i]); 85 } 86 87 int main() { 88 freopen("test.in", "r", stdin); 89 //freopen("test.out", "w", stdout); 90 solve(); 91 return 0; 92 }
笔试今日头条-线段树查询
【题目描述】给定两个长度为 n 的整数数列 A 和 B。再给定 q 组查询,每次查询给出两个整数 x 和 y,求满足 Ai>=x 且 Bi>=y 这样的 i 的数量。输入格式第一行给定两... 查看详情
2018今日头条笔试(第二题)
题目描述给定一个数组序列,需要选出一个区间,使得该区间是所有区间中经过如下计算的值最大的一个。区间中的最小数*区间所有数的和最后程序输出经过计算后的最大值即可,不需要输出具体的区间。如给定序列[6,2,1]可得... 查看详情
实习生求职今日头条笔试
时间:大三下学期职位:测试开发过程: 首先,会有练习题,但是练习题没有针对性,而且编程题会很简单;主要是用来检查自己的环境是否合适、熟悉系统。 然后就是正式考试了——开始会很卡(反... 查看详情
字节跳动(今日头条)的题目真的难吗?
大家好鸭,我是好好学习天天编程的天天,一个每天都努力精进,并努力分享的主儿。今天给聊得话题是关于字节跳动笔试题难度的。在各种交流群了,总是能看到大家在说字节跳动的题目好难呀,4个编程题没有一个题AC。天天... 查看详情
今日头条2018aicamp5月26日在线笔试编程题第一道——最佳路径(代码片段)
题目给定一个n*m的矩阵A,矩阵中每一个元素为一个十六进制数。寻找一条从左上角都右下角的路径,每次只能向右或者向下移动, 使得路径上所有数字之积在16进制下的后缀0最少。输入描述:第一行:n,m(2<=n,m<=1000) ... 查看详情
字节跳动(今日头条)的题目真的难吗?
大家好鸭,我是好好学习天天编程的天天,一个每天都努力精进,并努力分享的主儿。今天给聊得话题是关于字节跳动笔试题难度的。在各种交流群了,总是能看到大家在说字节跳动的题目好难呀,4个编程题没有一个题AC。天天... 查看详情
今日头条和今日头条极速版有什么区别
3C数码您的浏览器不支持HTML5视频zymedia(\'video\')参考技术A今日头条和今日头条极速版区别为:安装包大小不同、占用运行内存不同、特色功能不同。一、安装包大小不同1、今日头条普通版:今日头条普通版的安装包大小为22.8M。2... 查看详情
如何区分今日头条与今日头条极
参考技术A今日头条和今日头条极速版区别有:内存大小不一样、定位人群不一样、功能特色不一样、界面设计不一样。1、内存大小不一样今日头条极App:4.7M。今日头条极速版App:安装包4.7M。2、定位人群不一样普通版:面向的... 查看详情
“今日头条”和“今日头条极速版”有啥不同?
...A面对客户人群不一样,界面不一样,功能体验不一样。今日头条界面比较复杂,体验功能更加多元化。今日头条极速版界面简单,功能体验比较少。今日头条:基于个性化推荐引擎技术,根据每个用户的兴趣、位置等多个维度... 查看详情
今日头条的惊惶时刻
今日头条到底怎么了?昨天上午,国家知识产权局用一纸决定书驳回了今日头条关于UC一条专利的无效宣告请求,这意味着今日头条很可能要面临巨额的专利侵权罚款。不过UC并不是唯一和今日头条“对簿公堂”的企业。在1月26... 查看详情
今日头条的核心架构解析
今日头条创立于2012年3月,到目前仅4年时间。从十几个工程师开始研发,到上百人,再到200余人。产品线由内涵段子,到今日头条,今日特卖,今日电影等产品线。一、产品背景今日头条是为用户提供个性化资讯客户端。下面就... 查看详情
今日头条
<resources><stringname="app_name">头条</string><stringname="openDrawer">今日头条</string><stringname="closeDrawer">用户目录</string></resources>/****/<?xmlvers 查看详情
今日头条爬虫
今日头条是一个js动态加载的网站,尝试了两种方式爬取,一是页面直接提取,一是通过接口提取:version1:直接页面提取#coding=utf-8#今日头条fromlxmlimportetreeimportrequestsimporturllib2,urllibdefget_url():url=‘https://www.toutiao.com/ch/news_hot/‘gl... 查看详情
如何在头条做营销:2022今日头条营销价值洞察报告.pdf(附下载链接)
本报告共包含如下四大部分:1、趋势:品牌内容营销难题;2、人群:今日头条人群特征;3、内容:今日头条内容生态;4、商业:今日头条商业生态。更多细节和行研干货资料请到小程序省时查报告中查看全文并下载。 查看详情
今日头条核心技术“个性推荐算法”揭秘
今日头条核心技术“个性推荐算法”揭秘最近面试华兴资本,他们比较关注今日头条算法的实现,今天特转载网上今日头条算法解密 【IT168 评论】互联网给用户带来了大量的信息,满足了用户在信息时代对信息的需求,... 查看详情
go--今日头条架构
夏绪宏,今日头条架构师,专注对高性能大规模Web架构,云计算、性能优化、编程语言理论等方向,PHPcommitter,HHVM项目贡献者。2009加入百度,先后从事大规模IDC自运维设施建设、云计算平台的架构设计、贴吧业务性能优化、百... 查看详情
[新浪]今日头条被高估了吗?
今日头条被高估了吗? 欢迎关注“创事记”的微信订阅号:sinachuangshiji 文/华生 来源:砺石商业评论(ID:libusiness) 砺石导言 对于今日头条这样一家缺乏核心竞争力,并且始终头顶较大法律与道德风险... 查看详情
今日头条算法
...u014114990/article/details/48165781 日头条涉及到算法:(1)今日头条服务器1000台左右,通过代码实现的爬虫功能,在其他传媒的网站和门户上抓取各种信息。如果在网站上抓取到纸媒的内容,优先从纸媒门户上抓取信息(2)抓取... 查看详情