xzm2019

北京理工大学2019年计算机学院小学期程序设计方法与实践 - 热身赛 题解
Problem A. A + B ProblemI don't know I need to say what. ...
扫描右侧二维码阅读全文
15
2019/08

北京理工大学2019年计算机学院小学期程序设计方法与实践 - 热身赛 题解

Problem A. A + B Problem

I don't know I need to say what. But I know there are many teams using BigInteger. They get Time Limit Exceeded and some people get Wrong Answer or Runtime Error because they didn't deal negative numbers well.

However, $-10^{18} \leq a,b \leq 10^{18}$, which means $-2 \times 10^{18} \leq a + b \leq 2 * 10^{18}$. That's ok for long long.

#include <bits/stdc++.h>

using namespace std;

int main() {
    long long a, b;
    while (scanf("%lld%lld", &a, &b) == 2)
        printf("%lld\n", a + b);
}

Problem B. 谁是助教

何(he)金(jin)岷(min) 和 马(ma)泽(ze)航(hang)是你们的助教。请认准哦,一开始题面的确有一点点表述的不太清楚,没有说明白是按照姓名的顺序输出。

本题主要是为了测试Special Judge在oj的正常使用。

#include <bits/stdc++.h>
using namespace std;

int ans1[3], ans2[3];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        if (s == "he") ans1[0] = i;
        if (s == "jin") ans1[1] = i;
        if (s == "min") ans1[2] = i;
        if (s == "ma") ans2[0] = i;
        if (s == "ze") ans2[1] = i;
        if (s == "hang") ans2[2] = i;
    }
    bool flag = true;
    for (int i = 0; i < 3; i++) 
        if (!ans1[i]) flag = false;
    if (flag)
        return printf("3\n%d %d %d\n",ans1[0],ans1[1],ans1[2]),0;
    flag = true;
    for (int i = 0; i < 3; i++) 
        if (!ans2[i]) flag = false;
    if (flag)
        return printf("3\n%d %d %d\n",ans2[0],ans2[1],ans2[2]),0;
    return printf("-1\n"), 0;
}

Problem C. 助教的麻将

原题解:

显而易见就是在一个空间里面尽可能装长度为 $3$ 的金条,然后再将剩下的空间装满长度为 $2$ 的金条就可以了。然后特判一下剩余空间仅为 $1 \times 1 \times 1$ 时,可以抽出一根长度为 $3$ 的放下两根长度为 $2$ 的。显然这种情况更优。
再考虑箱子大小只有 $1 \times 1 \times 1$ 时无法塞下金条就可以了。

然而忘记考虑在 $5 \times 5 \times 2$ 的情况下,最优解其实可以螺旋摆放的,放$16$根 $1 \times 3$ 的然后在中间插入一根 $1 \times 2$ 的,这样总价值是$83$。 然而原来的方法总价值是$82$。

注意多考虑这种情况即可。

本题经过rejudge以后,有$8$个提交由Accepted变为了Wrong Answer,同时有$3$个提交从Wrong Answer变为了Accepted

PS:由于这一题实际最后通过人数并不多,助教就不想默默的改正式赛的题了。

void solve()
{
    ll all = 1ll*a*b*c;
    if( a == 1 && b == 1 && c == 1 ){
        printf("0\n");
        return;
    }
    if( a%3 == 0 || b%3 == 0 || c%3 == 0 ){
        printf("%lld\n", all/3*5);
    }
    else if( a%3 == 1 && b%3 == 1 && c%3 == 1 ){
        printf("%lld\n", (all/3-1)*5+6); 
    }
    else if( a%3 == 2 && b%3 == 2 && c%3 == 2 ){
        if( a+b+c >= 12 ) printf("%lld\n", (all-50)/3*5+83);
        else printf("%lld\n", (all/3-2)*5+12);
    }
    else if( all%3 == 1 ){
        printf("%lld\n", (all/3-1)*5+6);
    }else{
        printf("%lld\n", all/3*5+3);
    }
}

Problem D. 助教的血流成河

大!模!拟!

蛮力法作为程序设计中最经典也是最古老的的一种算法,为什么大家都不想去接触呢?

