ZJ第六套总结

Author Avatar
Llf0703 10月 24, 2018
  • 在其它设备中阅读本文章

其实徐妈口中的所谓的ZJ十套就是《全国青少年信息学竞赛培训教材复赛》中的十套膜你题。今天先应徐妈之要求把今天的总结了，以后再补之前的。

分组(group)

洛谷题目：P1109 学生分组

大水题，直接放代码。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n,l,r,a,sum,ans1,ans2,ans,s[55];

int main()
{
    freopen("group.in","r",stdin);
    freopen("group.out","w",stdout);
    n=read();
    for (int i=1;i<=n;i++) s[i]=read();
    l=read(); r=read();
    for (int i=1;i<=n;i++)
    {
        sum+=s[i];
        if (s[i]>=l && s[i]<=r) continue;
        if (s[i]>r) ans1+=s[i]-r;
        if (s[i]<l) ans2+=l-s[i];
    }
    ans=max(ans1,ans2);
    if (sum>n*r || sum<n*l) printf("-1");
    else printf("%d",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

阶乘(num)

洛谷上并没有这道题。

找下规律，发现末尾都是偶数，而且如果没有5的话直接按照个位来乘就行了。但是遇到5、15之类的就非常恶心了，所以对于这些肯定要分类讨论。

可以知道，最后的0的来源肯定是2和5，显然，5的个数小于2的个数，所以我们考虑5。

首先假设没有5存在。即便这样 $ O(n) $ 的时间复杂度还是不现实的。由于只和最后一位有关，所以我们可以将其10个分为一组运算，这样最多算2009次就行了。

最后总的阶乘和 $ \div 10^{x} $ 就是答案，我们不考虑5的话只需要最后 $ \div 2^{x} $ 就行了（x是5的个数也是0的个数）。所以最后有多少个5我们 $ \div 2 $ 多少个2就行了。可以发现 $ \div 2 $ 后的对应关系

  • 2—>6
  • 4—>2
  • 6—>8
  • 8—>4

所以不断除5，并且把答案不断除2也就是变成对应关系就行了，其他的就按10分组直接算。显然要用高精。

然后我在考场上很开心的写完了TLE代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct bigint{
    int s[5005],len;
    bigint(){memset(s,0,sizeof(s));len=0;}
} n;
int t,a,b,c,ans;

inline bigint division(bigint x,int y)
{
    bigint z;
    int sum=0,len=x.len;
    for (int i=len;i;i--)
    {
        sum=sum*10+x.s[i];
        z.s[i]=sum/y;
        sum%=y;
    }
    while (!z.s[len]) len--;
    z.len=len;
    return z;
}

inline void clear(bigint &x)
{
    for (int i=1;i<=x.len;i++)
        x.s[i]=0;
    x.len=0;
}

int main()
{
    freopen("num.in","r",stdin);
    freopen("num.out","w",stdout);
    t=read();
    while (t--)
    {
        clear(n); ans=1;
        char ch[2018];
        scanf("%s",ch);
        for (int i=strlen(ch)-1;i>=0;i--) n.s[++n.len]=ch[i]-'0';
        if (n.len==1 && n.s[1]==1)
        {
            printf("1\n");
            continue;
        }
        while (n.len>=1)
        {
            for (int i=1;i<=n.s[1];i++)
            {
                if (i==5) continue;
                ans=(ans*i)%10;
            }
            n=division(n,5);
            int sum=n.s[1]+n.s[2]*10;
            if (sum%4==0) ans=(ans*6)%10;
            else if (sum%4==1) ans=(ans*8)%10;
            else if (sum%4==2) ans=(ans*4)%10;
            else if (sum%4==3) ans=(ans*2)%10;
        }
        printf("%d\n",ans);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

然后很开心的得了50.

考后看书才发现那个每一位上都循环乘一遍太浪费时间了，树上直接预处理了一个数组：

int val[10]={1,1,2,6,4,4,4,8,4,6};

时间复杂度变成了原来的 $ \dfrac {1}{10} $ ，但还是50分。我想是不是高精度初始化和clear太浪费了，就把它删了，毕竟都是重新赋值。然后就有70分了。最后把函数直接写在了main函数里就A了。这TM卡常是有多严重啊

附上AC代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct bigint{
    int s[3005],len;
} n;
int t,a,b,c,ans,val[10]={1,1,2,6,4,4,4,8,4,6};

int main()
{
    freopen("num.in","r",stdin);
    freopen("num.out","w",stdout);
    t=read();
    while (t--)
    {
        n.len=0;
        ans=1;
        char ch[2018];
        scanf("%s",ch);
        for (int i=strlen(ch)-1;i>=0;i--) n.s[++n.len]=ch[i]-'0';
        if (n.len==1 && n.s[1]==1)
        {
            printf("1\n");
            continue;
        }
        while (n.len>=1)
        {
            ans=(ans*val[n.s[1]])%10;
            int sum=0,len=n.len;
            for (int i=len;i;i--)
            {
                sum=sum*10+n.s[i];
                n.s[i]=sum/5;
                sum%=5;
            }
            while (!n.s[len]) len--;
            n.len=len;
            sum=n.s[1]+n.s[2]*10;
            if (sum%4==0) ans=(ans*6)%10;
            else if (sum%4==1) ans=(ans*8)%10;
            else if (sum%4==2) ans=(ans*4)%10;
            else if (sum%4==3) ans=(ans*2)%10;
        }
        printf("%d\n",ans);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

拐弯(ddos)

洛谷题目：P1649 [USACO07OCT]障碍路线Obstacle Course

真·玄学题目

我在11:23的时候花5分钟写了个DFS，然后忘了回溯爆0了。。。加了一句话多了60分。代码长这样：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n,mp[105][105],st[2],ed[2],fx[4]={1,0,-1,0},fy[4]={0,1,0,-1},ans;
bool vis[105][105];

void dfs(int x,int y,int last,int now)
{
    if (x==ed[0] && y==ed[1])
    {
        vis[x][y]=1;
        ans=min(ans,now);
        return;
    }
    if (vis[x][y]) return;
    vis[x][y]=1;
    for (int i=0;i<4;i++)
    {
        int tx=x+fx[i],ty=y+fy[i];
        if (tx<1 || tx>n || ty<1 || ty>n || mp[tx][ty]==0) continue;
        int sum;
        if (i==last || last==-1) sum=0;
        else sum=1;
        dfs(tx,ty,i,now+sum);
    }
    vis[x][y]=0;
}

int main()
{
    n=read();
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            char ch;
            cin>>ch;
            if (ch=='.') mp[i][j]=1;
            else if (ch=='x') mp[i][j]=0;
            else if (ch=='A') st[0]=i,st[1]=j,mp[i][j]=1;
            else ed[0]=i,ed[1]=j,mp[i][j]=1;
        }
    }
    ans=1e9;
    dfs(st[0],st[1],-1,0);
    if (!vis[ed[0]][ed[1]]) printf("-1");
    else printf("%d",ans);
    return 0;
}

这真的是我5分钟打出来的！除了头文件和快读是粘贴的。看来我搜索没有那么蒻了。

然后改成BFS就能过。。。只需要注意为了保证拐弯次数递增，每次需要把当前方向走到底再换方向走

AC代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define pr pair<int,int>
#define mpr make_pair

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n,mp[105][105],st[2],ed[2],fx[4]={1,0,-1,0},fy[4]={0,1,0,-1},ans[105][105];

inline void bfs()
{
    queue <pr> q;
    q.push(mpr(st[0],st[1]));
    ans[st[0]][st[1]]=0;
    while (!q.empty())
    {
        int x=q.front().first,y=q.front().second; q.pop();
        if (x==ed[0] && y==ed[1]) break;
        for (int i=0;i<4;i++)
        {
            int tx=x,ty=y;
            for (;;)
            {
                tx+=fx[i]; ty+=fy[i];
                if (tx<1 || tx>n || ty<1 || ty>n || !mp[tx][ty]) break;
                if (ans[x][y]+1<ans[tx][ty])
                {
                    ans[tx][ty]=ans[x][y]+1;
                    q.push(mpr(tx,ty));
                }
            }
        }
    }
    if (ans[ed[0]][ed[1]]==1e9) printf("-1");
    else printf("%d",ans[ed[0]][ed[1]]-1);
    return;
}

int main()
{
    n=read();
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            ans[i][j]=1e9;
            char ch;
            cin>>ch;
            if (ch=='.') mp[i][j]=1;
            else if (ch=='x') mp[i][j]=0;
            else if (ch=='A') st[0]=i,st[1]=j,mp[i][j]=1;
            else ed[0]=i,ed[1]=j,mp[i][j]=1;
        }
    }
    bfs();
    return 0;
}

赛马(horse)

洛谷题目：P1650 田忌赛马

贪心。

以下内容转载自：https://www.luogu.org/blog/user55918/solution-p1650

  1. 开始也是先排序，可以使用sort快排
  2. 然后将田忌最大的马与国王进行比较
  3. 如果田忌最大的马大于国王，那么就胜场++
  4. 如果田忌最大的马小于国王，那么就一定会输，所以用田忌最小的马输给国王最大的马
  5. 如果田忌最大的马等于国王，那么就比较最小的马
    1. 如果田忌最小的马大于国王，那么胜场++
    2. 如果田忌最小的马小于国王，那么就输给国王
    3. 如果田忌最小的马等于国王，就用田忌最小的马对国王最大的马，如果国王最大的马大，那么财产要减200
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n,x[2005],y[2005],ans;

inline bool cmp(int x,int y)
{
    return x>y;
}

int main()
{
    n=read();
    for (int i=1;i<=n;i++) x[i]=read();
    for (int i=1;i<=n;i++) y[i]=read();
    sort(x+1,x+n+1,cmp);
    sort(y+1,y+n+1,cmp);
    int i=1,j=n,k=1,l=n;
    while (i<=j)
    {
        if (x[i]>y[k])
        {
            ans+=200;
            i++; k++;
        }
        else if (x[i]<y[k])
        {
            ans-=200;
            j--; k++;
        }
        else if (x[j]>y[l])
        {
            ans+=200;
            j--; l--;
        }
        else
        {
            if (x[j]<y[k]) ans-=200;
            j--; k++;
        }
    }
    printf("%d",ans);
    return 0;
}

总结

我今天的第一次提交分数是100+50+10+10=170，其中低级失误占的分数有50分，也就是那个忘了回溯。当然，这也反映出来我时间安排不当的问题。耗费大量时间在第二题，甚至连比较简单的贪心的第四题都没怎么写，而且第二题因为复杂度差了一点也只有50分。

总的来说现在低级失误还是越来越少了，但还是没有消失，所以还要多刷题啊！

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
This work is licensed under a CC BY-NC-SA 4.0 International License.
本文链接：https://llf0703.com/p/contest-summary-zj6.html