杭电校赛
递增数
Problem Description
Input
Output
Sample Input
Sample Output
参考AC代码(模拟数位dp)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
| using namespace std; int len; string num; int fun(int n,int po) { int sum=0; if(po==len) return 1; for(int i=n;i<=9;i++) sum+=fun(i,po+1); return sum; } int check() { for(int i=0;i<len-1;i++) if(num[i]-'0'>num[i+1]-'0') return 0; return 1; } int main() { int t; cin>>t; while(t--) { cin>>num; len=num.length(); int sum=0; for(int i=0;i<num.length();i++) { if(i==0) { for(int j=0;j<num[i]-'0';j++) sum+=fun(j,i+1); } else { if(num[i-1]-'0'>num[i]-'0') break; for(int j=num[i-1]-'0';j<num[i]-'0';j++) num+=fun(j,i+1); } } if(len==1||check()) cout<<sum<<endl; else cout<<sum-1<<endl; } return 0; }
|
参考AC代码（数位dp）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
| using namespace std; int dp[10][10],A[10]; //dp[i][j]表示长度为i 最高位为j的递增数个数 void init() { memset(dp,0,sizeof(dp)); for(int i=0;i<=9;i++) dp[1][i]=1; for(int i=2;i<=9;i++) for(int j=0;j<=9;j++) for(int k=j;k<=9;k++) dp[i][j]+=dp[i-1][k]; } int sum(int a) { int ans=0,m=0; while(a) { A[m++]=a%10; a/=10; } for(int i=1;i<m;i++) for(int j=1;j<=9;j++) ans+=dp[i][j]; for(int i=1;i<A[m-1];i++) ans+=dp[m][i]; for(int i=m-1;i>=1;i++) { for(int j=A[i];j<=A[i-1];j++) ans+=dp[i][j]; if(A[i]-A[i-1]>0) break; } return ans; } int main() { init(); int t; cin>>t; while(t--) { int x; cin>>x; cout<<sum(x+1)<<endl; } return 0; }
|
思路
模拟数位dp的思想。
fun函数参数代表的是从左往右数第po个位置存放的数字是n，功能是利用递归求出比他小的所有递增数。
接着挨个判断该数。例如54321，第一步fun函数会求出比50000小的所有递增数。接着算大于50000的递增数，从第二位开始，只要有一位不满足递增数直接break。
后面不会再有满足条件的递增数了，否则把所有比该位小，大于等于前一位的数带入到fun函数中计算。
例如56789，再求出比50000小的递增数后会代入函数fun（5，2）fun（6，3）·······实际求的就是55000和56600的递增数。
洗衣服
Problem Description
Input
Output
Sample Input
Sample Output
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
| using namespace std; int solve(int k) { int ans=0; int temp1=k/10,temp2=k%10; ans+=temp1*4; if(temp2==0) return ans; if(temp2<=3) ans+=2; if(temp2>3&&temp2<=6) ans+=3; else ans+=4; return ans; } int main() { int t; cin>>t; while(t--) { int n,m; cin>>n>>m; int temp1=m/3,temp2=m%3; int ans,ans1,ans2,ans3; ans1=temp1+solve(n-m+temp2); ans2=temp1+1+solve(n-m); ans=min(ans1,ans2); for(int i=1;i<10;i++) { if(temp1-i<0) break; ans3=temp1-i+solve(n-m+temp2+i*3); ans=min(ans,ans3); } cout<<ans<<endl; } return 0; }
|
思路
贪心即可。
首先写出solve函数：大于10的情况下先考虑10的情况 接下来考虑剩下的衣服。若小于3使用快速洗，若在3和6中间使用标准洗，若大于6则使用大物洗。
下面考虑三种情况：首先求出m件单脱水除以3的除数和余数。第一种情况：把余数放入到清洗的范围里。第二种情况：余下的数继续使用单脱水，剩下的
n-m件衣服使用清洗。第三种情况：把余数+3*k放到清洗的范围里，依次比较求出最小值。三种情况的最小值即为所求。
炉石
Problem Description
Input
Output
Sample Input
Sample Output
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
| using namespace std; map<string,int>mp; string op[4]={"Fire","Ice","Dog","Evolved"}; int flag; int n,m; void dfs(int harm,int left,int buff) { if(harm>=m) { flag=1; return ; } for(int i=0;i<=3;i++) { if(mp[op[i]]) { if(i==2&&left>=2) { mp[op[i]]--; dfs(harm,left-2,buff+1); mp[op[i]]++; } if(i==3&&left>=4) { mp[op[i]]--; dfs(harm,left-4,buff+2); mp[op[i]]++; } if(i==0&&left>=4) { mp[op[i]]--; dfs(harm+buff+6,left-4,buff); mp[op[i]]++; } if(i==1&&left>=2) { mp[op[i]]--; dfs(harm+buff+3,left-2,buff); mp[op[i]]++; } } } } int main() { int t; cin>>t; while(t--) { mp.clear(); cin>>n>>m; string st; for(int i=1;i<=n;i++) { cin>>st; mp[st]++; } flag=0; dfs(0,10,0); if(flag) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }
|
思路
深搜，加4层判断即可。
利用map的映射统计出每个字符串的个数。深搜中：若造成的伤害大于等于剩余的血量退出函数。接下来进行四层判断，需要额外
注意四种技能都在特定的条件下才能使用。
