SXKDZ

Author: SXKDZ

  • 冲刺NOIp2011模拟题（二）

    一、数列（sequence.pas/c/cpp, 1s,128M）

    【问题描述】
    一个数列定义如下：f(1)=1，f(2)=1，f(n)=(A*f(n-1)+B*f(n-2))%7。给定A, B和n的值，要求计算f(n)的值。
    【输入格式】
    输入文件sequence.in仅一行，包含3个整数A, B和n，其中（1<=A, B<=1000，1<=n<=100,000,000）。
    【输出格式】
    输出文件sequence.out仅一行，一个整数，即f(n)的值。
    【输入样例1】
    1 1 3
    【输出样例1】
    2
    【输入样例2】
    1 2 10
    【输出样例2】
    5
    【数据规模】
    20%的数据：n<=1000；
    40%的数据：n<=100,000；
    100%的数据：n<=100,000,000；
     
    二、最长路（path.pas/c/cpp, 1s,128M）
    【问题描述】
    设G为有n个顶点的有向无环图，G中各顶点的编号为1到n，且当<i,j>为G的一条边时有i<j。设w(i,j)为边<i,j>的长度，请设计算法，计算图G中<1,n>间的最长路径。
    【输入格式】
    输入文件path.in的第一行有两个整数n和m，表示有n个顶点和m条边，其中2<=n<=1500，m<=50000；接下来m行中每行输入3个整数a, b, v表示从a点到b点有条边，边的长度为v。
    【输出格式】
    输出文件path.out，一个整数，即1到n之间的最长路径。如果1到n之间没连通，输出-1。
    【输入样例1】
    2 1
    1 2 1
    【输出样例1】
    1
    【输入样例2】
    2 0
    【输出样例2】
    -1
    【数据规模】
    20%的数据：n<=100, m<=1000；
    40%的数据：n<=1000, m<=10000；
    100%的数据：n<=1500, m<=50000；
     
    3．木棍（wooden.cpp/pas/c, 1s,128M）
    【问题描述】
    有n根木棍，每根的长度L和重量W已知。这些木棍将被一台机器一根一根地加工。机器需要一些启动时间来做准备工作，启时间与木棍被加工的具体情况有关。启动时间遵循以下规则：
    1．  加工第一根木棍的启动时间为1分钟。
    2．  加工完长度为L[i]，重量为W[i]的木棍后，紧跟着加工长度为L[i+1]，重量为W[i+1]的木棍，若L[i]<=L[i+1]且W[i]<=W[i+1]，则加工木棍i+1时，不需要启动时间。例如：有5根木棍，它们的长度和重量为(9,4),(2,5),(1,2),(5,3),(4,1)，则最小启动时间为2分钟（加工序列为(4,1),(5,3),(9,4),(1,2),(2,5)）。
    【输入格式】
    输入文件wooden.in的第一行是一个整数n（1<=n<=5000）,表示木棍的数量。第二行2*n个整数，L1,W1,L2,W2,……,Ln,Wn（1<=Li,Wi<=10000），为各木棍的长度和重量，这2*n个整数以若干个空格分隔。
    【输出格式】
    输出文件wooden.out仅一行一个整数，即最小总启动时间。
    【样例输入1】
    5
    4 9 5 2 2 1 3 5 1 4
    【样例输出1】
    2
    【样例输入2】
    3
    2 2 1 1 2 2
    【样例输出2】
    1
     
    四、括号匹配（bracket.pas/c/cpp, 1s,128M）
    【问题描述】
    定义如下括号匹配序列：
    1．  空序列是匹配序列；
    2．  如果S是匹配序列，那么(S),[S],{S}和<S>也是匹配序列；
    3．  如果A和B都是匹配序列，那么AB也是匹配序列。
    例如，下面的字符串都是匹配序列：
    ()，[]，(())，([])，()[]，/em>()[()]，{{}}<>，([]<>{{}})，<<{}>>

    而以下几个则不是：

    (，[，]，)(，())，([()，<<，{(})，<{}>)
    序列中可能包含通配符，含义如下：
    /表示任意1个左括号
    #表示任意2个左括号
    @表示任意4个左括号
    ?表示任意8个左括号
    \表示任意1个右括号
    *表示任意2个右括号
    &表示任意4个右括号
    !表示任意8个右括号
    现在，给你一些由“(”、“)”、“[”、 “]”、 “{”、“}”、“<”、“>”和通配符构成的序列。你要做的是判断该序列是否为匹配序列。
    【输入格式】
    第一行：一个正整数N，表示测试数据组数；
    接下来N行：每行一个括号序列(长度不超过L)。
    【输出格式】
    共N行：对于每一个括号序列，判断其是否匹配。
    对于不匹配的序列，直接输出FALSE。
    对于匹配的序列，输出用单一空格隔开的3个信息：
    第一个信息为TRUE；
    第二个信息为括号的最大深度(层数)；
    第三个信息为达到最大深度的次数。
    【样例输入】
    3
    {()}@<>{})))>
    ([})
    ?\\\\\\\]
    【样例输出】
    TRUE 5 2
    FALSE
    TRUE 8 1
    【样例解释】
    对于第一组数据，@相当于<(((，是匹配的，括号的最大深度为5，该深度出现了2次。
    对于第二组数据，[和}不匹配。
    第三组数据想要说明的是通配符间可以匹配。
    【数据规模】
    对于20%的数据：N=1，0<L<=20；
    对于60%的数据：0<N<=5，0<L<=2E+3；
    对于100%的数据：0<N<=10，0<L<=2E+6；

    对于40%的数据：序列中没有通配符。

     

  • SXKDZ Compare 1.0发布

    SXKDZ Compare是SXKDZ实验室开发的一款用于信息学奥赛对拍的小软件。

    特色功能：

    • 使用标准输入输出进行读写，能智能判断选手程序是否超时和运行时错误
    • 能重复运行指定次数的对拍
    • 使用C++ Builder 2010开发，轻巧方便，绿色无污染

    版本：1.0.0.0 Build 14
    欢迎下载使用。下载链接：SXKDZ Compare

     

  • [动态规划练习题]潜水

    【问题描述】
    潜水员用特殊的装备潜水，需要两个容器的钢瓶：一个装氧气，另一个装氮气。根据潜水员要待在水下的时间和所潜的深度，他需要不同量的氧气和氮气。提供给潜水员一定数量的钢瓶，每个钢瓶由它的重量和它所容纳的气体的体积描述。为了完成任务，潜水员需要特定量的氧气和氮气，需要求他完成任务所需的钢瓶的最少重量是多少？
    例如，潜水员能够使用的5个钢瓶描述如下，每个描述包含：氧气的体积，氮气的体积（每个值都是以升为单位）和钢瓶的重量。
    3 36 120
    10 25 129
    5 50 250
    1 45 130
    4 20 119
    如果潜水员需要5升氧气和60升氮气，那么他必须带两个总重量为249的钢瓶（例子中的第1与第2或者第4与第5）。

    【任务】
    读入潜水员的氧气和氮气的需求量，提供的钢瓶的数目及它们的描述；
    计算潜水员完成任务所需要的钢瓶最少重量；
    注：提供的钢瓶总能够完成给定的任务。 
       
    【输入格式】
    第一行有两个整数T，A，它们由空格隔开，1≤T≤100，1≤A≤100，它们分别表示氧气的体积和氮气的体积，这些是完成任务需要的。第二行有一个整数N，1≤N≤1000，表示提供钢瓶的总数量，接下来的N行是对每个钢瓶的描述，第I+2行包含3个整数，TI，AI，WI，它们由空格隔开，其中1≤TI≤100，1≤AI≤100，1≤WI≤800；它们分别表示第I个钢瓶内氧气的体积、氮气的体积以及该钢瓶的重量，1≤I≤N。  

    【输出格式】
    输出只有一个整数，就是潜水员完成任务所需钢瓶的最少总重量。 

    【样例输入】
    5 60
    5
    3 36 120
    10 25 129
    5 50 250
    1 45 130
    4 20 119

    【样例输出】
    249

    【时间限制】
    每个测试点1s。

    【解析】

    • 状态：f[j][k]表示氧气为j，氮气为k时的钢瓶最小重量
    • 状态转移方程：f[j+t[i]][k+a[i]] = min(f[j+t[i]][k+a[i]], f[j][k]+c[i])
    • 答案：f[T][A]
    • 时间复杂度：O(N*T*A)

    [cpp]#include <cstdio>
    int T, A, N, f[200][200], t[1020], a[1020], v[1020];
    int main(void)
    {
        scanf(“%d%d%d”, &T, &A, &N);
        for (int i=1; i<=N; ++i)
            scanf(“%d%d%d”, &t[i], &a[i], &v[i]);
        for (int i=0; i<=T; ++i)
            for (int j=0; j<=A; ++j)
                f[i][j]=10000000;
        f[0][0]=0;
        for (int i=1; i<=N; ++i)
            for (int j=T; j>=0; –j)
                for (int k=A; k>=0; –k)
                {
                    int o1, o2;
                    if (t[i]+j > T)
                        o1=T;
                    else
                        o1=t[i]+j;
                    if (a[i]+k > A)
                        o2=A;
                    else
                        o2=a[i]+k;
                    if (f[o1][o2]>f[j][k]+v[i])
                        f[o1][o2]=f[j][k]+v[i];
                }
        printf(“%d\n”, f[T][A]);

        return 0;
    }

    [/cpp]

  • 冲刺NOIp2011模拟题 （一）题解

    题目在这里。

    一、报数

    【解析】模拟

    此题为字符串处理，没有什么技巧，完全考基本功，得分容易，拿满分一定要仔细，只要细心地考虑每一种情况，就可以AC。

    二、跑步

    【解析】关键点

    可以依次枚举除了1点和N点外的每个点（设当前枚举点为i），然后从1点开始DFS，看能不能不经过i点就遍历到N点。如果不能，那i就是关键点。时间复杂度为O（n^2）。

    三、装备运输

    【解析】动态规划0-1背包

    本题为加了一个限制条件的0-1背包，但是解法与传统的0-1背包完全一样。

    • 状态：f[i][j][k]表示前i件物品，火车的体积为j、重量为k时的最大火力值；
    • 状态转移方程：f[i][j][k] = max(f[i-1][j-V[i]][k-G[i]]+T[i], f[i][j][k])
    • 目标状态：f[n][v][g]
    • 时间复杂度：O(n*v*g)

    由于前i件物品只与i-1件物品有关，于是可以降为二维。

    【参考代码】
    [cpp]

    #include <cstdio>
    FILE *fin, *fout;
    int V, G, n, max=0;
    int f[401][401], t[401], v[401], g[401];
    int main(void)
    {
        fin = fopen(“transport.in”, “r”);
        fout = fopen(“transport.out”, “w”);

        fscanf(fin, “%d%d%d”, &V, &G, &n);
        for (int i=1; i<=n; ++i)
            fscanf(fin, “%d%d%d”, &t[i], &v[i], &g[i]);
        for (int i=1; i<=n; ++i)
            for (int j=V; j>=v[i]; –j)
                for (int k=G; k>=g[i]; –k)
                    if (f[j][k]<f[j-v[i]][k-g[i]]+t[i])
                        f[j][k]=f[j-v[i]][k-g[i]]+t[i];

        fprintf(fout, “%d\n”, f[V][G]);

        return 0;
    }[/cpp]

    【练习题】潜水

    四、翻转游戏

    【解析】位运算，广度优先搜索（BFS）

    例：

    bwbw
    wwww
    bbwb
    bwwb

    按输入顺序（从0到15），我们把这个状态转换为

    数组num[i]的值为2^i（i=0,1…15），对于输入过程中的每一个“b”，我们通过按位或运算，可以把上面的二进制表示的状态1001101100000101，转换成10进制状态39685。对每一个状态，我们可依次选择第0到第15个位置进行翻转尝试。对位置i可以通过i/4取得它在棋盘中所在的行号，可以通过i%4取得它在棋盘中所在的列号。然后再通过循环改变它相邻位置物件，此处通过异或运算求出选择在该位置翻转时得到的状态，判断这个状态是不是出现过，没出现过就入队，做相应的标记。直到出现目标状态即可退出搜索，或者队列为空时无解。此题中用到了按位或运算（|）、按位异或运算（^）及左移运算（<<）。

    【参考代码】

    [cpp]
    #include <cstdio>
    const int flip[]= {51200, 58368, 29184, 12544, 35968, 20032, 10016,
    4880, 2248, 1252, 626, 305, 140, 78, 39, 19};
    int map[70000], step[70000], h=0, t=1;
    bool hash[70000];
    int main(void)
    {
        for (int i=1; i<=4; ++i, getchar())
        {
            char t[4];
            scanf(“%s”, t);
            for (int j=0; j<4; ++j)
            {
                map[1]<<=1;
                if (t[j]==’b’)
                    ++map[1];
            }
        }
        hash[map[1]]=true;
        if (map[1]==0 || map[1]==(1<<16)-1)
        {
            printf(“0\n”);
            return 0;
        }
        while (h<t)
        {
            ++h;
            for (int i=0; i<=15; ++i)
            {
                int des = map[h]^flip[i];
                if (hash[des])
                    continue;
                else
                    hash[des]=true, map[++t]=des, step[t]=step[h]+1;
                if (des==0 || des==(1<<16)-1)
                {
                    printf(“%d\n”, step[t]);
                    return 0;
                }
            }
        }
        printf(“Impossible\n”);
        return 0;
    }[/cpp]

    【转载请注明本文出处，谢谢】

  • 冲刺NOIp2011模拟题（一）

    一、报数

    【题目描述】
    CG同学又弄到一批新牛，新牛到了农场后，首先学习汉语，数的朗读成为新牛的难题。朗读绝对值小于10亿的数。
    新牛们知道汉语中有如下的朗读规则：
    1、首先读符号位，然后读整数部分。整数部分之后可能出现小数点，如果有小数部分则小数点一定出现，并且读出小数点之后读小数部分。
    2、符号位的读法是：
    （1）正数，不论正号“+”是否出现，都不必读出符号位；
    （2）负数最左边的符号是“-”读成“负”（以“F”来表示“负”）。
    3、整数部分的读法是：
    （1）如果整数部分不存在或整数部分全为零则直接读成“零”（以“0”来表示“零”）；
    （2）否则从整数部分中最左边的非零数字开始读起，然后以十，百，千，万，亿（分别以“S”,“B”,“Q”“W”,“Y”来表示）等数量单位来拼读整数部分。
    4、整数部分中：
    （1）每一个非零数字都必须结合各个相应的数量单位读出来。
    （2）每一段连续的“零”只能读成一个“零”，但是某一段连续的“零”的左侧或者右侧不存在非零数字（这里只考虑整数部分）则这一段“零”不应该读出来。
    5、如果有小数部分，则首先读“点”（以“D”来表示“点”），然后从左至右有顺序的读出各个小数位。在读小数部分的时候不可以使用十，百，千，万，亿等数量单位；但是小数部分的每一个数字都要读出来，连续的零不可以读成一个零，而应该分别读出。
    6、如果数中有小数点而没有小数部分，则不应该把小数点读出来。
    例如：
    -0020030004.567应该读成“F2Q03W04D567”，000.89应该读成“0D89”。
    请你编写程序帮助新牛把给定的数正确地读出来。

    【输入数据】
    输入文件仅一行，存放了一个数（不超过50个字符），其绝对值小于10亿。
    【输出数据】
    输出文件仅一行，输出这个数的正确读法。

    【样例输入】
    -0020030004.567
    【样例输出】
    F2Q03W04D567

    二、跑步

    【题目描述】
    新牛到部队，CG要求它们每天早上搞晨跑，从A农场跑到B农场。从A农场到B农场中有n-2个路口，分别标上号，A农场为1号，B农场为n号，路口分别为2…n-1号，从A 农场到B农场有很多条路径可以到达，而CG发现有的路口是必须经过的，即每条路径都经过的路口，CG要把它们记录下来，这样CG就可以先到那个路口，观察新牛们有没有偷懒，而你的任务就是找出所有必经路口。

    【输入数据】
    第一行两个用空格隔开的整数n（3≤n≤2000）和e（1≤e≤8000）。
    接下来从第2到第e+1行，每行两个用空格隔开的整数p和q，表示路口p和q之间有路径直达。
    输入数据保证必经路口一定存在，并且每个路口都和A农场、B农场相连通。
    【输出数据】
    第一行一个整数m，表示必经路口的数目。
    第二行按从小到大的顺序依次输出每个必经路口的编号，每两个数之间用一个空格隔开。
    注意：不包括起点和终点。

    【样例输入】
    6 6
    1 2
    2 4
    2 3
    3 5
    4 5
    5 6
    【样例输出】
    2
    2 5

    三、装备运输

    【题目描述】德国放松对英国的进攻后，把矛头指向了东边――苏联。
    1943年初，东线的战斗进行到白热化阶段。据可靠情报，90余万德国军队在库尔斯克准备发动浩大攻势。因此，朱可夫元帅要求你立即从远东的军工厂运输大量装备支援库尔斯克前线。
    列车司机告诉你，一趟列车最多可以容纳V体积的武器装备，但是你可能不能装满，因为列车承受不了那么大的重量，一趟列车最多可以承载G单位的重量。同时，军工厂仓库提供给你一份装备清单，详细记录了每件装备的体积、重量和火力。为了有效支援朱可夫元帅，你要找到一种方案，使得总火力值最大。

    【输入数据】
    第一行：V和G表示最大重量和体积。
    第二行：N表示仓库有N件装备。
    第三行到N+2行：每行3个数Ti Vi Gi表示各装备的火力值、体积和重量。
    【输出数据】
    输出一个数，表示可能获得的最大火力值。

    【样例输入】
    6 5
    4
    10 2 2
    20 3 2
    40 4 3
    30 3 3
    【样例输出】
    50

    【数据范围】
    对于50%的数据，V,G,N≤100；
    对于100%的数据，V,G,N≤400；

    四、翻转游戏

    【问题描述】
    翻转游戏是在一个4格*4格的长方形上进行的，在长方形的16个格上每个格子都放着一个双面的物件。每个物件的两个面，一面是白色的，另一面是黑色，每个物件要么白色朝上，要么黑色朝上，每一轮你只能翻3至5个物件，从而由黑到白地改变这些物件上面的颜色，反之亦然。每一轮被选择翻转的物件遵循以下规则：

    • 从16个物件中任选一个。
    • 翻转所选择的物件的同时，所有与它相邻的左方物件、右方物件、上方物件和下方物件（如果有的话），都要跟着翻转。

    以下为例：
    bwbw
    wwww
    bbwb
    bwwb
    这里“b”表示该格子放的物件黑色面朝上，“w”表示该格子放的物件白色朝上。如果我们选择翻转第三行的第一个物件（如下图所示），那么格子状态将变为：

    bwbw
    bwww
    wwwb
    wwwb
    游戏的目标是翻转到所有的物件白色朝上或黑色朝上。你的任务就是写一个程序求最少的翻转次数来实现这一目标。
    【输入格式】
    输入文件flip.in包含4行，每行4个字符，每个字符“w”或“b”表示游戏开始时格子上物件的状态。
    【输出格式】
    输出文件flip.out仅一个整数，即从给定状态到实现这一任务的最少翻转次数。如果给定的状态已经实现了目标就输出0，如果不可能实现目标就输出“Impossible”。
    【输入样例】
    bwwb
    bbwb
    bwwb
    bwww
    【输出样例】
    4

    题解在这里。

  • 大家好！！我来了！！

    欢迎来到SXKDZ的实验室哦~
    我可能会有点懒，有时候很久才写日志。不过我还是会关注博客的！
    谢谢FC提供的空间！