走线的时候要提高自己的姿势水平

发生了啥

有这么一个库 ESP32_MP3_Decoder 简单来说就是一个蓝牙WiFi放歌的小玩意

它的pinmap是这样的

ESP pin   - I2S signal
----------------------
GPIO25/DAC1   - LRCK
GPIO26/DAC2   - BCLK
GPIO22        - DATA

当然是很普通的ESP32上的I2S接线

DATA这根线,在我的opamp上对应的脚名字叫做SDATA, 于是这根线也就被我叫做SDATA

也就是说,把 SDATA 连到 GPIO22

而ESP32上有这么一个脚叫做SD1, 用来连接存储器的,就是这么巧,我用的这个ESP模块它这个脚对应的编号也是22……

我一看,哇,这不是SDATA麽!

然后因为显示了SDATA这个脚的GPIO号就没有显示了

于是

还好又不是不能用(大概)……

Google Codejam 2016 Round1B

傻Ⅹ编程之美不想多说什么了…… 到现在我也没能用上azure…… 15号比赛结束,玩奶子去吧

来说点开心的事,这个1B啊…… 最简单的是A这肯定没话说,也没什么好说的呀,然后是C呀,就是个辣鸡边覆盖,当然你如果上网搜边覆盖然后贴公式的话…… good luck 呀.

那个B呀,其实也是水题啊…… 但是我智商不够啊,上来就奔着搓,怎么撕考都是dp啊,智商不够dp写不出来啊…… 还是老司机飙车经验足啊…… 暴力飙车啊……

