陕西师范大学第九届ACM程序设计竞赛补题

60 阅读 0 评论 40 点赞

我是靠谱客的博主高兴鲜花，最近开发中收集的这篇文章主要介绍陕西师范大学第九届ACM程序设计竞赛补题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

传送门

A强连通分量 + 并查集 + 优先队列

首先输出的数字是入度为零的强连通分量的个数

然后把这些强连通分量以入度为零为根节点建树，

每一层的每一个强连通分量至少选择一个点后才能选择与该前联通分量相连的下一层强连通分量中的点

要求符合要求的序列字典树最小，不难想出用优先队列

ac代码

#include <cstdio>
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <vector>
#define N 2000100
using namespace std;
int head[N];
int z,x;
int n[N], ne[N], h[N], idx;
bool vis[N];
priority_queue <int, vector <int>, greater<int>> q;
void add(int a,int b){
n[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int findd(int t){
if(head[t] == t)
return t;
return head[t] = findd(head[t]);
}
void hanshu(){
int l;
while(!q.empty()){
l = q.top();
q.pop();
printf("%d ",l);
for(int i = h[l] ; ~i ; i = ne[i]){
int j = n[i];
if(!vis[j]){
q.push(j);
vis[j] = true;
}
}
}
printf("n");
return ;
}
int main(){
int _;
int a,b;
scanf("%d",&_);
while(_--){
scanf("%d%d",&z,&x);
memset(h, -1, sizeof h);
memset(vis, false, sizeof vis);
for(int i = 0;i <= z;i ++)
head[i] = i;
while(!q.empty()) q.pop();
while(x--){
scanf("%d%d",&a,&b);
add(a,b), add(b,a);
int fa = findd(a);
int fb = findd(b);
if(fa > fb)
head[fa] = fb;
else
head[fb] = fa;
}
for(int i = 1; i <= z;i ++)
if(head[i] == i){
q.push(i);
vis[i] = true;
}
printf("%dn",q.size());
hanshu();
}
return 0;
}

C组合数学

从m个数字中挑出n-1个，其中除最大值为有一对重复的数子，组成序列

最大值以前严格递增，最大值以后严格递减，

对于除最大和一对重复数字的其他的数子来说，可以放在最大值的右面或者左面

ans = c(m , n - 1) * (n - 2) * 2 ^ (n - 3)

ac代码

#include <stdio.h>
#define LL long long
#define mod 998244353
LL qpow(LL a, LL k){
LL res = 1;
while (k) {
if (k & 1) res = res * a % mod;
k >>= 1;
a = a * a % mod;
}
return res;
}
LL C(LL a, LL b){
LL res = 1;
for (int i = 1, j = a; i <= b; i++, j--)
res = res * j % mod * qpow(i, mod - 2) % mod;
return res;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
if (n == 2) {
printf("0n");
return 0;
}
printf("%lldn", C(m, n - 1) * (n - 2) % mod * qpow(2, n - 3) % mod);
return 0;
}

F次短路板子

也就是单元最短路的算法为基础上记录一下次短路

用两个数组进行存储，一个存储最短路，一个存储次短路，

如果该路比最短路短，比次短路长，在、次短路等于最短路，最短路更新

如果该路比最短路长，比次短路短，那么更新次短路，

ac代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#define inf 0x3f3f3f3f
#define debug(x) cerr << #x << " = " << x << 'n'
#define LL long long
#define x first
#define y second
#define N 5050
#define M 202000
#define inf 0x3f3f3f3f
using namespace std;
struct edge{
int x, y;
bool operator < (const edge a) const{
return a.y < y;
}
};
priority_queue <edge> q;
int m;
int h[N], ne[M], n[M], w[M], idx;
void add(int a, int b, int c){
n[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int dij1[N];
int dij2[N];
int dij(){
edge e;
edge add;
add.x = 1;
add.y = 0;
dij1[1] = 0;
q.push(add);
while(!q.empty()){
e = q.top();
q.pop();
int s = e.x;
for(int i = h[s]; ~i ;i = ne[i]){
int j = n[i];
int l = e.y + w[i];
if(dij1[j] > l){
swap(dij1[j], l);
add.x = j;
add.y = dij1[j];
q.push(add);
}
if(dij2[j] > l && dij1[j] < l){
swap(dij2[j], l);
add.x = j;
add.y = dij2[j];
q.push(add);
}
}
}
return dij2[m];
}
int main(){
int _;
int a, b, c;
fill(h, h+N, -1);
fill(dij1, dij1 + N, inf);
fill(dij2, dij2 + N, inf);
scanf("%d%d",&m,&_);
while(_--){
scanf("%d%d%d", &a, &b, &c);
add(a+1, b+1, c), add(b+1, a+1, c);
}
printf("%d",dij());
return 0;
}

G 多重背包板子

需要注意的是

如果第 i 个物品，背包体积为 j ，选择 k 个，k >= 2

for(int k = 2; (w[i] - (1 << k-2)) >= 0 && k*t[i] <= j ;k ++)

而累加的时候是

dp[i][j] = max(dp[i][j] ,dp[i-1][j-k * t[i]] + k * w[i] - (1 << k-1) + 1);

这两步的位运算是不一样的，一个是累加了，一个没累加，

写的时候写成一个了，输入样例还判断不出来，就一直wa

ac代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <cmath>
#define inf 0x3f3f3f3f
#define debug(x) cerr << #x << " = " << x << 'n'
#define LL long long
#define N 110
#define M 10010
using namespace std;
int n,T;
int w[N], t[N];
LL dp[N][M];
int main(){
scanf("%d%d", &n, &T);
for(int i = 1;i <= n;i ++)
scanf("%d%d",&w[i], &t[i]);
LL ans = 0;
for(int i = 1;i <= n;i ++)
for(int j = 0;j <= T; j ++){
dp[i][j] = dp[i-1][j];
if(j >= t[i])
dp[i][j] = max(dp[i][j], dp[i-1][j-t[i]] + w[i]);
for(int k = 2; (w[i] - (1 << k-2)) >= 0 && k*t[i] <= j ;k ++)
dp[i][j] = max(dp[i][j] ,dp[i-1][j-k * t[i]] + k * w[i] - (1 << k-1) + 1);
ans = max(ans,dp[i][j]);
}
printf("%lldn",ans);
return 0;
}