这里有很多的方法判断胡牌。单纯的谈心在清一色的情况下可能要考虑很多,希望大家可以考虑如何使用别的姿势判断胡牌,拓展题目:Jongmah

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
#define PI acos(-1)
#define eps 1e-9
#define mp(x,y) make_pair(x,y)
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
#define LOCAL
char s[30];
int cnt[3][10], tmp[3][10], tmp2[3][10];
int qingyise;
int yitiaolong;
int anqidui;
int longqidui;
int duiduihu;
int pinghu;
int gen;
int jiang;
void init(){
    memset( cnt, 0, sizeof( cnt ));
    pinghu = 0;
    qingyise = 0;
    yitiaolong = 0;
    anqidui = 0;
    longqidui = 0;
    duiduihu = 0;
    gen = 0;
    jiang = 0;
}
void check_anqidui(){
    for(int i = 0; i < 3; i++ ){
        for(int j = 1; j < 10; j++ ){
            if( cnt[i][j] ){
                if( cnt[i][j] != 2 && cnt[i][j] != 4 ){
                    anqidui = 0;
                    return;
                }
            }
        }
    }
    anqidui = 1;
}
void check_longqidui(){
    for(int i = 0; i < 3; i++ ){
        for(int j = 1; j <= 9; j++ ){
            if( cnt[i][j] == 4 ){
                longqidui = 1;
                return;
            }
        }
    }
}
bool check( ){
    memcpy( tmp2, tmp, sizeof(tmp) );
    int count = 4;
    // for(int i = 0; i < 3; i++ ){
    //     for(int j = 1; j < 10; j++ ){
    //         printf("%d ", tmp2[i][j]);
    //     }
    //     printf("\n");
    // }
    for(int i = 0; i < 3; i++ ){
        for(int j = 1; j <= 9; j++ ){
            if( tmp2[i][j] >= 3 ){
                tmp2[i][j] -= 3;
                count--;
            }
            while( tmp2[i][j] && j <= 7 ){
                if( !tmp2[i][j+1] || !tmp2[i][j+2] ) return 0;
                tmp2[i][j]--;
                tmp2[i][j+1]--;
                tmp2[i][j+2]--;
                count--;
            }
        }
    }
    // for(int i = 0; i < 3; i++ ){
    //     for(int j = 1; j < 10; j++ ){
    //         printf("%d ", tmp2[i][j]);
    //     }
    //     printf("\n");
    // }
    // printf("%d\n", count);
    if( count == 0 ) return 1;
    else return 0;
}
void check_duiduihu( int jian ){
    for(int i = 0; i < 3; i++ ){
        for(int j = 1; j < 10; j++ ){
            if( cnt[i][j] ){
                if( jian == i*10+j ){
                    if( cnt[i][j] > 2 ){
                        duiduihu = 0;
                        return;
                    }
                }else if( cnt[i][j] <= 2 ){
                    duiduihu = 0;
                    return;
                }
            }
        }
    }
    duiduihu = 1;
}
void check_pinghu(){
    memcpy( tmp, cnt, sizeof(tmp));
    for(int i = 0; i < 3; i++ ){
        for(int j = 1; j < 10; j++ ){
            if( tmp[i][j] >= 2 ){
                tmp[i][j] -= 2;
                if( check() ){
                    // printf("####\n");
                    pinghu = 1;
                    // printf("pinghu %d %d\n", pinghu, &pinghu);
                    if( !jiang ) jiang = i*10+j;
                    check_duiduihu( i*10+j );
                    if( duiduihu ){
                        jiang = i*10+j;
                        return;
                    }
                }
                tmp[i][j] += 2;
            }
        }
    }
}
void check_qingyise(){
    int count = 0;
    for(int i = 0; i < 3; i++ ){
        count += cnt[i][0];
    }
    if( count == 1 ) qingyise = 1;
}
void check_yitiaolong(){
    for(int i = 0; i < 3; i++ ){
        int flag = 1;
        for(int j = 1; j <= 9; j++ ){
            if( !cnt[i][j] ){
                flag = 0;
                break;
            }
        }
        if( flag ){
            yitiaolong = 1;
            return;
        }
    }
}
void count_gen(){
    for(int i = 0; i < 3; i++ ){
        for(int j = 1; j <= 9; j++ ){
            if( cnt[i][j] == 4 ){
                gen++;
            }
        }
    }
    if( longqidui ) gen--;
}
void print_anqidui(){
    char huase;
    for(int i = 0; i < 3; i++ ){
        if( i == 0 ) huase = 'm';
        else if( i == 1 ) huase = 'p';
        else huase = 't';
        for(int j = 1; j <= 9; j++ ){
            while( cnt[i][j] ){
                printf("%d%c%d%c\n", j, huase, j, huase );
                cnt[i][j] -= 2;
            }
        }
    }
}
void print_pinghu(){
    char huase;
    for(int i = 0; i < 3; i++ ){
        for(int j = 1; j <= 9; j++ ){
            if( jiang == i*10+j ) cnt[i][j] -= 2;
            if( i == 0 ) huase = 'm';
            else if( i == 1 ) huase = 'p';
            else huase = 't';
            while( cnt[i][j] >= 3 ){
                printf("%d%c%d%c%d%c\n", j, huase, j, huase, j, huase );
                cnt[i][j] -= 3;
            }
            while( cnt[i][j] ){
                printf("%d%c%d%c%d%c\n", j, huase, j+1, huase, j+2, huase );
                cnt[i][j]--;
                cnt[i][j+1]--;
                cnt[i][j+2]--;
            }
        }
    }
    int op = jiang/10;
    if( op == 0 ) huase = 'm';
    else if( op == 1 ) huase = 'p';
    else huase = 't';
    int num = jiang%10;
    printf("%d%c%d%c\n", num, huase, num, huase );
}
void get_ans(){
    int ans;
    int op;
    if( qingyise && longqidui ) {ans = 32; op = 1;}
    else if( qingyise && anqidui ) {ans = 16; op = 2;}
    else if( qingyise && yitiaolong ) {ans = 8; op = 3;}
    else if( longqidui ) {ans = 8; op = 4;}
    else if( qingyise && duiduihu ) {ans = 8; op = 5;}
    else if( qingyise ) {ans = 4; op = 6;}
    else if( anqidui ) {ans = 4; op = 7;}
    else if( yitiaolong ) {ans = 2; op = 8;}
    else if( duiduihu ) {ans = 2; op = 9;}
    else {ans = 1; op = 10;}
    while( gen-- ) ans *= 2;
    if( anqidui ) print_anqidui();
    else print_pinghu();
    if( op == 1 ) printf("QingLongQiDui");
    else if( op == 2 ) printf("QingQiDui");
    else if( op == 3 ) printf("QingYiSeYiTiaoLong");
    else if( op == 4 ) printf("LongQiDui");
    else if( op == 5 ) printf("QingYiSeDuiDuiHu");
    else if( op == 6 ) printf("QingYiSe");
    else if( op == 7 ) printf("AnQiDui");
    else if( op == 8 ) printf("YiTiaoLong");
    else if( op == 9 ) printf("DuiDuiHu");
    else if( op == 10 ) printf("PingHu");
    printf(" *%d\n", ans);
}
void solve()
{
    char huase;
    int num;
    init();
    for(int i = 0; i < 28; i += 2 ){
        num = s[i]-'0';
        huase = s[i+1];
        // printf("%d%c\n", num, huase);
        if( huase == 'm' ){
            cnt[0][0] = 1;
            cnt[0][num] ++;
        }else if( huase == 'p' ){
            cnt[1][0] = 1;
            cnt[1][num]++;
        }else{
            cnt[2][0] = 1;
            cnt[2][num]++;
        }
    }
    if( cnt[0][0] && cnt[1][0] && cnt[2][0] ){
        printf("ZhaHu\nHuaZhu\n");
        return;
    }
    check_anqidui();
    if( !anqidui ) check_pinghu();
    else check_longqidui();
    // printf("pinghu %d %d\nanqidui %d\n", pinghu, &pinghu, anqidui);
    if( !pinghu && !anqidui ){
        printf("ZhaHu\n");
        return;
    }
    check_qingyise();
    check_yitiaolong();
    count_gen();
    get_ans();
}
int main(int argc, char * argv[]) 
{
    #ifdef LOCAL
    //freopen("data.in", "r", stdin);
    //freopen("data.out", "w", stdout);
    #endif
    while( ~scanf("%s", s) ){
        solve();
    }
    return 0;
}
Last modification:August 14th, 2019 at 11:57 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment