天天看点
返回

czl蒻蒟的OI之路10、11、12好久没有发微博了，表示自己也很绝望啊，今天来个三连击。—>XJOI奋斗群（蒻蒟群）群赛11<— RANK排名11—>XJOI奋斗群（蒻蒟群）群赛12<— RANK排名11—>XJOI奋斗群（蒻蒟群）群赛13<— RANK排名13

  • 好久没有发微博了表示自己也很绝望啊今天来个三连击
  • XJOI奋斗群蒻蒟群群赛11 RANK排名11
      • T1The Wall WA一次后AC
          • 题意
          • 分析过程
          • 给出题解
      • T2Maximal Area Quadrilateral WA六次后AC
          • 题意
          • 分析过程
          • 给出题解
      • T3Tourist Problem WA两次后AC
          • 题意
          • 分析过程
          • 给出题解
      • T4Bubble Sort Graph 已AC
          • 题意
          • 分析过程
          • 给出题解
      • T5Fire in the City
          • 题意
          • 分析过程
          • 给出题解
  • XJOI奋斗群蒻蒟群群赛12 RANK排名11
      • T1Jzzhu and Children 已AC
          • 题意
          • 分析过程
          • 给出题解
      • T2Jzzhu and Sequences WA三次后AC
          • 题意
          • 分析过程
          • 给出题解
      • T3Jzzhu and ChocolateWA三次后AC
          • 题意
          • 分析过程
          • 给出题解
      • T4Jzzhu and CitiesWA三次后AC
          • 题意
          • 分析过程
          • 给出题解
      • T5Jzzhu and Apples 已AC
          • 题意
          • 分析过程
          • 给出题解
  • XJOI奋斗群蒻蒟群群赛13 RANK排名13
      • T1Dima and Guards 已AC
          • 题意
          • 分析过程
          • 给出题解
      • T2Dima and To-do List WA四次后AC
          • 题意
          • 分析过程
          • 给出题解
      • T3Dima and SaladWA一次后AC
          • 题意
          • 分析过程
          • 给出题解
      • T4Dima and Trap Graph WA一次后AC
          • 题意
          • 分析过程
          • 给出题解
      • T5Dima and Trap Graph已AC
          • 题意
          • 分析过程
          • 给出题解
      • 蒻蒟的总结

好久没有发微博了，表示自己也很绝望啊，今天来个三连击。

—>XJOI奋斗群（蒻蒟群）群赛11<— RANK排名11

T1：The Wall （WA一次后AC）

题意：

给出两个数a，b，是a的倍数的砖块会被涂成红色，是b的倍数的砖块会被涂成粉红色，求在n，m区间内有几块砖被同时涂成粉色和红色。

分析过程：

只需要求出a，b的最小公倍数，只要是最小公倍数的倍数的砖就是粉色和红色的。（表示竟然把求最小公倍数的函数写萎了）。

给出题解： 
#include<bits/stdc++.h>
using namespace std;
#define maxn 100050

int get_gcd(long long a,long long b)
{
    long long m=min(a,b);
    for(int i=m;i>=;i--)
    {
        if(a%i==&&b%i==)return i;
    }
}
int main()
{
    long long n;
    long long ans=,cnt=;
    int a[maxn];
    scanf("%lld",&n);
    for(int i=;i<=n;i++)
    {
        scanf("%d",&a[i]);
        ans+=a[i];
    }
    sort(a+,a++n);
    for(int i=;i<n;i++)
    {
        cnt+=(a[i+]-a[i])*i;
        ans+=cnt*;
    }
//  cout<<ans<<" "<<n<<endl;
    int gcd=get_gcd(ans,n);
    printf("%lld %lld\n",ans/gcd,n/gcd);
    return ;
}

T2：Maximal Area Quadrilateral （WA六次后AC）

题意：

给出一些点，让你求出由这些点组成的面积最大的四边形的面积。

