分类： 技术

　　很简单的一个题目，没一次AC，因为忘记判断0了，有可能出现十位或个位上有零的情况，代码：
#include <stdio.h>
#include <string.h>
int sum;
int used[10];
int ck[10];

int check(int n)
{
        int t;
        while(n){
                t = n % 10;
                if(ck[t] || (t == 0)){
                        //要考虑不能为0的情况 
                        return 0;
                }
                ck[t] = 1;
                n /= 10;
        }
        return 1;
}

void srch(int now)
{
        int i;
        if(now == 3){
                memset(ck, 0, sizeof(ck));
                if(check(sum) && check(2  sum) && check(3  sum)){
                        printf("%d %d %d\n", sum, 2  sum, 3  sum);
                }
                return;
        }
        sum = ((sum << 3) + (sum << 1));
        //sum *= 10;
        for(i = 1; i <= 9; i++){
                sum += i;
                srch(now + 1);
                sum -= i;
        }
        sum /= 10;
}

int main(void)
{
        srch(0);
}

　　麻烦的题目，第一次只拿了30分，代码如下：

　　这一题我的思路(应该)是O(nlogn)的，就是进行一趟快排加上对数组进行一次扫描。
　　快排直接调用库函数，扫描就是用j记录当前自然数，c记录当前自然数出现的次数，如果num[i]和j相同，c++；不同就输出j和c，然后j=num[i], c = 1。在循环结束后还要将最后一个自然数输出。
　　下面贴出代码：
#include <stdio.h>
int num[200000];

int com(const void a, const void b)
{
        return (int )a – (int )b;
}

int main(void)
{
        int n;
        int i, j, c;
        scanf("%d", &n);
        for(i = 0; i < n; i++){
                scanf("%d", &num[i]);
        }
        qsort(num, n, sizeof(int), com);
        j = num[0];
        //是num[0] 不是num[j] 
        c = 1;
        // c 要从1开始而不是0
        for(i = 1; i < n; i++){
                if(num[i] != j){
                        printf("%d %d\n", j, c);
                        j = num[i];
                        c = 1;
                        // c 要从1开始而不是0
                }else{
                        c++;
                }
        }
        printf("%d %d\n", j, c);
        return 0;
}

　　这个题目我的思路很简单，就是读入一个数据，判断是否小于s1的顶元素，如果是则讲数据压入s1，否则该数据是否小于s2的顶元素，如果是则将它压入栈s2。然后再判断s1的顶是否等于当前需要输出的值（就是安顺序来是不是对的），如果是就输出b。再同样判断s2，如果是就输出d。
　　很可惜，只有30分，代码如下：
#include <stdio.h>
int num[1000];
int s1[1000], s2[1000];
int t1, t2;
char ans[2000];
int len;

void add(char ch)
{
        ans[len++] = ch;
}

int main(void)
{
        int n;
        int i, j, r, t;
        scanf("%d", &n);
        for(i = 0; i < n; i++){
                scanf("%d", &num[i]);
        }
        s1[0] = s2[0] = 10000;
        for(i = 1, j = 0; i <= n;){
                r = j;
                if(s1[t1] > num[j] && j < n){
                        s1[++t1] = num[j++];
                        add(‘a’);
                }else if(s2[t2] > num[j] && j < n){
                        s2[++t2] = num[j++];
                        add(‘c’);
                }
                t = i;
                if(s1[t1] == i){
                        t1–;
                        add(‘b’);
                        i++;
                }
                if(s2[t2] == i){
                        t2–;
                        i++;
                        add(‘d’);
                }
                if(t == i && r == j){
                        printf("0\n");
                        return 0;
                }
        }
        for(i = 0; i < 2  n; i++){
                if(i != 0){
                        printf(" ");
                }
                printf("%c", ans[i]);
        }
        printf("\n");
        return 0;
}
　　继续学习中。。
　　额, 照着网上一个人抄的(当然是在理解的前提下, 再自己徒手打出来的.), 竟然没有AC, 然后试了试他自己的代码, 也没AC
　　思路是这样的, 对于这样的数据i < j < k 且 num[k] < num[i] < num[j] 的情况下，i和j一定不能在同一个栈中，不然就是无解的情况，你想想啊，如果小的先入栈，大的又入栈，这能有解码？所以这里使用了二分图染色的算法，具体的解释看这位大牛和另一位的Blog: 
　　http://www.byvoid.com/blog/noip2008-twostack/

