Codeforces比赛中的unordered_map Hacks
打了一下Codeforces Round 891 (Div. 3),赛后看到F题的赛时通过解答被叉(hack)了一大把,非常好奇为啥,所以笔者在hack phase结束之后看了一下这些hack数据的hack点是什么,发现大多数都是叉unordered_map的。这又让我想起刚开始打cf的时候在某场Div. 4中使用了unordered_map结果在hack phase被叉的惨痛经历,然后我突然就想以牙还牙,以后也要叉别人的unordered_map,于是就有了这篇文章。
unordered_map 和 map 的工作原理在Codeforces比赛中,我们通常会选择map而不是unordered_map,尽管map上的插入和查找操作的时间复杂度是$O(log\ N)$的,而unordered_map的插入和查找操作却是均摊$O(1)$的。为什么我们要做这种令人费解的时间复杂度牺牲?原因就在于哈希表的内部工作原理使得它可能被轻易地攻击。
map根据Cpp Reference的说明:
1234std::map is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function Compare. S ...
Codeforces Round 888 (Div.3) A-G 题解
每个题目的代码部分只给出了一组数据的解题流程。请注意,Codeforces上都是多组数据的。
代码中的il均表示long long类型。
Problem A. Escalator Conversations题意有$n$个人,$m$级台阶,每节台阶的高是$k$,给出每个人的身高$h_i$,以及自己的身高$H$。其中某人能与另一人对话的条件是他们的身高差等于一级或多级台阶的高度差。现在问$n$个人中有几人能和自己对话,可行性相互独立。
题解注意对话两人不能站在同一级台阶上。能对话的条件是两人身高差的绝对值能被$k$整除,并且大于$0$,小于$k\cdot m$
代码123456789101112131415void solve() { int n, m ,k, H; cin >> n >> m >> k >> H; vector<int> h(n); for (auto &v : h) { cin >> v; } int ans = 0;; for (auto v : h) { if (abs(v - H) % k == 0 && abs(v - H) / k < m &a ...
AtCoder Beginner Contest 311 A-E 题解
代码中的il或i64均表示long long类型。
Problem A. First ABC题意给定一个包含大写字母ABC的字符串$S$,长度为$N$,保证ABC在该串中都至少出现过一次,输出第一个保证ABC都至少出现过一次的位置的序号。
题解既然ABC都至少出现过一次,我们直接查找ABC这几个字母第一次出现的位置,取最大值即可
代码123456void solve() { int n; string s; cin >> n >> s; cout << std::max({s.find('A'), s.find('B'), s.find('C')}) + 1;}
Problem B. Vacation Together题意有$N$个人,给出他们$D$天的计划表(x表示该天上班,o表示该天休息)。现在求这$N$个人在这$D$天中能够一起休息的最长连续天数。
题解我们用$v[i]$表示第$i$天是否有人上班。在读入数据时,如果某人在第$i$天上班,直接令$v[i]$加一即可(当然,你也可以使用bool数组做或运算)。然后我们线性地遍历整个数组,找到最长连续0段的长度即可。数组中的每个元素都只会被访问一次。
代码123456 ...
AtCoder Beginner Contest 310 A-F 题解
代码中的il或i64均表示long long类型。
Problem A. Order Something Else题意一瓶饮料的正常价格是$P$元,现在有一张优惠券,使得你可以以$Q$元的价格购买这瓶饮料,条件是是必须从给出的$N$道菜中选择一道菜一并购买,第$i$道菜的价格是$D_i$。求出购买这瓶饮料的最低价格。
题解我们可以使用优惠券也可以不使用优惠券。
如果我们使用优惠券,则需要再购买一份小菜,我们肯定选择最便宜的小菜,那么买下这瓶饮料的价格最低是$Q+min(D_1, D_2,..,D_n)$。
如果不使用优惠券,那么会以原价$P$买下这瓶饮料。
答案就是上面两式的较小者。
代码123456789101112131415void impl() { int n, p, q; cin >> n >> p >> q; int m, c; cin >> m; for (int i = 1;i < n;i++) { cin >> c; m = std::min(m, c); } if (q + m < p) { cout << (q + m); } else ...
WHUT2022秋C语言A类答案
C理论A_编程练习1-顺序结构主要是一些基础语法,输入输出,和对类型的理解。
7-1 计算整数各位数字之和这里直接用循环实现了。
123456789#include<stdio.h>int main() { int a, b = 0; scanf("%d", &a); while (a) b += a % 10, a /= 10; printf("%d", b); return 0;}
7-2 计算代数表达式使用内置的数学函数解决
12345678910#include<stdio.h>#include<math.h>#define PI 3.14159#define to(x) (x * PI / 180)int main() { double x; scanf("%lf", &x); printf("%.2lf", sqrt((sin(to(60)) + 1) * (sin(to(30)) + 1) / cos(to(x)))); return 0;}
7-3 A乘以B1234567#include<stdio.h>int mai ...
使用Android RenderNode加速绘制
写在前面的废话研究RenderNode的起因…作为一个代码编辑器的开发者,我十分关注我写的View的绘制速度。于是国庆节放假,心血来潮测试自己编辑器和EditText绘制的性能。发现一段代码,在两个View中显示出来几乎没什么区别,但是TextView的绘制比咱快多了,这是为什么呢?我尝试一段一段注释自己的除了文本以外元素的绘制代码。从屏蔽代码区划线,到屏蔽空白字符的绘制,最后甚至把代码高亮都换成了普普通通的文本绘制,但是就是比不上EditText。笔者一下子就十分纳闷了,于是开始摸TextView的绘制部分。
摸索TextView源码…下面以Andoird Q的源码为例。打开onDraw()方法翻了一会,看到了调用Layout绘制的代码,不过伴随着的还有mEditor:
123456Path highlight = getUpdatedHighlightPath();if (mEditor != null) { mEditor.onDraw(canvas, layout, highlight, mHighlightPaint, cursorOffsetVertical);} else { layout.draw(canvas, highlight, mHighlightPaint, cursorOffsetVertical);} ...
Sora-editor - Get started
PreThe project is fast-moving. This page may not be updated in time. The content of this page may be invalid for newest editor versions.
Introductionsora-editor is a optimized editor library with a lot of features on Android.It aims at making more people able to develop their own IDEs with less efforts. Also developing the editor is part of the interest of mine.However its license is LGPL v2.1. Be careful about that.As it is still developing and being tested, there may be some bugs and APIs can be easily changed at the stage.
Get StartedWe use Android Gradle project for example.
Check your app ...
👴玩爆QQ涂鸦
作业原因最近逛b站时发现一个宝藏up主:鉴无虚发QQ涂鸦(uid402778937),他利用QQ不久前更新的涂鸦功能进行创作,绘制了许多有趣的涂鸦,还让粉丝群的成员发送一张图 片,他照着画出来。这让我很羡慕,可是我美术不行,加之用手机画画实在不是一键容易的事,手指太粗,屏幕太小,据up自述,完成一件创造大约需要30min,这让我这个急性子更难受。不过我会一点编程,于是想尝试写一个简单的程序来实现此功能。
过程准备自己使用的手机用的安卓系统,安卓在安卓7.0(Nougat)为辅助功能(AccessibilityService)添加了
1Boolean dispatchGesture(gesture: GestureDescription, callback: AccessibilityService.GestureResultCallback?, handler: Handler?)
来在触摸屏上执行一个手势。我们可以利用这个方法来实现涂鸦的功能。不过原生安卓开发很麻烦,受时间限制,采取跨平台的Auto.js来编写js脚本实现。我把步骤分为两步1读取图片并出来成类似简笔画的效果2在屏幕上画出来
图片处理处理过程见代码了。
12345678910111213141516var img = images.read("/storage/emulated/0/n.jpg" ...
Text Warrior中一些不足之处
前言不少Android项目中,都使用了Text Warrior作为它们的代码编辑器。这个项目的视图是直接继承自View的,与那些继承TextView、EditText的项目不同。使用TextView,我们虽然能够获得较为出色的显示效果,但是在文本较长的时候,会造成卡顿阻碍用户输入,因为我们不得不在主线程中更新我们的Spans,而且每更新一个Span,都会导致TextView重绘。而且经常因为正则表达式不够准确而导致高亮出错。TextWarrior则没有此问题。它收到文本更新的时候,会调用其他线程启动Lexer来刷新高亮,在该线程结束之后刷新绘制,这既保证了高亮的正确性,也保证了UI线程的流畅。然而,它其中有一些不足之处导致大文本仍然不能较快地显示,以及一些用户体验的问题。
绘制问题Span查找问题TextWarrior的Span是用ArrayList,依照顺序依次存起来的,Span中保存了它的Start Index。利用有序的性质,我们可以很快地利用二分将特定Index对应的Span找出来。尤其是在绘制时,这十分有用,直接将O(N)复杂的降到O(log N),很快。但是,目前在各处流传的版本都是按照顺序对Span进行查找的,这是realDraw()中关于查找的一段代码
1234567891011121314151617181920212223//--------------- ...
记Android开发中一个坑 - ViewRootImpl
玩Android开发已经两年有余了,一直保持这一些错误思想,终于在前几天给打破了。作为一个开发老者,你一定看过这样的报错:
12android.view.ViewImple$CalledFromWrongThreadException:Only the original thread that created a view hierarchy can touch its views.at android.view.ViewImple.checkThread(ViewImpl.java:xxx)
毫无疑问,八成是你在别的线程尝试对UI进行更新。我们常说那是UI线程之外的线程。但是,为什么报错不是UI thread,而是original呢?我觉得,大多数人都没有想过.前几天看到一篇文章,把我的错误观念打爆了,所以今天记录一下.先来看看checkThread()方法:
123456void checkThread() { if (mThread != Thread.currentThread()) { throw new CalledFromWrongThreadException( "Only the original thread that created a view hierarch ...
一个高亮编辑框的构建历程
前言制作背景我已经在这之前多次写过高亮编辑框了,自从我入门编程以来,就一直在尝试自己造个高亮编辑框的轮子。如果你不想看Rose无聊的背景叙述,请直接从侧栏跳到“本项目的开端”部分。
第一次尝试 - Editable原理这还是在我玩iApp的时候了。当时觉得一个高亮代码编辑框是iApp源码的一大空缺,所以打算造个源码。初次的尝试对Android原生的控件还是抱有很大的期望的。所以选用了Android自带的TextView来制作。众所周知,TextView自己就能显示不同颜色的文本,比如经常看到的链接就是一个例子。所以TextView拿来玩,不存在原理上的问题。因此,我们用Editable来设置文本颜色Spans,并且用TextView显示就好了。我们在文本更新时对高亮进行更新。至于行号,我们只需要编辑框的左边加一个TextView就好了,然后在文本改变时生成文本设置就好了。而滚动,只需要ScrollView和HorizontalScrollView套娃就行了。再者,Spans的匹配只需要轻轻地写个正则表达式Pattern + Matcher就可以匹配了。
过程于是我们造出了第一个高亮编辑框。这个编辑框比较原始,因为遇到一些转义的写法,字符串的高亮就可能发生错乱。下面是用于高亮SpannableStringBuilder的方法(Editable的唯一自带实现类)。代码只给出了一 ...