题目链接

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

简单，没什么说的，但是要注意尽量不要使用小数去运算，转化成正整数运算不会出现精度问题

#include<iostream>

using namespace std;

int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    int sum=a+b+c;
    if(sum>=180)puts("NO");
    else puts("YES");
    return 0;
}

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

就是简单的把字符串转化成数字比较一下，比赛脑子瓦特了，搞了半天

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

using namespace std;

const int N = 100010;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    string s1, s2;
    cin >> s1 >> s2;
    long long ans1 = 1, ans2 = 1;
    for (int i = 0; i < s1.size(); i++)ans1 *= (s1[i] - 'A' + 1);
    for (int i = 0; i < s2.size(); i++)ans2 *= (s2[i] - 'A' + 1);
    //cout<<ans1<<' '<<ans2<<endl;
    if ((ans1 % 47) == (ans2 % 47))puts("GO");
    else puts("STAY");
    //cout<<'A'-'A'<<endl;
    return 0;
}

C L1-3成绩

仔细读题就好了

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

using namespace std;

const int N = 100010;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int a, b, c;
    cin >> a >> b >> c;
    cout << a * 0.2 + b * 0.3 + c * 0.5;
    return 0;
}

D L1-4素数分布

打表找素数,学习一下素数的几种筛法

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

using namespace std;

const int N = 100010;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        long long cnt = 0;
        for (int i = 2; i  <= n; i++) {
            bool flag = true;
            for (int j = 2; j < i; j++) {
                if (i % j == 0){
                    flag = false;
                    break;
                }
            }
            if (flag)cnt++;
        }
        cout << cnt << endl;
    }
    return 0;
}

E L1-5便便传送门(一)

把所有可能出现的情况考虑进去就好了，贪心，距离近的痛拖拉机，距离远的用传送门，注意a，b的相对大小不确定。

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

using namespace std;

const int N = 100010;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int a, b, x, y;
    cin >> a >> b >> x >> y;
    if(a>b)swap(a,b);
    int dis = 0;
    dis += abs(a - min(x, y));
    dis += abs(b - max(x, y));
    if(dis<abs(a-b))cout << dis << endl;
    else cout<<abs(a-b)<<endl;
    return 0;
}

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

这题是相当简单了，直接读入所有数，排个序即可。

看看我愚蠢的做法，我要被蠢哭了

#include<iostream>
#include<cstring>
#include<algorithm>
#define int long long

using namespace std;

const int N = 100010;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    int a[n + 10];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int y;
    cin >> y;
    int ret = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] > y && ret == 0)cout << y << ' ', ret = 1;
        cout << a[i] << ' ';
    }
    if(ret==0)cout<<y<<' ';
    return 0;
}

直接读入排序它不香

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

using namespace std;

int a[55];
int n;

int main()
{
    cin>>n;
    for(int i=0;i<=n;i++)cin>>a[i];
    sort(a,a+n+1);
    for(int i=0;i<=n;i++)cout<<a[i]<<' ';
    return 0;
}

G L1-7货物收集

这个题就是关于图论的题，它的意思就是尽量耗费少的代价会获得目标货物和，可以看成最短路径的问题，可以用迪杰斯特拉来做，也可以直接用bfs来做，一层一层的扩展，还可以使用dfs+二分来做。

bfs(使用优先队列来实现)

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

typedef pair<int,int> PII;

const int N = 1000010;

int n, W;
int va[N];  //货物储备
int e[N], ne[N], h[N], idx, w[N];  //w为所要消耗的体力
bool vis[N];

