c++等级考试第8级第2卷

                                                                     道路(2024.3八级)

代码

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
struct Road
{
    int d,L,t;
};
int N,K,R;
vector < vector <Road> > G(110);//用二维数组表示临界表，G[s]表示和s邻接的路
int minLen;//全局变量，记录最短的路径长度
int totalCost;//当前状态的花费
int totalLen;//当前状态的长度
int visited[110];
int minL[110][10010];//minL[i][j]的意义是当到达i点是花费为j时的最短路径
void Dfs(int s)
{
    if(s==N)
    {
        minLen=min(minLen,totalLen);
        return ;
    }
    int len=G[s].size();
    for(int i=0;i<len;i++)//枚举和s相邻接额情况
    {
        Road r=G[s][i];
        if(!visited[r.d])//如果没有被走过
        {
            /*下面三个if语句是三条剪枝条件*/
            if(totalCost+r.t>K)//如果当前花销大于K了
                continue;
            if(totalLen+r.L>=minLen)//如果当前的路径已经超过了已存在的最短路径，那就没必要往后dfs了
                continue;
            //如果存在两种方式都到达同一点并且花销相同，但是如果当前的长度大于另一种方式的长度，则continue
            if(totalLen+r.L>minL[r.d][totalCost+r.t])
                continue;
            minL[r.d][totalCost+r.t]=totalLen+r.L;
            visited[r.d]=1;
            totalCost+=r.t;
            totalLen+=r.L;
            Dfs(r.d);
            visited[r.d]=0;//因为可能存在多种方式的dfs的路径，所以每次dfs之后都要还原到之前的状态
            totalCost-=r.t;
            totalLen-=r.L;
        }
    }
}
int main()
{
    cin>>K>>N>>R;
    for(int i=0;i<R;i++)
    {
        int s;
        Road r;
        cin>>s;
        cin>>r.d>>r.L>>r.t;
        G[s].push_back(r);
    }
    totalCost=0;
    totalLen=0;
    minLen=1<<30;//无穷大
    memset(visited,0,sizeof(visited));
    for(int i=1;i<=N;i++)
        for(int j=0;j<10010;j++)
            minL[i][j]=1<<30;
    visited[1]=1;
    Dfs(1);
    if(minLen<(1<<30))
        cout<<minLen<<endl;
    else
        cout<<-1<<endl;
    return 0;
}

                                                                   Freda的越野跑(2024.3八级)

代码

#include <iostream>
#define N 100002
int a[N] = {0}, t[N] = {0};
long long c = 0;
void merge(int l, int m, int r) {
  int i = l, j = m + 1, k = l;
  while (i <= m && j <= r)
    if (a[i] > a[j])
      t[k++] = a[i++];
    else {
      t[k++] = a[j++];
      c += 1 + m - i;
    }
  while (i <= m)
    t[k++] = a[i++];
  while (j <= r)
    t[k++] = a[j++];
  for (i = l; i <= r; ++i)
    a[i] = t[i];
}
void divide(int l, int r) {
  int m;
  if (r > l) {
    m = (r + l) / 2;
    divide(l, m);
    divide(m + 1, r);
    merge(l, m, r);
  }
}
int main() {
  int n, i = 0;
  std::cin >> n;
  while (i < n)
    std::cin >> a[i++];
  divide(0, n - 1);
  std::cout << c;
}

                                                               Rainbow的商店(2024.3八级)

代码

#include<iostream>
#include<algorithm>
#include<queue>
#pragma warning (disable:4996);
using namespace std;
int N;
struct Goods
{
	int w;
	int d;
	friend bool operator <(const Goods a, const Goods b)
	{
		if (a.w != b.w)
		{
			return a.w < b.w;//大的天数小的在前
		}
		else
		{
			return a.d > b.d;
		}
	}
}good[10005];
bool vis[10005] = {};
int main()
{
	cin >> N;
	priority_queue<Goods>que;
	int maxval=0;
	for (int i = 1; i <= N; i++)
	{
		scanf("%d %d", &good[i].w, &good[i].d);
		que.push(good[i]);
	}
	while (!que.empty())
	{
		Goods now = que.top();
		que.pop();
		for (int i = now.d; i >= 1; i--)
		{
			if (!vis[i])
			{
				vis[i] = 1;
				maxval += now.w;
				break;
			}
		}
	}
	printf("%d\n", maxval);
	return 0;
}

                                                                  冰阔落|(2024.3八级）

代码

#include <bits/stdc++.h>
using namespace std;
string str;
int a[50000+5],cnt;
int root(int x)
{
    if(a[x]==x) return x;
    return root(a[x]);
}
void find(int l,int r)
{
    int ll=root(l),rr=root(r);
    if(ll==rr)
    {
        printf("Yes\n");
        //cout<<"Yes"<<endl;
    }
    else
    {
        a[rr] =ll;
        cnt--;
        //cout<<"No"<<endl;
        printf("No\n");
    }
}
int main()
{
    int m,n,l,r;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        cnt=n;
        for(int i=1;i<=n;i++)
        {
            a[i]=i;
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d %d",&l,&r);
            //cin>>l>>r;
            find(l,r);
        }
        printf("%d\n",cnt);
        //cout<<cnt<<endl;
        for(int i=1;i<=n;i++)
            if(a[i]==i) printf("%d ",i);//cout<<i<<" ";
        //cout<<endl;
        printf("\n");
    }
    return 0;

}