ZAFU_2021_1_28_2021寒假個人賽第三場題解

A題
原題鏈接:https://codeforces.com/problemset/problem/1409/A
相關tag:貪心，簡單結論

算出x和y的差值，
我們必然是盡可能用最大的步子10去縮短這個差值，
最后一步可能少于10，

直接算(x+y)/10+(x+y)%10!=0即可，等價于(x+y+9)/10

#include<bits/stdc++.h>
#define ll long long
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

int32_t main()
{
    IOS;
    int t;
    cin>>t;
    while(t--)
    {
        ll a,b;
        cin>>a>>b;
        a=abs(a-b);
        cout<<(a+9)/10<<endl;
    }
}

B題
原題鏈接:https://codeforces.ml/problemset/problem/1201/A
相關tag:貪心

記錄下每道題選每個選項的有幾個人，每道題都把選的人最多的選項當做答案去算即可，

#include<bits/stdc++.h>
#define ll long long
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

int n,m;
int num[1007][5];//num[i][j]代表第i題選'A'+j的有幾個人

int32_t main()
{
    IOS;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        string s;cin>>s;
        for(int j=0;j<m;j++)
            num[j][s[j]-'A']++;
    }
    int ans=0;
    for(int i=0;i<m;i++)
    {
        int x;cin>>x;
        int y=0;
        for(int j=0;j<5;j++) y=max(y,num[i][j]);
        ans+=x*y;
    }
    cout<<ans<<endl;
}

C題
原題鏈接:https://codeforces.com/problemset/problem/1175/A
相關tag:貪心

注意到除k必然是比-1更優的，因此能整除k的時候優先使用除k，不能的時候把余數全部減掉即可，

#include<bits/stdc++.h>
#define ll long long
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;


int32_t main()
{
    IOS;
    int t;cin>>t;
    while(t--)
    {
        ll n,k;cin>>n>>k;
        ll ans=0;
        while(n)
        {
            if(n%k)
            {
                ans+=n%k;
                n-=n%k;
            }
            else {n/=k;ans++;}
        }
        cout<<ans<<endl;
    }
}

D題
原題鏈接:https://codeforces.com/problemset/problem/977/D
相關tag:dfs，排序

給出dfs和結論后排序兩種做法，

注意到最多只有100個數字，并且每個數字可能的變換方法只有兩種，
我們可以把每個數字看成一個點，每種變換方式都是一條單向邊，那么每個點最多只有兩條出邊，也就是整個圖最多只有200條有向邊(當然這種情況是不存在的)，
我們可以暴力列舉起點是哪一個進行dfs搜索，單次搜索這張無環有向圖的復雜度等于有向邊的數量，
總復雜度最大為O(2 × \times ×n × \times ×n)

由于點的數量n非常小，我們可以通過一次n × \times ×n的回圈暴力比對每兩個數字是否可以由這兩種操作得到這張無環有向圖的所有邊，

#include<bits/stdc++.h>
#define ll long long
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

vector<int>field[107];//保存圖的邊資訊i點與field[i]中的元素存在有向邊
ll num[107];
int n;
bool visit[107];//記錄各個點被訪問的情況
vector<int>road;//保存路徑，用陣列實作而不是使用vector的push和pop操作會更快,這里出于方便理解的考慮寫成vector形式

void dfs(int now)
{
    visit[now]=1;//當前位置置為訪問過
    road.push_back(now);//壓入路徑中

    if(road.size()==n)
    {
        for(int i=0;i<n;i++) cout<<num[road[i]]<<' ';
        exit(0);//找到滿足的路徑后直接結束程式
    }

    for(int i=0;i<field[now].size();i++)//遍歷當前結點出發可以走到的其他點
        if(!visit[field[now][i]]) dfs(field[now][i]);//如果下個位置未被訪問過，即未被走過的路徑，繼續遞回搜索

    road.pop_back();//還原
    visit[now]=0;//還原
}

int main()
{
    IOS;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>num[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(num[j]*3==num[i]||num[i]*2==num[j])//暴力for一遍建圖
                field[i].push_back(j);
    for(int i=1;i<=n;i++) dfs(i);//以這n個數字分別作為第一個數字進行搜索
}

我們進行的操作只有 × \times × 2或者 ÷ \div ÷ 3
那么隨著我們操作的進行，當前數字分解質因數后，2出現的次數是不斷在上升的，而3出現的次數是不斷在下降的，
依靠這一點直接sort一遍即可，第一排序關鍵字為分解質因數后3出現的個數，3個數相同的情況下直接比較數值大小即可，大的數值在后面，

#include<bits/stdc++.h>
#define ll long long
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

struct Node
{
    ll num;//保存數值
    int base;//num分解質因數后3出現了幾次
};

Node node[107];
int n;

bool cmp(Node a,Node b)
{
    if(a.base==b.base) return a.num<b.num;
    else return a.base>b.base;//排序的第一關鍵字為3出現的次數
}

int32_t main()
{
    IOS;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>node[i].num;
        ll temp=node[i].num;
        node[i].base=0;
        while(temp%3==0)
        {
            temp/=3;
            node[i].base++;
        }
    }
    sort(node,node+n,cmp);
    for(int i=0;i<n;i++) cout<<node[i].num<<' ';
}

