本文主要是介绍码蹄集部分题目(2024OJ赛8.28-9.1),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1🐋🐋都市路径(黄金;BFS)
时间限制:1秒
占用内存:64M
🐟题目思路
这道题目给的提示是使用BFS,但是使用Floyd更简单,也能过。
🐟代码
#include<bits/stdc++.h>
using namespace std;
int dp[105][105]={0};
int main( )
{int n,m,cur;cin>>n;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (i == j) dp[i][j] = 0;else dp[i][j] = 0x3f3f3f3f;}}for (int i = 1; i <= n; i++) {cin>>cur>>m;for(int j=1;j<=m;j++){int next;cin>>next;dp[i][next]=1;}}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);}}}for(int i=1;i<=n;i++){if(dp[1][i]>n) cout<<i<<" "<<-1<<endl;else cout<<i<<" "<<dp[1][i]<<endl;}return 0;
}
2🐋🐋P序列(钻石;找规律)
时间限制:1秒
占用内存:256M
🐟题目思路
2024年码蹄杯职业院校赛道初赛第三场题解_哔哩哔哩_bilibili
🐟代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+7;
const int mod=998244353;
int cnt[N],n,mx=-0x3f3f3f3f,ans=1;
signed main( )
{cin>>n;for(int i=1;i<=n;i++){int x;cin>>x;cnt[x]++;mx=max(mx,x);}for(int i=1;i<mx;i++){if(cnt[i]) ans=ans*(cnt[i]+1)%mod;}cout<<ans;return 0;
}
3🐋🐋魔法链路(黄金;拓扑排序模板题)
时间限制:1秒
占用内存:256M
🐟题目思路
2024年码蹄杯本科院校赛道决赛题解_哔哩哔哩_bilibili
🐟代码
#include<bits/stdc++.h>
using namespace std;
#define L long long
struct edge{int e;edge *n;edge(int x=0,edge *y=NULL):e(x),n(y){}
}*pre[100005];
void insert(int s,int e){edge *tmp(new edge(e,pre[s]));pre[s]=tmp;
}
int n,m,fin[100005],ans[100005],ind[100005],outd[100005];
L f[100005];
priority_queue<int,vector<int>,greater<int> > q;
int main(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>f[i];for(int i=1,x,y;i<=m;i++){cin>>x>>y;insert(x,y);++outd[x],++ind[y];}for(int i=1;i<=n;i++){if(!outd[i]) fin[++fin[0]]=i;if(!ind[i]) q.push(i);}while(!q.empty()){int u(q.top());q.pop();ans[++ans[0]]=u;for(edge *i=pre[u];i;i=i->n){int e(i->e);f[e]+=f[u];--ind[e];if(!ind[e]){q.push(e);}}}for(int i=1;i<=n;i++) cout<<ans[i]<<" ";cout<<endl;for(int i=1;i<=fin[0];i++) cout<<f[fin[i]]<<" ";cout<<endl;return 0;
}
4🐋🐋魔法占卜(白银;字符串)
时间限制:1秒
占用内存:256M
🐟题目思路
这道题目直接用最长公共子序列的模板会超出内存。
2024年码蹄杯本科院校赛道决赛题解_哔哩哔哩_bilibili
🐟代码
#include<bits/stdc++.h>
using namespace std;
char s[100005],t[100005];
int head=1,len;
int main( )
{scanf("%s%s",s+1,t+1);len=strlen(s+1);for(int i=1;i<=len;i++){if(s[i]==t[head]) head++;}if(head>strlen(t+1)) cout<<"Lucky!";else cout<<"QAQ Unlucky!";return 0;
}
5🐋🐋异或(星耀;前缀和|差分、树上问题、位运算)
时间限制:3秒
占用内存:512M
🐟题目思路
2024年码蹄杯本科院校赛道初赛题解_哔哩哔哩_bilibili
🐟代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
const int mod=1e9+7;
struct GRAPH{int head[N],nxt[N<<1],to[N<<1],cnt;void add(int u,int v){nxt[++cnt]=head[u];to[cnt]=v;head[u]=cnt;}
}gr;
int f[N][30][2],n,q,k,a[N],st[N],top;
void dfs(int u,int fa){st[++top]=u;for(int j=0;j<30;j++) f[u][j][(a[u]>>j)&1]++;if(top>k+1)for(int j=0;j<30;j++)f[st[top-k-1]][j][(a[u]>>j)&1]--;for(int i=gr.head[u];i;i=gr.nxt[i]){int v=gr.to[i];if(v==fa) continue;dfs(v,u);}top--;
}
void dfs_sum(int u,int fa){for(int i=gr.head[u];i;i=gr.nxt[i]){int v=gr.to[i];if(v==fa) continue;dfs_sum(v,u);for(int j=0;j<30;j++) f[u][j][0]+=f[v][j][0],f[u][j][1]+=f[v][j][1];}
}
int main( )
{cin>>n>>q>>k;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<n;i++){int u,v;cin>>u>>v;gr.add(u,v);gr.add(v,u);}dfs(1,0);dfs_sum(1,0);while(q--){int x;cin>>x;int ans=0;for(int j=0;j<30;j++){ans+=1ll*f[x][j][0]*f[x][j][1]%mod*(1<<j)%mod;ans%=mod;}cout<<ans<<endl;}return 0;
}
⭐创作不易,点个赞吧~
⭐点赞收藏不迷路~
这篇关于码蹄集部分题目(2024OJ赛8.28-9.1)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!