河南萌新联赛2024第（三）场：河南大学

河南萌新联赛2024第（三）场：河南大学

2024.7.31 13:00————15:00

过题数5/13
补题数8/13

• 圆周率日挑战
• 正则表达式
• Circle
• 开心消消乐（Right Version）
• 区间
• 累加器
• 求值
• 魔法
• 游戏
• keillempkill学姐の卷积
• 暴食之史莱姆
• SSH
• 推箱子

B - 正则表达式

题解：
给出n个ip地址，试问每个ip地址是否合法，ip地址形式如x.x.x.x，要求x属于0——255。
签到题
代码：

#include<bits/stdc++.h>

using namespace std;
#define int long long
int n;

signed main() {
    cin >> n;
    int ans = 0;
    while(n--) {
        string s;
        cin >> s;
        int res = 0;
        bool st = true;
        for (int i = 0; i <s.length(); i++) {
            if(s[i] == '.') {
                if(res <0 || res > 255)st = false;
                res = 0;
                continue;
            }
            res = res*10+(s[i]-'0');
        }
        if(res <0 || res > 255)st = false;
        if(st)ans++;
    }cout << ans << endl;
    return 0;
}

C - Circle

题解：
t组询问，求n个圆可以分割的最大区域数。
可以想像，每次新加入一个圆最多可以和前面的圆各自分别有俩个交点，形成2个新的区域，所以第n个圆可以与前面的圆共同形成2(n-1)个区域，就有一个递推公式，最后可以得出n*n-n+2就是所能获得的最大区域数。
代码：

#include<bits/stdc++.h>

using namespace std;
#define int long long
int t;

signed main() {
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        if(n == 0)cout << 1 << ' ';
        else cout << n*n-n+2 << ' ';
    }
    return 0;
}

F - 累加器

题解：
存在一个累加器，每次可以对一个数进行加1操作，对一个数x进行y次累加操作，总共有多少位发生变化。
用一个数组储存每加一之后的位数变化，前缀和维护，每次查询即可。这里担心超时所以用了一个简便方法，打表可得每次增加的值是从后往前找到的第一位0的位置。
代码：

#include<bits/stdc++.h>

using namespace std;
#define int long long
const int N = 2e6+5;
int t;
int qz[N];

signed main() {
    for (int i = 2; i <= 2000005; i++) {
        int p = i-1;
        int res = 1;
        while(p) {
            if(p & 1)res++;
            else break;
            p >>= 1;
        }
        qz[i] = qz[i-1]+res;
    }
    cin >> t;
    while(t--) {
        int x,y;
        cin >> x >> y;
        cout << qz[x+y]-qz[x] << endl;
    }
    return 0;
}

G - 求值

题解：
有三个整数a,b,c，求三个整数x,y,z,满足x+y+z=n，且0<=x,y,z,使得xa+yb+c*z-w的绝对值最小。
先遍历x的值，固定以后，由于z=n-x-y，可以代入消去z，得到y的值越大时整个式子的值会越大，所以这是一个随着y递增的式子，二分并分情况讨论大于0和小于0的情况，找到大于0的最小值，小于0的最大值，然后进行比较赋值。
代码：

#include<bits/stdc++.h>

using namespace std;
#define int long long
int t;

signed main() {
    cin >> t;
    while(t--) {
        int ans = 1e18+11;
        int a,b,c,n,w;
        cin >> a >> b >> c >> n >> w;
        if(b < c)swap(b,c);
        for (int i = 0; i <= n; i++) {
            int x = a*i-w;
            int my = n-i;
            int res = -1,ts = -1;
            int l = 0,r = my;
            while (l <= r) {
                int mid = (l+r)/2;
                if(mid*b + (my-mid)*c + x >= 0) {
                    res = mid*b + (my-mid)*c + x;
                    r = mid-1;
                }else l = mid+1;
            }
            int ll = 0,rr = my;
            while(ll <= rr) {
                int mid = (ll+rr)/2;
                if(mid*b + (my-mid)*c + x <= 0) {
                    ts = -(mid*b + (my-mid)*c + x);
                    ll = mid+1;
                }else rr = mid-1;
            }
            if(res != -1) ans = min(res,ans);
            if(ts != -1) ans = min(ans,ts);
        }
        cout << ans << endl;
    }
    return 0;
}

