题解系列
- 自己写的题解
2020年上海理工大学算法竞赛训练场11 I~K
I. Count
题意：
题解：
由于数据范围很大，考虑矩阵加速，构造如下矩阵A
AC代码：
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=123456789;
struct M{
ll mat[10][10];
};
int t;
ll n;
M operator*(M x1,M x2){
M res;
memset(res.mat,0,sizeof(res.mat));
for(int i=1;i<=6;i++){
for(int j=1;j<=6;j++){
for(int k=1;k<=6;k++){
res.mat[i][j]+=(x1.mat[i][k]%mod*x2.mat[k][j]%mod)%mod;
res.mat[i][j]%=mod;
}
}
}
return res;
}
inline M mqpow(M aa,ll y,M A){
while(y>0){
if(y&1) aa=aa*A;
y>>=1;
A=A*A;
}
return aa;
}
int main(){
scanf("%d",&t);
M a,b;
memset(a.mat,0,sizeof(a.mat));
memset(b.mat,0,sizeof(b.mat));
a.mat[1][1]=1;
a.mat[1][2]=2;
a.mat[1][3]=27;
a.mat[1][4]=9;
a.mat[1][5]=3;
a.mat[1][6]=1;
b.mat[1][2]=b.mat[5][4]=2;
b.mat[4][3]=b.mat[5][3]=3;
b.mat[2][1]=b.mat[2][2]=b.mat[3][2]=b.mat[3][3]=b.mat[4][4]=b.mat[5][5]=b.mat[6][3]=b.mat[6][4]=b.mat[6][5]=b.mat[6][6]=1;
while(t--){
scanf("%lld",&n);
M ans=mqpow(a,n-1,b);
printf("%lld\n",ans.mat[1][1]);
}
return 0;
}
|
J. 没有兄弟的舞会
题意：
求一棵节点带权值的树的节点权值和的最大值和最小值，条件是所选节点中至多只有一对兄弟节点（父节点相同）
题解：
用vector（set好像也可，还省去了排序）存每个父节点的儿子节点，然后对每个节点都贪心地选最大和最小的儿子节点加到答案中，最后再遍历所有节点找到次大和次小的权值加上去就行了
注意：
- 权值有正有负，因此大于零的节点都没必要加到最小值里面，同理小于零的节点也没必要加到最大值里面
- 此题似乎用快读会TLE（不知道是不是我的问题？）
另外，此题很像树形dp，应该也可但我不会，如有大佬用树形dp写的希望能分享一波？
AC代码
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<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const ll inf=1ll<<60;
ll fa[100015],t,n,x;
vector<ll> wdnmd[100015];
int main(){
ios::sync_with_stdio(false);
cin>>t;
while(t--){
cin>>n;
for(int i=0;i<=n;i++) wdnmd[i].clear();
for(int i=2;i<=n;i++){
cin>>fa[i];
}
for(int i=1;i<=n;i++){
cin>>x;
wdnmd[fa[i]].push_back(x);
}
for(int i=0;i<=n;i++){
if(!wdnmd[i].empty()) sort(wdnmd[i].begin(),wdnmd[i].end());
}
ll ansmin=0,ansmax=0;
ll minh=0,maxh=0;
for(int i=0;i<=n;i++){
ll Size=wdnmd[i].size();
if(Size!=0){
if(wdnmd[i][0]<0) ansmin+=wdnmd[i][0];
if(wdnmd[i][Size-1]>0) ansmax+=wdnmd[i][Size-1];
if(wdnmd[i].size()>=2){
minh=min(minh,wdnmd[i][1]);
maxh=max(maxh,wdnmd[i][Size-2]);
}
}
}
cout<<ansmax+maxh<<" "<<ansmin+minh<<endl;
}
return 0;
}
|
K. 代码派对
题意：
在1000*1000的网格中给出若干矩形，若任意三个矩形重合到至少包含一个格子的区域中则算这三个矩形组成了一个答案，求共有多少个这样的答案
题解：
首先想到二维前缀和可以把1000*1000中的所有格子对应的矩形重合次数算出来，然后求一下
但是会发现，好多格子都被重复算了，因为矩形和矩形可以重合到含有多个格子的矩形中（而这写都只能算一个答案），因此需要减掉这部分多出的答案
采用容斥原理，存前缀和的时候把到i,j,i-1,j,i,j-1,i-1,j-1的和都存一遍，然后像求二维前缀和一样容斥一下答案，即
这样就能把答案缩到一个小正方形中了
AC代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[1005][1005],b[1005][1005],c[1005][1005],d[1005][1005];
int main(){
int t;
scanf("%d",&t);
while(t--){
ll n,x1,y1,x2,y2;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
memset(d,0,sizeof(d));
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
a[x1][y1]++,a[x2+1][y2+1]++,a[x2+1][y1]--,a[x1][y2+1]--;
b[x1][y1]++,b[x2+1][y2]++,b[x2+1][y1]--,b[x1][y2]--;
c[x1][y1]++,c[x2][y2+1]++,c[x2][y1]--,c[x1][y2+1]--;
d[x1][y1]++,d[x2][y2]++,d[x2][y1]--,d[x1][y2]--;
}
ll ans1=0,ans2=0,ans3=0,ans4=0;
for(int i=1;i<=1000;i++){
for(int j=1;j<=1000;j++){
a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1];
if(a[i][j]>=3){
ans1+=a[i][j]*(a[i][j]-1)*(a[i][j]-2)/6;
}
}
}
for(int i=1;i<=1000;i++){
for(int j=1;j<=1000;j++){
b[i][j]+=b[i][j-1]+b[i-1][j]-b[i-1][j-1];
if(b[i][j]>=3){
ans2+=b[i][j]*(b[i][j]-1)*(b[i][j]-2)/6;
}
}
}
for(int i=1;i<=1000;i++){
for(int j=1;j<=1000;j++){
c[i][j]+=c[i][j-1]+c[i-1][j]-c[i-1][j-1];
if(a[i][j]>=3){
ans3+=c[i][j]*(c[i][j]-1)*(c[i][j]-2)/6;
}
}
}
for(int i=1;i<=1000;i++){
for(int j=1;j<=1000;j++){
d[i][j]+=d[i][j-1]+d[i-1][j]-d[i-1][j-1];
if(d[i][j]>=3){
ans4+=d[i][j]*(d[i][j]-1)*(d[i][j]-2)/6;
}
}
}
printf("%lld\n",ans1-ans2-ans3+ans4);
}
return 0;
}
|