有些题是不需要高级算法的

扯淡的 题解(和题目大意)

T1

    近日,CWTV网络电视公司为了提高收视率,举办了一场CWTV拳击擂台赛。一共有n名选手参赛,分别为A1,A2……An。拳击赛的举办者对每名参赛选手的实力作了详尽的分析,发现若Ai能击败Aj,则一定有Ai>Aj。
    现在举办者需要制定一个出场次序,第一个出场的作为第一任擂主,然后其他选手依次出场向擂主挑战,凡是挑战者战胜了擂主,那么这个挑战者就顶替原擂主的位置成为新的擂主。由于举办者希望比赛尽量的精彩,他希望在整个擂台赛中一共更换k次擂主。请你帮助他算出满足他的要求的出场次序的个数。
    例如:出场顺序14253说明了擂主依次是1,4,5,这符合n=5和k=2。

第二类斯特林数…GG
还得写高精…GG GG

T2

给出n(n <= 100)个矩形(坐标范围 < 1000), 问将平面分成了几个部分

显然离散化乱搞
把坐标离散化后在bool矩阵中暴力修改矩形的边, 最后floodfill求部分, 别忘了最外面的也是一部分

T3

给一个四位素数, 每次只能修改四位数的一位, 且每次修改后这个数也要是素数, 求把这个素数变成另一个给定素数需要的最小步数

打表
最短路 || 搜索

T4

给定一个带点权的无向图, 从中挑出最多的节点, 让这些节点两两不**直接**相连, 如果有多种方案, 输出点权最大的

搜索 && 剪枝

总结

考得都不是很高级的算法…但是我就是不会…
T1 想到另一个题上去了(忽略了如果打不过擂主擂主是不会变的)…推出了方程沾沾自喜然后发现…诶样例不对啊…这时候大概心态就有点崩了…

T2 肛T1花了1.5h+吧(太菜了)…然后T2就没有时间了…

T3 简单的最短路居然没有看出来TUT觉得这几天出的迭代加深就应该是个迭代加深…然后就写了半天…说好的图论是强项呢???!!! GG…

T4 Dev和我的心头一起崩了…迭代加深是没毛病…然后剪枝剪残了…然后搜索的方向也反了…GG

总之…非常失败…感觉状态还是太差…一天三节课感觉并无卯月…醒醒啊!陈严宽! 说好的叉院呢!!! 老师家长你对得起谁啊!!! 最近要练一下DP了…还有搜索…代码能力题也要写一下了…打好基础才是关键是不是…最近是不是又㕛叒叕太急于求成了…还有Blog已经花了太多时间了…Emmmm…颓废什么的还是要废止啊…Emmmmm

沙茶的 代码

T1

要压维要不然会爆空间…
f[i][j]代表在长度为i, 换了j个擂主的方案数

