20191114测试总结

CSP-S模拟总算有点CSP的样子了正解仍然十分不CSP-S

T1：WOJ4819

用dij跑一下宝藏之间两两的最小消费，然后10!枚举一下走到宝藏的顺序即可

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int n, k, t, lx, rx, r, g, b, sum, cnt, xt[15], yt[15], use[15], aa[505][505], head[505][505], vis[505][505];
long long ans = -0x7f7f7f7f7f7f7f7f, num, dis[505][505], w[15][15];
char s[505];
struct node
{
    int x;
    int y;
    long long dis;
    node(int aa, int bb, long long cc)
    {
        x = aa;
        y = bb;
        dis = cc;
    }
    bool operator<(const node &bb) const
    {
        return dis > bb.dis;
    }
};
priority_queue<node> q;
struct point
{
    int x;
    int y;
    int w;
    int nxt;
} a[2000005];
void ins(int x, int y, int xx, int yy, int w)
{
    ++sum;
    a[sum].x = xx;
    a[sum].y = yy;
    a[sum].w = w;
    a[sum].nxt = head[x][y];
    head[x][y] = sum;
    return;
}
void dijkstra(int x, int y)
{
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x7f, sizeof(dis));
    dis[x][y] = 0;
    q.push(node(x, y, 0));
    while (!q.empty())
    {
        node id = q.top();
        q.pop();
        int kx = id.x, ky = id.y;
        if (vis[kx][ky])
            continue;
        vis[kx][ky] = 1;
        int d = head[kx][ky];
        while (d)
        {
            int xx = a[d].x, yy = a[d].y;
            if (dis[a[d].x][a[d].y] > dis[kx][ky] + a[d].w)
            {
                dis[a[d].x][a[d].y] = dis[kx][ky] + a[d].w;
                q.push(node(a[d].x, a[d].y, dis[a[d].x][a[d].y]));
            }
            d = a[d].nxt;
        }
    }
    return;
}
void dfs(int id)
{
    if (cnt >= lx && cnt <= rx)
        ans = max(ans, num);
    if (cnt == rx)
        return;
    ++cnt;
    num += t;
    for (int i = 1; i <= k; ++i)
        if (!use[i])
        {
            use[i] = 1;
            num -= w[id][i];
            dfs(i);
            num += w[id][i];
            use[i] = 0;
        }
    num -= t;
    --cnt;
    return;
}
int main()
{
    scanf("%d%d%d%d%d%d%d%d", &n, &k, &t, &lx, &rx, &r, &g, &b);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%s", s + 1);
        for (int j = 1; j <= n; ++j)
            if (s[j] == 'S')
            {
                xt[0] = i;
                yt[0] = j;
            }
            else if (s[j] == 'T')
            {
                ++cnt;
                xt[cnt] = i;
                yt[cnt] = j;
            }
            else if (s[j] == 'R')
                aa[i][j] = r;
            else if (s[j] == 'G')
                aa[i][j] = g;
            else if (s[j] == 'B')
                aa[i][j] = b;
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
        {
            if (i != 1)
                ins(i, j, i - 1, j, aa[i - 1][j]);
            if (i != n)
                ins(i, j, i + 1, j, aa[i + 1][j]);
            if (j != 1)
                ins(i, j, i, j - 1, aa[i][j - 1]);
            if (j != n)
                ins(i, j, i, j + 1, aa[i][j + 1]);
        }
    for (int i = 0; i <= k; ++i)
    {
        dijkstra(xt[i], yt[i]);
        for (int j = 1; j <= k; ++j)
            w[i][j] = dis[xt[j]][yt[j]];
    }
    cnt = 0;
    dfs(0);
    printf("%lld", ans);
}

T2：WOJ4821

发现T2和T3数据放反了，然后刷新之后发现直接交换了T2、T3的题目名称？？？这是个什么神奇的操作。

