zhangas

Pay more attention

0%

SDKD2023SummerTeamContest C

Veröffentlicht am

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;//可能全为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;//"impossible"的情况
}
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){//按照x轴的大小排序
	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];//存储与中间点距离小于d的点的下标
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;
}