A. Fence
题意
为了组成一个四边形，给定三边的长度，求最后一个边的长度
思路
我们可以想一下，当一个边固定，其余两个边分别在这个边的两个端点，且边在一边，只有有这个边的角度越大，第三个边越大，当为180°，就会成为一个直线，所以只需要小于三边之和就可以满足不是一个直线的情况，且为最大的可能，必然满足情况
代码
#include<iostream>
using namespace std
;
#define int long long
signed main(){
int T
;
cin
>>T
;
while(T
--){
int a
,b
,c
;
cin
>>a
>>b
>>c
;
cout
<<(a
+ b
+ c
- 1)<<endl
;
}
return 0;
}
B. Nice Matrix
题意
给定一个矩阵，为了使矩阵的行和列都满足回文串的性质，每次操作可以个任意一个数加一或减一，求最小操作数
思路
我们可以想象一下回文串的性质，所以一个点要和算他在内的四个点相同（奇数可能为两个个或一个），即求四个点相同的最小步数，和货仓选址是一个道理，只需给他的四份之一的点遍历一遍就可以了
代码
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std
;
#define int long long
const int N
= 110;
int a
[N
][N
];
signed main(){
int T
;
cin
>>T
;
while(T
--){
int n
,m
;
cin
>>n
>>m
;
for(int i
= 1;i
<=n
;i
++){
for(int j
= 1;j
<= m
;j
++) cin
>>a
[i
][j
];
}
int ans
= 0;
for(int i
= 1,ii
= n
;i
<=(n
+ 1)/2;i
++,ii
--){
for(int j
= 1,jj
= m
;j
<=(m
+ 1)/2;j
++,jj
--){
int b
[4];
b
[0] = a
[i
][j
],b
[1] = a
[i
][jj
],b
[2] = a
[ii
][j
],b
[3] = a
[ii
][jj
];
sort(b
,b
+ 4);
int x
= b
[1];
int res
= abs(b
[0] - b
[1]) + abs(b
[2] - b
[1]) + abs(b
[3] - b
[1]);
if((n
& 1)&&i
== (n
+ 1)/2)
res
/= 2;
if((m
& 1)&&j
== (m
+ 1)/2)
res
/= 2;
ans
+= res
;
}
}
cout
<<ans
<<endl
;
}
return 0;
}
C. Bargain
题意
给定一个很大的数，可以从中删除一段连续的部分（非空），这样就能使这个数有很多不同的可能，求这些可能的不同取值
思路
我们可以枚举这个数每一位的所有可能的和即在这个数的前面删除，或后面删除。 这个数位 a1a2a3···an-1an 假设他在i位 如果在前面删除 对于从他前面的第一位删除有 i - 1 种 对于从他前面的第两位删除有 i - 2 种 ·········· 对于从他前面的第i - 1位删除有 1 种 即有 i * (i - 1) / 2 中 结果为 ai * 10n-i * i * (i - 1)/2 如果在后面删除， 假设他后面有k为 如果这个数在最后一位，只能把后面的k位都删除，1种可能，且为 ai 如果这个数在倒数第二位，可以把连续的k - 1位删除，2种可能 且为 ai * 10 如果这个数在倒数第三位，可以把连续的k - 2位删除，3种可能 且为 ai * 102 这样我们就能发现所有的规律
代码
#include<iostream>
#include<cstring>
using namespace std
;
const int N
= 1e5+10,mod
= 1e9+7;
#define int long long
char s
[N
];
int f
[N
];
signed main(){
scanf("%s",s
+ 1);
int n
= strlen(s
+ 1);
int ans
= 0,p
= 1;
int now
= 0;
for(int i
= n
;i
>= 1;i
--){
int v
= s
[i
] - '0';
int cur
= (now
+ (i
* (i
- 1) / 2) % mod
* p
% mod
)%mod
;
ans
= (ans
+ cur
* v
) % mod
;
now
= (now
+ p
* (n
- i
+ 1)%mod
)%mod
;
p
= (p
* 10) % mod
;
}
cout
<<ans
<<endl
;
return 0;
}
感觉有点跳跃性，多看看还是可以理解的
D. Returning Home
题意
给定一个n * n 的地图，给定一个起点和一个终点，求起点到终点需要多少最短时间，走一步时间为1，给了m个神奇的点，如果在x坐标或y坐标在等于神奇的点的x坐标或y坐标，那么就可以瞬移到这个神奇的点
思路
我们可以把起点也可以看做神奇的点，因为没有必要走两次起点。我们很容易想到最后走到终点的点必然是这些神奇的点中的一个，一个最暴力的想法就是给这些神奇的点建边，求出到每个点的最短距离，但是这样就要给每个点建立 n - 1 条边即 n * (n - 1) 条边，无论在时间还是空间都是不允许，这就需要我们优化一下边，走到一个点无非是从x方向或y方向，如果在x方向上到达也可以想象成先到比他 x小的最大的那个点或大于x的最小的那个点，在走在这个点，因为他的特性，直接走和这样的时间是等价的，所以我们就可以这样直接建立在x方向上相邻的点和在y方向相邻的点之间的边（只需要建立 4 * n 条边），然后通过dijkstra直接算出到这些点距离。
代码
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std
;
const int N
= 1e5+10,M
= 4 * N
;
#define x first
#define y second
typedef pair
<int ,int > PII
;
int h
[N
],e
[M
],ne
[M
],w
[M
],idx
;
bool st
[N
];
int d
[N
],id
[N
];
PII a
[N
];
PII ed
;
bool
cmp1(int x
,int y
){
return a
[x
].x
< a
[y
].x
;
}
bool
cmp2(int x
,int y
){
return a
[x
].y
< a
[y
].y
;
}
void add(int a
,int b
,int c
){
e
[idx
] = b
,w
[idx
] = c
,ne
[idx
] = h
[a
],h
[a
] = idx
++;
}
void dijkstra(){
memset(d
,0x3f,sizeof d
);
d
[0] = 0;
priority_queue
<PII
,vector
<PII
> ,greater
<PII
>>hp
;
hp
.push({0,0});
while(hp
.size()){
auto t
= hp
.top();
hp
.pop();
int ver
= t
.y
,dist
= t
.x
;
if(st
[ver
]) continue;
st
[ver
] = true
;
for(int i
= h
[ver
];i
!=-1;i
= ne
[i
]){
int j
= e
[i
];
if(d
[j
] > dist
+ w
[i
]){
d
[j
] = dist
+ w
[i
];
hp
.push({d
[j
],j
});
}
}
}
}
int main(){
ios
::sync_with_stdio(false
);
memset(h
,-1,sizeof h
);
int n
,m
;
cin
>>n
>>m
;
cin
>>a
[0].x
>>a
[0].y
;
cin
>>ed
.x
>>ed
.y
;
id
[0] = 0;
for(int i
= 1;i
<= m
;i
++){
cin
>>a
[i
].x
>>a
[i
].y
;
id
[i
] = i
;
}
sort(id
,id
+ m
+ 1,cmp1
);
for(int i
= 1;i
<=m
;i
++){
int t
= a
[id
[i
]].x
- a
[id
[i
- 1]].x
;
add(id
[i
],id
[i
- 1],t
);
add(id
[i
- 1],id
[i
],t
);
}
sort(id
,id
+ m
+ 1,cmp2
);
for(int i
= 1;i
<=m
;i
++){
int t
= a
[id
[i
]].y
- a
[id
[i
- 1]].y
;
add(id
[i
],id
[i
- 1],t
);
add(id
[i
- 1],id
[i
],t
);
}
dijkstra();
int ans
= 2e9;
for(int i
= 0;i
<=m
;i
++){
ans
= min(ans
,d
[i
] + abs(ed
.x
- a
[i
].x
) + abs(ed
.y
- a
[i
].y
));
}
cout
<<ans
<<endl
;
return 0;
}
