中南林业科技大学第十一届程序设计大赛 牛客网

B 完全背包 链接：https://ac.nowcoder.com/acm/contest/910/B 来源：牛客网

题目描述 现有N元钱，兑换成小额的零钱，有多少种换法？币值包括1 2 5分，1 2 5角，1 2 5 10 20 50 100元。 (由于结果可能会很大，输出Mod 10^9 + 7的结果)

输入描述: 第一行输入一个整数T，代表有T组数据 接下来T行，每行输入1个数N，N = 100表示1元钱。(1 <= N <= 100000) 输出描述: 输出Mod 10^9 + 7的结果

备注: 5分钱兑换为零钱，有以下4种换法： 1、5个1分 2、1个2分3个1分 3、2个2分1个1分 4、1个5分

代码：

#include<bits/stdc++.h> using namespace std; int a[13]={1,2,5,10,20,50,100,200,500,1000,2000,5000,10000}; const int mod=1e9+7; long long dp[100001]; int main(){ ios::sync_with_stdio(0); int t;cin>>t; dp[0]=1; for(int i=0;i<13;++i) for(int j=a[i];j<=100000;++j)dp[j]=(dp[j]+dp[j-a[i]])%mod; while(t--){ int n;cin>>n; cout<<dp[n]<<endl; } return 0; }

C 模拟 进制转换 链接：https://ac.nowcoder.com/acm/contest/910/C 来源：牛客网

题目描述 给出一个m进制下的数a，现在请输出a在n进制下的表示。 输入描述: 第一行一个整数T，代表有T组数据 接下来T行： 每一行有3个整数，分别表示m，n，a，其中2=<m<=62，2=<n<=62，a的位数不超过350位且a>=0，样例个数不超过400。

偷懒直接套大数(。_。) 代码：