　　这题我以前就看过，一直不会做，后来看到别人说双线程动态规划，我以为是多么多么的神奇的一个东西，把它看的和Linux源码一样神奇了，现在学了之后也就是简单的DP，我用的四维DP，别人都说是三维，我先用四维做，以后再考虑三维（也许不会再考虑这一题了咯。）
　　我的方程如下:f[a][b][c][d] = max(f[a – 1][b][c – 1][d], f[a][b – 1][c – 1][d], f[a – 1][b][c][d – 1], f[a][b – 1][c][d – 1]) + map[a][b] + map[c][d].
　　a,b代表第一个线程（说线程夸张了一点），c,d代表第二个线程的坐标，map就是对应坐标的值。
　　代码如下：
#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
int f[51][51][51][51];
int map[51][51];
int m, n;
int s[4];

volatile void test(int a, int b, int c, int d, int t)
{
        if(a < 0 || b < 0 || c < 0 || d < 0){
                return;
        }
        t = max(*t, f[a][b][c][d]);
}

void dp(void)
{
        int a = s[0], b = s[1], c = s[2], d = s[3];
        int t = 0;
        test(a – 1, b, c – 1, d, &t);
        test(a – 1, b, c, d – 1, &t);
        test(a, b – 1, c, d – 1, &t);
        test(a, b – 1, c – 1, d, &t);
        f[a][b][c][d] = t + map[a][b] + map[c][d];
}

void srch(int now)
{
        int i, k;
        if(now == 4){
                if(s[0] != s[2] || s[1] != s[3]){
                        dp();
                }
                return;
        }
        if(now & 1){
                k = n;
        }else{
                k = m;
        }
        for(i = 1; i <= k; i++){
                s[now] = i;
                srch(now + 1);
        }
}

int main(void)
{
        int i, j, k, l;
        scanf("%d%d", &m, &n);
        for(i = 1; i <= m; i++){
                for(j = 1; j <= n; j++){
                        scanf("%d", &map[i][j]);
                }
        }
        f[1][1][1][1] = map[1][1];
        srch(0);

        s[0] = s[2] = m;
        s[1] = s[3] = n;
        dp();

        printf("%d\n", f[m][n][m][n]);
        return 0;
}

　　一道DP题，DP的方程很简单:
　　f[a][b][c][d][e] = min(f[a][b][c][d][e], f[a – cost[0][0]][b – cost[0][1]][c – cost[0][2]][d – cost[0][3]][e – cost[0][4]], f[a – cost[1][0]][b – cost[1][1]][c – cost[1][2]][d – cost[1][3]][e – cost[1][4]]…);
　　代码如下：
/
LANG: C
ID: zqynux2
PROG: shopping
/
#include <stdio.h>
#define min(a, b) ((a)<(b)?(a):(b))
struct you{
        int len;
        struct thing{
                int id, num;
        }buy[5];
        int priece;
}buy[99];
int money[6];
int num[6];
int good[1000];
int f[6][6][6][6][6];
int n, m;

int s[6];

void init(int now)
{
        int i;
        if(now == m){
                for(i = 0; i < m; i++){
                        f[s[0]][s[1]][s[2]][s[3]][s[4]] += money[i + 1] s[i];
                }
                return;
        }
        for(i = 0; i <= 5; i++){
                s[now] = i;
                init(now + 1);
        }
}

