【考试总结】一只蒟蒻再次暴露了自己的本性 ——litble

考试策略

​ QAQ 今天没考好真的是考试策略的锅。首先看到第一题 “卷积” 就懵了，题目都看不懂，然后什么 zyf 啊 boshi 啊 xzy 啊全部会做 T1，感觉自己要爆炸了。于是做 T2，做了一个多小时写了一个错误的状态转移方程，dp 了好半天，然后又爆炸了，检查都没检查去赶 T3，T3 又赶时间匆匆忙忙写了个错误贪心，回去一看 T2 想到了做法，但是没有时间打了，就 GG 了。

​ 以后一定要吸取教训，要想清楚证明白再下手，否则容易 GG。而且不要受到考试时话特多的人的影响，也不要对于题面很装逼的题目产生畏难情绪。

T1

期望得分：30 实际得分：30

题目描述：花 300 字的废话介绍了 Dirichlet 卷积，然后在一堆废话里藏了大概 10 个字左右的关键信息。总之就是给出 f 求其 Dirichlet 卷积 K 次自乘。

数据范围：

对于 30% 的数据满足，K=1；（就是读入，输出即可）

对于 100% 的数据满足，$1 \leq n \leq 10000 , 1 \leq k \leq 10 , 0 \leq f_i \leq 100000$

题目分析：

模拟题，非常简单。

