A 求余

code

#includeusing namespace std;typedef long long ll;const int N = 2e6 + 7;const int mod = 1e9 + 7;const int MOD = 998244353;#define sc(x) scanf("%lld", &(x))#define pr(x) printf("%lld\n", (x))#define int long long#define rep(i, l, r) for (int i = l; i <= r; ++i)void solve(){cout<<2021%20<<endl;}signed main(){int _=1;//cin>>_;while(_--) solve();return 0;}//答案：1

B 双阶乘

Code:

#includeusing namespace std;typedef long long ll;const int N = 2e6 + 7;const int mod = 1e9 + 7;const int MOD = 998244353;#define sc(x) scanf("%lld", &(x))#define pr(x) printf("%lld\n", (x))#define int long long#define rep(i, l, r) for (int i = l; i <= r; ++i)void solve(){int ans=1;for(int i=1;i<=2021;i+=2){ans=ans*i%100000;}cout<<ans<<endl;}signed main(){int _=1;//cin>>_;while(_--) solve();return 0;}/*59375*/

C 格点

code：

#includeusing namespace std;typedef long long ll;const int N = 2e6 + 7;const int mod = 1e9 + 7;const int MOD = 998244353;#define sc(x) scanf("%lld", &(x))#define pr(x) printf("%lld\n", (x))#define int long long#define rep(i, l, r) for (int i = l; i <= r; ++i)void solve(){int ans=0;for(int i=1;i<=2021;i++){for(int j=1;j<=2021;j++){if(i*j<=2021) ans++;}}cout<<ans<<endl;}signed main(){int _=1;//cin>>_;while(_--) solve();return 0;}/*15698*/

其实是可以优化的，但没必要，暴力跑的也快也准

D 整数分解

很常见的背包DP。

code：

#includeusing namespace std;typedef long long ll;const int N = 2e6 + 7;const int mod = 1e9 + 7;const int MOD = 998244353;#define sc(x) scanf("%lld", &(x))#define pr(x) printf("%lld\n", (x))#define int long long#define rep(i, l, r) for (int i = l; i <= r; ++i)void solve(){ll dp[6][2022];    memset(dp, 0, sizeof dp);    for(int i = 1;i<2022;i++) dp[1][i] = 1;    for(int i =2;i<=5;i++) for(int j =1; j<2022;j++)     for(int k = 1;k<2022;k++){  if(j-k > 0) dp[i][j] += dp[i-1][j-k];     }    cout<< dp[5][2021];}signed main(){int _=1;//cin>>_;while(_--) solve();return 0;}/*691677274345*/

E 城邦

看题一眼就知道这是一道的最小生成树的板子题。

最小生成树有两种算法，一个是Prim算法 O ( n 2 ) O(n^2) O(n2)和克鲁斯卡尔算法$O(mlogm)$。

这个题用Prim算法就行了，暴力杯，暴力就是了。

Prim算法

适用于稠密图，时间复杂度 O ( n 2 ) O(n^2) O(n2)。

核心思想：每次挑一条与当前集合相连的最短边。

C++ 代码

// st[i] 表示点i是否在当前生成树集合中// dist[i] 表示点i到当前集合的最短边的长度// g[i][j] 表示点i和点j之间边的长度// 返回值：最小生成树中所有边的总长度int Prim(){    int res = 0;    for (int i = 1; i <= n; i ++ )    { dist[i] = INF; st[i] = false;    }    dist[1] = 0;    for (int i = 1; i <= n; i ++ )    { int id = -1, min_dist = INF; // 寻找最短边 for (int j = 1; j <= n; j ++ )     if (!st[j] && dist[j] < min_dist)     {  id = j;  min_dist = dist[j];     } st[id] = true; res += dist[id]; // 用新加入的点更新其余点到生成树的最短边 for (int j = 1; j <= n; j ++ )     if (!st[j])  dist[j] = min(dist[j], g[id][j]);    }    return res;}

Kruskal算法

适用于稀疏图，时间复杂度 $O(mlogm)$.

核心思想：从小到大挑不多余的边。

C++ 代码

// 边的信息struct Edge{    int a, b, v;    bool operator< (const Edge &W) const    { return v < W.v;    }};// 并查集——寻找当前集合的代表元素int find(int x){    if (father[x] != x) father[x] = find(father[x]);    return father[x];}// 所有边存储在 Edge edges[M]; // 函数返回最小生成树中所有边的总长度int Kruskal(){    int res = 0;    // 初始化并查集代表元素    for (int i = 1; i <= n; i ++ ) father[i] = i;    sort(edge, edge + m);    for (int i = 0; i < m; i ++ )    { int a = edge[i].a, b = edge[i].b; if (find(a) != find(b)) {     res += edge[i].v;     father[find(a)] = find(b); }    }    return res;}

代码：

#includeusing namespace std;typedef long long ll;const int N = 2e6 + 7;const int mod = 1e9 + 7;const int MOD = 998244353;#define sc(x) scanf("%lld", &(x))#define pr(x) printf("%lld\n", (x))#define int long long#define rep(i, l, r) for (int i = l; i <= r; ++i)int st[N],dist[N],g[2030][2030],n;// st[i] 表示点i是否在当前生成树集合中// dist[i] 表示点i到当前集合的最短边的长度// g[i][j] 表示点i和点j之间边的长度// 返回值：最小生成树中所有边的总长度int Prim(){    int res = 0;    for (int i = 1; i <= n; i ++ )    { dist[i] = INT_MAX; st[i] = false;    }    dist[1] = 0;    for (int i = 1; i <= n; i ++ )    { int id = -1, min_dist = INT_MAX; // 寻找最短边 for (int j = 1; j <= n; j ++ )     if (!st[j] && dist[j] < min_dist)     {  id = j;  min_dist = dist[j];     } st[id] = true; res += dist[id]; // 用新加入的点更新其余点到生成树的最短边 for (int j = 1; j <= n; j ++ )     if (!st[j])  dist[j] = min(dist[j], g[id][j]);    }    return res;}int get(int i,int j){int ans=0;while(i||j){if(i%10!=j%10) ans+=i%10+j%10;i/=10;j/=10;}return ans;}void solve(){n=2020;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){g[i][j]=get(i,j);//cout<<g[i][j]<<" ";}}cout<<Prim()<<endl;}signed main(){int _=1;//cin>>_;while(_--) solve();return 0;}/*4045*/

H 完全平方数

思路：

要使得一个数是完全平方数，那么他所有的质因子都应该是偶数次幂。这样才能开根号，幂次除以 2 能整除。

所以我们把n分解质因数，所有质因子奇数次幂的相乘就是答案，奇数多加一次就变成偶数。

代码：

#includeusing namespace std;typedef long long ll;const int N = 2e6 + 7;const int mod = 1e9 + 7;const int MOD = 998244353;#define sc(x) scanf("%lld", &(x))#define pr(x) printf("%lld\n", (x))#define int long long#define rep(i, l, r) for (int i = l; i <= r; ++i)int a[N],n,m;void solve(){cin>>n;int ans=1;for(int i=2;i*i<=n;i++){if(n%i==0){int cnt=0;while(n%i==0) cnt++,n/=i;if(cnt&1) ans*=i;}}if(n>1) ans*=n;cout<<ans<<endl;}signed main(){int _=1;//cin>>_;while(_--) solve();return 0;}

与50位技术专家面对面 20年技术见证，附赠技术全景图