分析过程：

可以便利先确定最左边和最右边的点，然后分别找出在这条线上面的点和下面的点，用海伦公式算出每个三角形的面积，最后在求出组合成的最大的四边形的面积。

给出题解： 
#include<bits/stdc++.h>
using namespace std;
#define maxn 100050

int get_gcd(long long a,long long b)
{
    long long m=min(a,b);
    for(int i=m;i>=;i--)
    {
        if(a%i==&&b%i==)return i;
    }
}
int main()
{
    long long n;
    long long ans=,cnt=;
    int a[maxn];
    scanf("%lld",&n);
    for(int i=;i<=n;i++)
    {
        scanf("%d",&a[i]);
        ans+=a[i];
    }
    sort(a+,a++n);
    for(int i=;i<n;i++)
    {
        cnt+=(a[i+]-a[i])*i;
        ans+=cnt*;
    }
//  cout<<ans<<" "<<n<<endl;
    int gcd=get_gcd(ans,n);
    printf("%lld %lld\n",ans/gcd,n/gcd);
    return ;
}

T3：Tourist Problem （WA两次后AC）

题意：

有n个点，你要去这些点旅行，但如果你没有以这个点为目的地，就算你经过这个点，也不算在这个点旅行了。每次旅行的距离为两个点之间距离之差的绝对值。要你求出每种旅行方案的距离的平均值，输出平均值的分母和分子。

分析过程：

计算|ai-aj|实际上就是计算序列{a1,a2,a3,a4}任意两条线段的长度之和。利用ai->aj覆盖了ai->a(j-1)，从左向右观察，则以a2结束的线段只有S1=a1->a2，以a3结束的线段有a1->a3,a2->a3，其中a1->a3可以看做a1->a2+a2->a3，这里a1->a2已经计算好了,所以S2=S1+2*(a2->a3)。同理，以a4结束的线段有a1->a4,a2->a4,a3->a4，不考虑a3->a4，其余的均是将以a3结束的线段延长a3->a4，所以S3=S2+3*(a3->a4)。

状态方程：Si=S(i-1)+i*|ai-a(i+1)|

给出题解： 
#include<bits/stdc++.h>
using namespace std;
#define maxn 100050

int get_gcd(long long a,long long b)
{
    long long m=min(a,b);
    for(int i=m;i>=;i--)
    {
        if(a%i==&&b%i==)return i;
    }
}
int main()
{
    long long n;
    long long ans=,cnt=;
    int a[maxn];
    scanf("%lld",&n);
    for(int i=;i<=n;i++)
    {
        scanf("%d",&a[i]);
        ans+=a[i];
    }
    sort(a+,a++n);
    for(int i=;i<n;i++)
    {
        cnt+=(a[i+]-a[i])*i;
        ans+=cnt*;
    }
//  cout<<ans<<" "<<n<<endl;
    int gcd=get_gcd(ans,n);
    printf("%lld %lld\n",ans/gcd,n/gcd);
    return ;
}

T4：Bubble Sort Graph （已AC）

题意：

刚开始没看题，看了之后，才发现，这竟然只是用优化算法求最长不下降子序列。

分析过程：

用二分优化一下，把复杂度降为O（nlog（n））就行了。

给出题解： 
#include<bits/stdc++.h>
using namespace std;
#define M 100005

int n,a[M+],l[M];

int sort()
{
    l[]=a[];
    int len=;
    for(int i=; i<n; i++)
    {
        if(l[len-]<a[i])
        {
            l[len++]=a[i];
        }
        else
        {
            *lower_bound(l,l+len,a[i])=a[i];
        }
    }
    return len;
}
int main()
{
    int len;
    scanf("%d",&n);
    for(int i=; i<n; i++)
    {
        scanf("%d",&a[i]);
    }
    len=sort();
    printf("%d",len);
    return ;
}

T5：Fire in the City

题意：
分析过程：
给出题解：

