考试策略

​ 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$

题目分析

模拟题,非常简单。

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

代码

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我是傻逼。

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的,以此类推.....

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

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

代码