xjoi上的半天+废掉的下午和晚上TT 上午考试感觉都不会.第二题想出的方法一点也不科学.第一题乱猜的结论还不知道怎么构造.第三题完全ovo感觉有点像魔法森林不过不会写toptree于是想起当年的三分乱搞. 然后各种时间就在不知道干什么中过去了. 有时候觉得心里好乱啊根本沉不下心来做题.然后也没有办法解决.只有事后去感到后悔然后毫无用处继续循环… 所以是时候做出一些改变啊…其实事情不少啊少年ovoovo 看到zhx很早之前写的文章,“noi也许是因为心境不同所以也没认真考”.他没认真考还是能进队.我要是不认真后果可能就是死啊ovoovo 所以不能这样下去了啊…每次都这么说TT 所以我还是太弱了.
今天是中考day2ovoo今天是sccpc…ovoovo… 比赛过程可以概括为前三小时狂刷一度rank1然后开始卡题后两小时零输出惨烈牺牲ovoovo 还是自己太弱了没想清楚一些事情于是ovoovo a题水. b题和"无敌异或"有些像.于是搞之.虽然反应过来有点慢. c题usaco原题ovoovo d题竟然误以为是菊花…最后才反应过来.改对了程序然而dfs强行套bitset作die中… e题是啥?哦似乎是水水的推公式. f题两遍lis. g题果然是最小割然而我和mhy都没有想到正确的建图.ovoovo h题根本没时间想. i题写了个高端dijkstra于是被卡tle.mhy认为可以直接用堆于是wa.然后听到正解眼泪流下来ovoovo j题无脑… 想去年都过了7题去年最后延时怒过一题.比去年还差啊伐开心ovoovo 所以我还是太弱了.
mhy写此题写了良久啊然后T啊T,T啊T.然后我去翻了一下seter的博客.结合他的东西yy出一种比较优越的做法. 如果我是出数据的,我会出两种数据,菊花图和链. 如果是菊花图,直接朴素ovoovo如果是链,可以以每个叶子节点为根建一次可持久化线段树. 如果是链上长出了一团菊花… how to 结合? 不停地删叶子.如果删到某层时叶子足够少了,那就建可持久化线段树去. 对于询问,有若干种情况. 标记每个根里离得很近的点. 如果两个中有一个被标记过,那么直接以这个根求另一个的答案,然后朴素查找近的这个点到根的答案. 如果两个点都没有被删 ,那一定有至少一个根可以使得这条链的两个端点有祖先关系.这样的话直接用可持久化线段树求解. 好像完了?然后wa了ovoovo 还有一种情况是某个点被删了,但是删之后它是接在树枝上的! 于是它离根很远,还不一定有能搞出祖先关系的解. 于是先爬行到没被删的地方,看两个端点是否在同一棵被删的叶子树上. 如果是就朴素了. 如果不是的话,先求没被删的这一段,再朴素被删的一段. 终于完辣. 从来没写过这种代码.感觉自己萌萌哒.
#include #include #include using namespace std; struct seg { int v; seg *ch[2]; }; struct edge { int t; edge *ne; }; const int maxn = 40003; const int leafc = 20; const int maxk = leafc + 1;; const int maxl = 17; const int albsz = 1000003; int n, m, t, w[maxn], dl[maxn], df[maxn], fk[maxn], deg[maxn]; int tlf, lf[maxk], la[maxk][maxn], d[maxk][maxn], fr[maxk][maxn]; int dfb[maxk][maxn], dfe[maxk][maxn], dfn; int tvis, vis[maxn], vo[maxn], tv; seg *rt[maxk][maxn], *rl[maxk][maxn]; edge ebuf_arr[maxn « 1], *ebuf(ebuf_arr), *head[maxn];...
#include #include #include using namespace std; #define _l (long long int) const int maxn = 103; const int mod = 1e9 + 7; int modPow(int a, int x) { int s(1); for (; x; x »= 1, a = _l a * a % mod) if (x & 1) s = _l s * a % mod; return s; } int fac[maxn], finv[maxn], vinv[maxn]; int n, m, k, f[maxn], c[maxn];...
这题我的做法不太一样.所以mark一下.首先我把题里的n和m看反了,所以下面的m和n都与原题里的m和n相反. 首先考虑一行的方案.在不考虑顺序(即只考虑题中要求每个颜色个数这个条件一定时)的方案数. n是50,刚好可以正整数拆分,把n拆成不超过k个正整数时,可行的方案数为n! / c1! / c2! / … / s1! / s2! / …这个样子.其中cx表示正整数拆分中的第x个数(后面补0可以不管),s1表示第一种相同的cx的个数. 其实就是说怎么把k个颜色分配到我拆分出的这些整数里. 然后对于一种这样的方案的排列数也比较好求. 然后就是求m行的情况.我的思考方法是先按上面固定顺序,再乘m!.其实这样有问题虽然我没出事.也有可以补救的方法. 上面拆出来的一种拆分,设它有t个不同的颜色分配方案,一种方案有c种排列.这里用一个类似于背包的转移,f[i] = f[j] + 一坨东西. 这坨东西就是把(i - j)个方案按顺序排列的答案.(都叫方案啊好晕ovo)当然这里排列的话会用到判断t是否大于等于(i - j),但是t被模过ovoovo.我偷了个懒假设t如果被模过不会正好小到影响统计.果然也没有. 其实也可以不去除,而是乘组合数吧.不过写起来好麻烦. 咦写了这么多了.然而感觉还是没说清楚啊.ovoovo结合代码理解吧.
#include #include #include using namespace std; int calc(int i, int j, int d) { if ((i & 1) && (j & 1)) return d; else return calc((i + 1) » 1, (j + 1) » 1, d + 1); } int main() { #ifdef LAEKOV_LOCAL freopen(".in", “r”, stdin); #endif int t; scanf("%d", &t); while (t --) { int n, s(0); scanf("%d", &n); for (int i = 0; i < n; i += 2) { int a, b; scanf("%d%d", &a, &b); s ^= calc(a, b, 0); } puts(s ?...
mhy开了道找规律oovovo 打表找规律良久.最后还是没有O(1)的规律.倒是发现有点像分形,有个log级别的递推式. 怎么来的啊好神奇啊ovoovo
考了一下今年jsoi的某试.感觉整个人都是晕的. 第一题某三氧化萌在省选前正好和我说过.还记得我花了整个吃晚饭的时间去想终于想出了怎么证明.翻了一下qq聊天记录秒之ovoovo. 第二题之前省选集训的时候做过!?翻了一下正好是4月10号无疑.依稀记得当时我用了二分+线段树,比正解多一个log,一直以为是卡常数,后来才知道正解是单调队列.(5s的题要跑9s是什么心态) 于是狠狠地想了一会,然后发现可以分三种情况讨论,每种情况都可以用单调队列解决.其中两种还能通过翻转合并代码.于是开心ovo.感觉这题主要是在玩不等式和函数单调性. 第三题无脑可持久化trie打打就过了ovoovo 为啥bzoj上没这套题啊ovoovo 2个多小时ak然后去404被高三某学长虐狗. 下午颓颓颓,晚上颓颓颓. 于是我还是太弱了.
最近都在做梦的感觉啊.这道题倒是mhy的博客一语点醒梦中人. 只会加正数,所以每个数只有至多一次会从负变非负. 链剖是肯定的.然后记录一下当前最大的负数是谁.如果大于等于0就改掉.所以还是O(n*log2n). 所以我还是太弱了.于是读入优化大法抢了一个rank1.