2020ICPC·小米网络选拔赛第一场题解

程序员文章站 2022-06-02 19:54:26

...

题目总体情况

A 题：数论 + 动态规划
B 题：计算几何 + 最短路
C 题：模拟
D 题：图论（连通块个数）
E 题：略
F 题：二分答案
G 题：图论
H 题：略
I 题：搜索（BFS）/ 并查集
J 题：二维前缀和 + 二维差分
K 题：数学（难）

A、Intelligent Warehouse

2020ICPC·小米网络选拔赛第一场题解
题目大意:
给你一个序列,让你选出最多的数,使得选中的数之间互为倍数( a i a_i ai是 a j a_j aj的倍数或者 a j a_j aj是 a i a_i ai的倍数)

思路：

数据2e5，求的是最多的个数，考虑DP

官方题解:
2020ICPC·小米网络选拔赛第一场题解

方法一：直接暴力转移方程（注意，如果把范围设置为10000000才能AC，大一点都会TLE）

#include <cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>

using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 10000007;

int n;
int f[N];
int cnt[N];
int maxv;

int main()
{
    scanf("%d", &n);
    for(int i = 1;i <= n; ++ i){
        int x;
        scanf("%d", &x);
        cnt[x] ++;
    }
    int maxv = 10000000;
    int ans = 0;
    for(int i = 1 ;i <= maxv; ++ i){
        if(cnt[i]){
            f[i] += cnt[i];
            for(int j = 2 * i; j <= maxv; j += i){
                f[j] = max(f[j], f[i]);
            }
            ans = max(ans, f[i]);
        }
    }
    printf("%d\n", ans);
    return 0;
}

方法二（优化）：

按照题解里的方法，筛出来所有的素数，然后再枚举所有的素数，因为任意合数都可以用素数凑出来（唯一分解定理）

B、Intelligent Robot

C、Smart Browser

2020ICPC·小米网络选拔赛第一场题解

水题模拟，队友写的。

#include <iostream>
#include <cstring>

using namespace std;

const int N=1e5+10;
char a[N];

int main()
{
	cin>>a;
	int num,ans=0;
	for(int i=0;i<strlen(a);i++)
	{
		int num=0; 
		while(a[i]=='w')
		{
			ans++;
			num++;
			i++;
		}
		if(num) ans+=num-1;
	}
	cout<<ans<<endl;
	return 0;
}

D、Router Mesh

2020ICPC·小米网络选拔赛第一场题解
几乎就是一个tarjan模板题了，（但是我因为玩莫比乌斯反演，一个月没怎么碰图论了，所以这道题还卡了我一会…）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;
const int N = 500007, M = 5000007, INF = 0x3f3f3f3f;

int n, m;
int dfn[N], low[N], tim;
int ver[M], nex[M], edge[M], head[N], tot;
int ans;
int cut[N];
int num[N];//吧这个点删除以后能分成多少块

void add(int x,int y){
    ver[tot] = y;
    nex[tot] = head[x];
    head[x] = tot ++ ;
}

void tarjan(int x, int rt){//计算该割点连接了多少个连通块
    dfn[x] = low[x] = ++ tim;
    int flag = 0;
    int cnt = 0;//(割开这个点会将图分成cnt个连通块)
    for(int i = head[x]; ~i;i = nex[i]){
        int y = ver[i];
        if(!dfn[y]){
            tarjan(y, rt);
            low[x] = min(low[x], low[y]);
            if(dfn[x] <= low[y]){//该割点返回了一条独立的路
                cnt ++ ;
                flag ++ ;
                if(x != rt || flag > 1)cut[x] = 1;
            }
        }
        else low[x] = min(low[x], dfn[y]);
    }
    if(x != rt)cnt ++ ;//如果不是根的话说明该点的上面应该可以割出来一个连通块

    ans = max(ans,cnt);
    num[x] = cnt;
}



int main(){
    scanf("%d%d", &n, &m);

        memset(head, -1, sizeof head);
        memset(dfn, 0, sizeof dfn);
        tot = tim = 0;
        for(int i = 1;i <= m;++i){
            int x,y;
            scanf("%d%d",&x,&y);
            add(x,y);add(y,x);
        }
        ans = 0;
        int cnt = 0;
        for(int i = 1;i <= n;++ i){//数据从0到n - 1
            if(!dfn[i]){
                cnt ++ ;//可能有孤立点(孤立连通块)
                tarjan(i, i);
            }
        }
        //cnt是当前连通块的个数
        for(int i = 1; i <= n; ++ i){
            if(head[i] == -1){
                printf("%d ", cnt - 1);
            }
            else
                printf("%d ", num[i] + cnt - 1);
        }
        puts("");
        //printf("%d\n", ans + cnt - 1);//减去多算的这个点(ans是由这个点割开之后能分散开的连通块个数)

}

I、Walking Machine

