注意:本系列不是题解,我有时也会写一些好题的题解,但不是在这。我会分享做题过程与思考,但不会给出详细解析,贴出的代码也不一定是正解,纯属自嗨,还请多多包涵。

开学后为了刷存在感勉励自己,我决定在这里记录每周一次的爆零集训过程。

T1 Vigenère密码

16 世纪法国外交家 Blaise de Vigenère 设计了一种多表密码加密算法——Vigenère 密 码。Vigenère 密码的加密解密算法简单易用,且破译难度比较高,曾在美国南北战争中为 南军所广泛使用。
在密码学中,我们称需要加密的信息为明文,用 M 表示;称加密后的信息为密文,用 C 表示;而密钥是一种参数,是将明文转换为密文或将密文转换为明文的算法中输入的数据, 记为 k。 在 Vigenère 密码中,密钥 k 是一个字母串,k=k1k2…kn。当明文 M=m1m2…mn 时, 得到的密文 C=c1c2…cn,其中 ci=mi®ki,运算®的规则如下表所示:
(表略,运算规则为ci=mi+ki-‘a’,超出部分从回到a继续)
Vigenère 加密在操作时需要注意:
1.®运算忽略参与运算的字母的大小写,并保持字母在明文 M 中的大小写形式;
2.当明文 M 的长度大于密钥 k 的长度时,将密钥 k 重复使用。 例如,明文 M=Helloworld,密钥 k=abc 时,密文 C=Hfnlpyosnd。
【输入】
输入文件名为 vigenere.in。 输入共 2 行。
第一行为一个字符串,表示密钥 k,长度不超过 100,其中仅包含大小写字母。第二行 为一个字符串,表示经加密后的密文,长度不超过 1000,其中仅包含大小写字母。
【输出】
输出文件名为 vigenere.out。
输出共 1 行,一个字符串,表示输入密钥和密文所对应的明文。
【输入输出样例】
vigenere.in
CompleteVictory Yvqgpxaimmklongnzfwpvxmniytm
vigenere.out
Wherethereisawillthereisaway

