Fork me on GitHub

20190819模拟赛题解

qwq

又是爆零的一次比赛欸qwq…


T1: 让你在一个矩阵中,找出一条路径,使得经过的路径方差最小.

我就直接放题解了qwq…

qwq

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
#include<bits/stdc++.h>
template <class T>

bool Reduce(T &a,T const &b){
return a>b?a=b,1:0;
}
const int N=31,inf=1e9+7,S=59*30;
int n,m,ans;
int a[N][N];
int f[N][N];
int cnt=0;
void init(){
std::ios::sync_with_stdio(false);
freopen("path.in","r",stdin);
freopen("path.out","w",stdout);
std::cin>>n>>m;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
std::cin>>a[i][j];
}
int calc(const int &sum,const int &i,const int &j){
return (n+m-1)*a[i][j]*a[i][j]-2*sum*a[i][j];
}
int dp(int sum){
for(int i=0;i<N;++i)
for(int j=0;j<N;++j)
f[i][j]=inf;
f[1][1]=calc(sum,1,1);
for(int j=2;j<=m;++j)
Reduce(f[1][j],f[1][j-1]+calc(sum,1,j));
for(int i=2;i<=n;++i)
Reduce(f[i][1],f[i-1][1]+calc(sum,i,1));
for(int i=2;i<=n;++i)
for(int j=2;j<=m;++j){
Reduce(f[i][j],f[i-1][j]+calc(sum,i,j));
Reduce(f[i][j],f[i][j-1]+calc(sum,i,j));
}
return sum*sum+f[n][m];
}


int main(){
init();
ans=inf;
for(int sum=1;sum<=S;++sum)
Reduce(ans,dp(sum));
std::cout<<ans;
return 0;
}

T2:让你每次从一个区间向另一个区间连边,最后求起点到所有点的最短路.

很显然是线段树优化建图,开两颗线段树A,B,第一颗线段树从儿子节点向父亲连边,另外一条线段树从父亲向儿子连边.但是一个点一个点的向区间连边太麻烦了,所以我们需要建一个虚点,每次从区间[l1,r1]向一个虚点连边,然后再用这个虚点向区间[l2,r2]连边,这样就可以了. (但是我被卡常了)jiji

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

inline int read () {
int s = 0 , w = 1;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return s * w;
}

const int N = 500010;
const int M = 2210000;

int n , m , p , tot , cnt , root_f , root_s;
struct edge{
int to;
int next;
int date;
}e[11000000];
struct Node{
int lc;
int rc;
}tree[N<<2];
int head[M] , dis[M] , pos[N];
bool vis[M];

std :: priority_queue < std :: pair < int , int > , std :: vector < std :: pair < int , int > > , std :: greater < std :: pair < int , int > > > q;

inline void add(int x,int y,int date){
e[++cnt].to=y;
e[cnt].next=head[x];
head[x]=cnt;
e[cnt].date=date;
return;
}
void FBuild(int &root,int l,int r){
root=++tot;
if ( l == r ) {
pos[l]=root;
return;
}
int mid=l+r>>1;
FBuild(tree[root].lc,l,mid);
FBuild(tree[root].rc,mid+1,r);
add(tree[root].lc,root,0);
add(tree[root].rc,root,0);
return;
}
void SBuild(int &root,int l,int r){
root=++tot;
if(l==r){
add(root,pos[l],0);
return;
}
int mid=l+r>>1;
SBuild(tree[root].lc,l,mid);
SBuild(tree[root].rc,mid+1,r);
add(root,tree[root].lc,0);
add(root,tree[root].rc,0);
return;
}
void FAdd(int root,int l,int r,int x,int y){

if(x<=l&&r<=y) {
add(root,tot,1);
return;
}
int mid=l+r>>1;
if(x<=mid)
FAdd(tree[root].lc,l,mid,x,y);
if(y>mid)
FAdd(tree[root].rc,mid+1,r,x,y);
}
void SAdd(int root,int l,int r,int x,int y){

if(x<=l&&r<=y) {
add(tot,root,1);
return;
}
int mid=l+r>>1;
if(x<=mid)
SAdd(tree[root].lc,l,mid,x,y);
if(y>mid)
SAdd(tree[root].rc,mid+1,r,x,y);
return;
}
inline void Dijkstra(){
memset(dis,0x3f3f3f3f,sizeof(dis));
q.push(std :: make_pair(0,pos[p]));
dis[pos[p]]=0;
while(!q.empty()){
int x=q.top().second;
q.pop();
if(vis[x])
continue;
vis[x]=1;
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
if(dis[x]+e[i].date<dis[y]){
dis[y]=dis[x]+e[i].date;
q.push(std ::make_pair(dis[y],y));
}
}
}
return;
}

int main ( void ) {
freopen("road.in","r",stdin);
freopen("road.out","w",stdout);
n = read();
m = read();
p = read();
FBuild ( root_f , 1 , n );
SBuild ( root_s , 1 , n );
while ( m-- ) {
int x1 = read() , y1 = read() , x2 = read() , y2 = read();
tot++;
FAdd(root_f,1,n,x1,y1);
SAdd(root_s,1,n,x2,y2);
tot++;
FAdd(root_f,1,n,x2,y2);
SAdd(root_s,1,n,x1,y1);

}
Dijkstra();
for(int i=1;i<=n;++i)
printf("%d\n",dis[pos[i]]/2);
return 0;
}

T3:给你一个矩阵,让你求出这个矩阵中的一个最大的子矩阵,使得这个子矩阵的每一行和每一列都是等差数列

暂时咕咕咕一会,不会jiji

因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:20190819模拟赛题解

文章作者:KRrrrrrrrr

发布时间:2019年09月11日 - 18:09

最后更新:2019年11月05日 - 09:11

原始链接:http://krrrr.xyz/2019/09/11/20190819模拟赛题解/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。