bzoj

BZOJ里的第二道noip题，今年防ak题，OTZ。 最初直接用大素数取模的方法要TLE，虽然本机不会。 用几个小质数pni，算出在模pni的同余系里0~pni-1的答案。如果x为原方程的解的话x%pni在模pni意义下也应该为0。 然后还是会TLE，最后发现小质数乘的时候不用取模了。bzoj上这题纯粹是丧心病狂卡常数啊。 ORZMHY #define PROC "equation" #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef unsigned long long uqw; typedef long long qw; const int maxn = 109; const int maxl = 10009; const int maxm = 1000009; const int cp = 5; //const int pn[cp] = {111119, 23333, 11113, 23251, 33329}; const int pn[] = {22861, 22871, 22877, 22901, 22907, 22921}; const int p10[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};...

做过。但是不对。 迷之找负环。 初值直接赋为0，这样可以节省找没用的最短路的时间。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct edge { int t; double v; edge *next; }; const int maxn = 3009; const int maxm = 10009; const double eps = 1e-9; const double finf = 1e20;  int n, m; bool iq[maxn]; double d[maxn], ave; edge *ep, *head[maxn], elst[maxm]; bool dfs(int p) { iq[p] = 1; for (edge* e = head[p]; e; e = e-> next) if (d[e-> t] - (d[p] + e-> v) > eps) {...

数据结构题神马的最开心了。 乍一看动态树，其实不然。复杂度可以再乘一个log的。 启发式合并。然后合并的时候直接暴力重构整棵子树，建主席树只和父亲节点有关，所以还是能搞定。 写了一个机智的垃圾回收把log^2的空间变成了log。然后发现空间有512MB。 #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; struct edge { int t; edge* next; }; struct seg { int v, c; seg *ls, *rs; }; #define readInt(_s_) {\ int _d_;\ _s_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ } const int maxn = 80009; const int maxl = 33; const int maxnd = maxn * maxl;...

好恶心的数据结构题。 考虑单个询问。把(视作1，把)视作-1，设minprefix为最小前缀和，设cp=(minprefix+1)/2，那么答案为(sum/2+cp*2)，使劲想想想得出来。 所以就是用个splay或者smt来维护一下一段的最小前缀和以及总和。因为有两种操作所以写起来比较麻烦。要注意不要把操作看反了，还要注意标记的优先级和更新的问题。 恶心了一下午。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct dat { int sm, t[2][2]; inline void operator =(const dat& a) { sm = a. sm; t[0][0] = a. t[0][0]; t[0][1] = a. t[0][1]; t[1][0] = a. t[1][0]; t[1][1] = a. t[1][1]; } }; const int maxn = 100009; int n, m, cr, a[maxn], sz[maxn], ls[maxn], rs[maxn], pt[maxn], vl[maxn]; bool flip[maxn], rev[maxn]; dat d[maxn]; dat sgd(int v) { dat r; r. sm = v;...

好厉害的数据结构题，时限太吓人了。 最初想写莫队的，但是在数据范围下屈服了。 用可持久化线段树套可持久化线段树来维护可过。虽然跑了97s。本机跑得快得多，虽然有两个点被卡到了18s。 #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; struct seg { int v, ls, rs; }; #define readInt(_s_) {\ _s_ = 0;\ int _d_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ } const int maxn = 100009; const int maxl = 20; const int maxnd = maxn * maxl * maxl; seg s[maxnd]; int n, m, t, a[maxn], d[maxn], c[maxn], *r[maxn], sp, rt[maxn];...

这题就是考你怎么把能优化常数的地方都优化一下。 做法比较清晰，分块加持久化值域线段树。大块预处理，小块暴力算。虽然最初不想写持久化数据结构就试图用平衡树去做，结果发现做法是错的，单次复杂度是O(n*lgn)的。看来我太年轻了。后来改了但是常数巨大也没法跑。 本来是一次询问里有若干次在持久化线段树上查询的。然后首先发现可以预处理出从开头到一块末尾这一段里有多少个比后面任意一个位置大的数的个数。还有一个数前面比它大的数的个数。这俩加起来常数差不多就小到能过了。 丧心病狂！ #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; const int maxn = 50009; const int maxb = 259; const int maxnd = maxn * 30; struct seg { int v; seg *ls, *rs; }; inline bool cmpP(const int* a, const int* b) { return *a < *b; } #define readInt(_s_) {\ int _d_;\ _s_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\...

暑假的时候就听zhx讲过这题，不过好像当时讲复杂了。 很容易知道答案就是每次减去被出列的人里面没有出过列的人在原序列里右边的比她矮的人的个数。 所以每个人只会被算一次，均摊下来是O(n)的。然后就是怎么很快地找到这些人。我觉得用线段树比较方便，时间可以做到log。不知道是不是能用并查集。 好写好调。 #include <cstdio> #include <cstdlib> #include <cctype> #include <memory.h> #include <algorithm> using namespace std; #define readInt(_s_) {\ int _d_;\ while (!isdigit(_d_ = getchar()));\ _s_ = 0;\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ } typedef long long qw; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif struct seg { int l, r, v, p; seg *ls, *rs; }; const int maxn = 500009;...

连yjq都会做，简直是水暴了。 #include <cstdio> #include <cstring> #include <algorithm>   usingnamespacestd;   constintmaxn = 20009;   intn, m, a[maxn], t[maxn], *r[maxn], s;   intbtQry(int* t, intp) {     ints = 0;     while(p)         s += t[p], p -= (p & -p);     returns; }   voidbtChg(int* t, intp, intv) {     while(p < maxn)         t[p] += v, p += (p & -p); }   inlineboolcmpP(constint* a, constint* b) {     return*a < *b; }   intmain() { #ifndef ONLINE_JUDGE     freopen("in.txt", "r", stdin); #endif...

居然写了一半手贱就把所有东西都弄没了。严重地不开心。 既然这样那么简单说吧。 长度≤10^5这个条件在bzoj上没说。 用fft求出长度和为leni的组数。 枚举第三根火柴，可行的是（它作为最长的总组合数 - （长度≤它的组合数））那么多组。 fft必需常数够小。不写蝴蝶会tle。 #include <cstdio> #include <cmath> #include <cctype> #include <memory.h> #include <algorithm> using namespace std; typedef long long qw; #define readInt(_s_) {\ int _d_;\ _s_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ } struct cplx { double r, i; inline cplx() { r = 0, i = 0; } inline cplx(double r0, double i0) { r = r0, i = i0;...

很久之前就看过的题。不过一直没有勇气去做。爱真的需要勇气。 mex这个函数的性质比较奇妙。一端确定的话一定是单增的。两段和起来也一定是增加的。 可以很方便地求出从1到任何一个位置的mex。考虑把询问离线。按左端点排序。如果去掉一个数，那么对于右端点在（从这个数到下一个等于这个数的位置）这一段里的询问，它的值至多是这个数。 所以用线段树维护区修单查维护一下区间最小值就好了。注意如果没有下一个数了那么右端点是n。 据说要离散不过被我用map给水过去了。 #include <cstdio> #include <cctype> #include <memory.h> #include <map> #include <algorithm> using namespace std; #define readInt(_s_) {\ int _d_;\ _s_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ } struct seg { int l, r, z; seg *ls, *rs; }; struct query { int l, r, n; }; inline bool cmpQuery(const query& a, const query& b) { return a. l < b....