CSU 8月 月赛

本文从WordPress迁移而来, 查看全部WordPress迁移文章

B.

因为数据规模还是较小的,直接模拟即可,就是按照题意,每次+a,+b那样去模拟。另外的方法就是用优先队列去模拟,但是不必每次都+a,+b,用2个变量去累计多次的a,b

暴力模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
#define N 100010
#define M 210
#define INF 0x3f3f3f3f
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,lim,da,db;
int a[N];
int query[M];
int id,Max,numa,numb;

int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(scanf("%d%d%d%d",&n,&lim,&da,&db)!=EOF){
id = Max = -INF;
numa = numb = 0;
for(int i = 1; i <= n; i++){
scanf("%d",&a[i]);
if(a[i] <= lim) numa++;
else numb++;
if(a[i] > lim && a[i] > Max){
Max = a[i]; id = i;
}
}

for(int op = 1; op <= 200; op++){
query[op] = numb;
if(id != -INF){
a[id] = 0;
}
id = Max = -INF;
numa = numb = 0;
for(int i = 1; i <= n; i++){
if(a[i] <= lim){
a[i] += da;
}
else{
a[i] += db;
}
if(a[i] <= lim) numa++;
else numb++;
if(a[i] > lim && a[i] > Max){
Max = a[i]; id = i;
}
}
}
int q;
scanf("%d",&q);
while(q--){
int x;
scanf("%d",&x);
printf("%d\n",query[x]);
}
}
return 0;
}

优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define N 100010
#define M 220
#define INF 0x3f3f3f3f
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,k,a,b,query[M];
struct Set{
int val;
Set(){}
Set(int __val) : val(__val) {}
bool operator<(const Set &a)const{
return a.val > val;
}
};
priority_queue<Set>A;
priority_queue<Set>B;

int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);

while(scanf("%d%d%d%d",&n,&k,&a,&b)!=EOF){
while(!A.empty()) A.pop();
while(!B.empty()) B.pop();
for(int i = 0; i < n; i++){
int x;
scanf("%d",&x);
if(x <= k) A.push(x);
else B.push(x);
}

int da = 0 , db = 0;
for(int op = 1; op <= 200; op++){
int elem;
query[op] = B.size();
da += a; db += b;
if(!B.empty()){
B.pop();
A.push(Set(-da+a));
}
while(!A.empty()){
if(A.top().val + da > k){
Set tmp = A.top();
A.pop();
tmp.val += (da-db);
B.push(tmp);
}
else break;
}
}
int q;
scanf("%d",&q);
while(q--){
int x;
scanf("%d",&x);
printf("%d\n",query[x]);
}
}
return 0;
}

D.模拟,写好代码即可,这个代码写得不太好,仅供参考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX 10010
#define INF 0x3f3f3f3f
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

const char Float[4][10] = {"*NEW* " , "*DOWN* " , "*UP* " , "*STAY* "};

int n,tot;
struct song{
char name[50];
int num;
int rank;
bool used;
};
song now[15],all[MAX];

bool cmp1(song x,song y){
return x.num > y.num;
}

int find(int k){
for(int i = 0; i < tot; i++)
if(!strcmp(all[i].name , now[k].name))
return i;
return -1;
}