#include<bits/stdc++.h> #define MAXN 9999 #define MAXSIZE 1000 #define DLEN 4 using namespace std; class BigNum{ private: int a[MAXSIZE]; //可以控制大数的位数 int len; //大数长度 public: BigNum(){len=1;memset(a,0,sizeof(a));} BigNum(const int); BigNum(const char*); BigNum(const BigNum &); BigNum &operator=(const BigNum &); friend istream & operator>>(istream&, BigNum&); friend ostream& operator<<(ostream&, BigNum&); BigNum operator+(const BigNum &) const; BigNum operator-(const BigNum &) const; BigNum operator*(const BigNum &) const; BigNum operator/(const int &) const; BigNum operator^(const int &) const; int operator%(const int &) const; bool operator<(const BigNum& b)const{ if(len!=b.len)return len<b.len; for (int i=len-1;i>=0;--i)if(a[i]!=b.a[i])return a[i]<b.a[i]; return false; } bool operator>(const BigNum& b)const {return b<*this;} bool operator<=(const BigNum& b)const {return !(b<*this);} bool operator>=(const BigNum& b)const {return !(*this<b);} bool operator!=(const BigNum& b)const {return b<*this||*this<b;} bool operator==(const BigNum& b)const {return !(b<*this)&&!(*this<b);} void print(){ printf("%d",a[len-1]); for(int i=len-2;i>=0;--i)printf("d",a[i]); putchar('\n'); }; }; BigNum::BigNum(const int b){ int c,d=b; len=0; memset(a,0,sizeof(a)); while(d>MAXN){ c=d-(d/(MAXN+1))*(MAXN+1); d=d/(MAXN+1); a[len++]=c; } a[len++]=d; } BigNum::BigNum(const char*s){ int t,k,index,l,i; memset(a,0,sizeof(a)); l=strlen(s); len=l/DLEN; if(l%DLEN)++len; index=0; for(i=l-1;i>=0;i-=DLEN){ t=0; k=i-DLEN+1; if(k<0)k=0; for(int j=k;j<=i;j++)t=t*10+s[j]-'0'; a[index++]=t; } } BigNum::BigNum(const BigNum & T):len(T.len){//拷贝构造函数 memset(a,0,sizeof(a)); for(int i=0;i<len;++i)a[i]=T.a[i]; } BigNum & BigNum::operator=(const BigNum & n){//重载赋值运算符，大数之间进行赋值运算 len=n.len; memset(a,0,sizeof(a)); for(int i=0;i<len;++i)a[i]=n.a[i]; return *this; } BigNum BigNum::operator+(const BigNum & T) const{ BigNum t(*this); int i,big; //位数 big=T.len>len?T.len:len; for(i=0;i<big;++i){ t.a[i]+=T.a[i]; if(t.a[i]>MAXN){ ++t.a[i+1]; t.a[i]-=MAXN+1; } } if(t.a[big]!=0)t.len=big+1; else t.len=big; return t; } BigNum BigNum::operator-(const BigNum & T) const{ int i,j,big; bool flag; BigNum t1,t2; if(*this>T){ t1=*this; t2=T; flag=0; } else{ t1=T; t2=*this; flag=1; } big=t1.len; for(i=0;i<big;++i) if(t1.a[i]<t2.a[i]){ j=i+1; while(t1.a[j]==0)++j; --t1.a[j--]; while(j>i)t1.a[j--]+=MAXN; t1.a[i]+=MAXN+1-t2.a[i]; } else t1.a[i]-=t2.a[i]; t1.len=big; while(t1.a[len-1]==0&&t1.len>1)--t1.len,--big; if(flag)t1.a[big-1]=0-t1.a[big-1]; return t1; } BigNum BigNum::operator*(const BigNum & T) const{ BigNum ret; int i,j,up; int temp,temp1; for(i=0;i<len;++i){ up=0; for(j=0;j<T.len;++j){ temp=a[i]*T.a[j]+ret.a[i+j]+up; if(temp>MAXN){ temp1=temp-temp/(MAXN+1)*(MAXN+1); up=temp/(MAXN+1); ret.a[i+j]=temp1; }else up=0,ret.a[i + j]=temp; } if(up!=0)ret.a[i+j]=up; } ret.len=i+j; while(ret.a[ret.len-1]==0&&ret.len>1)--ret.len; return ret; } BigNum BigNum::operator/(const int & b) const{ BigNum ret; int i,down=0; for(i=len-1;i>=0;--i){ ret.a[i]=(a[i]+down*(MAXN+1))/b; down=a[i]+down*(MAXN+1)-ret.a[i]*b; } ret.len=len; while(ret.a[ret.len-1]==0&&ret.len>1)--ret.len; return ret; } int BigNum::operator %(const int & b) const{ int i,d=0; for (i=len-1;i>=0;--i)d=((d*(MAXN+1))%b+a[i])%b; return d; } BigNum BigNum::operator^(const int & n) const{ BigNum t,ret(1); if(n<0)exit(-1); if(n==0)return 1; if(n==1)return *this; int m=n,i; while(m>1){ t=*this; for(i=1;i<<1<=m;i<<=1)t=t*t; m-=i; ret=ret*t; if(m==1)ret=ret*(*this); } return ret; } string tf(int x,int y,string s){ string res=""; long long len=s.size(); BigNum sum(0); for(int i=0;i<len;++i){ if(s[i]>='0'&&s[i]<='9')sum=sum*x+s[i]-'0'; else if(s[i]>='A'&&s[i]<='Z')sum=sum*x+s[i]-'A'+10; else sum=sum*x+s[i]-'a'+36; } while(sum>0){ char tmp=sum%y; sum=sum/y; if(tmp<=9)tmp+='0'; else if(tmp<=35)tmp=tmp-10+'A'; else tmp=tmp-36+'a'; res=tmp+res; } if(res.length()==0)res="0"; return res; } int main(){ ios::sync_with_stdio(0); int t;cin>>t; while(t--){ int n,m;string a;cin>>n>>m>>a; cout<<tf(n,m,a)<<endl; } return 0; }

