仓库规划

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
#include<bits/stdc++.h>

using namespace std;

const int M = 15, N = 1010;

int a[N][M];

int n,m;

bool cmp(int line1,int line2)//对每一行行判断,line2是否全部大于line1
{
    for (int w = 1; w <= m; w++)
    {
        if (a[line2][w] <= a[line1][w])return false;
    }
    return true;
}

int find_line(int x)//返回查找到的上级
{
    for (int i = 1; i <= n; i++)
    {
        if (cmp(x, i))return i;
    }
    return 0;
}

int main()
{
    cin >> n >> m;

    //数据读入
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)cin >> a[i][j];
    }

    for (int i = 1; i <= n; i++)
    {
        cout << find_line(i) << endl;
        
    }

    return 0;
}

因子化简

会欧拉筛基本上就秒了，还有记得数据范围

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
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1e5+10;
bool not_prime[N];

vector<int>prime;

void solve()
{
    LL n,k;
    LL result=1,len=prime.size();
    cin>>n>>k;
    
    for(int i=0;prime[i]<=n&&i<len;i++)
    {
        int cnt=0;//cnt记录次方数
        
        while(n%prime[i]==0)
        {
            cnt++;
            n/=prime[i];
        } 
        if(cnt>=k)
        {
            while(cnt--)result*=prime[i];
        }
    }
    
    cout<<result<<'\n';
    
}

int main()
{
    int q;
    
    cin>>q;
    
    //首先筛选出小于1e5的所有质数
    for(int i=2;i<=N;i++)
    {
        if(!not_prime[i])prime.push_back(i);
        
        for(auto j:prime)
        {
            if(j*i>N)break;
            not_prime[i*j]=true;
            if(i%j==0)break;
        }
    }
    
    
    while(q--)
    solve();
    
    return 0;
}

树上搜索

一道考基础知识的题，思路并不复杂，基本功扎实就行,思路请看代码注释（以及尽可能详细了）

dfs 邻接表 递归

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>

typedef long long LL;

using namespace std;

vector<LL>temp,wi;//wi存储该点即子节点的权重和，temp存储每一点的权值
vector<vector<int>>ls;//邻接表（建树）
set<int>yes,no;//yes存储未被删除的点,no标记被删除的点 

int n,m;

void dfs(int cur)//初始化yes与wi
{
    yes.insert(cur);
    for(auto i:ls[cur])
    {
        if(no.find(i)!=no.end())continue;
        dfs(i);
        wi[cur]+=wi[i];
    }
}

int get_min(int cur)//寻找指定最小值 
{
    LL min_data=1e10;
    int min_idx;
    for(auto i:yes)
    {
        LL data=llabs(wi[cur]-wi[i]*2);
        if(data<min_data)
        {
            min_idx=i;
            min_data=data;
        }
    }
    return min_idx;
}

bool check(int num,int min_idx)//检验num是否在min_idx的子树中 
{
    if(min_idx==num)return true;
    for(auto i:ls[min_idx])
    {
        if(no.find(i)!=no.end())continue;
        if(i==num)return true;
        if(check(num,i))return true;
    }
    return false;
}



int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    cin>>n>>m;
    
    temp.resize(n+1);
    wi.resize(n+1);
    ls.resize(n+1);
    
    //输入权值 
    for(int i=1;i<=n;i++)
    {
        cin>>temp[i];
    }
    
    //建树
    for(int i=2;i<=n;i++)
    {
        int fa;
        cin>>fa;
        ls[fa].push_back(i);
    }
    
    for(int i=1;i<=m;i++)
    {
        no.clear();
        int num,cur=1;//num为要处理的编号 
        cin>>num;
        
        while(true)
        {
            yes.clear();
            wi=temp;
            
            dfs(cur);//初始化wi与yes
            
            if(yes.size()==1)break;//当只剩一个元素时查找成功 
            
            int min_idx=get_min(cur);//查找指定点 
            
            if(check(num,min_idx))cur=min_idx;//判断所要查找的num是否在min_idx的子树中 
            else no.insert(min_idx);
            
            cout<<min_idx<<' ';
        }
        cout<<'\n';
    }
    
    return 0;
}