—>XJOI奋斗群（蒻蒟群）群赛12<— RANK排名11

T1：Jzzhu and Children （已AC）

题意：

有n个小孩，每个小孩需要xi个糖果，每次能够给队首的小孩m个糖果，如果这个小孩已经得到了他想要的糖果数，就离开，否则就排到队尾，要求求出最后一个离开的孩子的位置。

分析过程：

可以写一个队列去模拟孩子的离开或是排到队尾，每次查出队伍的元素个数，直到为1，就输出这个孩子的位置。

给出题解： 
#include<bits/stdc++.h>
using namespace std;

struct child
{
    int x;
    int candy;
}a[];
int main()
{
    queue<child>q;
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=;i<=n;i++)
    {
        scanf("%d",&a[i].candy);
        a[i].x=i;
        q.push(a[i]);
//      cout<<a[i].x<<" "<<a[i].candy<<endl;
    }
    while(q.size()>)
    {
        child a=q.front();
        q.pop();
//      cout<<a.x<<" "<<a.candy<<endl;
        if(a.candy>m)
        {
            a.candy-=m;
            q.push(a);
        }
    }
    child b=q.front();
    printf("%d\n",b.x);
}

T2：Jzzhu and Sequences （WA三次后AC）

题意：

一个变形的斐波那契，f（n）=f（n-1）+f（n+1），求数列的第n项。

分析过程：

把这个公式变形成为f（n）=f（n-1）+f（n-2），然后找规律求解，注意数据范围。

给出题解： 
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;

int main()
{
    long long f1,f2,f;
    scanf("%lld %lld",&f1,&f2);
    long long n;
    scanf("%lld",&n);
    if(n==)
    {
        f=(f1+*mod)%mod;
        printf("%lld",f);
    }
    else if(n==)
    {
        f=(f2+*mod)%mod;
        printf("%lld",f);
    }
    else if(n==)
    {
        f=(f2-f1+*mod)%mod;
        printf("%lld",f);
    }
    else
    {
        long long ans=(n-)%6;
        long long f3=f2-f1;

        if(ans==)
        {
            f=-f1;
            f=(f+*mod)%mod;
            printf("%lld",f);
        }
        if(ans==)
        {
            f=-f2;
            f=(f+*mod)%mod;
            printf("%lld",f);
        }
        if(ans==)
        {
            f=-f3;
            f=(f+*mod)%mod;
            printf("%lld",f);
        }
        if(ans==)
        {
            f=f1;
            f=(f+*mod)%mod;
            printf("%lld",f);
        }
        if(ans==)
        {
            f=f2;
            f=(f+*mod)%mod;
            printf("%lld",f);
        }
        if(ans==)
        {
            f=f3;
            f=(f+*mod)%mod;
            printf("%lld",f);
        }
    }
    return ;
}

T3：Jzzhu and Chocolate（WA三次后AC）

题意：

你有一块n*m的巧克力，你可以进行切割，但只能横着切或竖着切，要你求切出的最小面积的最大值。

分析过程：

由于要求切出最小面积最大，所以每次尽量都要平均分，而且要求尽量不能重复，这样就能够保证切的时候最小面积能够最大。

给出题解： 
#include<bits/stdc++.h>
using namespace std;

int main()
{
    long long n,m,k;
    scanf("%lld %lld %lld",&n,&m,&k);
    long long s;
    s=n*m;
    long long cnt;
    cnt=(n-)+(m-);
    if(cnt<k)printf("-1");
//  else if(cnt==k)printf("1");
    else 
    {
        long long a=k;
        long long s1,s2;
        if(k>=m-)
        {
            k-=m-;
            s1=n/(k+);
        }
        else if(k<m-)
        {
            s1=m/(k+)*n;
        }
        k=a;
        if(k>=n-)
        {
            k-=n-;
            s2=m/(k+);
        }
        else if(k<n-)
        {
            s2=n/(k+)*m;
        }
        long long ans=max(s1,s2);
        printf("%lld",ans);
    }
    return ;
}

