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的结果 示例1 输入
2 5 4 输出 4 3 备注: 5分钱兑换为零钱，有以下4种换法： 1、5个1分 2、1个2分3个1分 3、2个2分1个1分 4、1个5分
ps：典型多重背包问题，注意循环条件，与状态转移方程
#include<bits/stdc++.h> using namespace std; const int mod=1e9+7; int w[13]={1,2,5,10,20,50,100,200,500,1000,2000,5000,10000}; int d[100005]; int n; int main() { int t; cin>>t; while(t--){ memset(d,0,sizeof d); cin>>n; d[0]=1; for(int i=0;i<13;i++){ for(int j=w[i];j<=n;j++){ d[j]=(d[j]+d[j-w[i]])%mod; } } cout<<d[n]<<endl; } return 0; }C——神奇的进制转换 题目描述 给出一个m进制下的数a，现在请输出a在n进制下的表示。 输入描述: 第一行一个整数T，代表有T组数据
接下来T行：
每一行有3个整数，分别表示m，n，a，其中2=<m<=62，2=<n<=62，a的位数不超过350位且a>=0，样例个数不超过400。 输出描述: 输出上述问题的答案，每个答案占一行。 示例1 输入
复制 1 10 2 3 输出
复制 11 备注: 每一位进制表示从小到大分别为
0~9, ‘A’~‘Z’, ‘a’~‘z’
#include<bits/stdc++.h> using namespace std; const int maxn = 2000; char str[maxn]; int start[maxn], ans[maxn], res[maxn]; int oldBase, newBase; int getNum(char c) { if(c >= '0' && c <= '9') return c-'0'; if(c >= 'A' && c <= 'Z') return c-'A'+10; return c-'a'+36; } char getChar(int i) { if(i >= 0 && i <= 9) return i+'0'; if(i >= 10 && i <= 35) return i-10+'A'; return i-36+'a'; } void change() { start[0] = strlen(str); for(int i = 1;i <= start[0]; i++){ start[i] = getNum(str[i-1]); } } void solve() { memset(res,0,sizeof(res)); int y, i, j; while(start[0] >= 1){ y = 0; i = 1; ans[0] = start[0]; while(i <= start[0]){ y = y*oldBase+start[i]; ans[i++] = y/newBase; y %= newBase; } res[++res[0]] = y; i = 1; while(i <= ans[0] && !ans[i]) i++; memset(start,0,sizeof(start)); for(j = i; j <= ans[0]; j++) start[++start[0]] = ans[j]; memset(ans,0,sizeof(ans)); } } void output() { for(int i = res[0]; i >= 1; i--) printf("%c",getChar(res[i])); printf("\n"); } int main() { int t; scanf("%d",&t); while(t--){ scanf("%d%d%s",&oldBase,&newBase,str); change(); solve(); output(); } return 0; }简短版：
#include <bits/stdc++.h> #include<iostream> const int maxn=1e5+10; char str1[maxn],str2[maxn]; int t[maxn],a[maxn]; int n,m; void solve(){ int k; int len=strlen(str1); for(int 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(int 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(int 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; }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列。 输出描述: 输出最大的“湖”所包含的格子数目 示例1 输入
复制 3 4 5 3 2 2 2 3 1 2 3 1 1 输出
复制 4
PS：dfs经典题
#include<bits/stdc++.h> using namespace std; int n,m,k,sum=0,maxn=-1,r,c; int a[105][105]; int X[4]={1,-1,0,0},Y[4]={0,0,1,-1}; void dfs(int x,int j){ a[x][j]=0; sum++; int i; for(i=0;i<4;i++) { int nx=x+X[i],ny=j+Y[i]; if(nx<=n&&nx>=1&&ny<=m&&ny>=1&&a[nx][ny]==1) dfs(nx,ny); } } int main(){ cin>>n>>m>>k; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>r>>c; a[r][c]=1; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i][j]==1){ sum=0; dfs(i,j); maxn=max(maxn,sum); } } } cout<<maxn<<endl; return 0; }E——砝码和天平 题目描述 现在有很多砝码，质量为w的0次方、1次方……n次方，每个砝码都只有一个。还有一个天平，可以在两端放置砝码和重物。现在要用这些砝码搭配出相等于重物的质量m，也可以把若干个砝码和重物一起放在天平的一侧，来平衡这个天平。 输入描述: 第一行为一个整数T，代表有T组数据
接下来T行，每行有两个整数w,m (2 ≤ w ≤ 10^9, 1 ≤ m ≤ 10^9)。 输出描述: 如果能，输出YES，否则输出NO。 示例1 输入
复制 2 3 7 4 22 输出
复制 YES NO 备注: 对第一组样例，可以将重物和质量为3的砝码放到一个托盘中，质量为9和1的砝码放到另外一个托盘中。
第二组样例无论怎么搭配砝码和重物，也无法使天平两端达到平衡。 ps：暂时不会，代码先放着以后看吧
#include<bits/stdc++.h> using namespace std; int main(){ int w,m,t; cin>>t; while(t--){ cin>>w>>m; int flag=0; while(m){ if((m-1)%w==0) m--; else if((m+1)%w==0) m++; else if(m%w){ puts("NO"); flag=1; break; } m/=w; } if(flag==0){ puts("YES"); } } return 0; }G——0和5 题目描述
小C手中有n张牌，每张牌上有一个一位数的数，这个数字不是0就是5。 小C从这些牌在抽出任意张（不能抽0张），排成一行就组成了一个数。 使得这个数尽可能大，而且可以被90整除。
注意： 1.这个数没有前导0， 2.小C不需要使用所有的牌。
输入描述: 每个测试数据输入共2行。
第一行给出一个n，表示n张牌。(1<=n<=1000)
第二行给出n个整数a[0],a[1],a[2],…,a[n-1] (a[i]是0或5 ) 表示牌上的数字。 输出描述: 共一行，表示由所给牌组成的可以被90整除的最大的数，如果没有答案则输出”-1”（没有引号） 示例1 输入
复制 4 5 0 5 0 输出
复制 0
ps：数学题，5必须是9的倍数才能整除
#include<bits/stdc++.h> using namespace std; int main() { int num_zero = 0, num_five = 0; int n, x; cin >> n; while(n--) { cin >> x; if(x == 0) num_zero++; else num_five++; } if(num_zero == 0) { puts("-1"); return 0; } int ans = -1; for(int i = num_five; i >= 9; --i) { if(i % 9 == 0) { ans = i; break; } } if(ans == -1) cout << "0"; else { for(int i = 1; i <= ans; ++i) cout << "5"; for(int i = 1; i <= num_zero; ++i) cout << "0"; } return 0; }