I - 游戏

题解：
一个n个点m条边的无向图，每条边有一个花费和状态，状态为0表示被锁住，1表示可通过，节点k出有钥匙，问从1到n的最小话费，无法到达输出-1。
先跑一遍Dijkstra，看看从1能不能跑到k，然后从k开始跑一遍Dijkstra跑到n，计算从1直接到n，和从1拿了钥匙再到n的较小值，如果都跑不到，那就输出-1。
代码：

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

using namespace std;
#define int long long
const int N = 2e6+5;
int head[N],dis[N],vis[N];
int n,m,k;
int cnt;
bool st = false;
typedef pair<int,int> PII;
const int INF  = 1e11;

struct uth{
    int to,w,next,zt;
}edge[N];

void add_edge(int u,int v,int w,int kaka) {
    cnt++;
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    edge[cnt].zt = kaka;
    head[u] = cnt;
}

void dij(int x) {
    priority_queue<PII,vector<PII>,greater<PII>>pq;
    pq.push(make_pair(0,x));
    dis[x] = 0;
//    fa[x] = -1;
    while(!pq.empty()) {
        x = pq.top().second;
        vis[x] = 1;
        pq.pop();
        for (int i = head[x];i!= -1; i=edge[i].next) {
            if(!vis[edge[i].to]) {
                int v = edge[i].to;
                int weight = edge[i].w;
//                cout << dis[x] <<' ' <<  weight << endl;
//                cout << v << '.' << dis[v] << endl;
                if(dis[v] > dis[x] + weight) {
                    if(edge[i].zt == 0)continue;
                    dis[v] = dis[x]+weight;
                    pq.push(make_pair(dis[v],v));
                    if(v == k)st = true;
                }
            }
        }
    }
}

void dij1(int x) {
    priority_queue<PII,vector<PII>,greater<PII>>pq;
    pq.push(make_pair(0,x));
    dis[x] = 0;
    while(!pq.empty()) {
        x = pq.top().second;
        vis[x] = 1;
        pq.pop();
        for (int i = head[x];i!= -1; i=edge[i].next) {
            if(!vis[edge[i].to]) {
                int v = edge[i].to;
                int weight = edge[i].w;
//                cout << dis[x] <<' ' <<  weight << endl;
//                cout << v << '.' << dis[v] << endl;
                if(dis[v] > dis[x] + weight) {
                    dis[v] = dis[x]+weight;
                    pq.push(make_pair(dis[v],v));
                }
            }
        }
    }
}

signed main() {
    memset(head,-1,sizeof head);
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i <= N; i++) dis[i] = 1e11;
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        add_edge(a,b,c,d);
        add_edge(b,a,c,d);
    }
    dij(1);
    int ans1 = 0;//1k
    int ans2 = 0;//1n
    int ans3 = 0;//kn
    
    if(dis[n] == 1e11 && !st)cout << "-1";
    else {
        ans1 = dis[k];
        ans2 = dis[n];
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i <= N; i++) dis[i] = 1e11;
        dij1(k);
        ans3 = dis[n];
        int res = min(ans2,ans1+ans3);
        cout << res;
    }
    return 0;
}

J - keillempkill学姐の卷积

题解：
给定一个n行n列的卷积核，m行m列需要进行卷积的矩阵，输出一个(m-n+1)*(m-n+1)的矩阵，表示卷积结果。
一道模拟题。
代码：

#include<bits/stdc++.h>

using namespace std;
#define int long long
const int N = 25;
int n,m;
int a[N][N];
int b[N][N];
int an[N][N];

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    for (int i= 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> b[i][j];
        }
    }
