2022.1.20解题报告

1.三元一次方程

题目描述：

https://www.acwing.com/problem/content/description/3629/

思路：

直接两层循环，暴力枚举x和y即可。

代码：

#include<iostream>
using namespace std;
int t,n;
int main(){
    scanf("%d",&t);
    while(t -- ){
        scanf("%d",&n);
        for(int i = 0 ; i * 3 <= n ; i ++ )
            for(int j = 0 ; j * 5 <= n - i * 3 ; j ++ ){
                if((n - i * 3 - j * 5) % 7 == 0){ //如果找到了满足条件的z了
                    printf("%d %d %d\n",i,j,(n - i * 3 - j * 5) / 7);
                    p = 1; //p表示是否找到解
                    n = -1; //将n变为负数，跳出循环
                }
            }
        if(!p) printf("-1\n");
        p = 0;
    }
}

2.最大差值

题目描述：

https://www.acwing.com/problem/content/3630/

思路：

直接贪心，将数组中最大的k个数的数值加到第k+1大的数上即是结果。

故此题转化为求数组中最大的k+1个数之和。

代码：

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int t,a[N],n,k;
int main(){
    scanf("%d",&t);
    LL ans = 0;
    while(t -- ){
        ans = 0;
        scanf("%d%d",&n,&k);
        for(int i = 1 ; i <= n ; i ++ )
            	scanf("%d",a + i);
        sort(a + 1,a + n + 1);
        for(int i = n ; i >= n - k ; i -- )
            ans += a[i];
        printf("%lld\n",ans);
    }
    return 0;
}

3.边的删减

题目描述：

https://www.acwing.com/problem/content/3631/

思路：

显然，这题会要用到最短路算法，那么选择什么最短路算法就很关键了。

注意到题意说明删去边以后要使仍能构成最短路的点尽可能多，也就是构成最短路的路径尽可能少被删掉，即我们留下来的边对于构成最短路是“有价值的”。

所以我们选择了Dijkstra算法，方便我们在计算最短路的同时记录构成最短路的边。

又由于Dijkstra是基于贪心的算法，且其贪心思想是：每次更新距离出发点最近的点的最短路，所以Dijkstra在每一次更新时所更新的最后一条边一定是“有价值的”。

所以我们只需在每一次更新最短路时把最后一次更新的边记录下来就好了。

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<pair<LL,int>,int> PIII;
const int N = 1e5 + 10,M = 2 * N;
int to[M],ne[M],w[M],h[N],idx;
int n,m,k;
int res[M],cnt;
LL dist[N];
bool st[N];
void add(int u,int v,int z){ //链式前向星
   	to[idx] = v;
    w[idx] = z;
    ne[idx] = h[u];
    h[u] = idx ++ ;
}
void dijkstra(){ //堆优化版Dijkstra
    memset(dist,0x3f,sizeof dist); //初始化
    priority_queue<PIII,vector<PIII>,greater<PIII>> heap;
    dist[1] = 0;
    heap.push({{0,1},-1});
    while(heap.size()){
        auto t = heap.top();
        heap.pop();
        int ver = t.x.x,distance = t.x.y;
        int edg = t.y;
        if(st[ver]) continue;
        st[ver] = true;
        res[cnt ++ ] = edg;//记录“有价值的”边 
        for(int i = h[ver] ; i != -1 ; i = ne[i]){
        	int j = to[i];
        	if(dist[j] > dist[i] + distance){
        		dist[j] = dist[i] + distance;
        		heap.push({{dist[j],j},i});
			}
		}
    }
}
int main(){
    memset(h,-1,sizeof h);
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 1 ; i <= m ; i ++ ){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z); //无向图 
    }
    dijkstra();
    cout << min(cnt - 1,k) << endl;
    for(int i = 1 ; i <= min(cnt + 1,k) ; i ++ ) cout << res[i] / 2 + 1 << " ";
    return 0;
}