2026年10月4日(day4题解）
2026-10-04 15:30:18
发布于：广东
23阅读
0回复
0点赞
第一题
#include<bits/stdc++.h>
using namespace std;
const int N=1000+10;
#define ll long long
char graph[N][N];
int vis[N][N];
void solve(){
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>graph[i][j];
vis[1][1]=1;
queue<pair<int,int>>que;
que.push({1,1});
while(que.size()){
auto cur=que.front();que.pop();
int x=cur.first,y=cur.second;
int len=1;
//枚举跳跳板；
if('1'<=graph[x][y]&&graph[x][y]<='9')len=graph[x][y]-'0';
for(int i=-len;i<=len;i++)
for(int flg=-1;flg<=1;flg+=2){//正负数
int nx=x+i,ny=y+(len-abs(i))*flg;
if(1<=nx&&nx<=n&&1<=ny&&ny<=m);else continue;
if(vis[nx][ny])continue;
if(graph[nx][ny]=='#')continue;
vis[nx][ny]=vis[x][y]+1;
que.push({nx,ny});
}
len=1;
//枚举上下左右四个方向；
for(int i=-len;i<=len;i++)
for(int flg=-1;flg<=1;flg+=2){//正负数
int nx=x+i,ny=y+(len-abs(i))*flg;
if(1<=nx&&nx<=n&&1<=ny&&ny<=m);else continue;
if(vis[nx][ny])continue;
if(graph[nx][ny]=='#')continue;
vis[nx][ny]=vis[x][y]+1;
que.push({nx,ny});
}
}
cout<<vis[n][m]-1<<endl;
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
第二题
解法1
//线段树的lazy标记版本//懒标记
//BFS+差分
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
ll a[N];
vector<int>graph[N];
ll sum[N];//sum[i]表示i点最终的值
void dfs(int inx,int fa){
sum[inx]+=sum[fa];
for(auto nxt:graph[inx]){
if(nxt==fa)continue;//不能回溯回去
dfs(nxt,inx);
}
}
void solve(){
int n;cin>>n;
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
graph[u].push_back(v);
graph[v].push_back(u);
}
int t;cin>>t;
while(t--){
int op,inx,val;
cin>>op>>inx>>val;
if(op==1)sum[inx]+=val;
else {
sum[1]+=val;
sum[inx]-=val;
}
}
dfs(1,0);
for(int i=1;i<=n;i++)cout<<sum[i]<<endl;
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
解法2
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
ll a[N];
int num=1;
ll dfs_num[N];//i节点的dfs序编号
ll num_dfs[N];//i编号对应的实际节点
ll son_num[N];//节点i的儿子个数
ll dif[N];//差分数组
vector<int>graph[N];
void dfs(int inx,int fa){
dfs_num[inx]=num++;
son_num[inx]++;
for(auto nxt:graph[inx]){
if(nxt==fa)continue;
dfs(nxt,inx);
son_num[inx]+=son_num[nxt];
}
}
void add(int inx,int val){//差分;
dif[dfs_num[inx]]+=val;
dif[dfs_num[inx]+son_num[inx]]-=val;
}
void solve(){
int n;cin>>n;//区间+val，单点查询。
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
graph[u].push_back(v);
graph[v].push_back(u);
}
dfs(1,0);
int t;cin>>t;
while(t--){
int op,inx,val;
cin>>op>>inx>>val;
if(op==1){
add(inx,val);
}else{
add(1,val);
add(inx,-val);
}
}
for(int i=1;i<=n;i++)dif[i]+=dif[i-1];
for(int i=1;i<=n;i++){
cout<<dif[dfs_num[i]]<<endl;
}
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
第四题
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
ll wl[N],n;//wl[i]表示i看守影响的范围（状压）0111
int cal1(int inx,int wl){//计算inx位置的看守对应wl的影响范围
int affect=(1<<(inx-1));//影响自己
//010
//100|001
while(wl--)affect|=(affect<<1)|(affect>>1);
//影响区间[1,n]
// (1<<n)-1//从最低位开始的n个1
return affect&((1<<n)-1);//最终得到守卫的影响区间
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>wl[i];
wl[i]=cal1(i,wl[i]);//将情况都进行状态压缩。
}
int q;cin>>q;
while(q--){
int k;cin>>k;
int table=0;//安排表
while(k--){
int x;cin>>x;
table|=(1<<(x-1));
}
ll ans=0;
for(int i=table;i>=0;i=((i-1)&table)){//枚举安排表的所有子状态
ll affect=0;//最终的影响
for(int j=1;j<=n;j++){
if((table&(1<<(j-1)))&&(i&(1<<(j-1)))==0){//在名单上，且没有被安排
affect^=wl[j];
}
}
ans+=__builtin_popcount(affect^i);
if(i==0)break;
}
cout<<ans<<endl;
}
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
这里空空如也
有帮助，赞一个