int main(){
int WEEK = 0;
tot = 0;
while(scanf("%d",&n)!=EOF && n){
WEEK++;
for(int i = 1; i <= n; i++){
scanf("%s%d",now[i].name,&now[i].num);
now[i].rank = -1;
}
for(int i = 0; i < tot; i++)
all[i].used = false;

sort(now+1,now+n+1,cmp1);

if(WEEK == 1){
printf("----------------WEEK %d----------------\n",WEEK);
for(int i = 1; i <= n; i++){
if(i <= 5) printf("%d.%s%s\n",i,Float[0],now[i].name);
now[i].rank = i;
}
for(int i = 1; i <= n; i++)
all[tot++] = now[i];
continue;
}
printf("----------------WEEK %d----------------\n",WEEK);
for(int i = 1; i <= n; i++){
now[i].rank = i;
int index = find(i);
if(index == -1){
if(i <= 5) printf("%d.%s%s\n",i,Float[0],now[i].name);
all[tot] = now[i]; all[tot++].used = true;
}
else{
int rank = all[index].rank;
int f = -1;
if(now[i].rank == rank) f = 3;
else if(now[i].rank < rank) f = 2;
else f = 1;
if(i <= 5) printf("%d.%s%s\n",i,Float[f],now[i].name);
all[index] = now[i]; all[index].used = true;
}
}
for(int i = 0; i < tot; i++)
if(!all[i].used)
all[i].rank = INF;
}
return 0;
}

F.用暴力去写,用的是二进制枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
using namespace std;
#define N 25
#define M 20
#define LL long long
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back

int n,m,tar[N];
int a[M][N];
vector<int>list,ans;

void solve(){
if(list.size() < ans.size()) return ;
if(list.size() > ans.size()){
ans.clear();
for(int i = 0; i < list.size(); i++)
ans.pb(list[i]);
}
else{
int delta = 0;
for(int i = 0; i < list.size(); i++){
delta = list[i] - ans[i];
if(delta) break;
}
if(delta == 0) return ;
if(delta < 0){
ans.clear();
for(int i = 0; i < list.size(); i++)
ans.pb(list[i]);
}
}

}

int main(){
while(scanf("%d",&n)!=EOF){
for(int i = 0; i < n; i++)
scanf("%d",&tar[i]);
scanf("%d",&m);
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
scanf("%d",&a[i][j]);

ans.clear();
int tot = (1<<m);
for(int sta = 1; sta < tot; sta++){
list.clear();
int s = sta;
for(int i = 0; i < m; i++){
if(s & 1) list.pb(i);
s >>= 1;
}
int point[N];
cl(point,0);
for(int i = 0; i < list.size(); i++){
int id = list[i];
for(int k = 0; k < n; k++)
point[k] += a[id][k];
}
bool ok = true;
for(int i = 0; i < n; i++)
if(point[i] < tar[i]){
ok = false; break;
}
if(ok) solve();
}

printf("%d",ans.size());
for(int i = 0; i < ans.size(); i++)
printf(" %d",ans[i]+1);
puts("");
}
return 0;
}

G. 简单题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 30
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int sum[N],n;

struct problem{
int t,id;
}a[N];

bool cmp(problem x , problem y){
if(x.t == y.t) return x.id < y.id;
return x.t < y.t;
}

int main(){
while(scanf("%d",&n)!=EOF){
cl(sum,0);
for(int i = 1; i <= n; i++){
scanf("%d",&a[i].t);
a[i].id = i;

}
sort(a+1,a+n+1,cmp);
int ans = 0,cnt = 0,Time = 0;
for(int i = 1; i <= n; i++){
sum[i] = sum[i-1] + a[i].t;
ans += sum[i]; cnt++;
Time += a[i].t;
if(Time > 300){
cnt--; ans -= sum[i]; break;
}
}
printf("%d %d\n",cnt,ans);
for(int i = 1; i <= cnt; i++)
printf("%d\n",a[i].id);
}
return 0;
}

I. 树DP求最长链
当边权有负的,要修改一些写法

但边权全部为正的时候,dp[u][0],dp[u][1]表示从u走到叶子的最远距离和次短距离

但是边权有负的时候,则不一定走到叶子,dp[u][0],dp[u][1],表示从u向下走,能走出的最远和次远距离,不一定是走到叶子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 50010
#define INF 10000000000LL
#define LL long long
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

LL ans;
int n,tot,head[N];
struct edge{
int u,v,next; LL w;
edge(){}
edge(int __u,int __v,LL __w){
u = __u; v = __v; w = __w;
}
}e[2*N];
LL dp[N][2];
bool vis[N];