void deal(int now)
{
        int used[6];
        int i;
        memset(used, 0, sizeof(used));
        for(i = 0; i < buy[now].len; i++){
                used[good[buy[now].buy[i].id]] += buy[now].buy[i].num;
        }
        if(used[0] != 0){
                return;
        }
        for(i = 0; i < 5; i++){
                if(used[i + 1] > s[i]){
                        return;
                }
        }
        f[s[0]][s[1]][s[2]][s[3]][s[4]] = min(f[s[0]][s[1]][s[2]][s[3]][s[4]], 
                f[s[0] – used[1]][s[1] – used[2]][s[2] – used[3]][s[3] – used[4]][s[4] – used[5]]
                + buy[now].priece);
}

void srch(int now)
{
        int i;
        if(now == m){
                for(i = 0; i < n; i++){
                        deal(i);
                }
                return;
        }
        for(i = 0; i <= 5; i++){
                s[now] = i;
                srch(now + 1);
                //写成了init 
        }
}

int main(void)
{
        int i, j;
        freopen("shopping.in", "r", stdin);
        freopen("shopping.out", "w", stdout);
        scanf("%d", &n);
        for(i = 0; i < n; i++){
                scanf("%d", &buy[i].len);
                for(j = 0; j < buy[i].len; j++){
                        scanf("%d%d", &buy[i].buy[j].id,
                                        &buy[i].buy[j].num);
                }
                scanf("%d", &buy[i].priece);
        }
        scanf("%d", &m);
        for(i = 1; i <= m; i++){
                scanf("%d%d%d", &j, &num[i], &money[i]);
                good[j] = i;
        }

        init(0);                       / 将价格进行初始化 /
        srch(0);                       / DP */

        printf("%d\n", f[num[1]][num[2]][num[3]][num[4]][num[5]]);
        return 0;
}

　　这个题目很简单，不过我也提交了两次。。问题见注释。
#include <math.h>
#include <stdio.h>
#include <string.h>
char str[101];
int count[26];

int isprime(int n)
{
        int li;
        int i;
        if(n == 0 || n == 1){
                //0和1不算素数 
                return 0;
        }
        li = sqrt(n);
        for(i = 2; i <= li; i++){
                if(n % i == 0){
                        return 0;
                }
        }
        return 1;
}

int main(void)
{
        int i, len;
        int max = –1, min = 1000;
        int ans;
        scanf("%s", str);
        len = strlen(str);
        for(i = 0; i < len; i++){
                count[str[i] – ‘a’]++;
        }
        for(i = 0; i < 26; i++){
                if(max < count[i]){
                        max = count[i];
                }
                if(min > count[i] && count[i] != 0){
                                //如果字符没有出现的话就不算 
                        min = count[i];
                }
        }
        ans = max – min;
        if(isprime(ans)){
                printf("Lucky Word\n");
                printf("%d\n", ans);
        }else{
                printf("No Answer\n0\n");
                        //忘记输出0了  
        }
//      getch();
        return 0;
}

