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

题解：
给出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;
}

题解：
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;
}

题解：
存在一个累加器，每次可以对一个数进行加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;
}

题解：
有三个整数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;
}

题解：
一个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;//1kint ans2 = 0;//1nint ans3 = 0;//knif(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;
}

题解：
给定一个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;
}

题解：
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;
}

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

#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;
}