526互联

西南民族大学 春季 2023 训练赛3

发布时间 2023-04-04 00:21:50作者: Ke_scholar

L1-1小乐乐是否被叫家长

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

const int N = 1e5+10;
int n,m,t;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> t;
    if((n + m + t) >=  180) cout << "NO";
    else cout << "YES" ; 
    
    
    return 0;
}

L1-2你要乘坐的飞碟在这里

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

const int N = 1e5+10;
int n,m,t;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    string s1,s2;
    cin >> s1 >> s2;
    int ans1, ans2;
    ans1 = ans2 = 1;
    for(int i = 0 ;i < s1.size();i++)
     ans1 = (ans1 * (s1[i] - 'A' + 1)); 
    for(int i = 0; i < s2.size();i++)
     ans2 = (ans2 * (s2[i] - 'A' + 1));
    if(ans1 % 47 == ans2 % 47) cout << "GO" ;
    else cout << "STAY";
    return 0;
}

L1-3成绩

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

const int N = 1e5+10;
int n,m,t;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    string s1,s2;
    cin >> n >> m >> t;
    cout << n * 0.2+ m * 0.3 + t * 0.5 << endl; 
    return 0;
}

L1-4素数分布

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

const int N = 1e5+10;
int n,m,t;
bool su(int x) {
    if(x < 2) return 0;
    if(x == 2) return 1;
    for(int i = 2; i <= sqrt(x) ;i ++ )
     if(x % i == 0) return 0;
    return 1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> t;
    while(t--)
     {
         cin >> n;
         int ans = 0;
         for(int i = 1; i <= n; i++)
          if(su(i)) ans  ++;
         cout << ans << endl; 
     }
    return 0;
}

L1-5便便传送门(一)

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

const int N = 1e5+10;
int n,m,t;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int a,b,x,y,ans;
    cin >> a >> b >> x >> y;
    if(a > b) swap(a, b);
    if(x > y) swap(x, y);
    ans = min(abs(x - a) + abs(b - y) , (b - a));
    cout << ans << endl;
    return 0;
}

L1-6有序序列插入一个数

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

const int N = 1e5+10;
int n,m,t;
vector<int> a;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 0; i < n ;i ++)
     {
         cin >> m ;
         a.push_back(m); 
     }
     cin >> t;
     a.push_back(t);
     sort(a.begin(),a.end());
     for(int i = 0; i < a.size(); i++)
      cout << a[i] << ' ';
      
    return 0;
}

L1-7货物收集

用优先队列或者链表dfs二分答案都能做,优先取怪兽武力值低的,难点就是如何遍历所有的点

优先队列做法:

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <utility>
#define inf 0x3f3f3f3f
#define endl '\n'
#define PII pair<int,int>
using namespace std;

const int N = 1e5+10;

typedef long long ll;

int n,m,t,w0,ww[N];
vector<PII> a[N];
bool vis[N];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> w0;
    for(int i = 2; i <= n; i++)
     cin >> ww[i];
    for(int i = 1; i < n ;i ++)
    {
        int x,y,w;
        cin >> x >> y >> w;
        a[x].push_back({w,y});
        a[y].push_back({w,x});
    }
    //sort(a.begin(), a.end());
    int ans ,nows;
    ans = nows = 0;
    priority_queue <PII,vector<PII>,greater<PII> > q;
    q.push({0,1});
    while(!q.empty())
    {
        auto u = q.top();
        q.pop();
        ans = max(ans, u.first);
        nows += ww[u.second];
        vis[u.second] = 1;
        if(nows >= w0) 
         break;
        for(auto i : a[u.second])
        {
            if(!vis[i.second])
            {
                q.push({i.first,i.second});
            }
        }
    }
    cout << ans << endl;
    return 0;
}

链表存边dfs二分答案做法:

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <utility>
#define inf 0x3f3f3f3f
#define endl '\n'
#define int long long

using namespace std;

const int N = 1e5+10;

//typedef long long ll;
struct Edge{
    int to,next,w;
}edge[N];
int head[N];
bool vis[N]; 
int n,m,t,w0,cnt,a[N];
int dfs(int,int,int);
void add(int x, int y, int w)
{
    edge[cnt] = {y, head[x], w};
    head[x] = cnt++;
}
bool check(int x)
{
    int t = dfs(1, 0, x);
    return t >= w0;
}
int dfs(int u, int v, int x)
{
    int sum = a[u];
    for(int i = head[u]; ~i ;i = edge[i].next)
    {
        if(edge[i].to != v && edge[i].w <= x)
        {
            sum += dfs(edge[i].to, u, x); 
        }
     } 
    return sum;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0); 
    memset(head, -1, sizeof(head));
    cin >> n >> w0;
    for(int i = 2; i <= n ;i ++)
      cin >> a[i];
    for(int i = 1;i < n; i++)
     {
         int x,y,w;
         cin >> x >> y >> w;
         add(x, y, w);
         add(y, x, w);
     }
     int l = 1, r = 1e9;
     while(l <= r)
     {
         int mid = (l + r) >> 1;
         if(check(mid)) r = mid - 1;
         else l = mid + 1;
     }
    cout << l << endl; 
    return 0;
}

L1-8道路铺设

每次将后一个元素比前一个元素多的部分相加即可.因为后一个元素比前面少的部分必定会被前一个元素在填充时一起填充掉,所以只要算多的部分即可.

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

const int N = 1e5+10;
int n,m,t;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int w0,w[N],a[N];
    memset(w, 0, sizeof(w));
    cin >> n;
    int last,ans = 0,ma = -1;
    for(int i = 0; i < n;i ++)
     cin >> a[i];
     ans = last = a[0];
    for(int i = 1; i < n; i ++)
    {
        //int last = a[0];
        ans += max(0, a[i] - last);
        last = a[i];
    }
    cout << ans << endl;
    return 0;
}

L2-1货币系统

至少会有m = 1使得任务完成, 

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <utility>
#define inf 0x3f3f3f3f
#define endl '\n'
#define int long long

using namespace std;

const int N = 3e5+10;

//typedef long long ll;

int n,m,t;
bool vis[N];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> t;
    while(t--)
    {
        cin >> n;
        int ans = n;
        vector<int> a;
        memset(vis,0,sizeof(vis));
        for(int i = 0; i < n ;i++)
        {
            int x;
            cin >> x;
            a.push_back(x);
        }
        sort(a.begin(), a.end());
        for(int i = 0; i * a[0] <= a[n - 1]; i++)
            vis[i * a[0]] = 1;
        for(int i = 1;i < a.size(); i ++)
        {
            if(vis[a[i]])
            {
                ans -- ;
                continue;
            }
            for(int j = 0;j + a[i] <= a[n-1]; j++)
            {
                if(vis[j])
                 vis[j + a[i]] = 1;
            }
        }
        cout << ans << endl;
     } 
    
    
    return 0;
}