T4：Jzzhu and Cities（WA三次后AC）

题意：

有n个城市，有一些公路连接其中的两个城市，还有一些铁路连接城市1和其他城市。现在要去除几条铁路，要求去除后城市1到其他城市的最小距离不改变，求做多能去除的铁路的数量。

分析过程：

简单来说，就是求单源最短路，但还需要优化一下，如果更新最短路的是铁路，就做一个标记，最后用cnt记下标记的数量，最后用n-cnt便是答案。

给出题解： 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> p;
#define maxn 200050

struct edge
{
    ll to;
    ll cost;
    bool r;
    edge(bool r,ll to=,ll cost=):r(r),to(to),cost(cost) {}
};

int n,m,k;
vector<edge> g[maxn];
ll d[maxn];
bool d1[maxn],vis[maxn];

void danyuan()
{
    priority_queue<p,vector<p>,greater<p> >q;
    memset(d,,sizeof(d));
    d[]=;
    q.push(p(,));

    while(!q.empty())
    {
        ll v=q.top().second;
        q.pop();
        if(vis[v])continue;
        vis[v]=true;
        for(int i=; i<g[v].size(); i++)
        {
            edge e=g[v][i];
            if(d[e.to]>d[v]+e.cost)
            {
                d[e.to]=d[v]+e.cost;
                if(e.r==true)d1[e.to]=true;
                else if(e.r==false)d1[e.to]=false;
                q.push(p(d[e.to],e.to));
            }
            else if(d[e.to]==d[v]+e.cost&&d1[e.to]==true)
            {
                d[e.to]=d[v]+e.cost;
                if(e.r==false)d1[e.to]=false;
                q.push(p(d[e.to],e.to));
            }
        }
    }
}

int main()
{
    memset(d1,true,sizeof(d1));
    scanf("%d %d %d",&n,&m,&k);
    for(int i=; i<=m; i++)
    {
        ll s,t,v;
        scanf("%lld %lld %lld",&s,&t,&v);
        g[s].push_back(edge(false,t,v));
        g[t].push_back(edge(false,s,v));
    }
    for(int i=;i<=k;i++)
    {
        ll s,y;
        scanf("%lld %lld",&s,&y);
        g[].push_back(edge(true,s,y));
        g[s].push_back(edge(true,,y));
    }
    danyuan();
    int cnt=;
    for(int i=;i<=n;i++)
    {
        if(d1[i]==true)cnt++;
    }
    printf("%d",k-cnt);
}

T5：Jzzhu and Apples （已AC）

题意：

有n个编号为1-n的苹果，要求你将这些苹果两两分组，要求一组中的两个苹果不互质，输出能够组成的最多的组数和每组的苹果编号。

分析过程：

首先用埃氏筛法筛去质数，在把剩余的合数用i从n/2向一开始遍历，把i的倍数都存到数组中，如果数组中的元素为奇数，就把i*2和最后一个元素交换，然后两两配对，因为i*2在后面更容易配对，所以不用去管它，最后用pair数组储存并输出就行。

给出题解： 
#include<bits/stdc++.h>
using namespace std;
#define maxn 100050
pair<int,int >p[maxn];

int main()
{
    int n;
    int cnt=;
    scanf("%d",&n);
    int a[maxn]={},b[maxn]={};
    bool vis[maxn];
    b[]=;
    memset(vis,true,sizeof(vis));
    for(int i=;i<=n;i++)
    {
        if(b[i]==)continue;
        else
        {
            for(int j=*i;j<=n;j+=i)
            {
                b[j]=;
            }
        }
    }
    for(int i=n/;i>=;i--)
    {
        int tem=;
        if(b[i]==)continue;
        else 
        {
            for(int j=i;j<=n;j+=i)
            {
                if(vis[j]==true)a[++tem]=j;
            }
            if(tem%==)swap(a[],a[tem]);
            for(int j=;j<tem;j+=)
            {
                p[++cnt]=make_pair(a[j],a[j+]);
                vis[a[j]]=false;
                vis[a[j+]]=false;
            }
        }
    }
    printf("%d\n",cnt);
    for(int i=;i<=cnt;i++)
    {
        printf("%d %d\n",p[i].first,p[i].second);
    }
    return ;
}