结果看了题解呀,傻逼讨论呀,关键就是确认一组??后面就都是撒币玩意了呀,这样搞就是了呀,暴力$O(3^18)$`也TM使劲搓就行了呀。

总结,我是个傻逼。

编程之美2016 复赛题目翻译

Microsoft Academic Graph (MAG) is a large heterogeneous graph containing entities such as authors, papers, journals, conferences and relations between them. Microsoft provides Academic Knowledge API for this contest. The Entity attributes are defined here.

m\$搞了一套学术数据库的API的理论呀.

Participants are supposed to provide a REST service endpoint that can find all the 1-hop, 2-hop, and 3-hop graph paths connecting a given pair of entity identifiers in MAG. The given pair of entity identifiers could be [Id, Id], [Id, AA.AuId], [AA.AuId, Id], [AA.AuId, AA.AuId]. Each node of a path should be one of the following identifiers: Id, F.Fid, J.JId, C.CId, AA.AuId, AA.AfId. Possible edges (a pair of adjacent nodes) of a path are:

你们要给他搞一个REST服务呀,对给定的点对呀,寻找所有的1-hop, 2-hop, 3-hop路径呀。给定的点对关系可能是这样的呀[Id, Id], [Id, AA.AuId], [AA.AuId, Id], [AA.AuId, AA.AuId], 而你的路径上可以涵盖这些点Id, F.Fid, J.JId, C.CId, AA.AuId, AA.AfId

而两个点之间连边的要求是呀

  • Id1 -> Id2 当且仅当它们的Rid相等呀
  • Id1 -> F.Fid2 当且仅当Id1的F.Fid等于F.Fid2呀

... 以此类推呀, 自己去看原文哒吖, 没什么翻译的必要的呀

For each test case, the REST service endpoint will receive a JSON array via HTTP with a pair of entity identifiers, where the identifiers are 64-bit integers, e.g. [123, 456]. The service endpoint needs to respond with a JSON array within 300 seconds. The response JSON array consists of a list of graph paths in the form of [path1, path2, …, pathn], where each path is an array of entity identifiers. For example, if your program finds one 1-hop paths, two 2-hop paths, and one 3-hop paths, the results may look like this: [[123,456], [123,2,456], [123,3,456], [123,4,5,456]]. For a path such as [123,4,5,456], the integers are the identifiers of the entities on the path. After receiving the response, the evaluator will wait for a random period of time before sending the next requests.

对于每组输入,REST会通过HTTP apply 一个JSON数组,比如[123, 456]呢。 你要在300s内呢,给它这个算出之前说的这些路径呢。每个路径就是一堆的他这个标识符呢。然后你要得到呀这个数组就是上面说的这个样子啊。每个路径的数组里面就是他经过的点的编号(点可以是很多类型的呢)呀。之后呢,你会有一个随机的时间,等待下一组输入呢!

The REST service must be deployed to a Standard_A3 virtual machine for the final test. There are no constraints on the programming language you can use.

你们搞的这个东西呢,会在SA3的标准上跑,这个玩意呢,一句话就是辣鸡呀。对了呀, 你过你没用过啊卒死呢,我可以给你做一个报告啊,就是说它这个网络还是起飞的,就是硬盘啊…… 连香港记者都不如呢。

The test cases are not available before the final evaluation. When the evaluation starts, the evaluator system sends test cases to the REST endpoint of each team individually. Each team will receive 10 test cases (Q1to Q10). The response time for test case Qi is recorded as Ti(1≤i≤10). The final score is calculated using:

最终测试之前测试用例肯定不告诉你辣。测试开始的时候,每个队伍分别收到10个点,每个点它呀有这个Qi呢。然后我们就用这个式子,考虑一下你运行的努力和测试点行程算分咯。

where Ni is the size of the solution (the total number of correct paths) for Qi , Ki is the total number of paths returned by the REST service, Mi is the number of distinct correct paths returned by the REST service.

Ni是正确路径的个数,Ki是你算出路径个数,Mi是算出正确路径个数哒吖。

似乎是GDOI Day3 T1

题目的意思是第次有的几率给加上, 求.

表示前次中取中次的概率, 显然

, 于是

其实这就是第一类斯特林数.

那么就是

顺便开个脑洞, 第一类斯特林数和下降阶乘幂有个公式, 以及FFT大法...然而没什么卵用..

为了求出, 设就可以写出这样的转移...

由于

所以

再加上

就有

分为两部分就是

然而没什么用

又由二项式定理

所以这部分就可以变为

同样, 没啥用, 于是

最后, 我们可以很容易搞出, 于是就这样愉快的解决辣~

Google Codejam 2015 Qualification Round

请注意以下的复杂度均没有, 以及D我没做.

Problem A. Standing Ovation

翻译

种人,从编号到, 编号为的人鼓掌的条件是之前有个人鼓掌了.
一开始每种人有个, 问要让所有人都鼓掌, 需要增加的最少人数是多少?
你可以随意增加某种人.

种人的个数不会是.

题解

全部加到第种, 扫一遍, 如果当前人数不够触发下一种人,那就增加人数到下一种所需要的人数直到人数足够.

复杂度, 可以通过这题.

Problem B. Infinite House of Pancakes

翻译

有无数个队列, 其中有个队列有任务, 第个队列里面最开始有个任务.
每个时刻你可以做出以下两种操作:
1. 让每个有任务的队列里的任务,
2. 选择其中一个队列, 把其中的任务划出一部分, 放到另外一个队列里. 这个队列可以是那个队列之一, 也可以是一个新的空的队列.

问, 最少需要多少时刻可以把所有任务做完?

题解

一个很直观的想法是二分总的时间的上界, 然后再枚举消耗多少时间用于移动, 最后判断是否可行, 看起来是这样的:

bool check(int mt){
    for (int i = 0; i < mt; i++){
        int nt = mt - i; int left = i;
        for (int j = 0; j < d; j++){
            if (p[j] > nt){
                int cost = (p[j] / nt) + ((p[j] % nt) != 0) - 1;
                left -= cost;
            }
            if (left < 0)
                break;
        }
        if (left < 0) continue;
        return true;
    }
    return false;
}

可以通过这道题目

然而我们可以发现, 时间上界根本不需要二分, 完全可以枚举用于操作1的时间上界, 然后计算在这个情况下需要消耗的最少的移动时间,把它们加起来, 取最小就行了.

计算需要消耗的移动时间和上面的check类似, 就是里面的层循环, 就是我们枚举的时间上界.

Problem C. Dijkstra

翻译

定义一个在上的运算, 左取行, 右取列:

关于这个运算, 显然它满足结合律, 不满足交换律.

现在给你一个由ijk组成的字符串, 并把它重复遍, 问是否存在一种将这个新的字符串分成三个部分, 使得, 第一个部分的相乘的结果是, 第二部分相乘的结果是, 第三部分相乘的结果是的方案.

存在输出YES, 反之输出NO.

题解

一个很重要的性质是每一个小部分(就是)的乘方是有循环节的, 这个循环不是就是.

显然我们可以发现这个重复遍的字符串大概是这样的

..................... ..................... ..................... .....................

然后我们在上面的划分有两种

..................... .......|.......|....... ..................... .....................

或者

...............|...... ..................... ............|......... .....................

分别预处理处前缀和后缀的乘积, 然后枚举两个端点, 利用循环节和或者的余数就可以轻松计算出这两个端点能否凑出答案了.

在O2的帮助下,跑出large需要若干分钟. 勉强可以通过.

相比上面麻烦的讨论, 这个情况使用了一个更重要的性质, 结合律.
我们要把分成满足要求三个部分, 不妨叫他们,,. 于是我们可以得到, 以及, , , .

然而实际上, 只要满足, , , 就一定会有成立.

在由于循环节最大为, 只需要在最多前个, 后里, 求一个最小的前缀等于, 最小的后缀等于, 并且满足这时候就行了, 这里需要一些些细节处理, 然而比上面的简单多了.

可以通过这题.

Noi2014滚粗记

Day-1

火车晚点65分钟……滚到sz,住进了坑爹的宿舍,嗯,这枕头真不错,跟没有一样。

Day0

练习赛,直接就是去年的题目,以及笔试随便搞搞就过了……

Day1

第一题是noip普及组傻逼题,随便A,然后第二题一看lct,怂了不敢写,写了个50分暴力,然后开始玩第三题,玩啊玩啊51分……

结果出来一看第二题各种花样满分,用脚趾头估算一下名次80多……深深地感觉摇滚粗了。

题解:
第一题按位枚举,可以1,并且1比0优就1,不然这位就0,没了。数据sb到把m当做0可50 = =。
第二题lct维护1到n链上最大值,动态加边维护MST,至于出题人说的傻逼分块,who cares。
但是这题还有各种花样ac,比如花样ac还分卡时和不卡时,不卡时的ac方法有错误的三分(我觉得出题人特意调整数据让三分过了……妈蛋我15分钟造出一组卡掉三分的数据= =),三分之后在附近暴力,分段考虑一下bound花样暴力,或者直接卡时= =。以上算法通过顺序加边+并查(其实也有个alpha)维护……或者各种花样维护,二分+bfs(多个log)皆可。
以及一个看起来很厉害的spfa,就是按照a顺序加边,然后每加一条边就松弛一下S->xxx->u->v这条边,更新dist[v],进行一次spfa……这种算法随便拉一条链就卡掉了好吗,这样能ac...
第三题 多次迭代减深搜索+回文判定+手动剪剪剪!
有人通过特别的调整搜索顺序的技巧拿到了更多的分数。
我没去处理质数,实在懒得弄了。

Day2

去雷柏公司参观,结果在车上至少坐了1h……

然后进去参观,简直一股化(su)工(liao)厂的味道……
最后也不送个鼠标什么的,差评。。
下午按照传统三国杀。

Day3

第一题……看到要对每个prefix计算一个num[x],以为要在sam上维护xxxxx,然后拍出sam模板,把Len输出来看好像没有什么features,然后把|Right|弄出来,好像也没什么特性,感觉这题好神,所以怂了写了个30分暴力……

第二题,写完第一题去上(leng)了(jing)个(leng)厕(jing)所,发现随(set)便(shi)搞(O)搞(1)就可以了,然后大自爆了……

第三题,想着Day1T2各种花样AC,却没考虑其实真去写lct的没几个人……想着不能怂赶(kuai)紧(gun)上(cu),写完就能金牌回老家结婚了! 于是开始写可持久化平衡树,结果大自爆……(以及残酷的事实告诉我们就算30+200=230,230+201=431也没到BC类的金牌线。。)

题解:
第一题,考虑KMP,做过阿狸的打字机的少年都知道AC自动机的fail树,或者说KMP的next数组构成的树的性质,就是当前位置的suffix等于prefix的最大长度,而取一次next,就意味着变成了次大长度,这是可以反证得到的,就不多说了。

于是问题就变成对每个i求出的最小的, 显然这可以倍增常数写得好就过了。

但是有更简(sha)单(bi)的做法,考虑dfs的时候,维护一个pos,表示1~len(pos)的node都符合要求了,然后dfs下一层的时候,按照后面的len从小到大进行dfs(显然这样复杂度就是对的了),这个pos也同步往下,而退出dfs的时候,这个pos就恢复一下,这样就可以了……是不是很直观……
至于排序这个问题嘛……我不知道快排有没有问题,反正可以边链表/deque/vector然后从后往前/从前往后加边对吧。。

第二题,前面是模拟,然后……我们按照顺程序枚举……每个数
现在显然如果这个数在之前取的情况下可以取就取走,不然就不取考虑下一个数。
考虑取走一个数后的影响,显然按照取走的这个数,把原来一个矩形区域分成4块,分别要从左上走到取的这个数,从取的这个数到右下这两个可以走的区域,以及左下到取的这个数左下的数和取的这个数右上的数到右上这两个不能取,
如果每次暴力判断一个点在不在可取区域内,这个显然是要滚粗的。
考虑到每个位置最多在一次取走数时变成不可取区域,所以我们可以用bitmap暴力维护每个位置是否是不可取的,然后这就可以了……
接下来,我们要判定一个位置在哪个矩形区域内,并把它分裂,显然这个操作只需要每次遍历所有区域就够了,复杂度,不过血淋淋的事实告诉我们set的常数太大……

手写链表吧……少年

第三题,直接说了吧,链上不做限制就是dp+斜率优化,做了限制就麻烦很多因为删去前面的点可能对后面的凸包造成影响,而删除点的顺序不固定(l不单调),不过这个还是可以各种恶搞。。

但是树上就蛋疼多了,没有l限制的可以用splay/treap乱搞维护,有的话就更麻烦了。

一个直观的做法是hld,这样就变成维护每个链上的答案,对于每个链上的节点,直接套用链上的做法弄出这条链上的答案,然后再在之前的链上计算出可行答案,链上用可持久化凸包维护区间凸线。之后更新这条链的答案……听说这是std的做法……现场ak的大爷还有各种好写的做法……

后面的团抗我就没去围观了……粗奶玩了,结果……不多说。。。

就这样萌萌哒退役了,不能不说这种题目还真是让人各种遗憾……换个标题就能塞到noip去还能有一堆大爷ak你信不信……(出点diao zha tian的题目0分滚粗也不带这样遗憾的不是?),出题人的sxbk简直让人感动。

不过这样也送出了好几位浙江的AK(除了提答)爷,和高达541(441+100)的Au线……尽管还是暴力Au……

另外@roosephu 您给我的地址只有清华大学紫荆公寓XXX的话顺风和EMS都寄不了刀片啊。

最佳平方逼近

在群里听到有人说这个看起来很厉害的东西……

求一个多项式函数使得这玩意最小……

Read on

具体数学第7章习题5

服气了。。
为啥C(r,k)反而让(1+z^2)提供,这样有提供C(r,k)的指数反而是2k,卷积的另一边就变成n-2k。

TCO2014 R2C

Topcoder Open 2014 Round2 C

A

傻逼题,同样的还有教你做人的傻逼样例。。

题目说是给一个字符串,求一个尽可能小的使得的字典序最小。

用脑洞YY一下,如果存在一个尽可能小的位置使得存在一个使得的话,更大的就不用考虑了。反之,如果这个位置找不到一个使得, 那么这个一定不可能成为答案。

然后无脑乱搞……

这题Cha+FST真是太TM惨烈了……

B

看到AC代码我和我的小伙伴都惊呆了!

题目大意:给一个数组, , 以此来构建一个无向图:

对于的前缀和, 给连边,其中, 要你计算任意点对之间的最短距离的和,

如果没有这个坑爹的, 就可以有很多恶搞的做法……可惜。。

结果只要大力出奇迹就行了= =。吓哭。

C

笨蛋都会做的扫描线,不多说。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cstring>

using namespace std;

class InverseRMQ{
public:
    struct E {
        int Pos, Lmt, type, Id;
    } Ev[1111];
    static bool cmp(E a, E b){
        return a.Pos == b.Pos ? (a.type < b. type) : a.Pos < b.Pos;
    }
    bool okay[555];
    bool inrange(int L, int R, int V){
        return V >= L && V <= R;
    }
    string possible(int n, vector <int> A, vector <int> B, vector <int> ans){
        map<int,int> used;
        // map<int,int> lmts;
     multiset<int> minLmt;
        map<int,set<int> > requires;
        map<int,bool> F;
        A.push_back(1);
        B.push_back(n);
        ans.push_back(n);

        int m = A.size();
        int cnt = 0, rid = 0;
        for (int i = 0; i < m; i++){
            if (F[ans[i]])
                continue;
            int a = ans[i];
            int L = A[i], R = B[i];
            for (int j = 0; j < m; j++){
                if (ans[j] == a){
                    if (!inrange(L,R,A[j]) && !inrange(L,R,B[j]) && !inrange(A[j],B[j],L) && !inrange(A[j],B[j],R)){
                        return "Impossible";
                    }
                    if (inrange(L,R,A[j]))
                        L = A[j];
                    if (inrange(L,R,B[j]))
                        R = B[j];
                }
            }
            Ev[cnt].Pos = L;
            Ev[cnt].Lmt = ans[i];
            Ev[cnt].type = 1;
            Ev[cnt].Id = rid;
            cnt++;

            Ev[cnt].Pos = R + 1;
            Ev[cnt].Lmt = ans[i];
            Ev[cnt].type = 2;
            Ev[cnt].Id = rid;
            cnt++;
            rid++;
        }
        for (int i = 0; i < m; i++)
            if (ans[i] > n)
                return "Impossible";
        for (int i = 0; i < m; i++)
            for (int j = 0; j < m; j++)
                if (A[i] == A[j] && B[i] == B[j] && ans[i] != ans[j]){
                    return "Impossible";
                }
        
        for (int i = 0; i < m; i++) {
            Ev[cnt].Pos = A[i];
            Ev[cnt].Lmt = ans[i];
            Ev[cnt].type = 1;
            Ev[cnt].Id = rid;
            cnt++;
            Ev[cnt].Id = rid;
            Ev[cnt].Pos = B[i] + 1;
            Ev[cnt].Lmt = ans[i];
            Ev[cnt].type = 2;
            cnt++;rid++;
        }
        
        m = cnt / 2;
        sort(Ev, Ev + 2 * m, cmp);
        int lastPos = 1;
        for (int i = 0; i < 2 * m; i++){
            if (i == 0 || Ev[i - 1].Pos != Ev[i].Pos){
                if (Ev[i].Pos != lastPos){
                    if (minLmt.size()){
                        used[*minLmt.begin()] += Ev[i].Pos - lastPos;
                        int lmt = *minLmt.begin();
                        for (set<int>::iterator it = requires[lmt].begin(); it != requires[lmt].end(); it++){
                            okay[*it] = true;  
                        }
                        requires[lmt] = set<int>();
                    }
                    lastPos = Ev[i].Pos;
                }
            }
            if (Ev[i].type == 1){
                minLmt.insert(Ev[i].Lmt);
                requires[Ev[i].Lmt].insert(Ev[i].Id);
            }
            if (Ev[i].type == 2){
                minLmt.erase(minLmt.find(Ev[i].Lmt));
                requires[Ev[i].Lmt].erase(Ev[i].Id);
            }
        }
        if (n != lastPos){
            used[n] += n - lastPos;
        }
        for (int i = 0; i < rid; i++)
            if (!okay[i]){
                return "Impossible";
            }
        long long sum = 0;
        for (map<int,int>::iterator it = used.begin(); it != used.end(); it++){
            sum += it->second;
            if (it->first < sum)
                return "Impossible";
        }
        if (sum > n)
            return "Impossible";
        return "Possible";
    }
};