考试策略

​ 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;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

3 条评论

litble · 2017年10月27日 9:38 下午

orz 感觉我好蒻,考完联赛估计就退役了。

    konnyakuxzy · 2017年10月28日 8:23 上午

    。。。您还装蒻
    那您这样我现在不就应该退役了。。。

konnyakuxzy · 2017年10月26日 7:53 下午

Orz 蒟蒻我会打第一题结果还 tmd 打错了我是不是炒鸡大傻逼了。。。

回复 konnyakuxzy 取消回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注