L2-024 部落 (25 分)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 7;
const int mod = 1e9 + 7;
const int MOD = 998244353;
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++i)
int a[N],n,m,s[N];
int find(int x){//采用递归的写法会超时
int rt=x;
while(rt!=s[rt]) rt=s[rt];
int tmp=x;
while(tmp!=rt)
{
int m=s[tmp];
s[tmp]=rt;
tmp=m;
}
return rt;
}
void uoion_set(int x,int y){
x=find(x);
y=find(y);
if(x!=y) s[x]=y;
}
bool vis[N];
void solve(){
cin>>n;
set<int> st1,st2;
for(int i=1;i<=10001;i++) s[i]=i;
while(n--){
int num;
cin>>num;
for(int i=0;i<num;i++){
cin>>a[i];
vis[a[i]]=1;
if(i>0){
uoion_set(a[i],a[i-1]);
}
}
}int ans=0;
for(int i=0;i<=10000;i++){
ans+=vis[i];
}
for(int i=0;i<=10000;i++){
if(vis[i]) st2.insert(find(i));
}
cout<<ans<<" "<<st2.size()<<endl;
cin>>m;
while(m--){
int x,y;
cin>>x>>y;
if(find(x)==find(y)){
cout<<"Y"<<endl;
}else{
cout<<"N"<<endl;
}
}
}
signed main(){
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}
L2-025 分而治之 (25 分)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 7;
const int mod = 1e9 + 7;
const int MOD = 998244353;
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++i)
struct node{
int a,b;
}rt[N];
int a[N],n,m;
void solve(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>rt[i].a>>rt[i].b;
}
int K;
cin>>K;
while(K--){
int num;
cin>>num;
vector<int>h(n+1,0);
for(int i=1,x;i<=num;i++){
cin>>x;
h[x]=1;
}
int ok=1;
for(int i=1;i<=m;i++){
if(h[rt[i].a]!=1&&h[rt[i].b]!=1){//如果原先还有的道路依旧联通，就输出NO
cout<<"NO"<<endl;
ok=0;
break;
}
}
if(ok) cout<<"YES"<<endl;
}
}
signed main(){
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}
L2-026 小字辈 (25 分)
树的遍历，BFS求树的深度。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 7;
const int mod = 1e9 + 7;
const int MOD = 998244353;
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++i)
int a[N],n,m;
vector<int> g[N];
int height[N];
void solve(){
cin>>n;
for(int i=1,x;i<=n;i++){
cin>>x;
if(x==-1){
x=0;
height[i]=1;
}
g[x].push_back(i);
}
queue<int> q;
q.push(0);
int now;
while(!q.empty()){
now=q.front();
q.pop();
for(auto t:g[now]){
height[t]=height[now]+1;
q.push(t);
}
}
int ans=height[now];
vector<int> rt;
for(int i=1;i<=n;i++){
if(height[i]==ans) rt.push_back(i);
}
cout<<height[now]<<endl;
for(int i=0;i<rt.size();i++){
if(i!=0) cout<<" ";
cout<<rt[i];
}
}
signed main(){
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}
L2-027 名人堂与代金券 (25 分)
简单结构体排序模拟
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e4 + 7;
const int mod = 1e9 + 7;
const int MOD = 998244353;
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++i)
int a[N],n,m;
struct node{
string name;
int score,rank;
}st[N];
bool cmp(node a,node b){
if(a.score==b.score) return a.name<b.name;
return a.score>b.score;
}
void solve(){
int N,G,K;
cin>>N>>G>>K;
int ans1=0;
for(int i=1;i<=N;i++){
cin>>st[i].name>>st[i].score;
if(st[i].score>=G&&st[i].score<=100) ans1+=50;
else if(st[i].score>=60&&st[i].score<G) ans1+=20;
}
sort(st+1,st+N+1,cmp);
st[1].rank=1;
for(int i=2;i<=N;i++){
if(st[i].score==st[i-1].score) {
st[i].rank=st[i-1].rank;
}else{
st[i].rank=i;
}
}
cout<<ans1<<endl;
for(int i=1;st[i].rank<=K&&i<=N;i++){//限制小于N，不然会段错误。
cout<<st[i].rank<<" "<<st[i].name<<" "<<st[i].score<<endl;
}
}
signed main(){
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}
L3-001 凑零钱 (30 分)
线性背包dp，输出方案，和上次做的那个堆硬币一模一样。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 7;
const int mod = 1e9 + 7;
const int MOD = 998244353;
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
//#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++i)
int values[N],dp[N],choose[10010][110];
bool cmp(int a,int b){
return a>b;
}
void solve(){
int i,j,n,m,k,t;
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d",&values[i]);
}
sort(values+1,values+n+1,cmp);
for(i=1;i<=n;i++)
{
for(j=m;j>=values[i];j--)
{
if(dp[j]<=dp[j-values[i]]+values[i])
{
choose[i][j]=1;
dp[j]=dp[j-values[i]]+values[i];
}
}
}
if(dp[m]!=m)
{
printf("No Solution\n");
return;
}
int index=n,sum=m;
vector<int> arr;
while(sum>0)
{
if(choose[index][sum]==1)
{
arr.push_back(values[index]);
sum-=values[index];
}
index--;
}
for(i=0;i<arr.size();i++)
{
if(i==0)
{
printf("%d",arr[i]);
}
else
{
printf(" %d",arr[i]);
}
}
printf("\n");
}
signed main(){
int _=1;
//cin>>_;
while(_--) solve();
return 0;
}
L3-002 特殊堆栈 (30 分)
STL模拟题
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 7;
const int mod = 1e9 + 7;
const int MOD = 998244353;
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++i)
// int a[N],n,m;
void solve(){
int n;
cin>>n;
vector<int> a,b;
while(n--){
string op;
cin>>op;
if(op=="Pop"){
if(a.size()==0) cout<<"Invalid"<<endl;
else{
cout<<a[a.size()-1]<<endl;
auto it=lower_bound(b.begin(),b.end(),a[a.size()-1]);
a.pop_back();
b.erase(it);
}
}else if(op=="PeekMedian"){
if(b.size()==0) cout<<"Invalid\n";
else
{
if(b.size()&1) cout<<b[b.size()>>1]<<endl;
else cout<<b[b.size()-1>>1]<<endl;
}
}else{
int key;
cin>>key;
a.push_back(key);
auto it=lower_bound(b.begin(),b.end(),key);
b.insert(it,key);
}
}
}
signed main(){
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}
L2-035 完全二叉树的层序遍历 (25 分)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 7;
const int mod = 1e9 + 7;
const int MOD = 998244353;
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++i)
int a[N],n,m;
int rt[N];
void dfs(int u){
if(u>n) return;
dfs(u<<1);
dfs(u<<1|1);
cin>>rt[u];
}
void solve(){
cin>>n;
dfs(1);
for(int i=1;i<=n;i++){
if(i>1) cout<<" ";
cout<<rt[i];
}
}
signed main(){
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}
L2-001 紧急救援 (25 分)
Dijkstra最短路，在找最短路的同时记录路径和数量。这个题数据比较小可以使用邻接矩阵来存图。
#include<bits/stdc++.h>
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 2e6 + 7;
const int mod = 1e9 + 7;
int n,m,s,d;
int weight[N],num[N],dist[N],g[510][510],pre[510],w[510],vis[N];
void print(int u){
if(u==s){
cout<<u;
return;
}
print(pre[u]);
cout<<" "<<u;
return;
}
void dij(){
for(int i=0;i<n-1;i++){
int to,mi=INT_MAX;
for(int j=0;j<n;j++){
if(!vis[j]&&dist[j]<mi){
mi=dist[j];
to=j;
}
}
vis[to]=1;
for(int j=0;j<n;j++){
if(dist[to]+g[to][j]<dist[j]){
dist[j]=dist[to]+g[to][j];
w[j]=w[to]+weight[j];
num[j]=num[to];
pre[j]=to;
}
else if(dist[to]+g[to][j]==dist[j]){
num[j]+=num[to];
if(w[to]+weight[j]>w[j]){
w[j]=w[to]+weight[j];
pre[j]=to;
}
}
}
}
}
signed main(){
cin>>n>>m>>s>>d;
for(int i=0;i<n;i++) dist[i]=INT_MAX;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
g[i][j]=INT_MAX;
}
}
for(int i=0;i<n;i++) cin>>weight[i];
int u,v,val;
for(int i=0;i<m;i++){
cin>>u>>v>>val;
g[u][v]=val;
g[v][u]=val;
}
dist[s]=0;
num[s]=1;
w[s]=weight[s];
dij();
cout<<num[d]<<" "<<w[d]<<endl;
print(d);
return 0;
}
L2-036 网红点打卡攻略 (25 分)
按照给定的路径走，判断有没有重复走和是否全部都走到了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int MOD = 998244353;
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++i)
int N, M, K, u, v, w, n, flag, cost, Ansnum, Ansid, Anscost = INT_MAX, Edge[201][201], Path[202], Has[201];
void solve(){
cin >> N >> M;
for (int i = 0; i < M; i++) {
cin >> u >> v >> w;
Edge[u][v] = Edge[v][u] = w;
}
cin >> K;
for (int i = 1; i <= K; i++) {
fill(Has, Has + N + 1, 0);
Path[N + 1] = flag = cost = 0;
cin >> n;
for (int j = 1; j <= n; j++){
cin >> Path[j];
if(Has[Path[j]]) Has[0] = 1;
Has[Path[j]] = 1;
}
if (Has[0] || n != N) continue;
for (int j = 1; j <= n + 1; j++) {
if (Edge[Path[j-1]][Path[j]] == 0) {
flag = 1;
break;
}
cost += Edge[Path[j - 1]][Path[j]];
}
if (!flag) {
Ansnum++;
if(cost < Anscost) Ansid = i, Anscost = cost;
}
}
cout << Ansnum << '\n' << Ansid << ' ' << Anscost;
}
signed main(){
int _=1;
//cin>>_;
while(_--) solve();
return 0;
}
京公网安备 11010502036488号