浙邮院程序设计竞赛解题报告

浙邮院程序设计竞赛-by Zhusha

A. 身份证编码问题

简单模拟, 按说的做就行

代码:

#include <bits/stdc++.h>

using namespace std ;

typedef long long ll ;


ll n ;

ll arr[20005] = {} ;

map <int, char> mic ;

int mci[] = {7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2} ;

int main() {

ios::sync_with_stdio(false) ;

string s ;

cin >> s ;


mic[0] = '1' ;

mic[1] = '0' ;

mic[2] = 'X' ;

mic[3] = '9' ;

mic[4] = '8' ;

mic[5] = '7' ;

mic[6] = '6' ;

mic[7] = '5' ;

mic[8] = '4' ;

mic[9] = '3' ;

mic[10] = '2' ;

ll ans = 0 ;

for (int i = 0 ; i < 17 ; ++i) {

ans += mci[i] * (s[i]-'0') ;

}


cout << s.substr(6, 4) << "-" << s.substr(10, 2) << "-" << s.substr(12, 2) << endl ;

bool xb ;

if (!(s[16] % 2)) xb = true ;

else xb = false ;

cout << (!xb ? "male" : "female") << endl ; 

if (mic[ans % 11] == s[17]) cout << "True" << endl ;

else cout << "False" << endl ;

return 0;

}


B.A变B

也是简单模拟,二进制比较一下就好,多余补0

代码:

#include <algorithm>

#include <iostream>

using namespace std;

typedef long long ll;

ll wys(ll a,ll b){

int n=0;

while(a||b){

if(a%2!=b%2)n++;

a>>=1;

b>>=1;

}

return n;

}

int main()

{

    long long a,b;

    while(cin>>a>>b){

    if(a==0&&b==0)break;

    cout<<wys(a,b)<<endl;

    }

}


c.R进制数排序

转成十进制比较,然后排序输出就好

代码

#include <bits/stdc++.h>

using namespace std ;

typedef long long ll ;


ll n ;


struct sz{

string z ;

int zh ;

sz() {}

sz(string x, int r) {

z = x ;

zh = 0 ;

ll p = 1 ;

for (int i = x.size()-1 ; i >= 0 ;i--){

zh += p*(x[i]-'0') ;

p *= r ;

}

}

bool operator <(const sz &b) const {

return zh < b.zh ;

}

}; //结构体存本来进制数和转化后的数字


sz arr[20005] = {} ;


int main() {

ios::sync_with_stdio(false) ;

int t ;

cin >> t ;

while (t--) {

cin >> n ;

int r ;

cin >> r ;

string x ;

for (int i = 1 ; i <= n ; i++) {

cin >> x ;

arr[i] = sz(x, r) ;

}

sort (arr+1, arr+n+1) ;

bool p = false;

for (int i = 1 ; i <= n ; i++) {

if (p) cout << " " ; p = true ;

cout << arr[i].z ;

} cout << endl ;

}


return 0;

}

D. 两个多项式的和 

每个指数对应的系数相加然后按指数从大到小输出就好

代码:

#include <bits/stdc++.h>

using namespace std ;

typedef long long ll ;

typedef pair<int, int> PII ;


map <ll, ll> mli ;

stack<PII> st ;


int main() {

ios::sync_with_stdio(false) ;


int a ;

cin >> a ;

ll x, z ;

for (int i = 1 ; i <= a ; ++i) {

cin >> x >> z ;

mli[z] += x ;

}

cin >> a ;

for (int i = 1 ; i <= a ; ++i) {

cin >> x >> z ;

mli[z] += x ;

}

for (auto i : mli) {//用栈把从小到大变成从大到小

st.push({i.second, i.first}) ;

}

bool p = false ;

while (!st.empty()) {

if (p) cout << " " ; p = true ;

cout << st.top().first << " " << st.top().second ;

st.pop() ;

} cout << endl;

return 0;

}


E.黑白棋子的移动

所有步骤都是固定,找到规律,比如说7的步骤是由6多了一步而来的

代码:

int main() {

    string s ;

    int n ;

    cin >> n ;


    cout << "step 0:" ;

    for (int i = 0; i < n; ++i) {

        cout << "o" ;

    }

    for (int i = 0; i < n; ++i) {

        cout << "*" ;

    }

    cout << "--" << endl ;


    for (int i = (n-1)*2-1; i > 0 ; --i) {

        cout << "step " << (n-1)*2-i << ":" ;

        if (i > 5) {

            if (i & 1) {

                for (int j = 1; j <= i/2+1; ++j) {

                    cout << "o" ;

                }


                cout << "--" ;


                for (int j = 1; j <= i/2+1; ++j) {

                    cout << "*" ;

                }


                for (int j = 1; j <= n - i/2-1; ++j) {

                    cout << "o*" ;

                }

            } else {

                for (int j = 1; j <= i/2+1; ++j) {

                    cout << "o" ;

                }


                for (int j = 1; j <= i/2+1; ++j) {

                    cout << "*" ;

                }


                cout << "--" ;


                for (int j = 1; j <= n - i/2-1; ++j) {

                    cout << "o*" ;

                }

            } ce("") ;

        } else {

            if (i == 5) {

                cout << "ooo--***o*" ;

                for (int j = 0; j < n-i/2-2; ++j) {

                    cout << "o*" ;

                } ce("") ;

            } else if (i == 4) {

                cout << "ooo*o**--*" ;

                for (int j = 0; j < n-i/2-2; ++j) {

                    cout << "o*" ;

                } ce("") ;

            } else if (i == 3) {

                cout << "o--*o**o" ;

                for (int j = 0; j < n-i/2-2; ++j) {

                    cout << "o*" ;

                } ce("") ;

            } else if (i == 2) {

                cout << "o*o*o*--" ;

                for (int j = 0; j < n-i/2-2; ++j) {

                    cout << "o*" ;

                } ce("") ;

            } else if (i == 1) {

                cout << "--" ;

                for (int j = 0; j < n; ++j) {

                    cout << "o*" ;

                } ce("") ;

            }

        }

    }

    return 0 ;

}


