190526--中南林业科技大学第十一届程序设计大赛

指路：https://ac.nowcoder.com/acm/contest/910#question

这个题目写的其实很爽，因为很多都有思路，不过即使如此我还是发现了我有很多短板，从排名也看的出来，其实刚刚好适合我这种刚刚入门的小菜鸡了。。。希望下周都是这种题呜呜呜

A:链表的合并

不说了，我数据结构还不够熟
附上合并链表的代码：1.https://www.cnblogs.com/idorax/p/7709419.html
2.https://www.2cto.com/kf/201712/709039.html
再附上大佬令我目瞪狗呆的极短代码（4分钟我也是佛了）
这个巧妙的思路真的厉害！
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40709376

#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#include<algorithm>
using namespace std;
long long a[40];
int main(){
    fo(i,1,30) scanf("%lld",&a[i]);
    sort(a+1,a+31);
    fo(i,1,30) printf("%lld ",a[i]);
    return 0;
}

#include <cstdio>
#include <malloc.h>
#include<iostream>
using namespace std;
typedef struct node
{
    int data;
    struct node *next;
}LNode,*LinkList;
  
LinkList GreatLinkList(int n)
{
    /*建立一个长度为n的链表*/
    LinkList p, r, list = NULL;
    int e;
    int i;
    for (i=1;i<=n;i++)
    {
        scanf("%d",&e);                     /*获取链表结点中的数据元素*/
        p=(LinkList)malloc(sizeof(LNode));  /*分配一个新的链表结点*/
        p->data=e;
        p->next=NULL;
        if (list == NULL)
        {
            list = p;           /*list指向第一个结点，list是头指针*/
        }
        else
        {
            r->next = p;     /*将新结点连接到链表的尾部*/
        }
        r = p;                      /*指针r始终指向链表的最后一个结点*/
    }
    return list;                    /*返回链表的头指针*/
}
  
LinkList MergeList(LinkList list1, LinkList list2)
{
    LinkList list3;
    LinkList p = list1, q = list2;
    LinkList r;
  
    if (list1->data <= list2->data)
    {  
        list3 = list1;          /*list1的第一个元素最小，list3指向它*/
        r = list1;              /*指针r指向list1的第一个元素*/
        p = list1->next;     /*p指向list1的第二个元素*/
    }
    else
    {
        list3 = list2;          /*list2的第一个元素最小，list3指向它*/
        r = list2;              /*指针r指向list2第一个元素*/
        q = list2->next;     /*q指向list2的第二个元素*/
    }
  
    while (p!=NULL && q!=NULL)
    {
        if (p->data<=q->data)  /*若当前p指向的结点值不大于q指向的结点值*/
        {  
            r->next = p;     /*将p所指向的结点链接到r所指向的结点的后面*/
            r = p;              /*指针后移*/
            p = p->next;     /*指针后移*/
        }
        else
        {
            r->next = q;     /*将所指向的结点链接到r所指向的结点的后面q*/
            r = q;              /*指针后移*/
            q = q->next;     /*指针后移*/
        }
    }
  
    r->next = p?p:q;         /*插入剩余结点*/
    return list3;               /*返回合并后的链表list3，即链表首地址*/
}
  
void printLink(LinkList list)
{
    while (list != NULL)
    {
        printf("%d ",list->data);    /*打印出每个结点中的数据data*/
        list = list->next;
    }
}
  
int main()
{
    LinkList list1,list2,list3;
    list1 = GreatLinkList(15);  /*创建一个按值有序的包含10个元素的链表*/
    list2 = GreatLinkList(15);  /*创建一个按值有序的包含10个元素的链表*/
    list3 = MergeList(list1,list2);
    printLink(list3);       /*打印出链表的内容*/
    printf("\n");
    getchar();
    getchar();
    return 0;
}

B.兑换零钱

动态规划中的完全背包问题。
大佬代码：

#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
const int mn=3e5;
int f[mn+20],T,n;
const int p=1e9+7,a[13]={1,2,5,10,20,50,100,200,500,1000,2000,5000,10000};
int main(){
    f[0]=1;
    fo(i,0,12)
        fo(j,a[i],mn){
            f[j]+=f[j-a[i]];
            if (f[j]>=p) f[j]-=p;
        }
    scanf("%d",&T);
    while (T--){
        scanf("%d",&n);
        printf("%lld\n",f[n]);
    }
}

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
int dimes[]={1,2,5,10,20,50,100,200,500,1000,2000,5000,10000};
ll dp[100005];
 
