今天爆零了


考了几道SB题…然而我比题目还SB就爆零了…
也许是下午状态不太好…也许是睡眠不足…也许是…
癌, 还是自己菜…
不知道怎么…考完试题目到似乎都很好做了…也许是潜意识里听见他们讨论做法了?
癌…_(:з」∠)_

懵逼的 题目

T1

usaco2016open bronze3 reduce
emmm…一道o(1)的SB题…被我写了200line+然后调不出来就弃了…(1.5h passed…
删除的奶牛一定在原先不删的时候最小的边界上…枚举哪个边界删几个就好了…

T2

传送至 Luogu

普通的区间DP…四重循环那叫一个暴力…然后考试的时候也没仔细看…就输了个样例…GG

bool f[i][j][k] // 在区间[i, j]是否能达到k这个值...
f[i][j][x] ||= (f[i][k][x - 1] && f[k + 1][j][x - 1]) //...

T3

传送至 Luogu

…本来以为这题能A的…离线倒序转成并查集加点…然后看任意一个点的祖先的rank是否 == 已经加入的点数…
结果没有考虑两个点已经连在一起的情况(就是祖宗一样)…结果卡成样例分…

T4

传送至 Luogu

也是非常水的一道题…但是不知道为什么考试的时候一头乱麻什么思路也没有…
刚考完就知道怎么做了…
一个类似于滑动窗口的东西…而且以前好像还做过…GG
先排序…
写一个队列…先从左向右push, 如果push的节点值比队首的节点值大k, 就弹队列…记录f[i] = max(q.size(), f[i - 1]), 就代表这个点到开头能放的最大的允许的钻石数
然后在从右向左跑一遍…
最后遍历一下就行了…

T5

传送至 Luogu

…没想到T5这么水…然后就想了一个奇奇怪怪的dijk…结果又是样例分…GG
其实就是枚举修改最短路上的哪条边…然后暴力跑最短路更新答案…GG
因为最短路的边个数最多是n - 1条…所以怎么也T不掉的…
改的时候WA90了一晚上…刚刚发现是转反向边的时候没加括号…^的优先级没有+高…GG
记住了反向边是这样的…

rev(a) (((a - 1) ^ 1) + 1) // 之前是 ((a - 1) ^ 1 + 1)....结果一直Wa...GG

然后…5个题全是样例分…

总之
这次考试的题…其实算法很简单..或者根本没有算法…但是确实我没有想到…
一个是思路不够开阔…一个是做题的时候太没有紧迫感了…是不是被数据结构弄傻了啊…
以后得听家父的话计着时间做题了…然后多做一做奶牛题提高一下姿势水平…

沙茶的 代码

T1


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN (50000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define INF (0x7fffffff)
using namespace std;
struct cow
{
    int x, y, bh;
}a[MAXN], b[MAXN], c[MAXN], d[MAXN];
int ans = INF;
int n;
bool cmpd(cow, cow);
bool cmpu(cow, cow);
bool cmpl(cow, cow);
void solve();
int cx(int, int, int, int);
int main()
{
    freopen("reduce.in", "r", stdin);
    freopen("reduce.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &a[i].x, &a[i].y);
        a[i].bh = i;
        b[i] = c[i] = d[i] = a[i];
    }
    solve();
    printf("%d", ans);
    return 0;
}
bool cmpd(cow x, cow y)
{
    return x.y < y.y;
}
bool cmpu(cow x, cow y)
{
    return x.y > y.y;
}
bool cmpl(cow x, cow y)
{
    return x.x < y.x;
}
bool cmpr(cow x, cow y)
{
    return x.x > y.x;
}
void solve()
{
    sort(a + 1, a + n + 1, cmpu);
    sort(b + 1, b + n + 1, cmpd);
    sort(c + 1, c + n + 1, cmpl);
    sort(d + 1, d + n + 1, cmpr);
    for (int i = 0; i <= 3; i++)
    {
        for (int j = 0; i + j <= 3; j++)
        {
            for (int k = 0; k + i + j <= 3; k++)
            {
                for (int w = 0; w + k + i + j <= 3; w++)
                {
                    ans = min(ans, cx(i, j, k, w));
                }
            }
        }
    }
}
int cx(int u, int dow, int l, int r)
{
    int re;
    bool v[MAXN];
    memset(v, false, sizeof(v));
    int maxx = d[1].x, minx = c[1].x, maxy = a[1].y, miny = b[1].y;
    for (int i = 1; i <= u; i++)
    {
        if (!v[a[i].bh])
        {
            v[a[i].bh] = true;
        }
        else
        {
            u++;
        }
    }
    for (int i = 1; i <= dow; i++)
    {
        if (!v[b[i].bh])
        {
            v[b[i].bh] = true;
        }
        else
        {
            dow++;
        }
    }
    for (int i = 1; i <= l; i++)
    {
        if (!v[c[i].bh])
        {
            v[c[i].bh] = true;
        }
        else
        {
            l++;
        }
    }
    for (int i = 1; i <= r; i++)
    {
        if (!v[d[i].bh])
        {
            v[d[i].bh] = true;
        }
        else
        {
            r++;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (!v[a[i].bh])
        {
            maxy = a[i].y;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (!v[b[i].bh])
        {
            miny = b[i].y;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (!v[c[i].bh])
        {
            minx = c[i].x;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (!v[d[i].bh])
        {
            maxx = d[i].x;
        }
    }
    re = (maxx - minx) * (maxy - miny);
    return re;
}

/*
6
1 1
7 8
10 9
8 12
4 100
50 7

*/

T2

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (248 + 5)
#define INF (40 + 8)
using namespace std;
int n;
int a[MAXN];
bool f[MAXN][MAXN][INF];
void solve();
int main()
{
    freopen("248.in", "r", stdin);
    freopen("248.out", "w", stdout);
    scanf("%d", &n);
    memset(f, false, sizeof(f));
    int maxa = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        maxa = max(a[i], maxa);
        f[i][i][a[i]] = true;
    }
    solve();
    for (int i = INF; i >= 0; i--)
    {
        for (int le = 1; le <= n; le++)
        {
            for (int ri = le; ri <= n; ri++)
            {
                if (f[le][ri][i])
                {
                    printf("%d\n", i);
                    return 0;
                }
            }
        }
    }
    printf("%d", maxa);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
void solve()
{
    for (int i = 1; i <= n; i++)
    {
        for (int le = 1; le + i <= n; le++)
        {
            int ri = le + i;
            for (int k = le; k < ri; k++)
            {
                for (int z = 0; z <= INF; z++)
                {
                    if (f[le][k][z] && f[k + 1][ri][z])
                        f[le][ri][z + 1] = true;
                }
            }
        }
    }
}

T3
// 注意并查集合并前要判断是否已经在一个集合里

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (200000 + 5)
#define MAXM (200000 + 5)
#define INF (0x7ffffff)
#define LL long long
#define DD double
#define pii pair<int, int>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mabs(a) ((a) > 0 ? (a) : (-(a)))
using namespace std;
struct edg
{
    int from;
    int to;
    int next;
} b[MAXM << 1];
int cntb = 0;
int g[MAXN];

struct bcj
{
    int fa;
    int rank;
} f[MAXN];

int n;
int m;
bool ans[MAXN];
int a[MAXN];
int find(int);
void uni(int, int);
void adn(int, int);
void solve();
int main()
{
    freopen("closing.in", "r", stdin);
    freopen("closing.out", "w", stdout);
    memset(ans, false, sizeof(ans));
    scanf("%d%d", &n, &m);
    int srx, sry;
    for (int i = 1; i <= n; i++)
    {
        f[i].fa = i;
        f[i].rank = 0;
    }
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &srx, &sry);
        adn(srx, sry);
        adn(sry, srx);
    }
    for (int i = n; i >= 1; i--)
    {
        scanf("%d", &a[i]);
    }
    solve();
    for (int i = n; i >= 1; i--)
    {
        if (ans[i])
            puts("YES");
        else
            puts("NO");
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}
void adn(int from, int to)
{
    b[++cntb].next = g[from];
    b[cntb].from = from;
    b[cntb].to = to;
    g[from] = cntb;
}
void uni(int x, int y)
{
    int fx = find(x);
    int fy = find(y);
    if (f[fx].rank > f[fy].rank)
    {
        f[fy].fa = fx;
        f[fx].rank += f[fy].rank;
    }
    else
    {
        f[fx].fa = fy;
        f[fy].rank += f[fx].rank;
    }
}
int find(int x)
{
    return ((x == f[x].fa) ? (x) : (f[x].fa = find(f[x].fa)));
}
void solve()
{
    for (int i = 1; i <= n; i++)
    {
        f[a[i]].rank = 1;
        for (int j = g[a[i]]; j; j = b[j].next)
        {
            if (f[b[j].to].rank)
            {
                if (find(a[i]) != find(b[j].to)) // GG 
                    uni(a[i], b[j].to);
            }
        }
        if (f[find(a[i])].rank == i)
        {
            ans[i] = true;
        }
    }
}

/*
4 3
1 2
2 3
3 4
3
4
1
2
*/

T4

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (50000 + 5)
#define INF (0x7ffffff)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
int n;
int le[MAXN];
int ri[MAXN];
int a[MAXN];
int k;
int ans;
bool cmp(const int x, const int y)
{
    return x < y;
}
void init();
void solve();
int main()
{
    freopen("diamond.in", "r", stdin);
    freopen("diamond.out", "w", stdout);
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    sort(a + 1, a + n + 1, cmp);
    init();
    solve();
    printf("%d", ans);
    return 0;
}
void init()
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        q.push(a[i]);
        if (a[i] > q.front() + k)
        {
            q.pop();
        }
        le[i] = max(le[i - 1], q.size());
    }
    while (!q.empty())
        q.pop();
    for (int i = n; i >= 1; i--)
    {
        q.push(a[i]);
        if (a[i] + k< q.front())
        {
            q.pop();
        }
        ri[i] = max(ri[i + 1], q.size()); // 可以向后延伸多少
    }
}
void solve()
{
    for (int i = 1; i < n; i++)
    {
        ans = max(ans, ri[i + 1] + le[i]);
    }
}

T5

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#define MAXN (250 + 5)
#define MAXM (250000 + 5)
#define INF (0x7ffffff)
#define pii pair<int, int>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define rev(a) ((a - 1) ^ 1 + 1)
using namespace std;
struct cmp
{
    bool operator () (const pii x, const pii y)
    {
        return x.second > y.second;
    }
};
struct edg
{
    int from;
    int to;
    int cost;
    int next;    
}b[MAXM << 1];
int cntb = 0;
int g[MAXN];

int n;
int m;
int ans;
int pre[MAXN];
int dis[MAXN];
void solve();
void dijk(int);
void adn(int, int, int);
int main()
{
    freopen("rblock.in", "r", stdin);
    freopen("rblock.out", "w", stdout);
    scanf("%d%d", &n, &m);
    int srx, sry, srz;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &srx, &sry, &srz);
        adn(srx, sry, srz);
        adn(sry, srx, srz);
    }
    solve();
    printf("%d", ans);
    return 0;
}
void adn(int from, int to, int cost)
{
    b[++cntb].next = g[from];
    b[cntb].from = from;
    b[cntb].to = to;
    b[cntb].cost = cost;
    g[from] = cntb;
}
void dijk(int start)
{
    bool v[MAXN];
    memset(dis, 0x7f, sizeof(dis));
    memset(v, false, sizeof(v));
    priority_queue<pii, vector<pii>, cmp> q;
    dis[start] = 0;
    q.push(make_pair(start, dis[start]));
    while (!q.empty())
    {
        pii dq = q.top();
        q.pop();
        if (v[dq.first])
            continue;
        v[dq.first] = true;
        for (int i = g[dq.first]; i; i = b[i].next)
        {
            if (dis[b[i].to] > dis[dq.first] + b[i].cost)
            {
                pre[b[i].to] = i;
                dis[b[i].to] = dis[dq.first] + b[i].cost;
                q.push(make_pair(b[i].to, dis[b[i].to]));
            }
        }
    }
}
void solve()
{
    int ch[MAXN];
    dijk(1);
    for (int i = 1; i <= n; i++)
    {
        ch[i] = pre[i];
    }
    int dis0 = dis[n];
    for (int i = n; i != 1; i = b[ch[i]].from)
    {
        b[ch[i]].cost <<= 1;
//        b[rev(ch[i])].cost <<= 1;
        dijk(1);
        ans = max(ans, dis[n] - dis0);
        b[ch[i]].cost >>= 1;
//        b[rev(ch[i])].cost >>= 1;
    }
}

By 又双叒叕倒数的 Cansult