传送门：河南萌新联赛2024第（三）场：河南大学_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ
B 正则表达式
思路：模拟
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;void solve()
{int n; cin >> n;int res = 0;while (n--){int a, b, c, d;scanf("%d.%d.%d.%d", &a, &b, &c, &d);if (a >= 0 && a <= 255 && b >= 0 && b <= 255 && c >= 0 && c <= 255 && d >= 0 && d <= 255)res++;}cout << res << endl;}
signed main()
{//ios_base::sync_with_stdio(0); cin.tie(0);int tt = 1;while (tt--)solve();return 0;
}C Circle
题意：
思路：（模拟 + 找规律）可以记下来，当做结论
当 n == 0 时 f(n) = 1
当 n > 0 时 f(n) = n * n - n + 2
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{int n ;cin >> n;if( n == 0 )cout << 1 << " ";else cout << n * n - n + 2 << " ";
}
signed main()
{ios_base::sync_with_stdio(0); cin.tie(0);int tt;cin>>tt;while(tt--)solve();return 0;
}F 累加器
题意：
思路：
1. 处理一个前缀和 f[i] 表示从 0 到 i ，累加1的操作次数
2. 函数 test 处理 num1 , num2的二进制上数字的不同 eg 011 100 这两个二进制最终的答案为3
3. 处理答案 f[x+y] - f[x]
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
int f[N];
int test( int a , int b )
{int res = 0;while( a || b ){if( ( a % 2 ) != ( b % 2 ))res++;a /= 2; b /= 2;}return res;
}
int main()
{for(int i = 1; i <= N;i++)f[i] = f[i-1] + test( i , i - 1 );int tt;cin >> tt;while(tt--){int x , y;cin >> x >> y;cout << f[x + y] - f[x] << endl;}return 0;
}G 求值
题意：
思路：
1. 运用平均数的性质
令 c > b > a , sum = n * b（ 平均数 * n )，若 sum >= w 则说明当前的总和过大 ，应减小，将其中
的一个 b 变为 a ，总和则是 sum + a - b，若总和过小，应增大，将其中的一个 b 变为 c ，总和为
sum + c - b
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{int a , b , c ,n , w;cin >> a >> b >> c >> n >> w;int temp[3] = { a , b , c };sort( temp , temp + 3 );a = temp[0] ; b = temp[1] ; c = temp[2];int sum = b * n;int ans = abs(sum - w);while(n--){if( sum <= w )sum += c - b;else sum += a - b;ans = min(ans , abs(sum - w));}cout << ans <<endl;
}
signed main()
{int tt;cin >> tt;while(tt--)solve();return 0;
}H 魔法
题意
思路：
dp问题
状态表示：f[i][j][k] 从（1,1）到达（i,j）其中使用k次魔法的最大生命值
状态转移方程：
当前这个(i,j)点不使用魔法
f[i][j][k] = max( f[i][j][k] , f[i-1][j][k] - a[i][j] )
f[i][j][k] = max( f[i][j][k] , f[i][j-1][k] - a[i][j] )
当前这个点使用魔法：
f[i][j][k] = max( f[i][j][k] , f[i-1][j][k-1] );
f[i][j][k] = max( f[i][j][k] , f[i][j-1][k-1] );
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 3e3 + 10;
const int M = 3e3 + 10;
int a[N][M];
int main()
{int n, m, h;cin >> n >> m >> h;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++)cin >> a[i][j];}vector<vector<vector<int>>> f(n + 1, vector<vector<int>>(m + 1, vector<int>(n + m + 1)));for (int i = 0; i <= n; i++)for (int j = 0; j <= m; j++)for (int k = 0; k <= n + m; k++)f[i][j][k] = -0x3f3f3f3f;for (int i = 0; i <= n + m; i++)f[1][1][i] = h;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){for (int k = 0; k <= n + m; k++){if (i > 1 && f[i - 1][j][k] > a[i][j])f[i][j][k] = max(f[i][j][k], f[i - 1][j][k] - a[i][j]);if (j > 1 && f[i][j - 1][k] > a[i][j])f[i][j][k] = max(f[i][j][k], f[i][j - 1][k] - a[i][j]);if (i > 1 && k && f[i - 1][j][k - 1] > 0) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k - 1]);if (j > 1 && k && f[i][j - 1][k - 1] > 0)f[i][j][k] = max(f[i][j][k], f[i][j - 1][k - 1]);}}}for (int i = 0; i <= n + m; i++)if (f[n][m][i] > 0) {cout << i << endl; return 0;}return 0;
}I 游戏
题意：
思路：
1. 不取钥匙的最小花费
2. 取钥匙的最小花费
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int N = 2e5 + 10;
const int M = 1e6;
const int INF = 1e18;
int h[N] , hs[N] , e[M] , ne[M] , idx , w[M];
int n , m , k;
int dist[N]; bool st[N] = { 0 };
void add( int h[] , int a , int b , int c)
{e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;
}
int spfa(int h[] ,int start , int pp )
{memset( st , 0 , sizeof st );for(int i = 0 ;i <= n;i++)dist[i] = INF;dist[start] = 0;queue<int> que;que.push(start);st[start] = true;while(que.size()){auto t = que.front();que.pop();st[t] = false;for( int i = h[t] ; i != -1 ;i= ne[i] ){int j = e[i];if( dist[j] > dist[t] + w[i] ){dist[j] = dist[t] + w[i];if( !st[j] ){que.push(j);st[j] = true;}}}}return dist[pp];
}
signed main()
{memset( hs , -1 , sizeof hs );memset( h , -1 , sizeof h );cin >> n >> m >> k;for( int i = 0 ; i < m ;i++){int a , b , c , d;cin >> a >> b >> c >> d;add( h , a , b , c );add( h , b , a , c );if( d )add( hs , a , b , c ), add( hs , b , a , c );}ll res = spfa( hs, 1, n );ll temp = spfa( hs ,1,k ) + spfa( h , k,n );if( res >= INF && temp >= INF )cout << -1 << endl;else cout << min(res , temp) <<endl;return 0;
}K 暴食之史莱姆
题意:
思路：单调栈
#include <bits/stdc++.h>
using namespace std;
#define int long longsigned main()
{int n;cin >> n;vector<int> a(n + 1);for(int i = 1;i <= n;i ++) cin >> a[i];vector<int> res;vector<int> ans(n + 1);for(int i = 1;i <= n;i ++){while(res.size() && res.back() > a[i]) res.pop_back();ans[i] = res.size();res.push_back(a[i]);}while(res.size()) res.pop_back();for(int i = n;i >= 1;i --){while(res.size() && res.back() > a[i]) res.pop_back();ans[i] += res.size();res.push_back(a[i]);}for(int i = 1;i <= n;i ++) cout << ans[i] <<" ";cout << endl;
}