—>XJOI奋斗群（蒻蒟群）群赛13<— RANK排名13

T1：Dima and Guards （已AC）

题意：

有四组守卫者，每组守卫者都有两个守卫，你可以用巧克力或果汁去贿赂他们，要求你刚好用完k元，贿赂其中的一组守卫，不行就输出-1。

分析过程：

先可以判断用k元能不能贿赂这组的守卫，然后在列举出贿赂这组守卫的花费，并不断更新，最后输出这个数据。

给出题解： 
#include<bits/stdc++.h>
using namespace std;
int a[][];
int main()
{
    int n;
    cin>>n;
    for (int i=; i<=; i++)
        for (int j=; j<=; j++) cin>>a[i][j];
    for (int i=; i<=; i++)
    {
        if (min(a[i][],a[i][])+min(a[i][],a[i][])<=n)
        {
            int ans1=min(a[i][],a[i][]);
            int ans2=n-min(a[i][],a[i][]);
            cout<<i<<" "<<ans1<<" "<<ans2;
            return ;
        }
    }
    cout<<"-1";
}

T2：Dima and To-do List （WA四次后AC）

题意：

简单来说，就是有n个任务，每个任务被提醒时，会有一定的消耗，当选择一个任务后，后面k-1个值都不用提醒。要求你输出消耗的最小值的下标。

分析过程：

由于数据比较小，所以我们可以遍历从第1个到第k个，分别以他们作为起点，计算一直到把任务做完时的消耗，并不断的更新最小值，最后输出最小值得下标。

给出题解： 
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n,k;
    long long res=;
    int pos,minpos;
    int a[];
    scanf("%d %d",&n,&k);
    for(int i=; i<=n; i++)
    {
        scanf("%lld",&a[i]);
    }
    int cnt=n/k;
//  cout<<cnt<<endl;
    for(int i=; i<=k; i++)
    {
        int pos=i;
        int ans=;
        for(int j=; j<=cnt; j++)
        {
            if(pos>n)pos-=n;
            ans+=a[pos];
            pos=pos+k;
        }
//      cout<<ans<<endl;
        if(ans<res)
        {
            res=ans;
            minpos=i;
        }
    }
    printf("%d",minpos);
}

T3：Dima and Salad（WA一次后AC）

题意：

有n个水果，每个水果都有各自的美味值ai和热量bi，要求你在取一定数量的水果后，美味值总和除以热量总和刚好等于k，求出这些水果的美味值总和单位最大值。

分析过程：

可以先用ai-bi*k计算出每个水果的价值（公式可推），然后由于这个值可能为负数，所以就把这个负值的极限改为0，其余的值都分别增加相同的档次，之后就是简单的01背包了。

给出题解： 
#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[],b[],c[];
int dp[][];
int main()
{
    scanf("%d %d",&n,&k);
    for(int i=; i<=n; i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=; i<=n; i++)
    {
        scanf("%d",&b[i]);
        c[i]=a[i]-b[i]*k;
    }
    const int x=n*;
    memset(dp,,sizeof(dp));
    dp[][x]=;
    for(int i=;i<=n;i++)
    {
        for(int j=*x;j>=;j--)
        {
            dp[i][j]=max(dp[i-][j],dp[i-][j-c[i]]+a[i]);
        }
    }
    if(dp[n][x]==)printf("-1");
    else printf("%d",dp[n][x]);
}

T4：Dima and Trap Graph （WA一次后AC）