对于一条链上，只要前缀gcd一刷新至少要小一半，因此总共只有log个不同的gcd的值，那么一个点到根节点的链上显然只有在gcd交接的log个位置可能产生最优解。我们对于每个叶节点dfs一次就可以找到所有的链，然后刷新答案即可。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstdlib>
using namespace std;
int n, sum, w[200005], num[200005], head[200005], dep[200005];
long long ans;
struct node
{
    int v;
    int nxt;
} a[400005];
struct point
{
    int id;
    int val;
    point(int aa, int bb)
    {
        id = aa;
        val = bb;
    }
};
vector<point> v[200005];
void ins(int u, int v)
{
    ++sum;
    a[sum].v = v;
    a[sum].nxt = head[u];
    head[u] = sum;
    return;
}
int gcd(int a, int b)
{
    if (!b)
        return a;
    return gcd(b, a % b);
}
void dfs(int k, int fa)
{
    v[k] = v[fa];
    v[k].push_back(point(k, w[k]));
    for (int i = 0; i < v[k].size(); ++i)
    {
        v[k][i] = point(v[k][i].id, gcd(v[k][i].val, w[k]));
        ans = max(ans, (long long)(dep[k] - dep[v[k][i].id] + 1) * v[k][i].val);
    }
    int j = 0;
    for (int i = 0; i < v[k].size(); ++i)
        if (v[k][i].val != v[k][i - 1].val)
            v[k][j++] = v[k][i];
    while (v[k].size() > j)
        v[k].pop_back();
    int d = head[k];
    while (d)
    {
        if (a[d].v != fa)
        {
            dep[a[d].v] = dep[k] + 1;
            dfs(a[d].v, k);
        }
        d = a[d].nxt;
    }
}
int main()
{
  	int size=40<<20;//40M
    //__asm__ ("movl  %0, %%esp\n"::"r"((char*)malloc(size)+size));//调试用这个 
    __asm__ ("movq %0,%%rsp\n"::"r"((char*)malloc(size)+size));//提交用这个 
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &w[i]);
    for (int i = 1; i < n; ++i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        ins(u, v);
        ins(v, u);
        ++num[u];
        ++num[v];
    }
    for (int i = 1; i <= n; ++i)
        if (num[i] == 1)
        {
            dep[i] = 0;
            dfs(i, 0);
        }
    printf("%lld", ans);
    exit(0);
}

T3：WOJ4820

又是毒瘤计数题。。。反正慢慢推总能推出来的

dp[i][j]表示从左往右选到第i个数，这i个数在形成安排的序列中形成了j个连通块

然后推导就如代码所示了

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mod 1000000007
using namespace std;
int n, s, e, ans, dp[2005][2005];
char S[2005];
int main()
{
    char ch = getchar();
    while (ch < 'A' || ch > 'Z')
        ch = getchar();
    while (ch >= 'A' && ch <= 'Z')
    {
        S[++n] = ch;
        ch = getchar();
    }
    scanf("%d%d", &s, &e);
    dp[0][0] = 1;
    for (int i = 0; i <= n - 2; ++i)
        for (int j = (i > 0); j <= i; ++j)
        {
            if (dp[i][j] == 0)
                continue;
            char k = S[i + 1];
            long long val = dp[i][j];
            int free = j;
            if (i >= s)
                free--;
            if (i >= e)
                free--;
            if (free < 0)
                continue;
            if (i + 1 == s)
            {
                if (k == 'R' || k == 'B')
                    dp[i + 1][j + 1] = (dp[i + 1][j + 1] + val) % mod;
                if (k == 'L' || k == 'B')
                    dp[i + 1][j] = (dp[i + 1][j] + val * free) % mod;
            }
            else if (i + 1 == e)
            {
                dp[i + 1][j + 1] = (dp[i + 1][j + 1] + val) % mod;
                dp[i + 1][j] = (dp[i + 1][j] + val * free) % mod;
            }
            else
            {
                if (k == 'R' || k == 'B')
                    dp[i + 1][j + 1] = (dp[i + 1][j + 1] + val) % mod;
                if (i + 1 > s && (k == 'R' || k == 'B'))
                    dp[i + 1][j] = (dp[i + 1][j] + val) % mod;
                if (i + 1 > s && (k == 'L' || k == 'B') && j)
                    dp[i + 1][j - 1] = (dp[i + 1][j - 1] + val * free) % mod;
                if (i + 1 > e && (k == 'L' || k == 'B'))
                    dp[i + 1][j] = (dp[i + 1][j] + val) % mod;
                if (i + 1 > e && (k == 'L' || k == 'B') && j)
                    dp[i + 1][j - 1] = (dp[i + 1][j - 1] + val * free) % mod;
                if (k == 'L' || k == 'B')
                    dp[i + 1][j] = (dp[i + 1][j] + val * free) % mod;
                if (k == 'R' || k == 'B')
                    dp[i + 1][j] = (dp[i + 1][j] + val * free) % mod;
                if (free >= 2 && (k == 'L' || k == 'B'))
                    dp[i + 1][j - 1] = (dp[i + 1][j - 1] + free * (free - 1) % mod * val) % mod;
            }
        }
    if (n == s)
    {
        if (S[n] == 'L' || S[n] == 'B')
            ans = dp[n - 1][1];
    }
    else if (n == e)
        ans = dp[n - 1][1];
    else if (S[n] == 'L' || S[n] == 'B')
        ans = dp[n - 1][2];
    printf("%d", ans);
    return 0;
}