2022河南萌新联赛第（五）场：信息工程大学

2022河南萌新联赛第（五）场：信息工程大学

B. 交通改造

Solution

按分值将所有道路从小到大排序，因为要将所有的道路都连通，所以改造的道路数必定是\(\ n-1\)条，从小到大将道路连通，第\(\ n-1\)条的分值就是最大的分值

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 305;

int fa[N];
struct node {int u, v, c;} road[100005];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
void merge(int x, int y) {fa[find(x)] = find(y);}

signed main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++) cin >> road[i].u >> road[i].v >> road[i].c;
    sort(road + 1, road + m + 1, [&] (node a, node b) {return a.c < b.c;});
    for(int i = 1; i <= n; i++) fa[i] = i;
    int count = 0;
    int i;
    for(i = 1; i <= m; i++)
    {
        if(find(road[i].u) != find(road[i].v))
        {
            merge(road[i].u, road[i].v);
            count++;
        }
        if(count == n - 1) break;
    }
    cout << count << ' ' << road[i].c;
    return 0;
}

C. 丢手绢

Solution

不难推出最后的位置

\(pos=(x+10^k*m)\% n\iff pos=(x\%n+10^k*m\%n)\%n\)

用一个快速幂就行了

Code

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

int kpow(int a, int b, int p)
{
    int ans = 1;
    while(b)
    {
        if(b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans % p;
}

signed main()
{
    int n, m, k, x;
    cin >> n >> m >> k >> x;
    int pos = (x % n + kpow(10, k, n) * m % n) % n;
    cout << pos;
    return 0;
}
//pos = (x + m * 10 ^ k) % n

D. 敌情侦查

Solution

因为第一个人只可以看到两个位置，所以可以对第一个位置的人数进行枚举，推出后面的人数。

递推公式\(a[i+1]=b[i]-a[i]-a[i-1]\)

只需要判断对于每一个方案是否可行就可以了

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;

int n, ans;
int a[N], b[N];

bool check(int x) //设第一个位置有x个人，可以跟据前两个位置的人数推出后面一个位置的人数
{
    a[1] = x;
    a[2] = b[1] - x;
    for(int i = 2; i < n; i++) a[i + 1] = b[i] - a[i] - a[i - 1];
    if(a[n] + a[n - 1] == b[n]) return 1; //判断这个方案是否可行
    return 0;
}

signed main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> b[i];
    int t = b[1];
    for(int i = 0; i <= b[1]; i++) //枚举第一个位置的人数
    {
        if(check(i)) ans++;
    }
    cout << ans;
    return 0;
}

F. 分割草坪

Solution

画图可以发现

以顶点1切每一个顶点得到的魔力值会是最小的，并且每一个多边形的魔力值都等于上一个多边形的魔力值加上一个三角形的魔力值，由此可以得到递推公式：\(a[i]=a[i-1]+i*(i-1)(i>=3)\)

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 6;

int a[N];
signed main()
{
    int n;
    cin >> n;
    a[3] = 6;
    for(int i = 4; i <= n; i++)
    {
        a[i] = a[i - 1] + i * (i - 1);
    }
    cout << a[n];
    return 0;
}

H. 小明喝奶茶

Solution

将所有奶茶店按照奶茶价格升序排序，遍历每一个奶茶店。如果它正在营业，就可以喝这家奶茶店，如果奶茶不够，再遍历后面的奶茶店；否则下一天。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;

struct node {int l, r, c, p;} d[N];
signed main()
{
    int n, m, k;
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++) cin >> d[i].l >> d[i].r >> d[i].c >> d[i].p;
    sort(d + 1, d + m + 1, [&] (node a, node b) {return a.p < b.p;});
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        int cnt = 0;
        for(int j = 1; j <= m; j++)
        {
            if(i >= d[j].l && i <= d[j].r)
            {
                if(d[j].c < k - cnt) ans += d[j].c * d[j].p, cnt += d[j].c;
                else {ans += d[j].p * (k - cnt); break;} 
            }
        }
    }
    cout << ans;
    return 0;
}

J. AC自动机

Solution

第一次二分找到最大值，将最大值作为第二次二分的上限。需要注意的是AC一道题后会删除所有代码，因此要将sum清空。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;

int len, k, a[N];

int check(int x)
{
    int cnt = 0, sum = 0;
    for(int i = 1; i <= len; i++)
    {
        sum += a[i];
        sum = max(sum, 0ll);
        if(sum >= x) cnt++, sum = 0;
    }
    return cnt;
}

signed main()
{
    cin >> len >> k;
    for(int i = 1; i <= len; i++) cin >> a[i];
    int lx = 1, rx = 0x3f3f3f3f3f3f3f3f;
    while(lx <= rx) //找最大值
    {
        int mid = lx + rx >> 1;
        if(check(mid) >= k) lx = mid + 1;
        else rx = mid - 1;
    }
    if(check(rx) != k) return cout << -1, 0;
    int li = 1, ri = rx;
    while(li <= ri) //找最小值
    {
        int mid = li + ri >> 1;
        if(check(mid) <= k) ri = mid - 1;
        else li = mid + 1;
    }
    cout << li << ' ' << rx;
    return 0;
}
//注意等于号

K. 矩阵生成

Solution

先将数字1放到第一行中间，用x，y记录坐标，对于每一个数i，判断条件并对x和y进行相应的变化。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'

int mp[45][45];

signed main()
{
    int n; 
    cin >> n;
    memset(mp, -1, sizeof mp);
    int x = 1, y = n / 2 + 1;
    for(int i = 1; i <= n * n; i++)
    {
        mp[x][y] = i;
        if(x == 1 && y != n) x = n, y++;
        else if(y == n && x != 1) y = 1, x--;
        else if(x == 1 && y == n) x++;
        else if(mp[x - 1][y + 1] == -1) x--, y++;
        else x++;
        
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++) 
        {
            cout << mp[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}