NOIP模拟27

淡淡的烟草味﹌ 2023-08-17 16:48 52阅读 0赞

两个机房又和在一起考试

开场看了看T1，感觉挺水的，过。

T2，这个式子有点奇怪，暂时没什么思路，过

T3，好像保留最后几位换个根处理一下就行了，过，先去打T1

于是T1大概打了0.5h，连暴力带正解带对拍，码完之后感觉挺稳的，就过了。去看T3。

T3换个根就没事了，但是我一开始状态设置的有问题，一拍就爆炸了。

调调调，调过了T3，拍上了，感觉很稳，就交了一下T3和T1，此时过了两个小时

去把T2的式子化简了一下，发现只与前面所有数的和有关，好像是个很简单的dp，就码出来了。

不太会打暴力，于是码了个dfs，拍上了，很稳。

然后我去上了个厕所

然后碰见了DeepinC

然后他问我：“你切了几个？”

然后我感觉不太对劲，他都用“切”了，说明。。。。。。他AK了？

然后我决定回答：3个（这句话目的在于给DeepinC压力，使他不会过早颓废）

出分了，T2T3都A了，T1爆炸了

T1.

注意这题不保证b是有序的，需要自己手动sort，不这么干会变成20分，别问我怎么知道的。

然而我打对拍时智障地认为输入保证有序，于是我将所有数生成了出来，然后sort了一遍，然后输出

然后错失了人生第一个AK

T2.

把式子化简了，考虑每个点的贡献就没了。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 int f[32][32][3005],t;
     4 int n,m,a[35][35],ans;
     5 int main(){
     6     scanf("%d",&t);
     7     while(t--){
     8         ans=0x7fffffff;
     9         memset(f,0x3f,sizeof(f));
    10         scanf("%d%d",&n,&m);
    11         for(int i=1;i<=n;i++)
    12             for(int j=1;j<=m;j++)
    13                 scanf("%d",&a[i][j]);
    14         f[1][1][a[1][1]]=(n+m-2)*a[1][1]*a[1][1];
    15         for(int i=1;i<=n;i++)
    16             for(int j=1;j<=m;j++){
    17                 if(i==1&&j==1)continue;
    18                 for(int k=1;k<=(i+j)*30;k++){
    19                     int sum=(n+m-2)*a[i][j]*a[i][j]-k*a[i][j]*2;
    20                     int mi=min(f[i-1][j][k],f[i][j-1][k]);
    21                     if(mi==0x3f3f3f3f)continue;
    22                     mi+=sum;
    23                     f[i][j][k+a[i][j]]=min(f[i][j][k+a[i][j]],mi);
    24                     if(i==n&&j==m)ans=min(ans,f[i][j][k+a[i][j]]);
    25                 }
    26             }
    27         printf("%d\n",ans);
    28     }
    29     return 0;
    30 }

T3.

换根dp，考虑每个数二进制最后4位，统计答案即可。

注意m!=0时不能算自己到自己的贡献。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 int n,m,fi[100005],ne[200005],to[200005],ans,dis[100005],w[200005],tot;
     4 int res[100005],sum[100005][16],siz[100005],ss[100005][16];
     5 inline void add(int x,int y,int z){
     6     ne[++tot]=fi[x];
     7     fi[x]=tot;
     8     to[tot]=y;
     9     w[tot]=z;
    10 }
    11 void dfs(int x,int fa){
    12     siz[x]=1;ss[x][0]=1;
    13     for(int i=fi[x];i;i=ne[i]){
    14         int y=to[i];
    15         if(y!=fa){
    16             dis[y]=dis[x]+w[i];
    17             ans+=dis[y]^m;
    18             res[1]+=dis[y];
    19             dfs(y,x);
    20             siz[x]+=siz[y];
    21             for(int j=0;j<=15;j++)
    22                 ss[x][(j+w[i])&15]+=ss[y][j];
    23         }
    24     }
    25 }
    26 void dfs2(int x,int fa){
    27     for(int i=fi[x];i;i=ne[i]){
    28         int y=to[i];
    29         if(y!=fa){
    30             res[y]=res[x]+(n-2*siz[y])*w[i];
    31             for(int j=0;j<=15;j++){
    32                 sum[y][(j+w[i])&15]+=sum[x][j]-ss[y][(j-(w[i]&15)+16)&15];
    33                 sum[y][j]+=ss[y][j];
    34             }
    35             dfs2(y,x);
    36         }
    37     }
    38 }
    39 int main(){
    40     scanf("%d%d",&n,&m);
    41     for(int i=1,x,y,z;i<n;i++)
    42         scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z);
    43     dfs(1,0);
    44     printf("%d\n",ans);
    45     for(int i=0;i<=15;i++)
    46         sum[1][i]=ss[1][i];
    47     dfs2(1,0);
    48     for(int i=2;i<=n;i++){
    49         sum[i][0]--;
    50         for(int j=0;j<=15;j++)
    51             res[i]=res[i]-j*sum[i][j]+(m^j)*sum[i][j];
    52         printf("%d\n",res[i]);
    53     }
    54     return 0;
    55 }

转载于:https://www.cnblogs.com/hzoi-cbx/p/11382659.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230809/7d823738573c4debae1a0b71648daad3.png