f[i][j] += (i - 1) * f[i - 1][j] //可以倒着推, 假设f[i - 1][j]里的序列是 2 ~ i, 那么f[i][j]就相当于插入一个1, 而1插入到哪里(除了开头)都不会对换擂主次数产生影响(因为谁都打不过, 像我TUT)
if (j > 0)
    f[i][j] += f[i - 1][j - 1] //向上面一样倒着推, 这就是1插入到开头的情况, 因为在f[i - 1][j]代表的序列中谁都能打败1, 所以换擂次数会 + 1, 所以是从f[][j - 1]转移
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <stack>
#define MAXN (500 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define BI (100000000)
#define INF (0x7ffffff)
#define LL gjd
//#define LL __int128
using namespace std;
struct gjd
{
    int len;
    long long a[MAXN];
    void init(int x)
    {
        memset(a, 0, sizeof(a));
        if (!x)
        {
            len = 1;
            a[len] = x;
        }
        while (x)
        {
            a[++len] = x % 10;
            x /= 10;
        }
    }
    void zl()
    {
        while (!a[len] && len > 0)
        {
            --len;
        }
        if (len <= 0)
            len = 1;
    }
    void print()
    {
        zl();
        printf("%lld", a[len]);
        for (int i = len - 1; i >= 1; i--)
        {
            printf("%08lld", a[i]);
        }
    }
};
int n;
int m;
LL f[2][MAXN];
void init();
void print(LL);
gjd jia(gjd&, gjd&);
void che(gjd&, gjd&, int);
int main()
{
    freopen("c.in", "r", stdin);
    freopen("c.out", "w", stdout);
    scanf("%d%d", &n, &m);
    init();
    f[n % 2][m].print();
    return 0;
}
void init()
{
    f[0][1].init(1);
    f[0][0].init(1);
    for (int i = 3; i <= n; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            che(f[i % 2][j], f[(i - 1) % 2][j], i - 1);
            if (j > 0)
                f[i % 2][j] = jia(f[(i - 1) % 2][j - 1], f[i % 2][j]);
//                f[i][j] = f[i - 1][j - 1] + (i - 1) * f[i - 1][j];
//                f[i][j] = (i - 1) * f[i - 1][j];
//            cout << f[i][j] << "\t";
//            f[i][j].print();
//            cout << "\t";
        }
//        cout << endl;
    }
}
gjd jia(gjd& js, gjd& jsh)
{
    gjd re;
    re.init(0);
    re.len = max(js.len, jsh.len);
    js.zl(), jsh.zl();
    int jw = 0;
    for (int i = 1; i <= max(js.len, jsh.len); i++)
    {
        re.a[i] = js.a[i] + jsh.a[i] + jw;
        jw = re.a[i] / BI;
        re.a[i] %= BI;
    }
    while (jw)
        re.a[++re.len] = jw % BI, jw /= BI;
    re.zl();
    return re;
}
void che(gjd& re, gjd& ch, int x)
{
    re.init(0);
    ch.zl();
    re.len = ch.len;
    int jw = 0;
    for (int i = 1; i <= ch.len; i++)
    {
        re.a[i] = ch.a[i] * x + jw;
        jw = re.a[i] / BI;
        re.a[i] %= BI;
    }
    while (jw)
        re.a[++re.len] = jw % BI, jw /= BI;
    re.zl();
}

/*
20922789888000
8683317618811886495518194401280000000
*/

T2

cena爆栈…Emmmmm…

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define OSTACK {int size = 50 << 20; char *p = (char*)malloc(size) + size; __asm__("movl %0, %%esp\n" :: "r"(p));}
#define MAXN (100 + 5)
#define MAXL (400 + 5)
#define bhs(a) (a)
#define bhx(a) ((a) + n)
const int xy[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
using namespace std;
struct node
{
    int x, y;
    bool isx;
    int belong;
    node() {}
    node(int a, int b): x(a), y(b) {}
} b[MAXN << 2];

int n;
int ans;
int cnts = 0;
bool a[MAXL][MAXL];
void init();
void solve();
void dfs(int, int);
bool cmp1(node, node);
bool cmp2(node, node);
void print(int, int, int, int);
void dqprint();
int main()
{
    freopen("rectangle.in", "r", stdin);
    freopen("rectangle.out", "w", stdout);
    scanf("%d", &n);
    int srx, sry, srxx, sryy;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d%d%d", &srx, &sry, &srxx, &sryy); // x1, y1 && x2, y2
        /*
                         s: (x2, y2)
        --------------------
        |                  |
        |                  |
        |                  |
        |                  |
        --------------------
        x: (x1, y1)
        */
        b[bhs(i)].belong = b[bhx(i)].belong = i;
        b[bhs(i)].x = srxx, b[bhs(i)].y = sryy;
        b[bhx(i)].x = srx, b[bhx(i)].y = sry;
    }
    init();
    OSTACK;
    solve();
    printf("%d", ans);
    return 0;
}
void init()
{
    memset(a, false, sizeof(a));
    int gz = 0;
    int last = -1;
    sort(b + 1, b + (n << 1) + 1, cmp1);
    for (int i = 1; i <= (n << 1); i++)
    {
        if (b[i].x != last)
            ++gz;
        last = b[i].x;
        b[i].x = gz << 1;
    }
    sort(b + 1, b + (n << 1) + 1, cmp2);
    gz = 0;
    last = -1;
    for (int i = 1; i <= (n << 1); i++)
    {
        if (b[i].y != last)
            ++gz;
        last = b[i].y;
        b[i].y = gz << 1;
    }
    for (int i = 1; i <= (n << 1); i++)
    {
        for (int j = i + 1; j <= (n << 1); j++)
        {
            if (b[i].belong == b[j].belong)
            {
                print(min(b[i].x, b[j].x), min(b[i].y, b[j].y), max(b[j].x, b[i].x), max(b[j].y, b[i].y));
//                printf("\n%d: -----------------------------------\n", b[i].belong);
//                dqprint();
            }

        }
    }
//    dqprint(); 

}
bool cmp1(node x, node y)
{
    return x.x < y.x;
}
bool cmp2(node x, node y)
{
    return x.y < y.y;
}
/*
      (x1, y2)             s: (x2, y2)
        --------------------
        |                  |
        |                  |
        |                  |
        |                  |
        --------------------
       x: (x1, y1)        (x2, y1)
*/
void print(int x, int y, int xx, int yy)
{
    for (int i = x; i <= xx; i++)
    {
        a[i][yy] = true;
        a[i][y] = true;
    }
    for (int i = y; i <= yy; i++)
    {
        a[x][i] = true;
        a[xx][i] = true;
    }
}
void solve()
{
    for (int i = 1; i <= (n << 3); i++)
    {
        for (int j = 1; j <= (n << 3); j++)
        {
            if (!a[i][j])
            {
                ++ans;
                dfs(i, j);
            }
        }
    }
}
void dfs(int dqx, int dqy)
{
//    printf("%d %d: %d\n", dqx, dqy, ++cnts);
    a[dqx][dqy] = true;
    for (int i = 0; i < 4; i++)
    {
        int nx = dqx + xy[i][0], ny = dqy + xy[i][1];
        if (nx < 1 || nx > (n << 3) || ny < 1 || ny > (n << 3) || a[nx][ny])
            continue;
        dfs(nx, ny);
    }
}
void dqprint()
{
    for (int i = 1; i <= (n << 2); i++)
    {
        for (int j = 1; j <= (n << 2); j++)
        {
            if (a[i][j])
            {
                printf("■");
            }
            else
            {
                printf("  ");
            }
        }
        puts("");
    }
}

