[原创]2016女生赛 【(7+2)/10】
2017-07-24 20:01:34 Tabris_ 阅读数:357
博客爬取于2020-06-14 22:39:31
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。https://blog.csdn.net/qq_33184171/article/details/76037429
感觉今天都好没状态啊。
dalao题解
A HDU 5702 Solving Order —————————————————————————————————————— 结构体排序没什么好说的。。
B HDU 5703 Desert —————————————————————————————————————— 给你一个整数,问你划分方法有多少种,然后用二进制输出,{1,2}{2,1}算两种
退了一下,发现 结果就是2 n − 1 2^{n-1} 2 n − 1
所以输出个1 1 1 ,和n − 1 n-1 n − 1 个0 0 0 就行了
C HDU 5704 Luck Competition —————————————————————————————————————— n(2~100)个人参加一个游戏, 每个人选择1~100范围的数。 然后得到所有数的平均数,再*=2/3,设得到的数为m。 如果一个人选的数,比m小,且相距m最为接近,那么其便在所有选数相同的人中等概率中奖。
现在,我们也参加比赛,其他n-1个人所选择的数也已经确定了,并且我们知道。 问你,选什么数拥有最高中奖率,并输出。
数据量比较小,暴力枚举然后在模拟计算就行了
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 # include <bits/stdc++.h> using namespace std; int vis[150]; int main() { int t; scanf("%d",&t); while(t--) { memset(vis,0,sizeof(vis)); int n; scanf("%d",&n); for(int i=1;i<=n-1;i++) { int x; scanf("%d",&x); vis[x]++; } double P=-1; int output=-1; for(int ans=100;ans>=0;ans--) { vis[ans]++; int sum=0; for(int j=0;j<=100;j++) { sum+=vis[j]*j; } double ave=sum; ave=(ave/(double)n); ave*=2; ave=ave*1.0/3.0; if(ans<=ave) { int pos; for(int j=(int)ave;j>=0;j--) { if(vis[j]>0) { pos=j; break; } } if(pos==ans) { double pp=1/(double)vis[ans]; if(pp>P) { P=pp; output=ans; } } else { if(0>P) { P=0; output=ans; } } } vis[ans]--; } printf("%d %.2f\n",output,P); } }
D HDU 5705 Clock —————————————————————————————————————— 给你一个时间,问你下一次时针和分针夹角为a度的时刻是多少,如果不是整数则把秒数向下取整
暴力模拟即可,
为了方便比较 可以扩大倍数,使得时针1s动1个单位
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 # include <bits/stdc++.h> # define maxs 20002020 # define mme(i,j) memset(i,j,sizeof(i)) using namespace std; # define abs(x) ((x)<0?-(x):(x)) int deg(int &h,int &m,int &s){ int hh = (h*60*60+m*60+s); int mm = (h*60*60+m*60+s)*12; hh %= 720*60; mm %= 720*60; int t = abs(hh-mm); return min(t,720*60-t); } void add1(int &h,int &m,int &s){ s++; if(s == 60){ m++; s=0; } if(m == 60) { h++; m=0; } if(h == 12){ h = 0; } } int main(){ // h 1/720 1 // m 1/60 12 // s 1 720 int _ = 1,kcase=0; int h,m,s,x,p,tp,th,tm,ts; while(~scanf("%d:%d:%d",&h,&m,&s)){ scanf("%d",&x); x*=120; p = deg(h,m,s); while(true){ th=h,tm=m,ts=s; add1(h,m,s); tp = deg(h,m,s); if(tp == x) break; if(tp<x&&p>x){ h=th,m=tm,s=ts; break; } if(x<tp&&p<x){ h=th,m=tm,s=ts; break; } p=tp; // printf("%d:%d:%d %d - %d\n",h,m,s,tp,x); } printf("Case #%d: %02d:%02d:%02d\n",++kcase,h,m,s); } return 0; }
E HDU 5706 GirlCat —————————————————————————————————————— 一个n*m的网格,每个格子有一个字母 ,问你能构成的girl和cat的个数
爆搜即可
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 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 # include <bits/stdc++.h> # define maxs 202002 using namespace std; int ok; int n,m; char a[1005][1005]; int fx[4]={0,0,1,-1}; int fy[4]={1,-1,0,0}; void Dfs(int x,int y,int num) { if(num==0)if(a[x][y]!='g')return ; if(num==1)if(a[x][y]!='i')return ; if(num==2)if(a[x][y]!='r')return ; if(num==3)if(a[x][y]!='l')return ; if(num==3) { ok++; return ; } for(int i=0;i<4;i++) { int xx=x+fx[i]; int yy=y+fy[i]; if(xx>=0&&x<n&&yy>=0&&yy<m) { Dfs(xx,yy,num+1); } } } void Dfs2(int x,int y,int num) { if(num==0)if(a[x][y]!='c')return ; if(num==1)if(a[x][y]!='a')return ; if(num==2)if(a[x][y]!='t')return ; if(num==2) { ok++; return ; } for(int i=0;i<4;i++) { int xx=x+fx[i]; int yy=y+fy[i]; if(xx>=0&&x<n&&yy>=0&&yy<m) { Dfs2(xx,yy,num+1); } } } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=0;i<n;i++)scanf("%s",a[i]); int output=0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(a[i][j]=='g') { ok=0; Dfs(i,j,0); output+=ok; } } } printf("%d ",output); output=0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(a[i][j]=='c') { ok=0; Dfs2(i,j,0); output+=ok; } } } printf("%d\n",output); } }
F HDU 5707 Combine String —————————————————————————————————————— 给你三个字符串,问你能不能将a,b合并成c,且a,b字符串的字母顺序不被改变
设f[i][j] 表示当前,到达a[i],b[j]的时候,能不能凑成c[0~i+j-1],
转移的时候就是
i f ( a [ i − 1 ] = = c [ i + j − 1 ] ) f [ i ] [ j ] ∣ ( 位或 ) = f [ i − 1 ] [ j ] ; i f ( b [ j − 1 ] = = c [ i + j − 1 ] ) f [ i ] [ j ] ∣ ( 位或 ) = f [ i ] [ j − 1 ] ; if(a[i-1]==c[i+j-1]) f[i][j]\Big |(位或)=f[i-1][j];\\ if(b[j-1]==c[i+j-1]) f[i][j]\Big |(位或)=f[i][j-1]; i f ( a [ i − 1 ] == c [ i + j − 1 ]) f [ i ] [ j ] ( 位或 ) = f [ i − 1 ] [ j ] ; i f ( b [ j − 1 ] == c [ i + j − 1 ]) f [ i ] [ j ] ( 位或 ) = f [ i ] [ j − 1 ] ;
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 # include<bits/stdc++.h> typedef long long int LL; using namespace std; # define abs(x) ((x)>0?(x):-(x)) const int N = 100000+7; const int M = 10000000+7; /***************************************************/ char a[2222],b[2222],c[2222]; int f[2222][2222]; int main(){ while(~scanf("%s",a)){ scanf("%s",b); scanf("%s",c); int la=strlen(a); int lb=strlen(b); int lc=strlen(c); if(lc!=la+lb){ puts("No"); continue; } memset(f,0,sizeof(f)); f[0][0]=1; for(int i=0;i<=la;i++)for(int j=0;j<=lb;j++){ if(i==0&&j==0) continue; if(i>0&&a[i-1]==c[i+j-1]) f[i][j] |=f[i-1][j]; if(j>0&&b[j-1]==c[i+j-1]) f[i][j] |=f[i][j-1]; } puts(f[la][lb]?"Yes":"No"); } return 0; }
G HDU 5708 Alice and Bob —————————————————————————————————————— 两个人走格子,从(1,1)开始走 ,每次可以从(x,y)走到(x+1,y),(x,y+1),(x+k,y+k) 轮到谁的时候不能走了 就输了. 两个人足够聪明 然后问你谁能赢,Alice先
手写了几组k,然后发现有一个规律, 然后就打表观察了下 ,然后就总结了下规律然后AC.了…
这个规律有点不好描述 自己看吧 打表代码为solve()函数
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 # include <bits/stdc++.h> # define maxs 20002020 # define mme(i,j) memset(i,j,sizeof(i)) using namespace std; # define abs(x) ((x)<0?-(x):(x)) int a[111][111],b[111][111]; void solve(){ int n = 20; int m = 20; int k = 4; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i][j]==0){ a[i][j+1]=1; a[i+1][j]=1; a[i+k][j+k]=1; } } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++) printf(" %d",a[i][j],i+j); puts(""); } return ; } int main(){ // solve(); int _ = 1,q,k,n,m; for(scanf("%d",&_);_--;){ scanf("%d%d",&q,&k); for(int i=1;i<=q;i++){ scanf("%d%d",&n,&m); if(n<m) swap(n,m); int flag = m/(k+1); if(k == 1){ if(n%2==0||m%2==0) puts("Alice"); else puts("Bob"); } else { if(m%(k+1)==0||(m-flag+n)&1) puts("Alice"); else puts("Bob"); } } } return 0; }
H HDU 5709 Claris Loves Painting —————————————————————————————————————— 有n(<=1e5)个点的树,每个点都有颜色(颜色可能重复),有m(<=1e5)个询问,每次询问(x,d)问在x的子树中,与x的距离不超过d的节点有多少种不同的颜色。强制要求在线。
维护两颗线段树,并还要有合并的操作,不是特别懂… 看claris的博客吧
I HDU 5710 Digit-Sum —————————————————————————————————————— 我们要找出最小的正整数n满足—— aS(n)==b S(2n) a,b的范围都在[1,100] s(x)为x的所有位的和
首先能明确的是
s ( 2 n ) = 2 s ( n ) − 9 L s(2n) = 2s(n)-9L s ( 2 n ) = 2 s ( n ) − 9 L ___L 为 n 里面大于 5 的数字的个数 L为n里面大于5的数字的个数 L 为 n 里面大于 5 的数字的个数
因为大于5 5 5 就会进位,相当于− 10 + 1 = 9 -10+1 = 9 − 10 + 1 = 9
所以有
a × s ( n ) = b × s ( 2 n ) = > a × s ( n ) = b × ( 2 s ( n ) − 9 L ) = > ( 2 ∗ b − a ) × s ( n ) = b × 9 L = > L s ( n ) = 2 ∗ b − a b ∗ 9 a\times s(n) =b\times s(2n) \\ => a\times s(n) = b\times (2s(n)-9L)\\=>(2*b-a)\times s(n) = b\times9L\\=>\dfrac{L}{s(n)} = \dfrac{2*b-a}{b*9} a × s ( n ) = b × s ( 2 n ) => a × s ( n ) = b × ( 2 s ( n ) − 9 L ) => ( 2 ∗ b − a ) × s ( n ) = b × 9 L => s ( n ) L = b ∗ 9 2 ∗ b − a
a = 2 b a=2b a = 2 b ,则L = 0 L=0 L = 0 ,S为任意值。可得最小的n = 1 n=1 n = 1 ;a > 2 b a>2b a > 2 b ,则L < 0 L<0 L < 0 ,矛盾!则无满足的n n n ,输出0 0 0 ;a < 2 b a<2b a < 2 b ,S = 9 b L 2 b − a ≤ 5 L S=\frac{9bL}{2b−a}≤5L S = 2 b − a 9 b L ≤ 5 L (至少有L个5),即必须满足b ≤ 5 a b≤5a b ≤ 5 a ,否则无满足的n,输出0。然后考虑数n的选取,
我们假设有l的长度是[0,4]范围,有L的长度是[5,9]范围
我们不妨假设答案n仅有长度为L,且每一位都是5 然后得到了把数位和sum分撒出去。
对于sum余下的数值,我们依次加到尾巴上。 如果sum最后把长度为L的字串都填充为‘9‘之后,还有剩余,那么在前面贪心填充。
J HDU 5711 Ingress —————————————————————————————————————— n(16)个点 m(n^2)条双向边 K(50)次hack机会 最远走L(2000)路程
每个点的初始点权为ai 每个点每hack一次点权下降bi
队友补的 我还不会 待补…