根本没做出来，我是不是个傻逼啊。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define LL long long
const int N=10005;
int n,k;
LL f[N],g[N],t[N],mod=1000000009;
int main()
{
    freopen("convolution.in","r",stdin);
    freopen("convolution.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i) scanf("%lld",&f[i]),g[i]=f[i];
    for(int i=2;i<=k;++i) {
        for(int j=1;j<=n;++j) {
            t[j]=0;
            for(int ys=1;ys*ys<=j;++ys)
                if(j%ys==0) {
                t[j]+=f[ys]*g[j/ys]%mod;
                if(ys*ys!=j) t[j]+=g[ys]*f[j/ys]%mod;
                t[j]%=mod;
            }
        }
        for(int j=1;j<=n;++j) g[j]=t[j];
    }
    for(int i=1;i<=n;++i) printf("%lld ",g[i]);
    return 0;
}

T2

期望得分：24 实际得分：24

题目描述：

Chanxer 终于当上了 “中华农民联盟” 的盟主，他举目四望，决定四处走走，巡视自己的农土。

“中华农民联盟” 的成员有 n 个村庄，在 “村村通” 计划中，村庄们被 条道路联通了起来，Chanxer 计划从某个村庄出发，访问所有的村庄。

可是 Chanxer 出行有一个特殊的要求，那就是必须以农车代步，现在我们知道哪些村庄配备有农车，也就是说，只有配备有农车的村庄才能够被作为出发点。

Chanxer 有点懒，他想知道访问全部的村庄所要走的路程长度最小是多少。

数据范围：

6 个测试点满足：$N \leq 10$

100% 的数据满足，$N \leq 100000,1 \leq x_i,y_i \leq N,1 \leq z_i \leq 10000$

题目分析：

QAQ 考前 20 分钟想出解法，我是不是个傻逼。

从点 i 出发遍历所有点的最短路是从它出发的最长路路上边权和+其他路边权和*2，这个应该挺好证明的，看它走哪些边后不回来哪些回来即可。

我首先写了个特傻的 dp…..QAQ 我是傻逼。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
const int N=100005;
int n,tot,ans,sum,flag;
int h[N],to[N<<1],ne[N<<1],w[N<<1],f[N],g[N],se[N],bj[N];
void add(int x,int y,int z)
{to[++tot]=y,ne[tot]=h[x],h[x]=tot,w[tot]=z;}
void dfs1(int x,int las) {
    for(int i=h[x];i!=-1;i=ne[i]) {
        if(to[i]==las) continue;
        dfs1(to[i],x);
        if(f[to[i]]+w[i]>=f[x])
            se[x]=f[x],f[x]=f[to[i]]+w[i],bj[x]=to[i];
        else if(f[to[i]]+w[i]>se[x]) se[x]=f[to[i]]+w[i];
    }
}
void dfs2(int x,int las) {
    for(int i=h[x];i!=-1;i=ne[i]) {
        if(to[i]==las) continue;
        if(bj[x]==to[i]) {
            if(se[x]+w[i]>=f[to[i]])
                f[to[i]]=se[x]+w[i],se[to[i]]=f[to[i]],bj[to[i]]=x;
            else if(se[x]+w[i]>se[to[i]]) se[to[i]]=se[x]+w[i];
        }
        else {
            if(f[x]+w[i]>=f[to[i]])
                f[to[i]]=f[x]+w[i],se[to[i]]=f[to[i]],bj[to[i]]=x;
            else if(f[x]+w[i]>se[to[i]]) se[to[i]]=f[x]+w[i];
        }
        dfs2(to[i],x);
    }
}
int main()
{
    freopen("path.in","r",stdin);
    freopen("path.out","w",stdout);
    int i,x,y,z;
    n=read();
    for(i=1;i<=n;++i) h[i]=-1;
    for(i=1;i<n;++i) {
        x=read(),y=read(),z=read(),sum+=z;
        add(x,y,z),add(y,x,z);
    }
    dfs1(1,0),dfs2(1,0);
    for(i=1;i<=n;++i) {
        x=read();
        if(x) {
            if(!flag||f[i]+(sum-f[i])*2<ans) ans=f[i]+(sum-f[i])*2;
            flag=1;
        }
    }
    if(!flag) puts("-1");
    else printf("%d",ans);
    return 0;
}

T3

期望得分：0 实际得分：70

题目描述：

“农气大炮” 是 Chanxer 毕生精力凝结而成的心血。

“当大炮建成时，普天之下，莫非农土！”，现在 Chanxer 还有最后一步，就是为大炮装载农气续航系统，换句话说，就是上电池。

Chanxer 现在有 N 条能量棒，第 i 条的长度为 $2^{k_i}$ ，且拥有一个不稳定值 。

为了避免因为单次高强度攻击而导致大炮瘫痪，Chanxer 觉得采用能源分离装置，他准备了许多能量槽，每个能量槽都是条形的，横截面积恰好容得下一根能量棒插入，而能量槽的深度也为 $2^t$的形式。

现在，Chanxer 需要再能量棒中选择一些插入能量槽中，为了保证续航时间的最大化，Chanxer 要求每个能量槽都必须完全装满，也就是说，插入其中的能量棒的最（总）长度要正好等于能量槽的深度，与此同时，Chanxer 希望被选择的能量棒的总不稳定值最小。

数据范围：

对于 30% 的数据，$1 \leq n,m \leq 12$

对于 100% 的数据，$1 \leq n \leq 10000,0\leq k_i \leq 1000,0 \leq W_i \leq 10000,0 \leq t \leq 1000,0 \leq h,\sum h \leq 5000$

题目分析：

这题目一个错别字（“总” 写成 “最”）害得我以为是一道水题……

首先，t=0 的能力槽只能用 k=0 的能量棒，并尽可能用 W 小的，然后合并，每次将剩下来的 k=0 的能量棒中最小的两根合并成一根 k=1 的，以此类推…..

这样该用的能量棒一定不会漏掉。理性的证明我懒的写了，感性地想一想应该也会明白。

所以我为什么那么蠢，当时打了个傻逼错误贪心…..

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
int n,m,ans;
priority_queue<int,vector<int>,greater<int> > q[1001];
int need[1001];
int main()
{
    freopen("noligon.in","r",stdin);
    freopen("noligon.out","w",stdout);
    int i,w,k,x,y;
    n=read();
    for(i=1;i<=n;++i) k=read(),w=read(),q[k].push(w);
    m=read();
    for(i=1;i<=m;++i) w=read(),k=read(),need[w]+=k;
    for(i=0;i<=1000;++i) {
        while(need[i]) {
            if(q[i].empty()){puts("-1");return 0;}
            x=q[i].top(),ans+=x,q[i].pop(),--need[i];
        }
        while(!q[i].empty()) {
            x=q[i].top(),q[i].pop();
            if(q[i].empty()) break;
            y=q[i].top(),q[i].pop();
            if(i!=1000) q[i+1].push(x+y);
        }
    }
    printf("%d",ans);
    return 0;
}