亟待解决的问题

我大概是啥都不会吧（好吧hello world还是会的）

另：收集到的小玩意儿<—戳这里低级错误<—戳这里 USACO囤题计划<—戳这里

三月份

3.4.2018

　　1.并查集里的“秩”是什么？

　　http://hzwer.com/3951.html里有一句话“秩其实有的时候很不好用，维护子树大小比较赞。。。”所以说秩不是子树大小...？网上也没有什么资料，只找到一个贴吧的帖子

3.6.2018

　　1.邻接表和前向星的区别？

　　我觉得就不过是一个用链表一个用数组（或是其他结构例如set）实现啊？

　　找到的一些东西链式前向星与邻接表对比；邻接表与链式前向星

3.7.2018

　　1.luogu3393一道诡异的图论……开O2MLE，不开O2TLE……似乎所有能加的优化都加上了，难道必须要SPFA的吗？堆优化的dijkstra是什么情况……交了20+，调了3个多小时……有一位的题解和我思路差不多但是我就……

3.13.2018

　　1.luogu3864字符串的锅……

    for (int i=1; i<=4617; i++)
    {
        cin >> f[i];
        for (int j=0; j<f[i].size(); j++)
            x[i][j] = cg[f[i][j]-'A'+1];
    }

　　这样x[]是空的……

3.16.2018

　　1.luogu1475的随笔留档玄学的题面和玄学的解题

3.26.2018

　　1.二项堆和二叉堆的区别？

　　参考文档：

　　1.简介 - 二叉堆 & 二项树 & 二项堆 & 斐波那契堆

　　2.优先队列三大利器——二项堆、斐波那契堆、Pairing 堆

3.30.2018

　　1.又是一道鬼畜的题目奶牛家谱，这篇是题解。问题在于

　　　　1. 树形dpⅠ的锅在哪里？

　　　　2. 树形dpⅡ中这个f[][]表示前缀和的dp方程还是第一次见到呢。表示只会感性理解

3.31.2018

　　1.luogu2528P2528 [SHOI2001]排序工作量之新任务的dp方程以及思想。Manchery学长提到了一个叫做反序表的东西？

　　参考资料： [反序表 DP] 51Nod 1020 逆序排列

四月份

4.15.2018

　　1.HHHOJ#37 反等差数列 I的分治思想

4.21.2018

　　1.欧拉筛的时间复杂度？网上大多说是线性的，但是紫书上写是O(nloglogn)的？

　　ans：好吧筛欧拉函数那个不叫欧拉筛……欧拉筛是用来筛素数的，确保了每一个合数仅被它最小的因数筛过，所以是O(n)的

五月份

5.6.2018

　　1.HHHOJ#72. 飞　　别人的博客（大致题意）：https://blog.csdn.net/KGV093/article/details/78170128

5.7.2018

　　1.bzoj1208[HNOI2004]宠物收养所　　带旋treapMLE了？？？　　代码：https://paste.ubuntu.com/p/By2ckNMkyf/

　　　　然后好像加了一些奇奇怪怪的特判就过了？？？（1.delete时候如果root==0退出；2.ans统计时候如果ans<0则ans=0）

　　ans：调营业额统计的时候发现了……好像原来是INF开成了2147483647，然后就溢出了？

5.10.2018

　　1.bzoj4520 [Cqoi2016]K远点对里面我有一个想法：如果$n>k$,那么把每个点的最远点加进堆里（应该需要去重），然后第$k$个点对就是全图的第k远点对。那么问题就成为了如何求出二维图中离每个点各自最远的点。

5.23.2018

　　1.luoguP4169 [Violet]天使玩偶/SJY摆棋子这个玄学的爆零！https://paste.ubuntu.com/p/yVbFdg4xP9/

　　ans：1.rebuild时候要先nth_element再a[mid]=t[mid]；

　　　　2.update时候一定要注意mn和mx的更新很容易错！

　　　　3.rebuild时候是tot不是n！

六月份

6.23.2018

　　1.HHHOJ#21的

 1     for (int i=1; i<=m; i++)
 2     {
 3         // char ch = getchar();
 4         // while (ch!='O'&&ch!='I'&&ch!='?') {
 5         //     if (ch!=' '&&ch!='
'){
 6         //         printf(""%c"",ch);
 7         //         // return 0;
 8         //     }
 9         //     ch = getchar();
10         // }
11         char ch[3];
12         scanf("%s",ch);
13         if (ch[0]!='?') scanf("%d",&q[i].x);
14         else q[i].opt = 2;
15         if (ch[0]=='I') q[i].opt = 1;
16         else if (ch[0]=='O') q[i].opt = 0;
17     }

　　如果用getchar()那么会读入读进负号并且读入超时。这个真的是很玄妙了

　　ans：垃圾数据出题人的锅，输入数据不合法行数不够