　　刚刚拿到题目感觉非常容易，第一次提交，发现把数据写错了，6是6根火柴，我写的5根。第二次提交我发现题目不止是个位的运算，还可以十位，百位。。第三次提交，AC了，不过效率太慢了，代码如下：
#include <stdio.h>
int num[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
                    //数据写错了

int count(int n)
{
        int t = 0;
        if(n == 0){
                t = num[0];
        }
        while(n){
                t += num[n % 10];
                n /= 10;
        }
        return t;
}

int main(void)
{
        int n;
        int i, j;
        int ans = 0;
        scanf("%d", &n);
        for(i = 0; i <= 2000; i++){
                for(j = 0; j <= 2000; j++){                           
                        if(count(i) + count(j) + count(i + j) + 4 == n){
                                ans++;
                        }
                }
        }
        printf("%d\n", ans);
        return 0;
}
　　后来看到七妹的代码，发现自己的代码太破了，本来我是想用数组记录一下的，后来发现这都不用。，修改后的代码如下：
#include <stdio.h>
int num[5001] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
                    //数据写错了
int main(void)
{
        int n;
        int i, j;
        int ans = 0;
        scanf("%d", &n);
        for(i = 10; i <= 5000; i++){
                num[i] = num[i / 10] + num[i % 10];
        }
        for(i = 0; i <= 5000; i++){
                for(j = 0; j <= 5000; j++){
                        if(i + j <= 5000 && num[i] + num[j] + num[i + j] + 4 == n){
                                ans++;
                        }
                }
        }
        printf("%d\n", ans);
        return 0;
}

　　苦难的题目，我做着题只有一个想法：深搜，，暴力搜索！但是就连样例都超时了，我就直接找题解去了。
　　网上找到一个题解，用位运算做的，大概看了下就开始仿造着写，去掉了感觉无用的功能（其实很有用），结果超时了。。。超时代码如下，75分。
#include <stdio.h>
#define getindex(t) ({\
        int i;\
        switch(t){\
        case 1:\
                i = 0;\
                break;\
        case 2:\
                i = 1;\
                break;\
        case 4:\
                i = 2;\
                break;\
        case 8:\
                i = 3;\
                break;\
        case 16:\
                i = 4;\
                break;\
        case 32:\
                i = 5;\
                break;\
        case 64:\
                i = 6;\
                break;\
        case 128:\
                i = 7;\
                break;\
        case 256:\
                i = 8;\
                break;\
        }\
        i;\
})
#define getboxid(i, j) ((3 * ((i) / 3)) + ((j) / 3))
int rol[9],             //记录横排出现的数字
    col[9],             //记录竖排出现的数字
    box[9],             //记录九各宫出现的数字
    use[9];             //记录横排
int ans = –1;
//初始化为-1而不是0 
int map[9][9];
int mul[9][9] = {{6, 6, 6, 6, 6, 6, 6, 6, 6},
                 {6, 7, 7, 7, 7, 7, 7, 7, 6},
                 {6, 7, 8, 8, 8, 8, 8, 7, 6},
                 {6, 7, 8, 9, 9, 9, 8, 7, 6},
                 {6, 7, 8, 9,10, 9, 8, 7, 6},
                 {6, 7, 8, 9, 9, 9, 8, 7, 6},
                 {6, 7, 8, 8, 8, 8, 8, 7, 6},
                 {6, 7, 7, 7, 7, 7, 7, 7, 6},
                 {6, 6, 6, 6, 6, 6, 6, 6, 6}};

void cal(void)
{
        int i, j;
        int tmp = 0;
        for(i = 0; i < 9; i++){
                for(j = 0; j < 9; j++){
                        tmp += map[i][j] * mul[i][j];
                }
        }
        if(tmp > ans){
                ans = tmp;
        }
}

void srch(int i)
{
        int j, x, y;
        int pos, p;
        if(i == 9){
                cal();
                return ;
        }
        x = 511 ^ use[i];
        if(x == 0){
                srch(i + 1);
                return;
                //掉了return  
        }
        y = x & -x;
        use[i] |= y;
        j = getindex(y);
        pos = 511 ^ (rol[i]|col[j]|box[getboxid(i, j)]);
        while(pos > 0){
                p = pos & -pos;
                pos ^= p;
                map[i][j] = getindex(p) + 1;
                rol[i] |= p;
                col[j] |= p;
                box[getboxid(i, j)] |= p;
                srch(i);
                rol[i] ^= p;
                col[j] ^= p;
                box[getboxid(i, j)] ^= p;
        }
        use[i] ^= y;
}

int main(void)
{
        int i, j;
        int p;
        freopen(“abc.txt”, “r”, stdin);
        for(i = 0; i < 9; i++){
                for(j = 0; j < 9; j++){
                        scanf(“%d“, &map[i][j]);
                        if(map[i][j] > 0){
                                use[i] |= 1 << j;
                                p = 1 << (map[i][j] – 1);
                                if(((rol[i] & p)) || ((col[j] & p))
                                        || ((box[getboxid(i, j)] & p))){
                                        printf(“-1\n“);
                                        return 0;
                                }
                                rol[i] |= p;
                                col[j] |= p;
                                box[getboxid(i, j)] |= p;
                        }
                }
        }
        srch(0);
        printf(“%d\n“, ans);
        return 0;
}