D BFS 链接：https://ac.nowcoder.com/acm/contest/910/D 来源：牛客网

题目描述 农场主约翰的农场在最近的一场风暴中被洪水淹没，这一事实只因他的奶牛极度害怕水的消息而恶化。 然而，他的保险公司只会根据他农场最大的“湖”的大小来偿还他一笔钱。

农场表示为一个矩形网格，有N（1≤N≤100）行和M（1≤M≤100）列。网格中的每个格子要么是干的，要么是被淹没的，而恰好有K（1≤K≤N×M）个格子是被淹没的。正如人们所期望的，一个“湖”有一个中心格子，其他格子通过共享一条边（只有四个方向，对角线不算的意思）与之相连。任何与中央格子共享一条边或与中央格子相连的格子共享一条边的格子都将成为湖的一部分。

输入描述: 第一行有三个整数N,M,K，分别表示这个矩形网格有N行，M列，K个被淹没的格子。

接下来K行，每一行有两个整数R,C。表示被淹没的格子在第R行，第C列。 输出描述: 输出最大的“湖”所包含的格子数目

代码：

#include<bits/stdc++.h> using namespace std; int mp[105][105],vis[105][105],f[4][2]={1,0,0,1,-1,0,0,-1},ans=0,n,m,k; struct st{ int x,y; }p[105*105]; void bfs(st a){ queue<st>q; vis[a.x][a.y]=1; q.push(a); int cnt=1; while(!q.empty()){ st now=q.front();q.pop(); for(int i=0;i<4;++i){ int nx=now.x+f[i][0],ny=now.y+f[i][1]; if(nx<1||ny<1||nx>n||ny>m||vis[nx][ny]||mp[nx][ny]==0)continue; vis[nx][ny]=1; q.push({nx,ny}); ++cnt; } } ans=max(ans,cnt); } int main(){ ios::sync_with_stdio(0); cin>>n>>m>>k; for(int i=0;i<k;++i){ int x,y;cin>>x>>y; mp[x][y]=1; p[i]={x,y}; } for(int i=0;i<k;++i)if(vis[p[i].x][p[i].y]==0)bfs(p[i]); cout<<ans; return 0; }

E 思维 砝码 链接：https://ac.nowcoder.com/acm/contest/910/E 来源：牛客网

题目描述 现在有很多砝码，质量为w的0次方、1次方……n次方，每个砝码都只有一个。还有一个天平，可以在两端放置砝码和重物。现在要用这些砝码搭配出相等于重物的质量m，也可以把若干个砝码和重物一起放在天平的一侧，来平衡这个天平。 输入描述: 第一行为一个整数T，代表有T组数据

接下来T行，每行有两个整数w,m (2 ≤ w ≤ 10^9, 1 ≤ m ≤ 10^9)。 输出描述: 如果能，输出YES，否则输出NO。

思路： 砝码数看作w进制，1表示用1个。将m化为w进制。 因为左右都能放，且每种一个。 m当出现某位置是1,砝码放在另一边。 是w-1 可以进一位，相当于该砝码放在同一边，在用进一位的砝码放在另一边。 代码：

#include<bits/stdc++.h> using namespace std; namespace io{ const int SIZE=1e7+10; char inbuff[SIZE]; char *l,*r; inline void init(){ l=inbuff,r=inbuff+fread(inbuff,1,SIZE,stdin); } inline char gc(){ if(l==r)init(); return(l!=r)?*(l++):EOF; } void read(int &x){ x=0;char ch=gc();int f=0; while(!isdigit(ch))f|=ch=='-',ch=gc(); while(isdigit(ch))x=x*10+(ch^48),ch=gc(); x=f?-x:x; } }using io::read; int main(){ int t;read(t); while(t--){ int w,m,ok=0;read(w),read(m); while(m){ while(m%w==0)m/=w; if(m==1)break; if((m+1)%w==0)++m; else if((m-1)%w==0)--m; else{ puts("NO"),ok=1; break; } } if(ok)continue; puts("YES"); } return 0; }