1 比赛

1.1 那23个路口

题目解析&题解

题意

给定一个$m $*$n$的权值图,求走23步后最大的可取的权值和。

分析

我们可以通过dp来解决此题。$dp[i][j][k]$表示在第$i$行$j$列走了$k$次最大的权值和。

那么可以轻易地得到$dp[i][j][k] = dp[i -1][j][k-1]+dp[i+1][j][k-1]+dp[i][j+1][k-1]+dp[i][j-1][k-1]$

Code

#include <iostream>

using namespace std;

const int N = 500 + 5;
const int fx[4] = {0, 0, -1, 1};
const int fy[4] = {-1, 1, 0, 0};

typedef long long ll;

int a[N][N];
ll f[N][N][25];

int n, m, sx, sy;

bool check_where(int x, int y)
{
    return x < 1 ? false : x > n ? false : y < 1 ? false : y <= m;
}

int main()
{
    cin >> m >> n;
    for (int i = 1; i <= n; i ++ )
    {
        f[i][0][0] = -100000;
        f[i][m + 1][0] = -100000;
        for (int j = 1; j <= m; j ++ )
        {
            f[0][j][0] = -100000;
            f[n + 1][j][0] = -100000;
            cin >> a[i][j];
            if (!a[i][j])
            {
                sx = i, sy = j;
            }
            f[i][j][0] = -100000;
        }
    }
    f[sx][sy][0] = 0;
    for (int k = 1; k <= 23; k ++ )
    {
        for (int i = 1; i <= n; i ++ )
        {
            for (int j = 1; j <= m; j ++ )
            {
                long long t = -100000000;
                for (int e = 0; e < 4; e ++ )
                {
                    int nx = i + fx[e];
                    int ny = j + fy[e];
                    if (!check_where(nx, ny))
                    {
                        continue;
                    }
                    t = max(t, f[nx][ny][k - 1]);
            
                }
                if (t <= -1 || a[i][j] == -1 || a[i][j] == 0)
                {
                    f[i][j][k] = -100000;
                    continue;
                }
                f[i][j][k] = t + a[i][j];
            }
        }
    }
    ll res = 0; 
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
        {
            res = max(res, f[i][j][23]);
        }
    }
    cout << res;
}

总结

认 真 读 题

1.2 我们的可可西里

题面&思路

题面

转眼到了2008年的6月9日,盼望已久的高考结束了。我们踏上了向西的旅程(本来是想写西去之路,可是考虑不太妥当)。可可西里,多么诱人的名词,充满了奇幻的色彩和自然的淳朴。从可可西里徒步走回家的决定是在1年半前定下的,而现在,终于可以实现那个钩过手指的预定。我们的可可西里。。。

在回家的路上,疯子和蚊子看到了许多可爱的藏羚羊,无意之中疯子和蚊子发现藏羚羊的居住地的分布也是有规律的,虽然疯子和蚊子早就听说藏羚羊是一种群体性很强又有超高IQ的动物,但是还是为它们的居住地分布规律感到惊叹。经过细心的观察,疯子和蚊子发现,如果假设一个藏羚羊群体有N只羊,就可以把它们的领地当做一个N*N的方阵,在这个方阵上第I列的第I 行都有一个圣地,它们不会居住在圣地,同时每行每列只能居住一只羚羊。于是他们很快算出一个有N只羊的藏羚羊群体的居住地分布方法数。

这是圣地的一种排列方法

思路

错排+高精。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>

using namespace std;

const int N = 2e3 + 5;

string f[N];

char c[10000], t[10000];
long long r[1000000];


string add(string a, string b)
{
    strcpy(c, a.c_str());
    strcpy(t, b.c_str());
    int lena = a.size(), lenb = b.size();
    for (int i = 0; i < lena; i ++ )
        c[i] -= '0';
    for (int i = 0; i < lenb; i ++ )
        t[i] -= '0';
    reverse(c, c + lena);
    reverse(t, t + lenb);
    int len = max(lena, lenb), jw = 0;
    for (int i = 0; i < len; i ++ )
    {
        r[i] = c[i] + t[i] + jw;
        jw = 0;
        if (r[i] >= 10)
        {
            r[i] -= 10;
            jw = 1;
        }
    }
    if (jw)
    {
        r[len] = 1;
        len ++;
    }
    string res = "";
    for (int i = len - 1; i >= 0; i -- )
    {
        res += char(r[i] + '0');
    }
    return res;
}