//     for(int i=1;i<=k;i++){
//         for(int j=1;j<=l;j++){
//             int ans=0;
//             for(int p=0;p<n-k+1;p++){
//                 ans+=sum[i+p][j+m-l]-sum[i+p][j-1];
// //                cout << sum[i+p][j+l-1]-sum[i+p][j-1] << ".";
// //                cout << ans << ' ';
//             }
//         }
//     }
    
    for (int i = 1; i <= m-n+1; i++) {
        for (int j = 1; j <= m-n+1; j++) {
            int res = 0;
            for (int k = i; k <= i+n-1;k++) {
                for (int p = j; p <= j+n-1; p++) {
                    res += (b[k][p]*a[k-i+1][p-j+1]);
                }
            }
            an[i][j] = res;
            cout << an[i][j] << ' ';
        }
        cout << endl;
    }
 
    return 0;
}

K - 暴食之史莱姆

题解：
n只史莱姆，每只只可以吃体积严格小于它的邻居，并且会变成它的体积。输出每只史莱姆最多可以吃的个数。
每只史莱姆往左边看，都可以吃掉第一只比它小的史莱姆，所以有一个递推公式，单调栈，每次加上1。右边同理，所以左右相加-2即可。
代码：

#include<bits/stdc++.h>

using namespace std;
#define int long long
const int N = 2e5+10;
int n;
int a[N],f[N],g[N];

signed main() {
    cin >> n;
    stack<int>ff;
    stack<int>gg;
    ff.push(-1);
    for (int i= 1; i <= n; i++)  {
        cin >> a[i];
        if(a[i] >= ff.top()) {
            f[i] = ff.size();
            ff.push(a[i]);
        }
        else {
            while(a[i] < ff.top()) {
                ff.pop();
            }
            f[i] = ff.size();
            ff.push(a[i]);
        }
    }
    gg.push(-1);
    for (int i = n; i >= 1; i--) {
        if(a[i] >= gg.top()) {
            g[i] = gg.size();
            gg.push(a[i]);
        }
        else {
            while(a[i] < gg.top()) {
                gg.pop();
            }
            g[i] = gg.size();
            gg.push(a[i]);
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << f[i]+g[i]-2 << ' ';
    }
    return 0;
}

L - SSH

题解：
一个大模拟，不说了看题自己理解。
⚠️注意一个点，同一台主机上的用户不能重名，不同主机上的用户有可能重复，每个用户有仅属于自己的一些公钥。
代码：

#include<bits/stdc++.h>

using namespace std;
#define int long long
int n,m,q;
map<string,string>my;
map<string,int>mp;
vector<string>tq[15];
vector<string>nam[1005];

signed main() {
    cin >> m >> n >> q;
    for (int i = 0; i < m; i++) {
        string a,b;
        cin >> a >> b;
        my[b] = a;
    }
    int res = 1;
    for (int i = 1; i <= n; i++) {
        string ls;
        int k;
        cin >> ls >> k;
        mp[ls] = i;
        for (int j = 0; j < k; j++) {
            string aaa;
            cin >> aaa;
            tq[i].push_back(aaa);
            if(mp[aaa]);
            else mp[aaa] = res++;
            int t;
            cin >> t;
            for (int zt = 0; zt < t; zt++) {
                string gy;cin >> gy;
                nam[mp[aaa]].push_back(gy);
            }
        }
    }
    while(q--) {
        string uer,ip,pri;
        cin >> uer >> ip >> pri;
        string mm = my[pri];
        bool st = false;
        for (auto x : tq[mp[ip]]) {
            if(x == uer) {
                st = true;
                break;
            }
        }
        bool stt = false;
        if(st) {
            for (auto y : nam[mp[uer]]) {
                if(y == mm) {
                    stt = true;
                    break;
                }
            }
        }
        if(st && stt) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}