inline void add(int u ,int v,LL w){
e[tot] = edge(u,v,w);
e[tot].next = head[u]; head[u] = tot++;
}

void dfs(int u){
vis[u] = true;
bool leaf = true;
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
LL w = e[k].w;
if(vis[v]) continue;
leaf = false;
dfs(v);
LL tmp = max(dp[v][0]+w , w);
tmp = max(tmp,0LL);
if(tmp > dp[u][0]){
dp[u][1] = dp[u][0]; dp[u][0] = tmp;
}
else if(tmp > dp[u][1]){
dp[u][1] = tmp;
}
}
if(!leaf){
ans = max(ans,dp[u][0] + dp[u][1]);
ans = max(ans,dp[u][0]);
}
else{
dp[u][0] = dp[u][1] = 0;
}
}

int main(){
int m;
while(scanf("%d%d",&n,&m)!=EOF){
tot = 0; cl(head,-1);
cl(vis,false); cl(dp,0);
bool flag = false; LL Max = -INF;
while(m--){
int u,v; LL w;
scanf("%d%d%lld",&u,&v,&w);
add(u,v,w); add(v,u,w);
if(w > 0LL) flag = true;
Max = max(w,Max);
}
if(!flag){
printf("%lld\n",Max);
continue;
}
ans = -INF;
dfs(1);
printf("%lld\n",ans);
}
return 0;
}

J.
题目要求最大值最小,这种类型,一看就反应是二分

把图中所有的边权保存下来(边权相同的只需要保存一次即可),然后排序

然后二分枚举这些边权,限定了从A走到B的路径中,所有边的边权都必须小于等于当前枚举的这个边权

即,在一个限制条件下求一次最短路

整个解题就是 二分答案 + 带限制地求最短路

别人的做法是模拟Kruskal的方法去添加边,直到A和B连通

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;
#define N 2010
#define M 50010
#define MAX 10010
#define INF 1000000000
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define mp make_pair
#define pii pair<int,int>

bool done[N],Hash[MAX];
int d[N];
int n,tot,head[N],A,B;
struct edge{
int u,v,w,next;
edge(){}
edge(int __u,int __v,int __w){
u = __u; v = __v; w = __w;
}
}e[2*M];
int EDGE[M];

inline void add(int u,int v,int w){
e[tot] = edge(u,v,w);
e[tot].next = head[u]; head[u] = tot++;
}

void solve(int lim){
cl(done,false);
for(int i = 1; i <= n; i++)
d[i] = (i == A ? 0 : INF);
priority_queue<pii,vector<pii>,greater<pii> > que;
//priority_queue <pii> que;
while(!que.empty()) que.pop();
que.push(mp(d[A],A));
while(!que.empty()){
pii x = que.top(); que.pop();
int u = x.second;
if(done[u]) continue;
done[u] = true;
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
int w = e[k].w;
if(w > lim) continue;
if(d[u] + w < d[v]){
d[v] = d[u] + w;
que.push(mp(d[v],v));
}
}
}
}

int main(){
int m;
while(scanf("%d%d%d%d",&n,&m,&A,&B)!=EOF){
tot = 0; cl(head,-1); cl(Hash,false);
int Minw = INF,Maxw = -INF,cnt = 0;
for(int i = 0; i < m; i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w); add(v,u,w);
Minw = min(Minw,w);
Maxw = max(Maxw,w);
if(Hash[w]) continue;
EDGE[cnt++] = w;
Hash[w] = true;
}
sort(EDGE,EDGE+cnt);

int low = 0,high = cnt-1,ans = INF;
while(low <= high){
int mid = (low + high) >> 1;
solve(EDGE[mid]);
if(d[B] != INF){
high = mid - 1;
ans = d[B];
}
else low = mid + 1;
}
printf("%d\n",ans);
}
return 0;
}