/*
3
10 20 50 30
40 10 50 25
40 25 80 30
*/

T3 Loli: 哈! 没想到吧! T3才是最水的~

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN (10000)
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
using namespace std;
int s, t;
int ans;
bool ok = false;
bool vis[MAXN];
bool v[MAXN];
void shai();
void solve();
void dfs(int, int);
int cmp(int, int);
int change(int, int, int);
int mpow(int, int);
int main()
{
//    std::cout << "Hello, World!" << std::endl;
    freopen("prime.in", "r", stdin);
    freopen("prime.out", "w", stdout);
    scanf("%d%d", &s, &t);
    shai();
    solve();
    printf("%d", ans);
    return 0;
}
void shai()
{
    memset(vis, true, sizeof(vis));
    for (int i = 2; i < MAXN; i++)
    {
        for (int j = 2; i * j < MAXN; j++)
        {
            vis[i * j] = false;
        }
    }
}
void solve()
{
    for (ans = 0; (!ok); ans++)
    {
        memset(v, false, sizeof(v));
        v[s] = true;
        dfs(s, 0);
    }
    ans--;
}
void dfs(int dq, int de)
{
    if (dq == t)
    {
        ok = true;
        return ;
    }
    if (de >= ans)
        return ;
    if (de + cmp(dq, t) > ans)
        return ;
    for (int i = 1; i <= 4; i++)
    {
        for (int j = 0; j <= 9; j++)
        {
            if (i == 1 && (!j))
                continue;
            int to = change(dq, i, j);
            if (!v[to] && vis[to])
            {
                v[to] = true;
                dfs(to, de + 1);
                v[to] = false;
            }
            if (ok)
            {
                // printf("%d\n", dq);
                return ;
            }
        }
    }
}
int cmp(int x, int y)
{
    int re = 0;
    while (x)
    {
        if (x % 10 != y % 10)
            re++;
        x /= 10, y /= 10;
    }
    return re;
}
int change(int x, int wz, int y)
{
    int tw = mpow(10, 4 - wz), re = x % tw + y * tw + x / (10 * tw) * (10 * tw);
    return re;
}
int mpow(int x, int y)
{
    int re = 1;
    for (int i = 1; i <= y; i++)
    {
        re *= x;
    }
    return re;
}