E題
原題鏈接:https://atcoder.jp/contests/arc111/tasks/arc111_a
相關tag:數學，快速冪

注意到10ⁿ可以分解成k × \times ×m²+d，（k和d均為整數）
其中k × \times ×m²在經歷/m%m的程序后必定為0，去除這部分對結果沒有影響，
故我們直接用快速冪計算10ⁿ對m²取模的結果d，用d/m%m即為結果，

#include<iostream>
#include<algorithm>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

ll qpow(ll x,ll p,ll mod)//快速冪計算10^n%(m*m)的結果
{
    ll ret=1;
    while(p)
    {
        if(p&1) ret=ret*x%mod;
        x=x*x%mod;
        p>>=1;
    }
    return ret;
}

int main()
{
    IOS
    ll n,m;cin>>n>>m;
    n=qpow(10,n,m*m);
    cout<<n/m%m<<endl;
}

F題
原題鏈接:https://codeforces.com/problemset/problem/976/C
相關tag:排序，貪心

區間[l1,r1]完全包含區間[l2,r2]的充要條件是l1<=l2且r1>=r2，

對每個區間[l2,r2]來說，我們實際上只需要先找左邊界l1<l2的所有區間與之對比，
或者l1=l2時，對比所有右區間r1>=r2的區間，

我們可以對所有區間進行一個排序，先按照左區間邊界從小到大的順序進行排序，
這樣的話我們就保證了，對于第i個區間來說，左區間邊界小于第i個區間的所有區間都在它的左側，
當左區間邊界相同時，按照右區間邊界從大到小排序，
這樣我們就保證了，左區間邊界相等的所有區間，右區間邊界大的在左側，

之后直接從左到右for一遍，記錄之前出現的最大右邊界，與當前的右邊界比較即可，

#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int maxn=3e5+7;

struct Node//區間結構體，tar標記這是第幾個區間，用于輸出
{
    int l,r;
    int tar;
};

bool cmp(Node a,Node b)//sort的比較函式，左邊界越靠左的排序后越在前，左邊界相同情況下，右邊界越靠右排序后越在前
{
    if(a.l==b.l) return a.r>b.r;
    else return a.l<b.l;
}

Node node[maxn];
int n;

int main()
{
    IOS
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>node[i].l>>node[i].r;
        node[i].tar=i+1;
    }
    sort(node,node+n,cmp);
    int pre=-1,r=0;//pre記錄前面右邊界最大的區間是第幾個，r標記當前出現的最大右邊界
    bool flag=0;
    for(int i=0;i<n;i++)
    {
        if(node[i].r<=r)
        {
            cout<<node[i].tar<<' '<<pre<<endl;
            flag=1;
            break;
        }
        else {pre=node[i].tar;r=node[i].r;}//更新右邊界最大的區間以及最大右邊界的值
    }
    if(!flag) cout<<-1<<' '<<-1<<endl;
}

G題
原題鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=1059
相關tag:dp，進制優化

我們把所有任務總共需要的天數記為sum，
這個題目一看是一個比較明顯的多重背包問題，我們可以dp去求sum/2總天數的方案是否存在，
但是問題在于這里的背包個數x最多為2e4，而sum最多也有6e4，
而多重背包的復雜度為O(x × \times ×sum/2)，打到12e8，并且還有多組資料，因此直接多重背包dp是會tle的，

這里我們可以利用二進制分解任務的件數，將復雜度降低為O(logx × \times ×sum/2)，
例如需要2天的任務有x2件，由于這些任務都是需要2天，可以被視作完全相同的任務，我們需要關注的只是這x2件任務需要選擇幾件，
而我們把這個x2件寫成二進制，按照二進制的每一位單獨拿出來，實際上就是x2的二進制各位取1還是取0，也就是取還是不取，
我們將x2的各個二進制位獨立出來，視作統一的一件任務，自此轉化為一個01背包問題，
而這個01背包擁有的背包數量len滿足2^len=x，故len=logx，

#include<stdio.h>
#include<string.h>
int sum,a[7],b[107],len;//sum為所有任務的天數綜合，a[i]代表需要i天的任務有幾件
bool dp[60001];
//b[]保存二進制優化的01背包
//dp[i]代表花費i天的分配方案是否存在

void get()
{
    sum=0;
    for(int i=1;i<=6;i++)
    {
        scanf("%d",&a[i]);
        sum=sum+i*a[i];
    }
}

void change()//二進制優化
{
    len=0;
    for(int i=1;i<=6;i++)//i代表當前優化的是需要i天的任務
    {
        int x=1;//對任務數量進行二進制分解,x從2進制最低位的1開始
        while(x<=a[i])
        {
            b[++len]=i*x;//x件任務合并為一個統一的任務
            a[i]-=x;
            x*=2;//二進制更高一位
        }
        if(a[i]) b[++len]=i*a[i];//剩余的部分合并為一個統一的任務
    }
}

