hihocoder编程练习赛49
A
描述
在CSS中我们可以用井号(#)加6位十六进制数表示一种颜色，例如#000000是黑色，#ff0000是红色，#ffd700是金色。
同时也可以将六位颜色#RRGGBB简写为#RGB三位颜色。例如#000与#000000是相同的，#f00与#ff0000是相同的，#639与#663399是相同的。
对于两个颜色#abcdef和#ghijkl，我们定义其距离是(ab - gh)2 + (cd - ij)2 + (ef - kl)2。(其中ab, cd, ef, gh, ij, kl都是十六进制数，也即0~255的整数)
给定一个六位颜色#abcdef，请你求出距离它最近的三位颜色#rgb。
输入
#abcdef
其中abcdef是’0’-‘9’或’a’-‘f’。
输出
距离输入颜色最近的#rgb
样例输入
#40e0d0
样例输出
#4dc
参考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
| using namespace std; string s; void solve(int x){ int Min=inf,id=-1; for(int i=0;i<=15;i++){ int tmp=i*16+i; if(abs(tmp-x)<Min){ Min=abs(tmp-x); id=i; } } if(id<=9) cout<<id; else cout<<(char)('a'+id-10); } int tran(char op){ if(op>='0' && op<='9') return op-'0'; else return (int)(op-'a'+10); } int main(){ // freopen("input.txt","r",stdin); cin>>s; int num1=tran(s[1])*16+tran(s[2]); int num2=tran(s[3])*16+tran(s[4]); int num3=tran(s[5])*16+tran(s[6]); cout<<"#"; solve(num1),solve(num2),solve(num3); cout<<endl; return 0; }
|
思路
每2个一组 划分出三个数字 并转换为10进制记为data
暴力00-ff的16种情况 大小为16×i+i 找出与data差值的最小值 输出对应的i即可
注意十六进制的转换即可
B
描述
给定N个整数A1, A2, … AN，小Hi希望从中选出M个整数，使得任意两个选出的整数的差都是K的倍数。
请你计算有多少种不同的选法。由于选法可能非常多，你只需要输出对1000000009取模的结果。
输入
第一行包含三个整数N、M和K。
第二行包含N个整数A1, A2, … AN。
对于30%的数据，2 ≤ M ≤ N ≤ 10
对于100%的数据，2 ≤ M ≤ N ≤ 100 1 ≤ K, Ai ≤ 100
输出
一个整数表示答案。
样例输入
5 3 2
1 2 3 4 5
样例输出
1
参考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
| using namespace std; const LL mod = 1000000009; int n,m,k; int a[maxn],hashh[maxn],c[maxn][maxn]; void init(){ mm(c,0); c[0][0]=1; for(int i=0;i<maxn;i++){ c[i][0]=c[i][i]=1; for(int j=1;j<i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod; } } int main(){ // freopen("input.txt","r",stdin); init(); while(scanf("%d%d%d",&n,&m,&k)!=EOF){ mm(hashh,0); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); a[i]%=k; hashh[a[i]]++; } LL ans=0; for(int i=0;i<k;i++){ int num=hashh[i]; if(num<m) continue; ans=(ans+c[num][m])%mod; } ans%=mod; printf("%d\n",ans); } return 0; }
|
思路
每个数字都mod k
余数在0-(k-1)这k个数字中 取出相同数字做差肯定是k的倍数 因为相同余数相减后为0 必为k的倍数
所以答案就是每个数字的个数n取Cnk的组合数 最后再相加
题目要mod 1e9 所以组合数要取模 三种方法均可以
C
描述
给定一个NxN的方格矩阵迷宫，每个格子中都有一个整数Aij。最初小Hi位于迷宫左上角的格子A11，他每一步可以向右或向下移动，目标是移动到迷宫的出口——右下角ANN。
小Hi需要支付的代价包括路径中经过的所有格子中的整数之和，以及改变移动方向需要支付的代价。
小Hi第一次改变方向的代价是1，第二次的代价是2，第三次的代价是4，…… 第K次的代价是2K-1。
请你帮小Hi算出要离开迷宫代价最小的路径，并输出要支付的代价。
输入
第一行一个整数N。 (1 ≤ N ≤ 100)
以下N行每行N个整数，代表矩阵A。 (1 ≤ Aij ≤ 100)
输出
从左上角到右下角路径的最小的代价。
样例输入
3
1 3 5
1 1 2
5 1 1
样例输出
9
参考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
| using namespace std; int n; int mp[maxn][maxn]; LL dp[maxn][maxn][16][2]; void init(){ memset(dp,inf,sizeof dp); dp[1][1][0][0]=dp[1][1][0][1]=mp[1][1]; for(int i=2;i<=n;i++) dp[i][1][0][0]=dp[i-1][1][0][0]+mp[i][1]; for(int i=2;i<=n;i++) dp[1][i][0][1]=dp[1][i-1][0][1]+mp[1][i]; } int main(){ // freopen("input.txt","r",stdin); cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) cin>>mp[i][j]; } init(); for(int i=2;i<=n;i++){ for(int j=2;j<=n;j++){ for(int p=1;p<=15;p++){ dp[i][j][p][0]=min(dp[i][j][p][0],dp[i-1][j][p][0]+mp[i][j]); dp[i][j][p][0]=min(dp[i][j][p][0],dp[i-1][j][p-1][1]+mp[i][j]+(1<<(p-1))); dp[i][j][p][1]=min(dp[i][j][p][1],dp[i][j-1][p][1]+mp[i][j]); dp[i][j][p][1]=min(dp[i][j][p][1],dp[i][j-1][p-1][0]+mp[i][j]+(1<<(p-1))); } } } LL ans=inf; for(int i=1;i<=15;i++){ ans=min(ans,dp[n][n][i][0]); ans=min(ans,dp[n][n][i][1]); } cout<<ans<<endl; return 0; }
|
思路
dp
dp[x][y][k][p]表示站在(x,y)的位置上 拐弯了k次 p为0表示向下 1表示向右
基本dp方程为：
Dp[i][j][s][d] = min(
dp[i-1][j][s][d] + A[i][j] 上面直走来的
dp[i-1][j][s-1][d^1]+ A[i][j] +(1<<(s-1)) 上面拐过来的
dp[i][j-1][s][d]+ A[i][j] 左面直走来的
dp[i][j-1][s-1][d^1] + A[i][j] +(1<<(s-1)) 左面拐过来的
)
注意处理好边界 这里先把第一行向右和第一列向下的情况先预处理出来 所以for里i和j从2开始 p从1开始