2020ICPC·小米网络选拔赛第一场题解
并查集过的，之前有一道题洛谷上的奶酪，跟这道题差不多，那道题就是用bfs或者并查集可过，我的dfs剪枝超时，所以试了一下并查集就过了。

官方题解：

2020ICPC·小米网络选拔赛第一场题解

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>

using namespace std;
typedef long long ll;
const int N = 5000007, M = 50007, INF = 5000007;
const double eps = 1e-6;

int n, m;
int fa[N];
string s[N];
int ans ;

int Find(int x)
{
    if(fa[x] == x) return x;
    return fa[x] = Find(fa[x]);
}

void unions(int x, int y)
{
    int fx = Find(x), fy = Find(y);
    fa[fx] = fy;
}

int main()
{

    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n * m; ++ i)
        fa[i] = i;
    fa[INF] = INF;
    for(int i = 0; i < n; ++ i){
        cin >> s[i];
    }
        //cout << "ok" << endl;
    for(int i = 0; i < n; ++ i){
        for(int j = 0; j < m; ++ j){
            if(s[i][j] == 'W'){
                if(i - 1 < 0)unions(i * m + j, INF);
                else unions(i * m + j, (i - 1) * m + j);
            }
            else if(s[i][j] == 'S'){
                if(i + 1 >= n)unions(i * m + j, INF);
                else unions(i * m + j, (i + 1) * m + j);
            }
            else if(s[i][j] == 'A'){
                if(j - 1 < 0)unions(i * m + j, INF);
                else unions(i * m + j, i * m + j - 1);
            }
            else if(s[i][j] == 'D'){
                if(j + 1 >= m)unions(i * m + j, INF);
                else unions(i * m + j, i * m + j + 1);
            }
        }
    }
    //cout << "ok" << endl;
    for(int i =  0; i < n; ++ i){
        for(int j = 0; j < m; ++ j){
            if(Find(i * m + j) == INF)
                ans ++ ;
        }
    }
    printf("%d\n", ans);
}

J、Matrix Subtraction

题意：有一个 n ∗ m n * m n∗m 的矩阵 M，通过反复选择 a ∗ b a*b a∗b大小的子矩阵并且使子矩阵中的所有元素都减去 1 ，问最终矩阵 M 能否变为全 0。如果可能，在一行中打印 ^_^，否则在一行中打印 QAQ。

思路：

我们直接 n 2 n^2 n2暴力枚举 a ∗ b a*b a∗b的子矩阵，每一块都减去 当前值 使之变为 0，利用二维差分可以快速实现这个操作。如果中途出现了负数或最后不全为 0，则输出 QAQ。（本来想的是用二维树状数组，结果写了半个小时调不出来…）注意

官方题解:

2020ICPC·小米网络选拔赛第一场题解

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 2007, M = 500007, INF = 0x3f3f3f3f;
const double eps = 1e-6;

int a[N][N];
int n, m, A, B;

void add(int x_1, int y_1, int x_2, int y_2, int z){
    a[x_1][y_1] += z;
    a[x_2 + 1][y_1] -= z;
    a[x_1][y_2 + 1] -= z;
    a[x_2 + 1][y_2 + 1] += z;
}

bool check()
{
    for(int i = 1; i <= n; ++ i){
        for(int j = 1 ; j <= m; ++ j){
            if(a[i][j] != 0)
                return false;
        }
    }
    return true;
}
int t;
int main()
{
    scanf("%d", &t);
    while(t -- ){
        memset(a, 0, sizeof a);
        scanf("%d%d%d%d", &n, &m, &A, &B);

        for(int i = 1; i <= n; ++ i){
            for(int j = 1; j <= m; ++ j){
                int x;
                scanf("%d", &x);
                add(i, j, i, j, x);
            }
        }

        bool success = 1;

        for(int i = 1; i <= n; ++ i){
            for(int j = 1; j <= m; ++ j){
                a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
                if(a[i][j] < 0){success = 0;break;}

                int ii = i + A - 1, jj = j + B - 1;
                if(ii <= n && jj <= m)
                    add(i, j, ii, jj, -a[i][j]);
            }
            if(success == 0)break;
        }

        if(success == 0){
            puts("QAQ");
            continue;
        }
        if(check())puts("^_^");
        else puts("QAQ");
    }
    return 0;
}

2020ICPC·小米网络选拔赛第一场题解

题目总体情况

A、Intelligent Warehouse

B、Intelligent Robot

C、Smart Browser

D、Router Mesh

I、Walking Machine

J、Matrix Subtraction

2020ICPC·小米网络选拔赛热身赛-A.ABBA

小米邀请赛第一场网络赛题解C，J，I

2020ICPC·小米网络选拔赛第一场 J.Matrix Subtraction

2020ICPC·小米网络选拔赛第一场 D - Router Mesh（求删掉割点后的连通块数）

2020ICPC·小米网络选拔赛第一场 A Intelligent Warehouse

2020ICPC·小米网络选拔赛热身赛