int main(){
    int t;int n;
    scanf("%d",&t);
    while(t--){
    memset(dp,0,sizeof(dp));
    scanf("%d",&n);
    dp[0]=1;
    for(int i=0;i<13;i++)
    {
        for(int j=dimes[i];j<=n;j++)
            dp[j]=(dp[j]+dp[j-dimes[i]])%1000000007;
    }
    printf("%lld\n",dp[n]);
}
    return 0;
}

C. 神奇的进制转换

思路参考：https://blog.csdn.net/SJF0115/article/details/8690581以及
https://blog.csdn.net/u012485480/article/details/81479071
代码地址来源：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40711225

//https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40711225
#include <bits/stdc++.h>
#define dbg(x) std::cerr << #x << " = " << x << endl
const int maxn = 10000 + 10;
int  t[maxn], A[maxn];
char str1[maxn], str2[maxn];
int n, m;
void solve()
{
    int i, len, k;
    len = strlen(str1);
    for(i=len; i>=0; --i) t[len-1-i] = str1[i] -(str1[i]<58 ? 48: str1[i]<97 ? 55: 61);
    for(k=0; len;) {
        for(i=len; i>=1; --i) {
            t[i-1] +=t[i]%m*n;
            t[i] /= m;
        }
        A[k++] = t[0] % m;
        t[0] /=m;
        while(len>0&&!t[len-1])  len--;
    }
    str2[k] = NULL;
    for(i=0; i<k; i++)
        str2[k-1-i] = A[i]+(A[i]<10 ? 48: A[i]<36 ? 55:61);
}
 
int main()
{
    int T;
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d%s",&n, &m, str1);
        solve();
        printf("%s\n", str2);
    }
    return 0;
}

附上这段大佬的代码https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40710774

#include <algorithm>
#include <cstring>
#include <cstdio>
 
using namespace std ;
 
const int D=10 ;
 
int mp[500] ;
char w[500] ;
 
char s[500] ;
int a[5000000] , b[5000000] , bit , m , n ;
int d[5000000] ;
inline void solve ()
{
    int i , j , l , r=0 ;
    for ( i=1 ; i<=bit ; i++ ) a[i]=0; bit=1;
    scanf(" %d %d %s ",&m,&n,s+1),l=strlen(s+1);
    // printf("%d\n",l);
    for ( i=1 ; i<=l ; i++ )
    {
        for ( j=1 ; j<=bit ; j++ ) a[j]=a[j]*m;
        for ( j=1 ; j<=bit ; j++ )
            if ( a[j]>=D ) a[j+1]+=a[j]/D,a[j]%=D;
        while ( a[bit+1] ) bit++;
        a[1]+=mp[s[i]];
        for ( j=1 ; j<=bit ; j++ )
            if ( a[j]>=D ) a[j+1]+=a[j]/D,a[j]%=D;
        while ( a[bit+1] ) bit++;
    }
    // puts("Debug");
    // for ( j=bit ; j>=1 ; j-- ) printf("%d ",a[j]);
    while ( bit>1 || ( bit==1 && a[1]!=0 ) )
    {
        int x=0 ;
        for ( i=bit ; i>=1 ; i-- ) b[i]=(x*D+a[i])/n,x=(x*D+a[i])%n;
        d[++r]=x;
        for ( i=1 ; i<=bit ; i++ ) a[i]=b[i],b[i]=0;
        while ( !a[bit] && bit>=1 ) bit--;
        // printf("%d\n",bit);
    }
    if ( r==0 ) puts("0");
    else
    {
        while ( r ) putchar(w[d[r--]]); puts("");
    }
    return;
}
 
int main ()
{
    int i , j=-1 ;
    for ( i='0' ; i<='9' ; i++ ) mp[i]=++j,w[j]=i;
    for ( i='A' ; i<='Z' ; i++ ) mp[i]=++j,w[j]=i;
    for ( i='a' ; i<='z' ; i++ ) mp[i]=++j,w[j]=i;
    int T ;
    scanf("%d",&T);
    while ( T-- ) solve();
    return 0 ;
}

D. 最大的湖(dfs）

附上大佬代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
 
const int N = 110;
 
int n, m, k;
int mp[N][N];
 
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
 
bool ok(int x, int y){
    return 1 <= x && x <= n && 1 <= y && y <= m;
}
 
int dfs(int x, int y) {
    mp[x][y] = 0;
    int cnt = 1;
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i], yy = y + dy[i];
        if (ok(xx, yy) && mp[xx][yy] == 1) {
            cnt += dfs(xx, yy);
        }
    }
    return cnt;
}
 