int main()
{
    int flag,t=0;
    dp[0]=1;
    while(get(),sum)//逗號運算式，回傳值為sum，當sum=0時推出回圈；get函式負責讀入
    {
        t++;//t記錄當前是第幾組資料
        flag=1;//標記是否存在平均分配的方案
        if(sum%2) flag=0;
        else
        {
            sum/=2;
            change();//將多重背包利用二進制優化為01背包
            for(int i=1;i<=len;i++)
                for(int j=sum;j>=b[i];j--)
                    if(dp[j-b[i]]) dp[j]=1;//01背包dp程序
            if(dp[sum]==0) flag=0;
            for(int i=1;i<=sum;i++) dp[i]=0;
        }
        printf("Collection #%d:\n",t);
        if(flag) printf("Can be divided.\n\n");
        else printf("Can't be divided.\n\n");
    }
}

H題
原題鏈接:
相關tag:樹的直徑，dfs

思路見注釋

#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int maxn=2e5+10;

//題意為給你一個有n個節點n-1條邊的樹(沒有倍訓的圖）
//要求你在這棵樹里找到三個節點，使得它們之間的三條路徑走過的邊數最多（多次經過同一條邊只算一次）
//首先要知道樹的直徑這個概念.樹的直徑是整棵樹中兩點距離最長的那一條路徑

//先用反證的方法證明三條路徑必定至少有一潭訓是樹的直徑
//如果三條路徑中沒有任何一條是樹的直徑
//我們可以將其中的兩個點更換為樹的直徑兩端的端點，會發現長度變得更大了
//因此三條路徑中沒有任何一條是直徑的情況必然不是總長度最長的

//因而首先我們可以確定這三條路徑中必定至少存在一條直徑，這樣就確定了兩個點，再就是第三個點如何確定
//第三個點和第一還有第二個點的路徑合起來的新路徑，必定包含了這條直徑
//那么在原來已經找到的這條直徑基礎上加上這個第三個點，規定第三和第一個點的距離為d1，第三和第二個點的距離為d2，樹的直徑為x
//那么加入第三個點后增加的邊數就應該是(d1+d2-x)/2，而x是我們計算出的一個定值
//所以實際上第三個點需要滿足的條件是和第一個點還有第二個點的距離和最大

//到此思路已經全部完成，首先是求取樹的直徑的兩個端點，這個方法和證明程序自己見演算法書或者博客
//dfs第一次從1點開始，dst[i][0]記錄i點到1點的距離，距離最大的點為直徑的第一個端點a
//dfs第二次從a點開始，dst[i][1]記錄i點到a點的距離，距離最大的點為直徑的第二個端點b
//dfs第三次從b點開始，dst[i][2]記錄i點到b點的距離，由此我們便計算出了整棵樹各個點到點a還有點b的距離，由此去尋找c點

vector<int>road[maxn];//記錄路徑
int dis[maxn][3];

void dfs(int now,int before,int sum,int cas)//now為當前所在節點位置，before為上一個節點位置，sum為當前到起點的距離，cas為dst第二個下標
{
    for(int i=0;i<road[now].size();i++)
    {
        if(road[now][i]!=before)         //這是個無倍訓的圖，因此我們任意的搜索路徑也都是無倍訓的，只要滿足不往回走就可以了
        {
            dis[road[now][i]][cas]=sum+1;
            dfs(road[now][i],now,sum+1,cas);
        }
    }
}

int main()
{
    IOS
    memset(dis,0x7f,sizeof(dis));
    int n;
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        road[x].push_back(y);
        road[y].push_back(x);
    }
    dis[1][0]=0;
    dfs(1,1,0,0);
    int a,b,c,Max=-INF;
    for(int i=2;i<=n;i++)
        if(dis[i][0]>Max)
        {
            Max=dis[i][0];
            a=i;
        }
    dis[a][1]=0;
    dfs(a,a,0,1);
    Max=-INF;
    for(int i=1;i<=n;i++)   //這個回圈結束后Max記錄的便是直徑的長度
    {
        if(dis[i][1]>Max)
        {
            Max=dis[i][1];
            b=i;
        }
    }
    dis[b][2]=0;
    dfs(b,b,0,2);
    int ans=-INF;
    for(int i=1;i<=n;i++)       //ans記錄的是c點到a點和b點的距離和
    {
        int x=dis[i][1]+dis[i][2];
        if(x>ans&&i!=a&&i!=b)  //注意這里如果整棵樹只有一條路徑的話尋找c點的時候可能會和a或者b點重復
        {
            ans=x;
            c=i;
        }
    }
    ans=(ans+Max)/2;            //原本應該是(ans-Max)/2+Max，化簡了一下
    cout<<ans<<endl;
    if(a>b) swap(a,b);
    if(b>c) swap(b,c);
    if(a>b) swap(a,b);
    cout<<a<<' '<<b<<' '<<c<<endl;
}