CSP-J模拟赛day5——解析+答案

题解

T1 三点连通块

考虑每个点作为中心时，方案数量实际上就是从相邻点中任意选两个组成三点连通块。

因此统计每个点的度，记为$d[i]$，对每个点来说方案数是$d[i]\ast (d[i]-1)/2$。

加和即可。注意long long。

#include<bits/stdc++.h>
using namespace std;

long long son[100010],k;
long long q[100010];
int main(){
int n;
cin>>n;
for (int i=1;i<n;i++){
int a,b;
cin>>a>>b;
son[a]++;
son[b]++;
}
for (int i=2;i<=n;i++){
q[i]=q[i-1]+i-1;
}
for (int i=1;i<=n;i++){
k+=q[son[i]];
}
cout<<k;
return 0;
}

T2 矩阵魔法

普通的模拟。

#include <bits/stdc++.h>
using namespace std;

int n,m;
int a[1505][1505];
int b[1505][1505];
int cnt=0;
void right(int x,int y,int r){
int sx=x-r,sy=y-r;
int ex=x+r,ey=y+r;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
b[i][j]=a[i][j];
}
}
for(int i=sx;i<=ex;i++){
for(int j=sy;j<=ey;j++){
b[x-y+j][x+y-i]=a[i][j];
//b[x+y-j][y-x+i]
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
a[i][j]=b[i][j];
}
}
}
void left(int x,int y,int r){
int sx=x-r,sy=y-r;
int ex=x+r,ey=y+r;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
b[i][j]=a[i][j];
}
}
for(int i=sx;i<=ex;i++){
for(int j=sy;j<=ey;j++){
b[x+y-j][y-x+i]=a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
a[i][j]=b[i][j];
}
}
}

int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cnt++;
a[i][j]=cnt;
}
}
for(int i=1;i<=m;i++){
int x,y,r,z;
scanf("%d%d%d%d",&x,&y,&r,&z);
if(z==0){
right(x,y,r); 
}else{
left(x,y,r); 
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
printf("%d ",a[i][j]);
}
printf("\n");
}

return 0;
}

T3 汪汪队立大功

先不考虑后面可能有机关跳过的问题，考虑每个机会使用后带来的影响：
首先不需要消耗这个机关的能量值，但是后续的所有机关都需要加一，所以减少的能量消耗为$a[i]-(n-i)$

然后你会发现选$k$个机关的话，这$k$个机关自己多消耗的加一是不存在的（因为被跳过了）
所以刚才算的答案比实际的消耗多了$ k * (k - 1) / 2$的能量，减掉即为答案。

#include<bits/stdc++.h>
using namespace std;

long long n,k,a[1010],dp[1010][1010];

int main(){
//freopen("dog.in","r",stdin);
//freopen("dog.out","w",stdout);
int t;
cin>>t;
while (t--){
cin>>n>>k;
for (int i=1;i<=n;i++){
cin>>a[i];
}
for (int i=0;i<=n;i++){
for (int j=0;j<=k;j++){
dp[i][j]=INT_MAX;
}
} 
for (int i=0;i<=k;i++){
dp[0][i]=0; 
} 
for (int i=1;i<=n;i++){
for (int j=0;j<=k;j++){
if(j==0)dp[i][j]=dp[i-1][j]+a[i]; 
else dp[i][j]=min(dp[i-1][j-1],dp[i-1][j]+a[i]+j);
}
}
cout<<dp[n][k]<<endl;
}
return 0;
}

T4 避水珠

首先要观察出一个结论：虽然不限制玩家持有避水珠的数量，但出于最小化的角度考虑，任何时候玩家最多持有一个避水珠。

考虑DP。设状态为$dp[i][j]$表示在点$i$处持有第j个避水珠时的最小能量消耗。其中$j=0$时表示不持有任何避水珠。

转移考虑下列情况：

1. 当这段路不是雨区，可以不持有 $dp[i + 1][0] = min(dp[i + 1][0], dp[i][j]) $
2. 当有一个避水珠时，可以保持 $dp[i+1][j]=min(dp[i+1][j],dp[i][j]+cost[j])$
3. 如果这个位置有新的避水珠，可以换掉 $dp[i+1][bid[i]]=min(dp[i+1][bid[i]],dp[i][j]+cost[bid[i]])$，其中$bid[i]$表示出现在点$i$处的最小重量的避水珠编号。

最后在$dp[a][1]$ ~ $dp[a][m]$ 之间取一个最小的答案即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 5;
const int INF = 0x3f3f3f3f;

int rain[maxn], bid[maxn], cost[maxn], dp[maxn][maxn];
int a, n, m;

int main() {
cin >> a >> n >> m;
for(int i = 1; i <= n; ++i) {
int l, r; cin >> l >> r;
        ++rain[l]; --rain[r];
}
    for(int i = 1;i <= a; ++i)
        rain[i] += rain[i - 1];

for (int i = 1; i <= m; ++i) {
int x, p; cin >> x >> p;
cost[i] = p;
        if(bid[x] == 0 || cost[bid[x]] > p) 
            bid[x] = i;
}
memset(dp, 0x3f, sizeof dp);

    dp[0][0] = 0;
    for(int i = 0;i < a; ++i) {
        for(int j = 0;j <= m; ++j) {
            if(dp[i][j] == INF) continue;
            if(rain[i] == 0) dp[i + 1][0] = min(dp[i + 1][0], dp[i][j]);
            if(j) dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + cost[j]);
            if(bid[i]) dp[i + 1][bid[i]] = min(dp[i + 1][bid[i]], dp[i][j] + cost[bid[i]]);
        }
    }

int ans = INF;
for (int i = 0; i <= m; ++i)
ans = min(ans, dp[a][i]);
cout << ans << '\n';
return 0;
}

原文地址：https://blog.csdn.net/CylMK/article/details/142882201

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！