int main() {
    int a, b;
    scanf("%d%d%d", &n, &m, &k);
    while (k--) {
        scanf("%d%d", &a, &b);
        mp[a][b] = 1;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (mp[i][j] == 1)
                ans = max(ans, dfs(i, j));
        }
    }
    printf("%d\n", ans);
    return 0;
}

E，砝码与天平 51Nod 1449（砝码称重）原题

https://blog.csdn.net/qq_38376279/article/details/72823404
https://blog.csdn.net/passer__/article/details/76818498

还要w次方的。既然砝码是w次方的并且一种就一个那么我们用w进制来想一下，每个砝码不就变成了 ——————1,10,100,1000之类的，重物化为w进制的或者重物直接满足这样的砝码想加，或者要再加上多个这种的砝码才能化为这种类似的砝码相加。
只要把有重物的一端（砝码+重物）化成w进制得数后只有0或者1数字表示那么就表示该重物能被称出来 ————>cout<<YES<<endl; 在往下写代码就简单了 我的一个AC代码贴在下边，可能会有比我更精简的但是问题应该描述清楚了.

#include<stdio.h>
  
int main()
{
    int t,a,b;
    scanf("%d",&t);
    while(t--){
        bool flag=true;
    scanf("%d%d",&a,&b);
    while(b)
    {
        int temp=b%a;
        if(temp==0||temp==1);
        else if(temp == a-1)
            b++;
        else
        {
            flag=false;
        }
        b=b/a; 
    }  
    if(flag==true)printf("YES\n");
    else printf("NO\n");
    }
    return 0;
}

F.得分（找规律）

其实就是通过找规律，发现一个O+1分，两个O+2分，依次递增直到出现X。。

#include<cstdio>
#include<iostream>
#include<cstring>
const int maxn=20000;
int main(){
    int t;
    char s[maxn];
    scanf("%d",&t);
    while(t--){
    int count=0,sum=0;
        scanf("%s",s);
    for(int i=0;i<strlen(s);i++){
       if(s[i]=='O'){
           sum++;
           count+=sum;
    }
        if(s[i]=='X'){
            sum=0;
        }
    }
    printf("%d\n",count);
    }
    return 0;
}

G.0和5

三张5可以整除3，那么9张5可以整除9 ，最后个位再补上0就可以
千万不要忘记0可以整除任何数
来自第一名大佬的代码https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40709489和另一个大佬的博客的代码https://blog.csdn.net/haohao_____/article/details/76098769

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int main()
{
    int n = 0;
    while (cin >> n)
    {
        //因为只出现0和5，所以就要求5的个数相加为9的倍数
        //因此 各个位的和 应该即为 5的倍数也是9的倍数
        //最小就是 5*9 = 45；9个5；
        //一般要有9*i个5
        vector<int> nVec(n);
        for (int i = 0; i < n; i++)
        {
            cin >> nVec[i];
        }
        int nNumOfFive = count(nVec.begin(), nVec.end(), 5);
        int nNumOfZero = n - nNumOfFive;
        if (nNumOfFive < 9)
        {
            if (nNumOfZero > 0)
            {
                cout << 0 << endl;
            }
            else
            {
                cout << -1 << endl;
            }
 
            continue;
 
        }
 
        if (nNumOfZero <1)
        {
            //必须要有一个0
            cout << -1 << endl;
            continue;
        }
        //能组成可行解的5的最大个数,nmaxnumoffive肯定大于9的
        //前面已经把小于9的情况排除了
        int nMaxNumOfFive = nNumOfFive / 9*9;
        //最大的数就是把所有的无方前面，所有的0放后边
        //这是就要求大数了，反而用字符串表示更容易点
        string str(nMaxNumOfFive, '5');
        str.append(nNumOfZero, '0');
        cout << str << endl;
    }
    return 0;
}

#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
int n,x,n5,n0;
int main(){
    scanf("%d",&n);
    fo(i,1,n){
        scanf("%d",&x);
        if (x) n5++;else n0++;
    }
    if (!n0){
        printf("-1\n");
        return 0;
    }
    n5=n5/9*9;
    fo(i,1,n5) putchar('5');
    if (n5) fo(i,1,n0) putchar('0');else putchar('0');
    putchar('\n');
}