D题出了一点锅,抱歉给大家带来的不便,现在已经rejudge了,可以在比赛的提交页面查看自己之前的提交。
小H的小猫
瞎枚举全排列一下就行了。
时间复杂度:
发现答案一定是两根 在坐标轴上 的柱子间的连线。
可以用两点之间线段最短来证明。
枚举一下就好了。
如果 轴或 轴上没有柱子,则无解。
时间复杂度:
假设有最优解(如果有解的话)所连的柱子为 和 ,则有 。
由于 和 是相互独立的,所以 为在 轴上纵坐标最小的柱子,而 为在 轴上横坐标最小的柱子。
排个序就好了。
时间复杂度:
如果卡卡常没准能过
为了防止卡常能过出题人用心良苦地加上了 空间限制,从此卡常再见。
但这样无法防止部分分 轴和 轴上均只有 根柱子 能过 好像这样在这个部分分本来时间复杂度就是对的。
- 所有柱子均在 轴和 轴上
这块建议先跳过,最后看你才能明白。
就是没想到答案一定是两根 在坐标轴上 的柱子间的连线但其它都想到了(还有一部分详见无特殊限制时的解决方法)的部分分。
时间复杂度:
- 轴和 轴上均只有 根柱子
用 的做法扫一遍做就行了。
时间复杂度:
发现在 的部分分中,求最小值这步可以 扫一遍就行了,不用 排序,所以直接扫一遍就行了。强行凑部分分系列
时间复杂度:
#include<bits/stdc++.h> using namespace std; inline int read(){ int res=0; bool zf=0; char c; while(((c=getchar())<'0'||c>'9')&&c!='-'); if(c=='-')zf=1; else res=c-'0'; while((c=getchar())>='0'&&c<='9')res=(res<<3)+(res<<1)+c-'0'; if(zf)return -res; return res; } const double eps=1e-6; signed main(){ int n=read(); double m1=3e9,m2=3e9; while(n--){ double x,y; scanf("%lf%lf",&x,&y); if(fabs(x)<eps)m2=min(m2,y); if(fabs(y)<eps)m1=min(m1,x); } if(m1>2e9||m2>2e9){ puts("Poor Little H!"); return 0; } printf("%.10lf",sqrt(m1*m1+m2*m2)); return 0; }
小H的数列
对于前 分,根据题意依次求值即可。
现在开始推到原来的公式:
由递推关系可以写到:
,
因为第二个式子不可能为 ,所以:
即 。
注意到:
,即 就等于 。
因此,只需要一个高精模板即可。
代码:
#include<bits/stdc++.h> using namespace std; char a1[1000001],b1[1000001]; int a[1000001],b[1000001],i,x,len,j,c[1000001]; int main(){ cin>>a1; int lena=strlen(a1); for(int i=0;i<lena;i++) b1[i]=a1[i]; int lenb=strlen(b1); for(i=1;i<=lena;i++) a[i]=a1[lena-i]-'0'; for(i=1;i<=lenb;i++) b[i]=b1[lenb-i]-'0'; for(i=1;i<=lenb;i++){ for(j=1;j<=lena;j++){ c[i+j-1]+=a[j]*b[i]; } } for(i=1;i<lena+lenb;i++){ if(c[i]>9){ c[i+1]+=c[i]/10; c[i]%=10; } } len=lena+lenb; while(c[len]==0&&len>1) len--; for(i=len;i>=1;i--) cout<<c[i]; return 0; }
小H的糖果
- :
瞎爆搜一下就行了。
注意特判 ,此时最小次数为 (使用 次 无中生有)。
时间复杂度:
- :
剪枝一下,记忆化或 一下就好了。
时间复杂度:
- 所有的 皆相同且
和上面的做法类似,只需要发现记忆化或 可以过单组 就行了。
读入 然后记忆化或 一下。
递推式:
时间复杂度:
容易发现 。
若 ,输出 。
否则,发现可以贪心,从 倒着考虑,也即若原变换路径为 ,则有 。
可以设计出以下算法:
每次 加上 , 变为 ,如果 就退出循环,最后输出 即可。
时间复杂度:
正难则反。
考虑当 时的算法。
发现也就是将题目转化为:
有一个初始值为 的变量 ,每次操作可以 除以 (如果能整除)(称为 仓陈度暗) 或 减去 (称为 有生中无),求使 变为 的的最少步数。
做法就显然了:
初始 。
若 则 加上 (因为后面只能用 有生中无,也即只能一直减 ),退出循环。
否则, 加上 除以 的余数(有生中无 的余数次)加 (仓陈度暗),再将 设置为 除以 向下取整后的值,并继续循环。
时间复杂度:
#include<bits/stdc++.h> #define int long long using namespace std; inline int read(){ int res=0; bool zf=0; char c; while(((c=getchar())<'0'||c>'9')&&c!='-'); if(c=='-')zf=1; else res=c-'0'; while((c=getchar())>='0'&&c<='9')res=(res<<3)+(res<<1)+c-'0'; if(zf)return -res; return res; } signed main(){ int T=read(); while(T--){ int k=read(),n=read(),ans=0; if(k==1){ printf("%lld\n",n-1); continue; } while(n>=k){ ans+=n%k+1; n/=k; } ans+=n-1; printf("%lld\n",ans); } return 0; }
旅游
第四题是floyd的考察,做法是每次消毒一个点以这个点为中间转移点宽松一次,虽然q范围大,但是一共只有n个点,由于会重复消毒,所以可以用标记数据标记一下, 没宽松过才宽松,复杂度是
#include<bits/stdc++.h> using namespace std; inline int read() { int x = 0 , f = 1 ; char c = getchar() ; while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; } while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; } return x * f ; } int f[400][400]; int v[1000]; int n,m,q,s; void floyd(int k) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(f[i][j]>f[i][k]+f[k][j]) { f[i][j]=f[i][k]+f[k][j]; } } } } int main() { //freopen("10.in","r",stdin); //freopen("10.out","w",stdout); cin>>n>>m>>s>>q; v[s]=1; floyd(s); memset(f,0x3f,sizeof f); for(int i=1;i<=n;i++) { f[i][i]=0; } for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); f[x][y]=min(z,f[x][y]); } floyd(s); while(q--) { int xx,yy; // cin>>x>>y; scanf("%d%d",&xx,&yy); if(xx==1) { if(!v[yy]) { floyd(yy); }v[yy]=1; }else { if(f[s][yy]==0x3f3f3f3f||v[yy]==0) { puts("-1"); continue; }else { printf("%d\n",f[s][yy]); s=yy; } } } return 0; }
全部评论
(2) 回帖