　　后来找了好久才想起来是把这个重要的剪枝去掉了（就是我认为不重要的部分。）
　　修改代码如下：
#include <stdio.h>
#define getindex(t) ({\
        int i;\
        switch(t){\
        case 1:\
                i = 0;\
                break;\
        case 2:\
                i = 1;\
                break;\
        case 4:\
                i = 2;\
                break;\
        case 8:\
                i = 3;\
                break;\
        case 16:\
                i = 4;\
                break;\
        case 32:\
                i = 5;\
                break;\
        case 64:\
                i = 6;\
                break;\
        case 128:\
                i = 7;\
                break;\
        case 256:\
                i = 8;\
                break;\
        }\
        i;\
})
#define getboxid(i, j) ((3 * ((i) / 3)) + ((j) / 3))
int rol[9],             //记录横排出现的数字
    col[9],             //记录竖排出现的数字
    box[9],             //记录九各宫出现的数字
    use[9];             //记录横排
int count[9];           //每行值为0的个数
int hk[9];              //按照这里的顺序进行深搜!! 重要剪枝
int ans = –1;
//初始化为-1而不是0 
int map[9][9];
int mul[9][9] = {{6, 6, 6, 6, 6, 6, 6, 6, 6},
                 {6, 7, 7, 7, 7, 7, 7, 7, 6},
                 {6, 7, 8, 8, 8, 8, 8, 7, 6},
                 {6, 7, 8, 9, 9, 9, 8, 7, 6},
                 {6, 7, 8, 9,10, 9, 8, 7, 6},
                 {6, 7, 8, 9, 9, 9, 8, 7, 6},
                 {6, 7, 8, 8, 8, 8, 8, 7, 6},
                 {6, 7, 7, 7, 7, 7, 7, 7, 6},
                 {6, 6, 6, 6, 6, 6, 6, 6, 6}};

void cal(void)
{
        int i, j;
        int tmp = 0;
        for(i = 0; i < 9; i++){
                for(j = 0; j < 9; j++){
                        tmp += map[i][j] * mul[i][j];
                }
        }
        if(tmp > ans){
                ans = tmp;
        }
}

void srch(int t)
{
        int i, j, x, y;
        int pos, p;
        if(t == 9){
        //这里是t不是i 
                cal();
                return ;
        }
        i = hk[t];
        x = 511 ^ use[i];
        if(x == 0){
                srch(t + 1);
                return;
                //掉了return  
        }
        y = x & -x;
        use[i] |= y;
        j = getindex(y);
        pos = 511 ^ (rol[i]|col[j]|box[getboxid(i, j)]);
        while(pos > 0){
                p = pos & -pos;
                pos ^= p;
                map[i][j] = getindex(p) + 1;
                rol[i] |= p;
                col[j] |= p;
                box[getboxid(i, j)] |= p;
                srch(t);
                rol[i] ^= p;
                col[j] ^= p;
                box[getboxid(i, j)] ^= p;
        }
        use[i] ^= y;
}

int main(void)
{
        int i, j;
        int p;

        for(i = 0; i < 9; i++){
                for(j = 0; j < 9; j++){
                        scanf(“%d“, &map[i][j]);
                        if(map[i][j] > 0){
                                use[i] |= 1 << j;
                                p = 1 << (map[i][j] – 1);
                                if(((rol[i] & p)) || ((col[j] & p))
                                        || ((box[getboxid(i, j)] & p))){
                                        printf(“-1\n“);
                                        return 0;
                                }
                                rol[i] |= p;
                                col[j] |= p;
                                box[getboxid(i, j)] |= p;
                        }else{
                                count[i]++;
                        }
                }
        }
        for(i = 0; i < 9; i++){
                hk[i] = i;
        }

        for(i = 1; i < 9; i++){
                p = hk[i];
                for(j = i – 1; j >= 0 && count[hk[j]] > count[p]; j–){
                        hk[j + 1] = hk[j];
                }
                hk[j + 1] = p;
        }
        srch(0);
        printf(“%d\n“, ans);
        return 0;
}