K-暴食之史莱姆_河南萌新联赛2024第（三）场：河南大学 (nowcoder.com)
思路: 注意到，当史莱姆的邻居体积比自己大时，可以使邻居吃掉其他史莱姆来使邻居体积缩小，再被史莱姆吃掉 那么，通过观察容易得到。在只考虑左侧史莱姆的情况，编号为i的史莱姆能吃掉的同伴个数，一定是左边第一个比i体积小的史莱姆所能吃的数量。 右侧同理。由于史莱姆可以优先选择左右中较大者吃，且吃 的条件为大于等于，所以答案就是左侧+右侧能吃的个数。
int n;
int arr[200005];
int ans[200005];
题解:
注意到，当史莱姆的邻居体积比自己大时，可以使邻居吃掉其他史莱姆来使邻居体积缩小，再被史莱姆吃掉
那么，通过观察容易得到。在只考虑左侧史莱姆的情况，编号为i的史莱姆能吃掉的同伴个数，一定是左边第一个比i体积小的史莱姆所能吃的数量。
右侧同理。由于史莱姆可以优先选择左右中较大者吃，且吃 的条件为大于等于，所以答案就是左侧+右侧能吃的个数。
暴食之史莱姆
https://ac.nowcoder.com/acm/contest/87865/K
void solve(){ 补K 单调栈--维护一个单调的序列,当栈顶元素比现在元素大时就pop.再push当前元素
cin>>n;
for(int i=1;i<=n;i++) cin>>arr[i];
stack<int> stk;
for(int i=1;i<=n;i++){ 左侧能吃多少个
while(stk.size()&&stk.top()>arr[i]) stk.pop();
ans[i]+=stk.size();
stk.emplace(arr[i]);
}
while(stk.size()) stk.pop();
for(int i=n;i>=1;i--){ 右侧能吃多少个
while(stk.size()&&stk.top()>arr[i]) stk.pop();
ans[i]+=stk.size();
stk.emplace(arr[i]);
}
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
}M-推箱子_河南萌新联赛2024第（三）场：河南大学 (nowcoder.com)
思路:记录状态vis[i][j][sx'][sy']为人走到(i,j)箱子位置在(sx',sy')进行暴力bfs即可.
int xx,yy,txx,tyy,sxx,syy,m;
bool block[40][40];
bool vis[40][40][40][40]; vis[i][j][sx'][sy']为人走到(i,j)箱子位置在(sx',sy')的状态
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int ans=-1;
bool ok(int x,int y,int sx,int sy){
return x>=1&&x<=30&&y>=1&&y<=30&&!block[x][y]&&!vis[x][y][sx][sy]&&sx>=1&&sx<=30&&sy>=1&&sy<=30&&!block[sx][sy];
}
void bfs(int x0,int y0){
vis[x0][y0][sxx][syy]=1;
queue<array<int,5>> que;
que.emplace((array<int,5>){x0,y0,sxx,syy,0});
while(que.size()){
int xx0=que.front()[0],yy0=que.front()[1];
int sxx0=que.front()[2],syy0=que.front()[3];
int d=que.front()[4];
que.pop();
if(sxx0==txx&&syy0==tyy){
ans=d;
return;
}
for(int i=0;i<4;i++){
int x=xx0+dx[i],y=yy0+dy[i];
int sx=sxx0+dx[i],sy=syy0+dy[i];
if(!(x==sxx0&&y==syy0)&&ok(x,y,sxx0,syy0)){ !(x==sxx0&&y==syy0),一开始判错了..
que.emplace((array<int,5>){x,y,sxx0,syy0,d+1});
vis[x][y][sxx0][syy0]=1;
}
if(x==sxx0&&y==syy0&&ok(x,y,sx,sy)){
que.emplace((array<int,5>){x,y,sx,sy,d+1});
vis[x][y][sx][sy]=1;
}
}
}
}
推箱子
https://ac.nowcoder.com/acm/contest/87865/M
void solve(){ 补M 维度比较多的bfs
cin>>xx>>yy>>txx>>tyy>>sxx>>syy>>m;
for(int i=1;i<=m;i++){
int x,y; cin>>x>>y;
block[x][y]=1;
}
bfs(xx,yy);
cout<<ans;
}H-魔法_河南萌新联赛2024第（三）场：河南大学 (nowcoder.com)
思路:三维dp.dp[i][j][h]定义为:走到(i,j)剩余h体力,需要最少使用魔法的次数.跟之前vj上做的那题四维dp差不多，这个简单很多。
int n,m,h;
魔法
https://ac.nowcoder.com/acm/contest/87865/H
void solve(){
cin>>n>>m>>h;
vector<vector<int>> maze(n+10,vector<int>(m+10));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>maze[i][j];
}
}
int dp[n+10][m+10][h+10]; dp[i][j][h]定义为:走到(i,j)剩余h体力,需要最少使用魔法的次数
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int g=0;g<=h;g++) dp[i][j][g]=INT_MAX;
dp[1][1][h]=0;
int ans=INT_MAX;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int g=0;g<=h;g++){
if(i<n){ 往下走
if(g>maze[i+1][j]) dp[i+1][j][g-maze[i+1][j]]=min(dp[i+1][j][g-maze[i+1][j]],dp[i][j][g]);
dp[i+1][j][g]=min(dp[i+1][j][g],dp[i][j][g]+1);
}
if(j<m){ 往右走
if(g>maze[i][j+1]) dp[i][j+1][g-maze[i][j+1]]=min(dp[i][j+1][g-maze[i][j+1]],dp[i][j][g]);
dp[i][j+1][g]=min(dp[i][j+1][g],dp[i][j][g]+1);
}
if(i==n&&j==m) ans=min(ans,dp[i][j][g]);
}
}
}
cout<<ans;
}G-求值_河南萌新联赛2024第（三）场：河南大学 (nowcoder.com)
思路:枚举x，然后可以二分y，也可以三分y。二分的话需要对A,B,C排序，三分可以直接分.
int A,B,C,n,W; 也可以枚举x,直接三分y,z可知,然后check
求值
https://ac.nowcoder.com/acm/contest/87865/G
void solve(){ G 裴蜀?--nope. 二分?--对A,B,C排序枚举x,二分y,z可知--太对了太对了,有单调性的
cin>>A>>B>>C>>n>>W;
int minn=min({A,B,C}),maxn=max({A,B,C});
B=A+B+C-minn-maxn,A=minn,C=maxn;
int ans=LONG_LONG_MAX;
for(int a=0;a<=n;a++){
int l=0,r=n-a;
while(l<=r){
int mid=(l+r)>>1;
int res=a*A+mid*B+(n-a-mid)*C;
ans=min(ans,abs(res-W));
if(res>W) l=mid+1;
else r=mid-1;
}
}
cout<<ans<<endl;
}F-累加器_河南萌新联赛2024第（三）场：河南大学 (nowcoder.com)
思路:这题写复杂了。直接计算(0->a+x)的变动次数减(0->a)的变动次数即可。
累加器
https://ac.nowcoder.com/acm/contest/87865/F
void solve(){ F wa爆了. .... 想复杂了,实现也很抽象..直接(0->a+x)减(0->a)即可
int n; cin>>n;
for(int i=1;i<=n;i++){
int ans=0,a,x; cin>>a>>x;
int up=0;
for(int j=0;;j++){
if((1<<j)>a&&(1<<j)>x) break;
ans+=x/(1<<j);
这里要想清楚进位:当本来就是1的时候可以change&1 or up 或者本来是0,但是同样拥有change&1 up 也可以进位
if( (((x/(1<<j)))&1 || up ) && (a>>j)&1 || ((x/(1<<j)))&1 && up ) ans++,up=1;
else up=0;
}
cout<<ans<<endl;
}
}A-圆周率日挑战_河南萌新联赛2024第（三）场：河南大学 (nowcoder.com)
思路:这题没补。c++得用高精度，Python的话可以直接秒了，但是不会Python，单纯贴一下Python的代码写法。
import decimal
from decimal import *
getcontext().prec = 40
pi = decimal.Decimal("3.1415926535897932384626433832795028841971")
ans, d = (0, 0), pi
for i in range(int(input())):
p, a = list(map(int, input().split()))
dis = abs(decimal.Decimal(decimal.Decimal(p) / decimal.Decimal(a)) - pi)
if dis == d:
if p < ans[0]:
ans = (p, a)
elif dis < d:
d = dis
ans = (p, a)
print(ans[0], ans[1])