2026年10月1日（南山S）
2026-10-01 16:41:41
发布于：广东
44阅读
0回复
0点赞
第一题
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
ll a[N],res[N];
ll n,k;
void dfs(ll inx,ll sum){
if(inx>n){
if(sum%k==0){
for(int i=1;i<=n;i++)cout<<res[i]<<' ';
cout<<endl;
}
return ;
}
for(int i=1;i<=a[inx];i++){
res[inx]=i;
dfs(inx****um+i);//inx位置拿i个，继续向后拿取
}
}
void solve(){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
dfs(1,0);
}
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 a[N];
int n;
ll sum[2];//要么放0，要么放1
ll ans=1e18;
void dfs(int inx){
//剪枝：快速跳过已经没有必要（不可能成为答案的枚举）
if(max(sum[0],sum[1])>ans)return ;//剪枝
if(inx>n){
ans=min(ans,max(sum[0],sum[1]));
return ;
}
sum[0]+=a[inx];
dfs(inx+1);
sum[0]-=a[inx];
sum[1]+=a[inx];
dfs(inx+1);
sum[1]-=a[inx];
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
dfs(1);
cout<<ans<<endl;
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
第三题
//每根竹子四种可能去A，B,C，都不去
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
ll a[N];//a[0],a[1] a[2] a[3];
ll zz[N];//竹子
//sum[i]表示i位置得到的竹子总长度,cnt[i]表示i位置得到的竹子数量
ll sum[N],cnt[N];
ll n,ans=1e18;
void dfs(int inx){
if(inx>n){
//a,b,c每个位置至少有一根竹子
ll res=0;//计算当前枚举的所有消耗
for(int i=1;i<=3;i++){
if(cnt[i]==0)return ;//没有竹子
res+=(cnt[i]-1)*10;//x个竹子合并起来需要(x-1)*10的消耗
}
for(int i=1;i<=3;i++){
res+=abs(sum[i]-a[i]);//每根竹子进行单独延长/缩短的消耗
}
ans=min(ans,res);
return ;
}
for(int i=0;i<=3;i++){
sum[i]+=zz[inx];//累计
cnt[i]++;//计数
dfs(inx+1);
sum[i]-=zz[inx];
cnt[i]--;
}
}
void solve(){
cin>>n;
for(int i=1;i<=3;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>zz[i];
dfs(1);
cout<<ans<<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 a[N],vis[N];//vis[i]=1;//表示i这一层的电梯已经走过了
ll res[N];//res[i]表示从起点s到i层所需要的操作数量
ll n,s,t;//s起点，t终点
void bfs(int s){
queue<int>que;//通过队列进行bfs枚举
que.push(s);
// int a=10;
while(que.size()){
int cur=que.front();que.pop();
//电梯上升,1.不能越界，2.不能是重复访问的点.
if(cur+a[cur]<=n&&!vis[cur+a[cur]]){
vis[cur+a[cur]]=1;//标记已经访问
res[cur+a[cur]]=res[cur]+1;//下一个点一定是上一个点的距离+1
que.push(cur+a[cur]);
}
//电梯下降,1.不能越界，2.不能是重复访问的点.
if(cur-a[cur]>=1&&!vis[cur-a[cur]]){
vis[cur-a[cur]]=1;//标记已经访问
res[cur-a[cur]]=res[cur]+1;//下一个点一定是上一个点的距离+1
que.push(cur-a[cur]);
}
}
}
void solve(){
cin>>n>>s>>t;
for(int i=1;i<=n;i++)cin>>a[i];
vis[s]=1;
bfs(s);
if(vis[t]==1)cout<<res[t]<<endl;
else cout<<-1<<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 a[N];
int n;
//去计算空柜子的位置
int cal(string &s){//使用引用类型更快,否则会直接进行复制
for(int i=0;i<s.size();i++)
if(s[i]=='.')return i;
}
void solve(){
string a,b;
cin>>n>>a>>b;
a+="..";
b+="..";//人为创造空位
map<string,int>mp;//状态-答案
mp[a]=0;//起始状态0 map默认的整数类型都是0
queue<string>que;
que.push(a);
while(que.size()){//BFS枚举，枚举所有状态，并计算次数
string cur=que.front();que.pop();
int cur_inx=cal(cur);//获取位置
cout<<cur<<' '<<cur_inx<<' '<<mp[cur]<<endl;
for(int i=0;i<cur.size()-1;i++){
//选择交换的位置不能是空柜子
//3 4 //set map<int>
//i!=3,i!=4,i!=2
if(i==cur_inx||i==cur_inx-1||i==cur_inx+1)continue;
string next=cur;
swap(next[i],next[cur_inx]);
swap(next[i+1],next[cur_inx+1]);
// if(mp[next]!=0)continue;//判断map中是否有那个下标
if(mp.count(next))continue;//
que.push(next);
mp[next]=mp[cur]+1;
}
}
if(mp.count(b))cout<<mp[b]<<endl;
else cout<<-1<<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 a[N],vis[N],res[N];
int n,m;
vector<int>graph[N];
//BFS剥皮写法
void solve(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
graph[u].push_back(v);
graph[v].push_back(u);
}
int x;cin>>x;
queue<int>que;
que.push(x);vis[x]=1;
int len=0;//当前层，
while(que.size()){
for(int i=1,size=que.size();i<=size;i++){
int cur=que.front();que.pop();
res[cur]=len;//层就是对应点的答案。
for(auto next:graph[cur]){//自动迭代写法
if(vis[next])continue;
vis[next]=1;
que.push(next);
}
}
len++;
}
for(int i=1;i<=n;i++)cout<<res[i]<<' ';
}
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 a[N],cnt[N];//cnt[i]统计i节点的入度
vector<int>graph[N];//存图
void solve(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;cin>>x>>y;//y是x的后代
graph[y].push_back(x);
cnt[x]++;//累计入度
}
//从入度为0的点开始，将其他所有点依次拿出来
queue<int>que;
for(int i=1;i<=n;i++){
if(cnt[i]==0)que.push(i);
}
vector<int>ans;
while(que.size()){
auto cur=que.front();que.pop();
// cout<<cur<<' ';//输出拓扑序
ans.push_back(cur);//
for(auto next:graph[cur]){
if(--cnt[next]==0)que.push(next);
}
}
reverse(ans.begin(),ans.end());//从祖先到子孙
for(auto cur:ans)cout<<cur<<' ';
}
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 a[N],b[N],vis[N];
ll fac[N];//fac[i]表示i！
int n;//n*n nlog(线段树/树状数组)
ll dfs(int inx,ll ans,ll *arr){//累计计数
if(inx>n)return ans;
for(int i=1;i<arr[inx];i++){
if(vis[i])continue;//如果前面拿过就跳过
ans+=fac[n-inx];
}
vis[arr[inx]]=1;//标记已经使用
ans=dfs(inx+1,ans,arr);
vis[arr[inx]]=0;//清空标记
return ans;
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
fac[1]=1;
for(int i=2;i<=n;i++)fac[i]=fac[i-1]*i;
// cout<<dfs(1,0,a)<<' '<<dfs(1,0,b)<<endl;
// ll a_cnt=dfs(1,0,a);
cout<<abs(dfs(1,0,a)-dfs(1,0,b));
}
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 a[N],cnt[N],mod=80112002;
ll dp[N];//dp[i]到i点的总方案数
vector<int>graph[N];
void solve(){
int n,m;cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
graph[u].push_back(v);
cnt[v]++;//累计入度
}
queue<int>que;
for(int i=1;i<=n;i++){
if(cnt[i]==0){
que.push(i);
dp[i]=1;
}
}
ll ans=0;
while(que.size()){
auto cur=que.front();que.pop();
//只有对于食物链顶端（没有上级了）才累计
if(graph[cur].size()==0)ans=(ans+dp[cur])%mod;
for(auto next:graph[cur]){
dp[next]=(dp[next]+dp[cur])%mod;
if(--cnt[next]==0)que.push(next);
}
}
cout<<ans<<endl;
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
第十题
// //对于任意的节点x
// 其中sum[x]为x节点的子节点数量
// 其中mx[x]为x节点中子节点坚持最久的时间
// k=1 对于x节点可以坚持mx[x]+1;
// k=2 对于x节点可以坚持mx[x]+2;
// 对于任意的k，x节点可以坚持mx[x]+k
// 对于任意的k，x节点的总坚持时间min(mx[x]+k,sum[x]);
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
ll sum[N],mx[N],cnt[N];
//sum[i]表示i点的子节点总和，mx[i]表示i节点最久坚持的时间
ll a[N];
ll n,k;
void solve(){
cin>>n>>k;
for(int i=1;i<=n;i++)sum[i]=mx[i]=cnt[i]=0;
for(int i=1;i<=n;i++)cin>>a[i],cnt[a[i]]++;
queue<int>que;
for(int i=1;i<=n;i++){
if(cnt[i]==0)que.push(i);
}
ll ans=0;
while(que.size()){
auto cur=que.front();que.pop();
sum[cur]++;//包含当前节点
int fath=a[cur];
sum[fath]+=sum[cur];//
ll D=min(mx[cur]+k,sum[cur]);//D表示当前节点最多坚持时间
ans=max(ans,D);
mx[fath]=max(mx[fath],D);
if(--cnt[fath]==0)que.push(fath);
}
cout<<ans+2<<endl;
}
int main(){
int t=1;
cin>>t;
while(t--){
solve();
}
}
这里空空如也
有帮助，赞一个