/*
1033 8179
*/

T4

搜索是从0开始搜索往上面加点比较方便剪枝
选下一步要选的节点时按照编号顺序枚举
这样就可以记录当前选的节点中编号最大的, 而在之后的枚举中比这个编号小的节点都不会被选上(之前节点少都选不上现在又添了一些节点更选不上了), 就可以达到剪枝的目的…详情见注释…%%%马浩然
癌…搜索还是菜啊…

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN (30 + 5)
#define INF (1073741825)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define MAXM (1000 + 5)
#define pii pair<int, int>
const int s = 0;
using namespace std;
struct edg
{
    int from;
    int to;
    int next;
} b[MAXN * MAXN << 1];
int gb[MAXN];
int cntb;

int cnt = 0;
bool ok = true;
int n;
int mon;
int minc = INF, maxc = 0;
int cost[MAXN];
bool vis[MAXN];
pii att[MAXN * MAXN];
bool g[MAXN][MAXN];
int ans, ansd, del, totc;
int attn;
void solve();
void dfs(int, int, int);
void dfs1(int, int, int);
void adn(int, int);
int ws(int);
int main()
{
    freopen("fish.in", "r", stdin);
    freopen("fish.out", "w", stdout);
    scanf("%d%d", &mon, &n);
    int srx, sry;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &srx, &sry);
        minc = min(minc, sry);
        maxc = max(maxc, sry);
        cost[srx] = sry;
        cost[0] += sry;
    }
    memset(g, false, sizeof(g));
    while (1)
    {
        scanf("%d%d", &srx, &sry);
        if ((!srx) && (!sry))
            break;
        if (!g[srx][sry])
        {
            att[++attn] = make_pair((1 << srx), (1 << sry));
            adn(srx, sry);
            adn(sry, srx);
            g[srx][sry] = g[sry][srx] = true;
        }
    }
    solve();
    /*int pn = 0, pc = 0;
    for (int i = 1; i <= n; i++)
    {
        if (ans & (1 << i))
        {
            pn++;
            pc += cost[i];
        }
    }
    printf("%d %d\n", pn, pc);*/
    printf("%d %d\n", del, totc);
    for (int i = 1; i <= n; i++)
    {
        if (ans & (1 << i))
        {
            printf("%d\n", i);
        }
    }
    return 0;
}
void adn(int from, int to)
{
    b[++cntb].from = from;
    b[cntb].to = to;
    b[cntb].next = gb[from];
    gb[from] = cntb;
}
void solve()
{
    for (del = 0; (ok) && del <= n; )
    {
        ok = false;
        dfs1(s, 0, 0);
        del++;
    }
    del -= 2;
    if (del < 0)
        del = 0;
}
void dfs1(int dq, int de, int dqc)
{
//    printf("%d\n", ++cnt);
    if (dqc > mon)
        return ;
    if (de == del)
    {
        if (de != ansd)
        {
            totc = dqc;
            ans = dq;
            ansd = de;
        }
        else if (dqc > totc)
        {
            ans = dq;
            totc = dqc;
        }
        ok = true;
        return ;
    }
    if (dqc + (del - de) * minc > mon) // 剪枝
        return ;
    int last = ws(dq); // 计算当前已经选的节点集合中最大的编号
    if (n - last < del - de)
        return ;
    for (int i = last + 1; i <= n; i++) // 从最大的编号开始枚举下一步要选的节点, 而不是从1到n枚举
    {
        if (!(dq & (1 << i)))
        {
            bool dqok = false;
            for (int j = gb[i]; j; j = b[j].next)
            {
                if (dq & (1 << b[j].to))
                {
                    dqok = true;
                    break;
                }
            }
            if (!dqok)
            {
                dfs1(dq | (1 << i), de + 1, dqc + cost[i]);
            /*    if (ok)
                    return ;*/
            }
        }
    }
}
int ws(int x)
{
    for (int i = n; i >= 1; i--)
    {
        if (x & (1 << i))
        {
            return i;
        }
    }
    return 0;
}

/*
170 7
1 70
2 50
3 30
4 40
5 40
6 30
7 20
1 4
1 7
3 4
3 5
5 7
6 7
0 0
*/