PTA天梯赛、RoboCom练习_robocom芬兰木棋

1.L2-003 月饼

输入样例：

3 20
18 15 10
75 72 45
1
2
3

输出样例：

94.50
1

#include<iostream>
#include<algorithm>
using namespace std;

struct moon
{
    float mount;
    float price;
    float pro;
}moons[1010];
bool cmp(moon a,moon b)
{
    return a.pro>b.pro;
}
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++) scanf("%f",&moons[i].mount);
    for(int i=0;i<n;i++) scanf("%f",&moons[i].price);
    for(int i=0;i<n;i++) moons[i].pro=moons[i].price/moons[i].mount;
    sort(moons,moons+n,cmp);
    double sum=0;
    for(int i=0;i<n;i++)
    {
        if(m>moons[i].mount) sum=sum+moons[i].price;
        else
        {
            sum=sum+m*moons[i].pro;
            break;
        }
        m=m-moons[i].mount;
    }
    printf("%.2f",sum);
    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

2.L2-024 部落

输入样例：

4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7
1
2
3
4
5
6
7
8

输出样例：

10 2
Y
N
1
2
3

#include<bits/stdc++.h>
using namespace std;

const int N=10010;
int p[N],visited[N];

int find(int x)//并查集模板
{
    if(p[x]!=x)
        p[x]=find(p[x]);
    return p[x];
}

