Codeforces Round #677 (Div. 3)
A. Boring Apartments
思路
设相同的数的数为n位数为k，可以很明显看到答案为 (n - 1) * 10 + (1 + 2 + 3 ···+ k )
代码
#include<iostream>
using namespace std
;
int main(){
int T
;
cin
>> T
;
while(T
--){
int n
;
scanf("%d",&n
);
int t
= n
% 10;
int ans
= (t
- 1) * 10;
int v
= 1;
while(n
){
n
/=10;
ans
+= v
;
v
++;
}
cout
<< ans
<<endl
;
}
return 0;
}
B. Yet Another Bookshelf
思路
在移动的过程中，前面的可以等待后面的，但是移动过程中移动的1和1之间的0的个数是不可以避免的，所以答案为所有1之间0的个数的总和
代码
#include<iostream>
using namespace std
;
const int N
= 55;
int a
[N
];
int main(){
int T
;
cin
>> T
;
while(T
--){
int n
;
scanf("%d",&n
);
for(int i
= 1;i
<= n
;i
++) scanf("%d",&a
[i
]);
int ans
= 0;
for(int i
= 1;i
<= n
;i
++){
if(a
[i
] == 1){
int j
= i
+ 1;
while(j
<= n
&&a
[j
] == 0) j
++;
if(j
<= n
) ans
+= j
- i
- 1;
i
= j
- 1;
}
}
cout
<< ans
<<endl
;
}
return 0;
}
C. Dominant Piranha
思路
因为只需要一个可以全部吃掉的点的下标，如果都相同那么必然不可以，在其他情况下，至少有一个最大值和他周围的两个数中的一个不一样，所以就可以依次吃掉全部
代码
#include<iostream>
using namespace std
;
const int N
= 3e5+10;
int a
[N
];
int main(){
int T
;
cin
>> T
;
while(T
--){
int n
;
scanf("%d",&n
);
int maxp
= 0;
for(int i
= 1;i
<= n
;i
++) scanf("%d",&a
[i
]),maxp
= max(maxp
,a
[i
]);
int ans
= -1;
for(int i
= 1;i
<= n
;i
++){
if(a
[i
] == maxp
){
if((i
< n
&&a
[i
+ 1] < maxp
)|| i
> 1&&a
[i
- 1] < maxp
)
ans
= i
;
}
}
cout
<< ans
<<endl
;
}
return 0;
}
D. Districts Connection
思路
所有的数都相同，那么必然不可以。对于其他情况，至少有两个点不一样，我们可以选出两个不一样的点，以一个为根节点，和他不相等的点建立子树，和他相同的点连接在另一个点上
代码
#include<iostream>
#include<algorithm>
using namespace std
;
const int N
= 5010;
int a
[N
];
int main(){
int T
;
cin
>> T
;
while(T
--){
int n
;
scanf("%d",&n
);
int flag
= 0;
for(int i
= 1;i
<= n
;i
++){
scanf("%d",&a
[i
]);
if(a
[i
] != a
[1]){
flag
= i
;
}
}
if(!flag
){
puts("NO");
}
else{
puts("YES");
for(int i
= 2;i
<= n
;i
++){
if(a
[i
] != a
[1]){
printf("%d %d\n",1,i
);
}
else {
printf("%d %d\n",flag
,i
);
}
}
}
}
return 0;
}
E. Two Round Dances
思路
由于是圆形我们可以固定一个点，其他点任意排列构成的必然是不相等。对于第一个dances来说，固定一个1，那么其余n / 2 - 1一个点就会有(n - 1) * (n - 2) *···(n / 2 + 1) 对于另一半来说也需要固定一个点，其他的点任意排列，那么剩余的点(n / 2 - 1) * (n / 2 -2)* ··· * 1
代码
#include<iostream>
#include<algorithm>
using namespace std
;
const int N
= 5010;
#define int long long
signed main(){
int n
;
cin
>> n
;
int ans
= 1;
for(int i
= n
- 1;i
> n
/ 2;i
--) ans
*= i
;
for(int i
= n
/ 2 - 1;i
;i
--) ans
*= i
;
cout
<<ans
<<endl
;
return 0;
}
F. Zero Remainder Sum
思路
我们可以依次统计每行的结果，第i的结果是第i+1行的初始化，利用dp的思想
对于单行而言
f[i][j][k]表示在第i列选了j个数模K为k的最大值
可以通过类似01背包的形式，选或不选两种方式
不选 f[i - 1][j][k]
选 f[i - 1][j - 1][ ((k - a[i])%K + K)] + a[i]
代码
#include<iostream>
#include<cstring>
using namespace std
;
const int N
= 75;
int f
[N
][N
][N
];
int a
[N
][N
];
int main(){
int n
,m
,K
;
scanf("%d%d%d",&n
,&m
,&K
);
for(int i
= 1;i
<= n
;i
++)
for(int j
= 1;j
<= m
;j
++)
scanf("%d",&a
[i
][j
]);
int ans
= 0;
memset(f
,-0x3f,sizeof f
);
f
[0][0][0] = 0;
for(int u
= 1;u
<= n
;u
++){
for(int i
= 1;i
<= m
;i
++){
for(int j
= 0;j
<= m
/ 2;j
++)
for(int k
= 0;k
< K
;k
++){
if(j
== 0) f
[i
][j
][k
] = f
[i
- 1][j
][k
];
else {
f
[i
][j
][k
] = max(f
[i
- 1][j
][k
],f
[i
- 1][j
- 1][((k
- a
[u
][i
])%K
+ K
) % K
] + a
[u
][i
]);
}
}
}
for(int j
= 0;j
<= m
/2;j
++){
for(int k
= 0;k
< K
;k
++)
f
[0][0][k
] = max(f
[0][0][k
],f
[m
][j
][k
]);
}
}
cout
<<f
[0][0][0]<<endl
;
return 0;
}
G. Reducing Delivery Cost
思路
我们很容易发现m(边数）很小所以我们就可以枚举使那条边变为0。所以我们需要首先处理每个点到各个点的最小值，因为m很小，所以使用堆优化的dijkstra。对于每条边变为0而言，对于每一个(a,b)都有两种情况，一种是过这条边min(d[a][x] + d[y][b],d[a][y] + d[x][b]，另一种是不过这条边d[a][b]，总体最小值即为这两种情况的最小值，所以我们只需要枚举一遍即可
代码
#include<iostream>
#include<cstring>
#include<queue>
using namespace std
;
#define x first
#define y second
typedef pair
<int ,int > PII
;
const int N
= 1010,M
= 2010,INF
= 0x3f3f3f3f;
int h
[N
],e
[M
],ne
[M
],w
[M
],idx
;
bool st
[N
];
int d
[N
][N
];
PII q
[N
];
int n
,m
,k
;
void add(int a
,int b
,int c
){
e
[idx
] = b
,w
[idx
] = c
,ne
[idx
] = h
[a
],h
[a
] = idx
++;
}
void dijkstra(int u
,int d
[]){
memset(d
,0x3f,sizeof h
);
memset(st
,0,sizeof st
);
d
[u
] = 0;
priority_queue
<PII
,vector
<PII
>,greater
<PII
> > hp
;
hp
.push({0,u
});
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(){
int n
,m
,k
;
scanf("%d%d%d",&n
,&m
,&k
);
memset(h
,-1,sizeof h
);
while(m
--){
int a
,b
,c
;
scanf("%d%d%d",&a
,&b
,&c
);
add(a
,b
,c
);
add(b
,a
,c
);
}
for(int i
= 1;i
<= k
;i
++){
int x
,y
;
scanf("%d%d",&x
,&y
);
q
[i
] = {x
,y
};
}
for(int i
= 1;i
<= n
;i
++)
dijkstra(i
,d
[i
]);
int ans
= INF
;
for(int i
= 0;i
< idx
;i
+= 2){
int res
= 0;
int x
= e
[i
],y
= e
[i
^ 1];
for(int j
= 1;j
<= k
;j
++){
int a
= q
[j
].x
,b
= q
[j
].y
;
res
+= min(d
[a
][b
],min(d
[a
][x
]+d
[y
][b
],d
[a
][y
] + d
[x
][b
]));
}
ans
= min(res
,ans
);
}
cout
<< ans
<<endl
;
return 0;
}
