Day 1
今天主要在补之前各种比赛的题目
AcWing4653. 数位排序
#include<bits/stdc++.h>
#define int long long
using namespace std;
int32_t main(){
int n , m;
cin >> n >> m;
vector< pair<int,int> > a;
auto f = []( int x ){
int t = 0;
while( x > 0 ) t += x % 10 , x /= 10;
return t;
};
for( int i = 1 ; i <= n ; i ++ ) a.emplace_back( f(i) , i );
sort( a.begin() , a.end());
cout << a[m-1].second;
}
AcWing4644. 求和
提公因式
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){
int x = 0 , f = 1 , ch = getchar();
while( (ch < '0' || ch > '9') && ch != '-' ) ch = getchar();
if( ch == '-' ) f = -1 , ch = getchar();
while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();
return x * f;
}
const int N = 200005;
int a[N] , b[N];
int32_t main(){
int n = read() , res = 0;
for( int i = 1 ; i <= n ; i ++ ) b[i] = a[i] = read();
for( int i = n-1 ; i >= 1 ; i -- ) b[i] += b[i+1];
for( int i = 1 ; i < n ; i ++ )
res += b[i+1] * a[i];
cout << res << "\n";
}
并查集按秩合并的一种写法
今天学了一种并查集按秩合并的一种写法，具体来说就是用fa[x]<0表示x是根节点，然后根节点abs(fa[x])表示集合的大小
class dsu{
private:
vector<int> fa;
public:
dsu( int n = 1 ){
fa = vector<int>( n+1 , -1 ) , fa[0] = 0;
}
int getfa( int x ){
if( fa[x] < 0 ) return x;
return fa[x] = getfa( fa[x] );
}
void merge( int x , int y ){
x = getfa(x) , y = getfa(y);
if( x == y ) return ;
if( fa[x] > fa[y] ) swap( x , y );
fa[x] += fa[y] , fa[y] = x;
}
bool check( int x , int y ){
x = getfa(x) , y = getfa(y);
return ( x == y );
}
};
Day 2
One Bamboo Contest Round #13(Clone from 2019 ICPC Yinchuan)
Day 3
One Bamboo Contest Round #14(Clone from 2021 ICPC Latin American)
Day 4
2020 ICPC·小米邀请赛 决赛
Day 5
今天主要还是以补题为主