• 欢迎光临~

# 2022百度之星 初赛1 A-B

A：洞穴

```//-------------------------代码----------------------------

//#define int ll
const int N = 200;
int n,m;

int dist[N][N];

struct node {
int a,b,w;
bool operator<(const node & x) const {
return w < x.w;
}
}p[N];
int f[N];

bool cmp(pii a,pii b) {
if(a.x == b.x) return a.y < b.y;
return a.x < b.x;
}

int find(int x) {
return x == f[x] ? x : f[x] = find(f[x]);
}

void solve()
{
//    cin>>n>>m;
fo(i,1,200) f[i] = i;
cin>>n;
int cnt = 0;
int w;
fo(i,1,n) {
fo(j,1,n) {
cin>>w;
if(j > i) {
p[++cnt] = {i,j,w};
}
}
}
sort(p+1,p+1+cnt);
int sum = 0;
V<pii>q;
cout<<n - 1<<endl;
for(int i = 1;i<=cnt;i++) {
int a = p[i].a,b = p[i].b,w = p[i].w;
if(find(a) == find(b)) {

} else {
f[a] = find(b);
sum ++ ;
q.pb({a,b});
}
if(sum == n - 1) break;
}
sort(all(q),cmp);
for(auto it:q) {
cout<<it.x<<' '<<it.y<<endl;
}
}
void main_init() {}
signed main(){
AC();clapping();TLE;
cout<<fixed<<setprecision(12);
main_init();
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
int t;cin>>t;while(t -- )
solve();
//    {solve(); }
return 0;
}

/*样例区

*/

//------------------------------------------------------------```

B.小度养小猫

```auto idx = q.end();
idx -- ;
res += 1ll * (*idx) * i * i;```

```//-------------------------代码----------------------------

//#define int ll
const int N = 1e5+10;
int n,m,k;
int c[N];
void solve()
{
//    cin>>n>>m;
cin>>n>>k;
ll res = 0;
fo(i,1,n) {
cin>>c[i];
res -= 1ll * i * i * c[i];
}
set<int> q;
fo(i,1,k) q.insert(c[i]);
fo(i,k + 1,k + n) {
if(i <= n)q.insert(c[i]);
auto idx = q.end();
idx -- ;
res += 1ll*(*idx) * i * i;
q.erase(idx);
}
cout<<res<<endl;

}
void main_init() {}
signed main(){
AC();clapping();TLE;
cout<<fixed<<setprecision(12);
main_init();
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
//    int t;cin>>t;while(t -- )
solve();
//    {solve(); }
return 0;
}

/*样例区

*/

//------------------------------------------------------------```

C: