Codeforces Round #677 (Div. 3)
Codeforces Round #677 (Div. 3)
A. Boring Apartments
#include <bits/stdc++.h>
using namespace std;
int main(){
int T;
cin>>T;
int x;
int ans;
while(T--){
ans=0;
cin>>x;
int k=x%10;
while(x%10!=0){
x/=10;
ans++;
}
ans=(1+ans)*ans/2;
ans=ans+(k-1)*10;
cout<<ans<<endl;
}
}
D. Districts Connection
同一个帮派连一个点就可以了，最简单的策略就是和一号点不同的连一号点，和一号点相同的连其他点，只有一种帮派就输出NO
#include <bits/stdc++.h>
using namespace std;
int T,n;
int a[5100];
int ans[5100];
int main(){
cin>>T;
int dif;
while(T--){
cin>>n;
dif=-1;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]!=a[1]){
ans[i]=1;
dif=i;
}
}
if(dif==-1){
cout<<"NO"<<endl;
continue;
}
cout<<"YES"<<endl;
for(int i=2;i<=n;i++){
if(a[i]==a[1])
ans[i]=dif;
cout<<i<<" "<<ans[i]<<endl;
}
}
}
E. Two Round Dances
先要分成两组，如果只挑一半情况是
C
n
n
/
2
{C}_{n}^{n/2}
Cnn/2但另一半也会计算，所以情况减少了一半。
对于两组都需要进行圆排列，所以最后的答案就是
1
2
×
C
n
n
2
×
(
(
n
2
−
1
)
!
)
2
\dfrac{1}{2} \times C_n^ \frac{n}{2} \times ((\dfrac{n}{2}-1)!)^2
21×Cn2n×((2n−1)!)2
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ll x;
cin>>x;
ll half=x/2;
ll ans=1;
for(ll i=x;i>x-half;i--){
ans*=i;
}
ans/=2;
for(ll i=1;i<=half;i++){
ans/=i;
}
for(ll i=1;i<half;i++){
ans=ans*i*i;
}
cout<<ans<<endl;
}
F. Zero Remainder Sum
写了一发暴力，T了
想到dp，一开始只想到对行列dp，一直推不出状态转移方程，后来看n不大，就想到多维。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int num[80][80];
int n,m,k;
int dp[80][80][80][80];
int main(){
cin>>n>>m>>k;
memset(dp,-1,sizeof(dp));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>num[i][j];
}
}
dp[0][0][0][0]=0;
int nx,ny,nr;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
for(int cnt=0;cnt<m/2+1;cnt++){
for(int r=0;r<k;r++){
if(dp[i][j][cnt][r]==-1)
continue;
if(j==m-1) {
nx=i+1;
ny=0;
}
else{
nx=i;
ny=j+1;
}
if (i != nx)
dp[nx][ny][0][r] = max(dp[nx][ny][0][r], dp[i][j][cnt][r]);
else
dp[nx][ny][cnt][r] = max(dp[nx][ny][cnt][r], dp[i][j][cnt][r]);
if (cnt + 1 <= m / 2) {
int nr = (r + num[i][j]) % k;
if (i != nx)
dp[nx][ny][0][nr] = max(dp[nx][ny][0][nr], dp[i][j][cnt][r] + num[i][j]);
else
dp[nx][ny][cnt + 1][nr] = max(dp[nx][ny][cnt + 1][nr], dp[i][j][cnt][r] + num[i][j]);
}
}
}
}
}
cout << max(0,dp[n][0][0][0])<<endl;
}
G. Reducing Delivery Cost
暴力枚举每条边权值变为0后，包含这条边的最短路
（刚开始用dijkstra一直没有调出来，后来拉了spfa的板子才过的，估计太久没有打dijkstra，之后复习）
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e3+10;
struct edge{
int to;
int w;
int next;
};
int x[maxn],y[maxn];
int f[maxn][maxn];
int n,m,k,u,v,w;
queue<int> q;
edge e[maxn];
int ne=0,head[maxn],dis[maxn],a[maxn];
bool b[maxn];
void add(int a,int b,int c){
e[++ne].to=b;e[ne].w=c;e[ne].next=head[a];head[a]=ne;
}
int now;
void spfa(int s){
int i;
memset(dis,0x3f,sizeof(dis));
memset(b,false,sizeof(b));
q.push(s);//源点入队
b[s]=true;
dis[s]=0;
while(!q.empty()){
s=q.front();
q.pop();//记录队首并弹出
b[s]=false;//撤销入队标记
for(i=head[s];i!=-1;i=e[i].next){
if(dis[e[i].to]>dis[s]+e[i].w){//若可以松弛
dis[e[i].to]=dis[s]+e[i].w;//更新距离
if(!b[e[i].to]){
q.push(e[i].to);//入队
b[e[i].to]=true;//标记已入队
}
}
}
}
for(int i = 1;i <= n;i++){
f[now][i] = dis[i];
}
}
int main(){
memset(head,-1,sizeof(head));
memset(e,0,sizeof(e));
scanf("%d%d%d",&n,&m,&k);
while(m--){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
for(int i = 1;i <= n;i++){
now=i;
spfa(i);
}
int ans = 0x3f3f3f3f;
for(int i = 0;i < k;i++)
scanf("%d%d",&x[i],&y[i]);
for(int i=1;i<=n;i++){
for(int j=head[i];j!=-1;j=e[j].next){
int sum = 0;
for(int p = 0;p < k;p++)
sum += min(f[x[p]][y[p]],min(f[x[p]][i] + f[y[p]][e[j].to],f[x[p]][e[j].to] + f[y[p]][i]));
ans = min(ans,sum);
}
}
/* for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
cout<<f[i][j]<<" ";
cout<<endl;
}*/
printf("%d\n",ans);
return 0;
}
本文地址：https://blog.csdn.net/tuakua/article/details/109251210