　　2.HHHOJ#111. 环游世界【在两个城市i,j之间旅行的代价是|wi–wj|^3 】贪心的正确性？

 1 #include<bits/stdc++.h>
 2 const int maxn = 100035;
 3 
 4 int n,a[maxn];
 5 long long ans;
 6 
 7 long long w(int x, int y){int t=abs(x-y);return 1ll*t*t*t;}
 8 int main()
 9 {
10     scanf("%d",&n);
11     for (int i=1; i<=n; i++) scanf("%d",&a[i]);
12     std::sort(a+1, a+n+1);
13     for (int i=3; i<=n; i+=2)
14         ans += w(a[i], a[i-2]);
15     for (int i=n-(n&1); i>2; i-=2)
16         ans += w(a[i], a[i-2]);
17     ans += w(a[1], a[2])+w(a[n], a[n-1]);
18     printf("%lld
",ans);
19     return 0;
20 }

七月份

7.1.2018

　　1.BZOJ1912 求k=2情形时，将最长链边权赋为-1的正确性？博客：https://www.cnblogs.com/antiquality/p/9248589.html

7.3.2018

　　1.hdu6184求共用一条边的三元环个数https://www.cnblogs.com/antiquality/p/9256837.html被32MB限制卡死

7.9.2018

　　1.hdu1814Peaceful Commission的2-sat板子题死活都WA……https://paste.ubuntu.com/p/RqWnTcnzZ7/

7.21.2018

　　1.7.21序列求和的前缀和巧妙思想

　　2.7.17magic的01字母树神奇操作

7.26.2018

　　1.kmp一题https://www.cnblogs.com/antiquality/p/9359509.html：最后一道，晚上困了改日研究。

八月份

8.17.2018

　　1.埃及分数：正的int传参下去就变负了？https://paste.ubuntu.com/p/bm75GV8CmC/

九月份

9.23.2018

　　1.给定若干带权线段，多次询问区间[l,r]内完整线段的权值和。

　　ans：直接差分，括号序列

9.26.2018

　　1.bzoj5180: [Baltic2016]Cities这题……明明本地大数据跑的比别人快，反而又WA又T……

　　https://loj.ac/submissions?problem_id=2783提交记录

9.27.2018

　　1.bzoj1579: [Usaco2009 Feb]Revamping Trails 道路升级第二种分层图做法挂了

十月份

10.17.2018

　　1.luoguP2505 [HAOI2012]道路　　取了模反而会更快？一脸懵逼。

　　ans：不是取模变快的问题。注意常数的影响！比如在dij时候处理距离的拓扑序列。然后可能还是有一点慢所以要开O2

10.21.2018

　　1.luoguP2145 [JSOI2007]祖码　　类似coci祖玛的思路做，还看了下精选试题解析那本书，然而依然WA。https://www.luogu.org/recordnew/lists?uid=18351&pid=P2145

10.22.2018

　　1.wqs二分这个东西……为什么一定要减去(强制要求的k*二分出的增量)？

一月份

1.5.2019

　　1.bzoj1778: [Usaco2010 Hol]Dotp 驱逐猪猡　　用f[i]表示在$i$点爆炸的概率，那么就是$f[i]=(i==1?0.5:0)+sum(1-f[j])*(p/q)/(deg[j])$，即把爆炸分割成两个条件：1.到达此点时没爆炸概率 2.在此点爆炸.。但这样好像会在某些地方算重，小样例都过不了。

二月份

2.7.2019

　　1.cf1110B. Tape　二分最长区间，然后每次贪心检查。WA

#include<bits/stdc++.h>
const int maxn = 100035;

int n,m,k,a[maxn],L,R;
long long ans;

int read()
{
    char ch = getchar();
    int num = 0, fl = 1;
    for (; !isdigit(ch); ch=getchar())
        if (ch=='-') fl = -1;
    for (; isdigit(ch); ch=getchar())
        num = (num<<1)+(num<<3)+ch-48;
    return num*fl;
}
bool check(int x)
{
    int seg = 0, lst = 1;
    long long cnt = 0;
    for (int i=1; i<=n; i++)
        if (a[i]-a[lst]+1 > x) seg++, cnt += a[i-1]-a[lst]+1, lst = i;
    seg++, cnt += a[n]-a[lst]+1;
    if (seg <= k) ans = std::min(ans, cnt);
    else return 0;
    return 1;
}
int main()
{
    n = read(), m = read(), k = read();
    for (int i=1; i<=n; i++) a[i] = read();
    L = 1, R = m, ans = 1ll<<60;
    for (int mid=(L+R)>>1; L<=R; mid=(L+R)>>1)
        if (check(mid)) R = mid-1;
        else L = mid+1;
    printf("%lld
",ans);
    return 0;
}

　　ans：我是zz吧。形如x.....x........x.x.x.x就会把后半段全覆盖了……题意相当于求k-1段最长空段。

2.8.2019

　　1.hh174　这个点分我为什么要跑1.5s？

  1 #include<bits/stdc++.h>
  2 typedef long long ll;
  3 const int maxn = 100035;
  4 const int maxm = 200035;
  5 const int maxNum = 10000035;
  6 
  7 struct Path
  8 {
  9     ll d;
 10     int mx;
 11     Path(ll a=0, int b=0):d(a),mx(b) {}
 12     bool operator < (Path a) const
 13     {
 14         return mx < a.mx;
 15     }
 16 }stk[maxn];
 17 ll ans;
 18 bool vis[maxn];
 19 int n,p,bloTot,cnt[maxNum],a[maxn];
 20 int size[maxn],son[maxn],root,top;
 21 int edgeTot,head[maxn],nxt[maxm],edges[maxm];
 22 
 23 int read()
 24 {
 25     char ch = getchar();
 26     int num = 0, fl = 1;
 27     for (; !isdigit(ch); ch=getchar())
 28         if (ch=='-') fl = -1;
 29     for (; isdigit(ch); ch=getchar())
 30         num = (num<<1)+(num<<3)+ch-48;
 31     return num*fl;
 32 }
 33 void addedge(int u, int v)
 34 {
 35     edges[++edgeTot] = v, nxt[edgeTot] = head[u], head[u] = edgeTot;
 36     edges[++edgeTot] = u, nxt[edgeTot] = head[v], head[v] = edgeTot;
 37 }
 38 void getRoot(int x, int fa)
 39 {
 40     size[x] = 1;
 41     for (int i=head[x]; i!=-1; i=nxt[i])
 42     {
 43         int v = edges[i];
 44         if ((v!=fa)&&(!vis[v])){
 45             getRoot(v, x), size[x] += size[v];
 46             son[x] = std::max(son[x], size[v]);
 47         }
 48     }
 49     son[x] = std::max(son[x], bloTot-size[x]);
 50     if (son[x] < son[root]) root = x;
 51 }
 52 void dfs(int x, int fa, ll d, int mx)
 53 {
 54     stk[++top] = Path(d, mx);
 55     for (int i=head[x]; i!=-1; i=nxt[i])
 56     {
 57         int v = edges[i];
 58         if ((v!=fa)&&(!vis[v])) dfs(v, x, d+a[v], std::max(mx, a[v]));
 59     }
 60 }
 61 void calc(int x, int fa, int d, int opt)
 62 {
 63     top = 0;
 64     dfs(x, fa, d+a[x], std::max(d, a[x]));
 65     std::sort(stk+1, stk+top+1);
 66 //    for (int i=1; i<=top; i++)
 67 //        printf("dis:%lld mx:%d
",stk[i].d,stk[i].mx);
 68     long long tot = 0;
 69     for (int i=1; i<=top; i++)
 70     {
 71         tot += cnt[(stk[i].mx+p-stk[i].d%p)%p]*opt;
 72         ++cnt[((stk[i].d-a[fa]%p+p)%p+p)%p];
 73     }
 74     ans += tot;
 75 //    printf("sum:%lld
",tot);
 76 //    puts("--------------------------");
 77     for (int i=1; i<=top; i++)
 78         --cnt[((stk[i].d-a[fa]%p+p)%p+p)%p];
 79 }
 80 void deal(int x)
 81 {
 82     ++dmd;
 83     calc(x, x, 0, 1), vis[x] = 1;
 84     for (int i=head[x]; i!=-1; i=nxt[i])
 85     {
 86         int v = edges[i];
 87         if (!vis[v]) calc(v, x, a[x], -1);
 88     }
 89     for (int i=head[x]; i!=-1; i=nxt[i])
 90     {
 91         int v = edges[i];
 92         if (!vis[v]){
 93             bloTot = size[v], root = 0;
 94             getRoot(v, 0), deal(root);
 95         }
 96     }
 97 }
 98 int main()
 99 {
100     freopen("hh174.in","r",stdin);
101     memset(head, -1, sizeof head);
102     n = read(), p = read(), bloTot = son[0] = n;
103     for (int i=1; i<n; i++) addedge(read(), read());
104     for (int i=1; i<=n; i++) a[i] = read();
105     getRoot(1, 0), deal(root);
106     printf("%lld
",ans+n);
107     return 0;
108 }

View Code

2.9.2019

　　1.hh182B. Rabbit 　贡献不独立？

2.11.2019

　　1.bzoj2502: 清理雪道　　其实并没有很懂

　　2.bzoj2406: 矩阵　　为什么以及如何判定上下界网络流已经明白了。但是还是没有懂虚拟源汇和超级源汇的建边过程。

三月份

3.10.2019

　　1.hh#187. Hashit　　哈希数字符串的正确姿势？血的事实说明并不是模数越多越好。

　　ans：这个，可以参考OI视角浅谈布隆过滤器，个人感觉低配多哈希性价比并不怎样。

3.17.2019

　　1.Bell数为什么是$B_{n+1}=sumlimits_{i=0}^{n}{nchoose i}B_i$而不是$B_{n+1}=sumlimits_{i=0}^{n}{nchoose i}B_{n-i}$

　　ans：原问题过水，已隐藏……

八月份

8.12.2019

　　1.8.12时空阵计数：使得地点 1 和地点 n 之间的最短距离恰好为 k。k=2部分分。

　　ans：预处理出错，已隐藏　　　　　　　　