大水题,无任何坑点。不过水题确实有助于进入状态,以后可以多来点(赞许
AC代码:

#include<bits/stdc++.h>
using namespace std;
char key[105];
char pw[1005];
char alp[105];
int main()
{
    scanf("%s",key+1);
    scanf("%s",pw+1);
    int i;
    for(i=0;i<26;i++)
    {
        alp[i]=alp[i+26]='a'+i;
    }
    int klen=strlen(key+1);
    for(i=1;i<=klen;i++)
    {
        if(key[i]>='A'&&key[i]<='Z')
        {
            key[i]-='A';
        }
        else
        {
            key[i]-='a';
        }
    }
    int pwlen=strlen(pw+1);
    for(i=1;i<=pwlen;i++)
    {
        char c=pw[i];
        bool bl=false;
        if(c>='A'&&c<='Z')
        {
            bl=true;
            c=c-'A'+'a';
        }
        char res;
        if(i%klen==0)
        {
            res=alp[c-'a'+26-key[klen]];
        }
        else
        {
            res=alp[c-'a'+26-key[i%klen]];
        }
        if(bl)
        {
            res=res-'a'+'A';
        }
        printf("%c",res);
    }
    return 0;
} 

T2 国王游戏

NOIP原题,题面略。

神TM出原题,全员保底200了…
然而事情并没有这么简单。我把函数里的没赋大小的数组memset了,光荣爆零。不过就算没出这个锅我也就90,因为好像不足1要特判按1算。
不过好像机房里没人特判也过了…我当场就???
咳咳。这道题就是按左右手乘积大小排序就成了,实在不行打表找规律也是可以的。
AC代码:

#include<bits/stdc++.h>
using namespace std;
#define MAXN 10005
int ans[MAXN<<1];
int sol[MAXN<<1];
struct price
{
    int l;
    int r;
}sec[MAXN];
bool cmp(price a,price b)
{
    return (a.l*a.r)<(b.l*b.r);
}
void mul(int x)
{
    int i;
    if(x==0)
    {
        memset(ans,0,sizeof(ans));
        ans[0]=1;
        return;
    }
    for(i=1;i<=ans[0];i++)
    {
        ans[i]*=x;
    }
    for(i=1;i<=ans[0];i++)
    {
        ans[i+1]+=ans[i]/10;
        ans[i]%=10;
    }
    while(ans[i]>0)
    {
        ans[i+1]+=ans[i]/10;
        ans[i]%=10;
        ans[0]++;
        i++;
    }
}
int main()
{
    int n;
    int kl,kr;
    scanf("%d",&n);
    scanf("%d%d",&kl,&kr);
    int i,j,k=1;
    for(i=0;i<n;i++)
    {
        scanf("%d%d",&sec[i].l,&sec[i].r);
    }
    sort(sec,sec+n,cmp);
    int tot=0;
    while(kl!=0)
    {
        tot++;
        ans[k]=kl%10;
        k++;
        kl/=10;
    }
    ans[0]=tot;
    for(i=0;i<n-1;i++)
    {
        mul(sec[i].l);
    }
    k=0;
    for(i=ans[0];i>=1;i--)
    {
        k=k*10+ans[i];
        sol[i]=k/sec[n-1].r;
        k%=sec[n-1].r;
    }
    bool flag=0;
    for(i=ans[0];i>=1;i--)
    {
        if(i==1&&flag==0&&sol[i]==0)
        {
            printf("1");//坑人呢
        }
        if(sol[i]==0&&flag==0)
        {
            continue;
        }
        else
        {
            flag=1;
            printf("%d",sol[i]);
        }
    }
    return 0;
}

T3 开车旅行

小 A 和小 B 决定利用假期外出旅行,他们将想去的城市从 1 到 N 编号,且编号较小的 城市在编号较大的城市的西边,已知各个城市的海拔高度互不相同,记城市 i 的海拔高度为 Hi,城市 i 和城市 j 之间的距离 d[i,j]恰好是这两个城市海拔高度之差的绝对值,即
d[i, j] = |𝐻i − 𝐻j |。
旅行过程中,小 A 和小 B 轮流开车,第一天小 A 开车,之后每天轮换一次。他们计划
选择一个城市 S 作为起点,一直向东行驶,并且最多行驶 X 公里就结束旅行。小 A 和小 B 的驾驶风格不同,小 B 总是沿着前进方向选择一个最近的城市作为目的地,而小 A 总是沿 着前进方向选择第二近的城市作为目的地(注意:本题中如果当前城市到两个城市的距离 相同,则认为离海拔低的那个城市更近)。如果其中任何一人无法按照自己的原则选择目的 城市,或者到达目的地会使行驶的总距离超出 X 公里,他们就会结束旅行。
在启程之前,小 A 想知道两个问题:
1.对于一个给定的 X=X0,从哪一个城市出发,小 A 开车行驶的路程总数与小 B 行驶 的路程总数的比值最小(如果小 B 的行驶路程为 0,此时的比值可视为无穷大,且两个无穷
大视为相等)。如果从多个城市出发,小 A 开车行驶的路程总数与小 B 行驶的路程总数的比 值都最小,则输出海拔最高的那个城市。
2.对任意给定的 X=Xi 和出发城市 Si,小 A 开车行驶的路程总数以及小 B 行驶的路程 总数。
【输入】
输入文件为 drive.in。
第一行包含一个整数 N,表示城市的数目。
第二行有 N 个整数,每两个整数之间用一个空格隔开,依次表示城市 1 到城市 N 的海 拔高度,即 H1,H2,……,Hn,且每个 Hi 都是不同的。
第三行包含一个整数 X0。
第四行为一个整数 M,表示给定 M 组 Si 和 Xi。
接下来的 M 行,每行包含 2 个整数 Si 和 Xi,表示从城市 Si 出发,最多行驶 Xi 公里。
【输出】
输出文件为 drive.out。 输出共 M+1 行。
第一行包含一个整数 S0,表示对于给定的 X0,从编号为 S0 的城市出发,小 A 开车行驶 的路程总数与小 B 行驶的路程总数的比值最小。
接下来的 M 行,每行包含 2 个整数,之间用一个空格隔开,依次表示在给定的 Si 和
Xi 下小 A 行驶的里程总数和小 B 行驶的里程总数。
drive.in
10
4 5 6 1 2 3 7 8 9 10
7
10
1 7
2 7
3 7
4 7
5 7
6 7
7 7
8 7
9 7
10 7
drive.out
2
3 2
2 4
2 1
2 4
5 1
5 1
2 1
2 0
0 0
0 0

又!是!原!题!
然而我没做过。不过正解也挺好想的吧,dp套倍增就完事了。
然而正解好像蛮难调的样子,于是打暴力。
n²预处理最近和次近然后暴力模拟=70分,这可太好骗了。正解貌似可以nlogn预处理,但爷不会。不是很懂为什么机房里没人做
70分代码:

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define INF 0x3f3f3f3f
#define LL long long
int n;
int h[MAXN];
int nst[MAXN],nst2[MAXN];
void Init()
{
    int i,j;
    for(i=1;i<=n;i++)
    {
        int n1=INF,n2=INF;
        for(j=i+1;j<=n;j++)
        {
            int len=abs(h[j]-h[i]);
            if(len<n1||(len==n1&&h[j]<h[nst[i]]))
            {
                n2=n1;
                nst2[i]=nst[i];
                n1=len;
                nst[i]=j;
            }
            else if((len>=n1&&len<n2)||(len==n2&&h[j]<h[nst2[i]]))
            {
                n2=len;
                nst2[i]=j;
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    int i;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&h[i]);
    }
    Init();
    int x0;
    scanf("%d",&x0);
    double least=INF;
    int ans=0;
    for(i=1;i<=n;i++)
    {
        int city=i;
        LL drived=0;
        LL ad=0,bd=0;
        int turn=1;
        while(1)
        {
            if(turn%2)
            {
                if(nst2[city]==0||drived+abs(h[city]-h[nst2[city]])>x0)
                {
                    if(bd==0&&least==INF&&ans==0)
                    {
                        ans=i;
                    }
                    else if(ad*1.0/bd*1.0<least)
                    {
                        least=ad*1.0/bd*1.0;
                        ans=i;
                    }
                    break;
                }
                drived+=abs(h[city]-h[nst2[city]]);
                ad+=abs(h[city]-h[nst2[city]]);
                city=nst2[city];
                turn++;
            }
            else
            {
                if(nst[city]==0||drived+abs(h[city]-h[nst[city]])>x0)
                {
                    if(bd==0&&least==INF&&ans==0)
                    {
                        ans=i;
                    }
                    else if(ad*1.0/bd*1.0<least)
                    {
                        least=ad*1.0/bd*1.0;
                        ans=i;
                    }
                    break;
                }
                drived+=abs(h[city]-h[nst[city]]);
                bd+=abs(h[city]-h[nst[city]]);
                city=nst[city];
                turn++;
            }
        }
    }
    printf("%dn",ans);
    int m;
    scanf("%d",&m);
    while(m--)
    {
        int s,x;
        scanf("%d%d",&s,&x);
        int city=s;
        LL drived=0;
        LL ad=0,bd=0;
        int turn=1;
        while(1)
        {
            if(turn%2)
            {
                if(nst2[city]==0||drived+abs(h[city]-h[nst2[city]])>x)
                {
                    printf("%lld %lldn",ad,bd);
                    break;
                }
                drived+=abs(h[city]-h[nst2[city]]);
                ad+=abs(h[city]-h[nst2[city]]);
                city=nst2[city];
                turn++;
            }
            else
            {
                if(nst[city]==0||drived+abs(h[city]-h[nst[city]])>x)
                {
                    printf("%lld %lldn",ad,bd);
                    break;
                }
                drived+=abs(h[city]-h[nst[city]]);
                bd+=abs(h[city]-h[nst[city]]);
                city=nst[city];
                turn++;
            }
        }
    }
    return 0;
}

总共100+0+70=170,机房基本都是200分…
要是第二题不出锅就260称霸机房了,草啊

中午趴桌子午睡下午讲题,就没啥好说的了。

大佬AK了,蒟蒻出了锅,我则爆了零,我们都有光明的前途。

作者 JohnZ

发表评论