题意：

给出你一个图（有重边和环），分别给出每条边的起点和终点，并且这条边只能通过li~ri的数据，问你能否从第1个点走到第n个点，并且到第n个点的时候数据不为0，如果可以就输出最大能够带到n的数据数。

分析过程：

由于迪杰斯塔拉算法和弗洛伊德算法都因为重边，环而无法处理，所以我们可以用并查集进行保存，并且先前把边进行排序，然后不断地添加进去这条边，当1和n连接了的时候，就break出来，此时输出的值便是能够到达n是带有数据的最大值，否则就输出Nice work, Dima!

给出题解： 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=;
const int inf=;
int p[MAXN];
int n,m,ans;
struct edge
{
    int from;
    int to;
    int l;
    int r;
} e[MAXN];
bool cmp(edge a,edge b)
{
    if(a.r==b.r) return a.l<b.l;
    return a.r>b.r;
}
int find(int n)
{
    if(p[n]==n) return n;
    else return p[n]=find(p[n]);
}
int main()
{

    scanf("%d %d",&n,&m);
    for(int i=; i<m; i++)
    {
        scanf("%d %d %d %d",&e[i].from,&e[i].to,&e[i].l,&e[i].r);
    }
    sort(e,e+m,cmp);
    for(int i=; i<m; i++)
    {
        for(int j=; j<=n; j++)
        {
            p[j]=j;
        }
        for(int j=; j<m; j++)
        {
            if(e[j].l>e[i].l) continue;
            if(e[j].r<e[i].l) continue;
            p[find(e[j].from)]=find(e[j].to);
            if(find()==find(n))
            {
                ans=max(ans,e[j].r-e[i].l+);
                break;
            }
        }
    }
    if(ans!=)
    {
        printf("%d",ans);
    }
    else
    {
        printf("Nice work, Dima!");
    }
    return ;
}

T5：Dima and Trap Graph（已AC）

题意：

简单来说，就是给出一个数据在1-9之间二维矩阵，然后再给你一个数列，要你求出每两个数据之间的最大的曼哈顿距离，并把它输出。

分析过程：

可以用a[10][5]来分别记录（i-j），（i+j），（-i-j），（-i+j）的值，并在之后不断进行更新，然后用这些值组合计算两个数据之间的曼哈顿距离，最后输出这个距离的最大值。

给出题解： 
#include<bits/stdc++.h>
using namespace std;
#define M 100005

int n,a[M+],l[M];

int sort()
{
    l[]=a[];
    int len=;
    for(int i=; i<n; i++)
    {
        if(l[len-]<a[i])
        {
            l[len++]=a[i];
        }
        else
        {
            *lower_bound(l,l+len,a[i])=a[i];
        }
    }
    return len;
}
int main()
{
    int len;
    scanf("%d",&n);
    for(int i=; i<n; i++)
    {
        scanf("%d",&a[i]);
    }
    len=sort();
    printf("%d",len);
    return ;
}

蒻蒟的总结：

再一次补发昨天的微博，真的是好难啊，果然啊，几个月达到别人几年的效果，真的是很艰难的一段路啊。不过还是能够坚持下去的，明天就是短暂的周末了，也要好好利用起来，今天晚上继续理解KMP，DP，树和队列，明天凌晨在去做一场比赛，先把CF上的分刷出来再说，最后再把这几天没补的题目补好。好好利用每个周末，这些都是宝贵的时间，顺便休整一下。

继续贴出吴老师的话：学信息的人永不服输！！！

蒟蒻OI之路
上一篇: #游戏#《橄榄石》：《宝可梦GO》玩法的电子宠物手游是怎样的体验？从实际的体验来看，《Peridot》融入了《宝可梦GO
下一篇: czl蒻蒟的OI之路16—&gt;XJOI奋斗群（蒻蒟群）群赛17&lt;— RANK排名9

继续阅读