void add(int x,int y, int c) {
    e[idx] = y, w[idx] = c, ne[idx] = h[x], h[x] = idx++;
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n >> W;
    for (int i = 2; i <= n; i++)cin >> va[i];
    for (int i = 1; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
//    for (int i = 1; i <= n; i++) {
//        cout << i << ':';
//        for (int j = h[i]; j != -1; j = ne[j]) {
//            cout << e[j] << '|' << w[j] << ' ';
//        }
//        puts("");
//    }
    va[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> q;
    int sum = 0;
    int ans = 0;
    q.push({0, 1});
    while (q.size()) {
        auto t = q.top();
        q.pop();
        ans = max(ans, t.first);
        sum += va[t.second];
        if (sum >= W)break;
        for (int i = h[t.second]; i != -1; i = ne[i]) {
            if (!vis[e[i]]) {
                vis[e[i]] = true;
                q.push({w[i], e[i]});
            }
        }
    }
    cout << ans << endl;
    return 0;
}

迪杰斯特拉算法求最短路

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

#define PII pair<int,int>
#define f first
#define s second

using namespace std;

const int N = 150010, INF = 0x3f3f3f3f;

int n, m;
int h[N], e[N], w[N], ne[N], idx;
bool vis[N];
int dis[N];
int val[N];
int sum;

void add(int x,int y,int z) {
    e[idx] = y, w[idx] = z, ne[idx] = h[x], h[x] = idx++;
}

int dijkstra() {
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    priority_queue<PII, vector<PII >, greater<PII>> heap;
    heap.push({0, 1});
    while (heap.size()) {
        auto t = heap.top();
        heap.pop();
        if (vis[t.s])continue;
        vis[t.s] = true;
        sum += val[t.s];
        if (sum >= m)return dis[t.s];
        for (int i = h[t.s]; i != -1; i = ne[i]) {
            if (dis[e[i]] > max(dis[t.s], w[i])) {
                dis[e[i]] = max(dis[t.s], w[i]);
                heap.push({dis[e[i]], e[i]});
            }
        }
    }
    if (dis[n] == INF)return -1;
    return dis[n];
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for(int i=2;i<=n;i++)cin>>val[i];
    for(int i=1;i<n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    cout << dijkstra() << endl;
    return 0;
}

H L1-8道路铺设

这个题不知道为什么，考试愣是没想起来，所以考试写了个递归最后超时只拿到了80%的分数，可以用dfs来做，但是正解应该是，从第一个开始遍历，如果后面的一个比它大，就对这个没有贡献，填这个会把下一个也填平，如果后面的更大就填不平，还需要用后一个减去前一个的插值才可以填平。

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

using namespace std;

const int N = 100010;

int n;
int a[N];

int main() {
    cin >> n;
    int sum = 0;
    for (int i = 1; i <= n; i++)cin >> a[i];
    sum += a[1];
    for (int i = 2; i <= n; i++) {
        if (a[i] > a[i - 1])sum += a[i] - a[i - 1];
    }
    cout << sum << endl;
    return 0;
}

dfs

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

using namespace std;

const int N = 100010;

int n;
int a[N];
int res;

void dfs(int l,int r) {
    int Min=100000010;
    for (int i = l; i <= r; i++)Min = min(Min, a[i]);
    for (int i = l; i <= r; i++)a[i] -= Min;
    res += Min;
    int pos = -1;
    for (int i = l; i <= r; i++) {
        if (pos == -1 && a[i] > 0)pos = i;
        else if (pos != -1 && a[i] == 0) {
            dfs(pos, i-1);
            pos = -1;
        }
    }
    if (pos != -1)dfs(pos, r);
    return ;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> a[i];
    dfs(1, n);
    cout << res << endl;
    return 0;
}

I L2-1货币系统

这个就是一个裸完全背包问题，抽象一下就是前面小的能不能凑成后面大的，如果能，后面的就是多余的，不需要的，所以就变成了先用完全背包，把能凑出来的标记一下，如果是用这个去凑，这个就不能标记，最后统计，如果给出的面值被标记了，那就是不需要的。

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

using namespace std;

const int N = 110, M = 25010;

int n;
int a[N];
int f[M];
bool vis[M];

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        int ans=n;
        for (int i = 1; i <= n; i++)cin >> a[i];
        sort(a+1,a+1+n);
        memset(vis,false,sizeof vis);
        memset(f,0,sizeof f);
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            if (vis[a[i]])continue;
            for (int j = a[i]; j <= 25000; j++) {
                f[j]|=f[j-a[i]];
                if (f[j])vis[j] = true;
            }
            vis[a[i]]=false;
        }
        //for (int k = 1; k <= 30; k++)cout<<vis[k]<<' ';cout<<endl;
        for (int i = 1; i <= n; i++)if (vis[a[i]])ans--;
        cout << ans << endl;
    }
    return 0;
}

J L2-2***

就是一道模拟题，读懂题目意思，耐心点。

#include<iostream>
#include<cstring>
#include<algorithm>
#define int long long

using namespace std;

const int N = 100010;

int l, r;
int n;
int a[N];
int m, p1, s1, s2;

int32_t main() {
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> a[i];
    cin >> m >> p1 >> s1 >> s2;
    for (int i = 1; i < m; i++)l += (m - i) * a[i];
    for (int i = m + 1; i <= n; i++)r += (i - m) * a[i];
    if (p1 > m)r += (p1 - m) * s1;
    else l += (m - p1) * s1;
    int diff = abs(l - r);
    int pos = m;
    for (int i = 1; i <= n; i++) {
        if (i == m)continue;
        else if (i < m) {
            int dif = abs((m - i) * s2 + l - r);
            if (dif < diff)diff = dif, pos = i;
        } else {
            int dif = abs((i - m) * s2 + r - l);
            if (dif < diff)diff = dif, pos = i;
        }
    }
    cout << pos << endl;
    return 0;
}