string mul(string a, string b)
{
    memset(r, 0, sizeof(r));
    strcpy(c, a.c_str());
    strcpy(t, b.c_str());
    int lena = a.size(), lenb = b.size();
    for (int i = 0; i < lena; i ++ )
        c[i] -= '0';
    for (int i = 0; i < lenb; i ++ )
        t[i] -= '0';
    reverse(c, c + lena);
    reverse(t, t + lenb);
    int len = max(lena, lenb), jw = 0;
    for (int i = 0; i < lena; i ++ )
    {
        for (int j = 0; j < lenb; j ++ )
        {
            r[i + j] += c[i] * t[j];
        }
    }
    for (int i = 0; i < lena + lenb; i ++ )
    {
        r[i] += jw;
        jw = r[i] / 10;
        r[i] %= 10;
    }
    if (jw)
    {
        r[lena + lenb] = jw;
    }
    lena ++;
    string res = "";
    bool flag = false;
    for (int i = lena + lenb - 1; i >= 0; i -- )
    {
        if (r[i] > 0)
            flag = true;
        if (flag == true)
            res += char(r[i] + '0');
    }
    return res;
}

string tostring(int x)
{
    string res = "";
    while (x >= 10)
    {
        res = char(x % 10 + '0') + res;
        x /= 10;
    }
    res = char(x % 10 + '0') + res;
    return res;
}

int main()
{
    int n;
    cin >> n;
    f[2] = "1";
    for (int i = 3; i <= n; i ++ )
    {
        f[i] = mul(tostring(i - 1), add(f[i - 1], f[i - 2]));
        //cout << tostring(i - 1) << "-" << add(f[i - 1], f[i - 2]) << endl;
        //cout << endl;
        //cout << f[i] << endl;
        //cout << endl;
        //cout << endl;
    }
    cout << f[n];
    return 0;
}
//dn=(n-1)*(dn-1 + dn-2)

总结

先写错排再写高精是好方法。

[heimu]这题高精太**难写了[/heimu]

[heimu]剩下两题摸了[/heimu]


2.L C A

2.1 P2937 [USACO09JAN]Laserphones S

[heimu]BFS好题[/heimu]

以上。

2.2 P3398 仓鼠找sugar

思路

我们可以假设若存在$a, b$与$c, d$路径相交。[heimu]不妨[/heimu]设$x=lca(a, b)$以及$y=lca(c, d)$。

那么因为$a, b$与$c, d$路径相交,则$x$在$c,d$上或$y$在$a,b$上。

好,我们再来设定$z$在$a,b$上,并且$z$与$c,d$相交。那么可以确认的就是$x,y$为$z$的祖先(不管多上面)

那么$x, y$的那个更深的那个,一定在另一个路径上。

那么问题就改成了给定一个点,确认这个点是否在另一条边上。(在此题中即判断$x是否在c,d边上,y是否在a,b边上。$)

判断方法为:

$$ dis_{x,a} +dis_{x,b}=dis_{a,b} \\dis_{a,b}=deep_a+deep_b-2*deep_{(lca(a,b))} $$

然后就可以解决这道题了awa

// Problem: P3398 仓鼠找sugar
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3398
// Memory Limit: 125 MB
// Time Limit: 1000 ms

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int N = 1e5 + 5;

int n, q;
vector<int> g[N];
int d[N], f[N][20];

void dfs(int x, int y)
{
    d[x] = d[y] + 1;
    f[x][0] = y;
    int len = g[x].size();
    for (int i = 0; i < len; i ++ )
    {
        if (g[x][i] != y)
        {
            dfs(g[x][i], x);
        }
    }
}

int lca(int x, int y)
{
    if (d[x] < d[y])
    {
        swap(x, y);
    }
    for (int i = 19; i >= 0; i -- )
    {
        if (d[f[x][i]] >= d[y])
        {
            x = f[x][i];
        }
    }
    if (x == y)
    {
        return x;
    }
    for (int i = 19; i >= 0; i -- )
    {
        if (f[x][i] != f[y][i])
        {
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}


int dis(int x, int y)
{
    return d[x] + d[y] - 2 * d[lca(x, y)];
}

int main()
{
    cin >> n >> q;
    for (int i = 1; i < n; i ++ )
    {
        int l, r;
        cin >> l >> r;
        g[l].push_back(r);
        g[r].push_back(l);
    }
    dfs(1, 0);
    for (int i = 1; i <= 19; i ++ )
        for (int j = 1; j <= n; j ++ )
            f[j][i] = f[f[j][i - 1]][i - 1];
    while (q --)
    {
        int ca, cb, cc, cd;
        cin >> ca >> cb >> cc >> cd;
        int x = lca(ca, cb);
        int y = lca(cc, cd);
        if (d[x] > d[y])
        { // x on c, d
            cout << ((dis(x, cc) + dis(x, cd) == dis(cc, cd)) ? 'Y' : 'N') << endl;
        }
        else
        { // y on a, b
            cout << ((dis(y, ca) + dis(y, cb) == dis(ca, cb)) ? 'Y' : 'N') << endl;
        }
    }
    return 0;
}
Last modification:July 22nd, 2021 at 04:56 pm
End.