E - Equalising Audio
题目链接
签到,保持$a_1$到$a_n$比例不变,给出K输出满足$K==\frac{1}{n}\sum a_i^2$的$a_i$
1 2 3 4 5 6 7 8 9 10 11 12
| int n=read(),k=read(); int cnt=0; for(int i=1;i<=n;i++){ a[i]=read(); cnt+=a[i]*a[i]; } double per; if(!cnt)per=0; else per=sqrt(x*n*1.0/cnt); for(int i=1;i<=n;i++){ printf("%.9lf ",per*a[i]); }
|
I - Imperfect Imperial Units
题目链接
n次definition
1
| 1 <unit> = <value> <unit>
|
q次query
1
| <value> <unit> to <unit>
|
保证每次询问前都曾有定义过
1 2 3 4 5 6 7
| int cnt; int id(string s){ if(!mp[s]){ mp[s]=++cnt; } return mp[s]; }
|
并查集维护是否可以兑换,输出”impossible”的情况
1 2 3 4 5 6 7 8 9 10
| int find(int x){ if(f[x]!=x)return f[x]=find(f[x]); return x; } bool check(string a,string b){ int ia=id(a),ib=id(b); ia=find(ia),ib=find(ib); if(ia==ib)return true; return false; }
|
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
| string t; int ans; void dfs(int t,int b,double e){ if(t==b){ ans=e; return ; } for(int i=h[t];i!=-1;i=ne[i]){ int j=e[i]; double d=w[i]; if(!st[j]){ st[j]=1; dfs(j,b,e*d); st[j]=0; } } } void add(int a,int b,double c){ e[idx]=b; ne[idx]=a; w[idx]=c; h[a]=idx++; } void de(){ double a;cin>>a; string s1;cin>>s1; cin>>t; double b;cin>>b; string s2;cin>>s2; int ida=id(s1),idb=id(s2); add(ida,idb,b); add(idb,ida,1.0/b); ida=find(ida),idb=find(idb); f[ida]=idb; } void qu(){ double a;cin>>a; string s1;cin>>s1; cin>>t; string s2;cin>>s2; if(!check(s1,s2))puts("impossible"); else{ memset(st,0,sizeof(st)); int ida=id(s1),idb=id(s2); st[ida]=1; dfs(ida,idb,1.0); printf("%.7g",ans); } }
|
L - Lowest Latency
求三维平面内 距离最小的两点
使用分治的思想 按照x轴大小排序后 分为左,中,右三部分
最短距离有三种可能
1.左部分之间的两点
2.右部分之间的两点
3.跨越中间的两点
求出1,2两部分的最小值$d=min(d1,d2)$后,借助贪心的思想,将与中间点距离小于d的点放入容器内,借助$O(M^2)\quad M<<N$遍历
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
| const int N = 1e5+5; struct node{ int x,y,z; }a[N]; bool cmp(node a,node b){ if(a.x!=b.x)return a.x<b.x; return a.y<b.y; } double dist(node a,node b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z)); } int t[N]; double merge(int l,int r){ if(l==r)return 0x3f3f3f3f; if(l+1==r)return dist(a[l],a[r]); int mid=l+r>>1; double d1=merge(l,mid); double d2=merge(mid+1,r); double ans=min(d1,d2);
int idx=0; for(int i=l;i<=r;i++){ if(fabs(a[i].x-a[mid].x)<ans){ t[++idx]=i; } } for(int i=1;i<=idx;i++){ for(int j=i+1;j<=idx;j++){ int td=dist(a[t[i]],a[t[j]]); ans=min(ans,td); } } return ans; }
|