int main()
{
    int n;
    cin>>n;
    for(int i=0; i<N; i++) p[i]=i;
    int k,a,b;
    for(int i=0; i<n; i++)
    {
        cin>>k>>a;
        visited[a]=1;
        for(int i=1; i<k; i++)
        {
            cin>>b;
            visited[b]=1;
            p[find(a)]=find(b);
        }
    }
    int num=0;
    set<int>root;
    for(int i=0; i<N; i++)
    {
        if(visited[i])
        {
            num++;
            root.insert(find(i));
        }
    }
    cout<<num<<" "<<root.size()<<endl;
    int q;
    cin>>q;
    for(int i=0; i<q; i++)
    {
        cin>>a>>b;
        if(find(a)==find(b)) cout<<"Y"<<endl;
        else cout<<"N"<<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

3.L1-006 连续因子

输入样例：

630
1

输出样例：

3
5*6*7
1
2

#include<iostream>
#include<cmath>
using namespace std;

int main()
{
    int n;
    cin>>n;
    int count_max=0;
    int f=1;
    for(int i=2;i<sqrt(n);i++)
    {
        int k=n;
        int j=i;
        while(k%j==0)//寻找连续的因子
        {
            k=k/j;
            j++;
        }
        if(j-i>count_max)
        {
            count_max=j-i;
            f=i;
        }
    }
    if(count_max)
    {
        cout<<count_max<<endl;
        for(int i=1;i<=count_max;i++)
        {
            if(i!=count_max)
            {
                cout<<f<<"*";
            }
            else cout<<f;
            f++;
        }
    }
    else cout<<"1\n"<<n;
    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

4.L1-011 A-B (20 分)

#include<iostream>
#include<string>
using namespace std;

int vis[256];
int main()
{
    string a,b;
    getline(cin,a);
    getline(cin,b);
    for(int i=0;i<b.size();i++) vis[b[i]]=1;
    for(int i=0;i<a.size();i++)
    {
        if(vis[a[i]]==1) continue;
        cout<<a[i];
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

5.7-46 整除光棍 (20 分)

#include<iostream>
using namespace std;

int main()
{
    int n;
    cin>>n;
    int sum=1,ans=0,f=0;
    while(1)
    {
        ans++;
        if(sum/n!=0) f=1;
        if(f) cout<<sum/n;
        sum=sum%n;
        if(!sum) break;
        sum=sum*10+1;
    }
    cout<<" "<<ans;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

python做法：

a=int(input())
j=1
while(1):
    if(j%a==0):
        print(int(j//a),end=" ")
        print(len(str(j)))
        break
    j=10*j+1
1
2
3
4
5
6
7
8

6. L2-3 清点代码库 (25 分)

输入：
7 3
35 28 74
-1 -1 22
28 74 35
-1 -1 22
11 66 0
35 28 74
35 28 74
输出：
4
3 35 28 74
2 -1 -1 22
1 11 66 0
1 28 74 35

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

int n,m;
vector<int> f[10010];
map<vector<int>,int> mp;

struct A//体会这个题结构体的关键之处，二重排序
{
    int sum;
    vector<int> vv;
};
vector<A> AA;//注意这种用法，可以不定义数组

bool cmp(A a,A b)
{
    if(a.sum!=b.sum) return a.sum>b.sum;
    for(int i=0;i<a.vv.size();i++)
    {
        if(a.vv[i]!=b.vv[i]) return a.vv[i]<b.vv[i];
    }
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            int aa;
            cin>>aa;
            f[i].push_back(aa);
        }
        mp[f[i]]++;
    }
    for(auto c:mp)//学习map的遍历
    {
        A k;
        k.sum=c.second;
        k.vv=c.first;
        AA.push_back(k);
    }
    sort(AA.begin(),AA.end(),cmp);//学习vector的排序
    cout<<mp.size()<<endl;
    for(int i=0;i<mp.size();i++)
    {
        cout<<AA[i].sum;
        for(int j=0;j<AA[i].vv.size();j++)
        {
            cout<<" "<<AA[i].vv[j];
        }
        cout<<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

7. L3-2 还原文件 (30 分)

输入：
17
95 70 80 97 97 68 58 58 80 72 88 81 81 68 68 60 80
6
4 68 58 58 80
3 81 68 68
3 95 70 80
3 68 60 80
5 80 72 88 81 81
4 80 97 97 68

输出：
3 6 1 5 2 4
1
2
3
4
5
6
7
8
9
10
11
12
13

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
int n,m;
vector<int> v[maxn], v1;
bool vis[maxn];
int h[maxn];

void dfs(int x) //x是当前纸条的下标
{
    if(x==n-1) //终止条件
    {
        for (int i = 0; i < v1.size(); i++) //遍历输出
        {
            if(i) cout << " ";
            cout << v1[i];
        }
    }
    for (int i = 1; i <= m; i++)//遍历每一个纸条
    {
        if(!vis[i]) //当前纸条未使用过
        {
            int flag = 1;
            for (int j = 0; j < v[i].size(); j++)
            {
                if(v[i][j]!=h[x+j])
                    flag = 0;//不满足题意
            }
            if(flag)
            {
                v1.push_back(i);
                vis[i] = 1;
                dfs(x + v[i].size() - 1);
                vis[i] = 0;//回溯
                v1.pop_back();//回溯
            }
        }
    }
}
void solve()
{
    cin >> n;
    for (int i = 0; i<n; i++)
    {
        cin >> h[i];
    }
    cin >> m;

    for (int i = 1; i<=m; i++)
    {
        int k, x;
        cin>>k;
        while(k--)
        {
            cin>>x;
            v[i].push_back(x);
        }
    }
    dfs(0);
}
int main()
{
    solve();
    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
62
63
64
65
66

8.L2-1 特立独行的幸福 (25 分)

输入：
10 40
输出：
19 8
23 6
28 3
31 4
32 3

1
2
3
4
5
6
7
8
9

#include<iostream>
#include<unordered_set>
#include<map>
using namespace std;

int a,b;
map<int,int> mp;
int visit[10010];
int flag;

int isPrime(int n)
{
    for(int i=2;i<=n/i;i++)
    {
        if(n%i==0) return 1;
    }
    return 2;
}

int fun(int t)
{
    int cnt=0;
    while(t)
    {
        cnt+=(t%10)*(t%10);
        t=t/10;
    }
    return cnt;
}

void solve(int l,int r)
{
    for(int i=l;i<=r;i++)
    {
        int t=i;
        if(visit[t]) continue;
        unordered_set<int> s;
        while(t!=1)
        {
            t=fun(t);
            if(s.count(t)) break;
            s.insert(t);
            visit[t]=1;
        }
        if(t==1) mp[i]=s.size();
    }
}


int main()
{
    cin>>a>>b;
    solve(a,b);

    for(auto i:mp)
    {
        if(!visit[i.first])//注意这个地方，用的十分巧妙，最开始遍历的那个点其实是没有被标记的，只是标记了他所产生的点
        {
            cout<<i.first<<" "<<i.second*isPrime(i.first)<<endl;
            flag=1;
        }
    }
    if(!flag) cout<<"SAD"<<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
62
63
64
65
66

9. 龙龙送外卖

输入：
7 4
-1 1 1 1 2 2 3  //第i个节点的父节点
5
6
2
4
输出：
2
4
4
6
1
2
3
4
5
6
7
8
9
10
11
12

题意： 一棵树（无向），从根节点出发，根节点编号为1，每次更新一个要到达的节点编号，并与之前的编号进行累加，每次更新后，求到达所有节点的最短路径，相邻两个节点的距离为1。

#include<iostream>
using namespace std;

int n,m;
int p[100010];
int mx;
int d[100010];//存每个节点到根节点的距离
int sum;//统计单向的总长度

int dfs(int u)
{
    if(d[u]>0||p[u]==-1) return d[u];
    sum++;
    d[u]=dfs(p[u])+1;
    return d[u];
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&p[i]);
    while(m--)
    {
        int a;
        scanf("%d",&a);
        mx=max(mx,dfs(a));//找到当前所有节点中距离根节点最远的节点
        printf("%d\n",2*sum-mx);
    }
    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

10. 大 众 情 人

输入：
6
F 1 4:1  //1对4的距离感（单方向的）
F 2 1:3 4:10
F 2 4:2 2:2
M 2 5:1 3:2
M 2 2:2 6:2
M 2 3:1 2:5
输出：
2 3
4
1
2
3
4
5
6
7
8
9
10
11

题意： n组数据，每一组数据代表一个人，编号分别为1-n，在每组数据中，F代表女，M代表男。求出每个性别中，所有异性对他的距离感的最大值的最小值。若存在多个最小值，则按编号大小输出。

#include<iostream>
#include<cstring>
using namespace std;

const int INF=0x3f3f3f3f;
int n,k;
int d[510][510];//一维对二维的距离感
char sex[510];
int mx;


int main()
{
    cin>>n;
    memset(d,0x3f,sizeof d);
    for(int i=1;i<=n;i++) d[i][i]=0;
    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s>>k;
        sex[i]=s[0];
        while(k--)
        {
            int a,b;
            scanf("%d:%d",&a,&b);
            d[i][a]=b;
        }
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    for(auto c:string("FM"))
    {
        int mn=INF;
        for(int i=1;i<=n;i++)  //找每个性别的最大距离感的最小值
        {
            if(sex[i]==c)
            {
                int mx=0;
                for(int j=1;j<=n;j++)
                {
                    if(sex[i]!=sex[j]) mx=max(mx,d[j][i]);
                }
                mn=min(mn,mx);
            }
            
        }
        int flag=1;
        for(int i=1;i<=n;i++)
        {
            if(sex[i]==c)
            {
                int mx=0;
                for(int j=1;j<=n;j++)  //统计是否存在多个最小值
                {
                    if(sex[i]!=sex[j]) mx=max(mx,d[j][i]);
                }
                if(mx==mn)
                {
                    if(flag) printf("%d",i),flag=0;
                    else printf(" %d",i);
                }
            }

        }
        cout<<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
62
63
64
65
66
67
68
69
70

11. 芬兰木棋

输入：
11
1 2 2  //前两个数为坐标，后一个数为值
2 4 3
3 6 4
-1 2 2
-2 4 3
-3 6 4
-1 -2 1
-2 -4 1
-3 -6 1
-4 -8 2
2 -1 999
输出：
1022 9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

题意： 在坐标原点(0,0)向各个方向投木棋，在某一个方向上可以选择一次投k个，（当投一次时，值取真实值，当投多次时，值取所投的次数），也可以在一个方向上投多次，求得到的最大值所用的最小木棋数量。

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;

int n;
long a,b;
int c;
int sum,cnt;
map<pair<long,long>,vector<pair<long,long> > > mp;

int main()
{
    cin>>n;
    while(n--)
    {
        scanf("%ld %ld %d",&a,&b,&c);
        sum+=c;
        int g=__gcd(a,b);
        if(a==0&&b>0) mp[{0,1}].push_back({abs(b),c});//这里要特别注意在坐标轴上的情况，需要特判
        else if(a==0&&b<0) mp[{0,-1}].push_back({abs(b),c});
        else if(a>0&&b==0) mp[{1,0}].push_back({abs(a),c});
        else if(a<0&&b==0) mp[{-1,0}].push_back({abs(a),c});
        else mp[{a/abs(g),b/abs(g)}].push_back({abs(a),c});
    }
    for(auto i=mp.begin();i!=mp.end();i++)
    {
        auto v=i->second;
        sort(v.begin(),v.end());
        for(int j=0;j<v.size();j++)
        {
            //cout<<v[j].first<<" "<<v[j].second<<endl;
            int flag=0;
            while(v[j].second==1) j++,flag=1;
            if(flag) cnt++;
            if(j<v.size()&&v[j].second!=1) cnt++;
        }
    }
    cout<<sum<<" "<<cnt<<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

12. 拼题A打卡奖励

输入：
5 110
70 10 20 50 60
28 1 6 18 22
输出：
40
1
2
3
4
5
6

#include<iostream>
#include<cstring>
using namespace std;

int n,m;
int v[1010],w[1010];
int f[1000010];
int sum;

int main()
{
    cin>>n>>m;
    memset(f,0x3f,sizeof f);
    for(int i=1;i<=n;i++) cin>>v[i];
    for(int i=1;i<=n;i++) cin>>w[i],sum+=w[i];
    /*
    for(int i=1;i<=n;i++)  //经典01背包做法，n*m会超时，而此时将金币数和时间替换是一种巧妙地思想
    {
        for(int j=m;j>=0;j--)
        {
            if(j-v[i]>=0) f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m]<<endl;
    */
    f[0]=0;
    for(int i=1;i<=n;i++)  //f表示下标为j的金币数的最小时间
    {
        for(int j=sum;j>=0;j--)
        {
            if(j-w[i]>=0) f[j]=min(f[j],f[j-w[i]]+v[i]);
        }
    }
    for(int i=sum;i>=0;i--)
    {
        if(f[i]<=m)
        {
            cout<<i<<endl;
            break;
        }
    }
    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