F.反素数

给定n,求n以内因子数最多的数。

一提到因子数,首先想到的就是把素因子分解。把n分解成

n=(p1的k1次方)*(p2的k2次方)**(p3的k3次方)


那么因子总数 ans=(k1+1)(k2+1)(k3+1)

考虑极端情况,n是某一个素数的k次幂,long long 为2的64次幂,所以我们最多就考虑到64层

当前因子大于我们想要的因子或正好为我们想要的因子或已经大于n我们就结束


ll primes[16] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};

int maxd, maxval;

long long n;


//dp 为当前枚举第几个素数。 num为当前因子的数量

//temp为当前因子数位num的数值。up为上一个素数的幂,这次应该小于等于这个幂次

void dfs(int dp, ll temp, int num, int up) {

    if ((num > maxd) || (num == maxd && maxval > temp)) {

        //当前因子数>maxd or 因子数相同,取值小的

        maxd = num;

        maxval = temp;

    }

    if (dp == 16) return;

    for (int i = 1; i <= up; i++) {

        if (primes[dp] * temp > n) break;

        temp *= primes[dp];

        dfs(dp + 1, temp, num * (i + 1), i);

    }

}


int main() {

    cin >> n;

    dfs(0, 1, 1, 60);

    cout << maxval << endl;

}


G.乘积最大

基础dp 用字符串来进行各个数位的拆分

f[i][j]表示前j位添加了i个乘号时的最优解


template <typename T> T to_math(string s) {

    stringstream ss(s) ;

    T num ;

    ss >> num ;

    return num ;

} //字符串流转化为数字


string number ;


int dp[45][45] = {};


void in() {


    int n, m ;

    cin >> n >> m ;


    cin >> number ;


    For_(i, 1, n) {

        dp[i][0] = to_math<int>(number.substr(0, i)) ;


        For_(j, 1, m) {

            For_(k, 1, i-1) {

                dp[i][j] = max(dp[i][j], dp[k][j-1] * to_math<int>(number.substr(k, i-k))) ; 

            }

        }

    }


    ce(dp[n][m]) ; // cout


}

int main() {

    in();

}


H.桃子的二分

前缀和记录连续区间和, 用二分答案去遍历数组序列


int n;

int s[2000005];


bool check(int mid)

{

    for(int i = 1; i <= n - mid + 1; i ++ )

    {

        if(s[i + mid - 1] - s[i - 1] > 0) return true;

    }


    return false;

}


int main()

{

    ios::sync_with_stdio(false) ;

    cin >> n ;

    for(int i = 1; i <= n; i ++ ) cin >> s[i] , s[i] += s[i - 1];


    int l = 0, r = n;

    while(l < r)

    {

        int mid = (l + r + 1) >> 1;

        if(check(mid)) l = mid; //如果当前区间和大于0了则可以再加长

        else r = mid - 1;

    }


    ce(r) ;


    return 0;

}


I.我要4444

注意同一天先处理报废的在处理申请的,记录已经使用了多少个车牌就好,如果超过了4444个就表示

已经取走4444号车牌了,除非报废的是4444车牌不然4444车牌一直没有

代码:

#include <bits/stdc++.h>

using namespace std ;

typedef long long ll ;

typedef pair<int, int> PII ;



struct day {

int x, l;

char bz ;

bool operator <(const day &b) const {

if (x == b.x) return bz < b.bz ;

return x < b.x ;

} //可以用外部cmp替代

};


day sd[55] ;


int main() {

ios::sync_with_stdio(false) ;


int t ;

cin >> t ;

while (t--) {

int k, p ;

cin >> k >> p ;

for (int i = 0; i < p ; i++){

cin >> sd[i].x >> sd[i].bz >> sd[i].l ;

} sort(sd, sd+p) ; 

bool yy = true ;

for (int i = 0; i < p ; i++) {

if (sd[i].bz == 'N') {

k += sd[i].l ;

if (k > 4444) yy = false ;

} else {

if (sd[i].l == 4444) yy = true ;

k -= 1 ;

} //报废了车牌使用-1

}

if (yy) cout << "Yes" << endl ;

else  cout << "No" << endl ;

}

return 0;

}



为解题报告打分
暂时不评分

★★
★★★
★★★★
★★★★★
发表您的评论(若贴AC代码或发表禁止言论等违禁行为将被删除并扣除积分)

|返回 |   | 转到页头|
Copyright @ 2008-2024(浙ICP备2022001332号), TZOJ. All Rights Reserved.