天天看點
傳回

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

繼續閱讀