免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

復(fù)現(xiàn)鏈接：https://ac.nowcoder.com/acm/contest/3405#question

shzr題解：https://www.cnblogs.com/shzr/p/12018915.html

echozhou題解：https://www.cnblogs.com/EchoZQN/p/12030689.html

A.牛妹愛(ài)整除

輸入3輸出10，輸入5輸出16，盲猜一發(fā)3n 1，看了第三個(gè)樣例輸入9輸出10，陷入沉思。

開(kāi)始推斷發(fā)現(xiàn)n 1進(jìn)制符合，理由如下：

假設(shè)為n 1進(jìn)制的cba，轉(zhuǎn)換為十進(jìn)制后為下式

(n 1)*a (n 1)*(n 1)*b (n 1)*(n 1)*(n 1)*c

mod的性質(zhì)：(a*b*c)%n=[(a%n)*(b%n)*(c%n)]%n

而(n 1)%n=1，故原式%n=1*a 1*1*b 1*1*1 c=a b c

任意n 1進(jìn)制的數(shù)同理，1 kn(k>=1)進(jìn)制的數(shù)同理，因?yàn)?1 kn)%n=1

要注意如果輸出不是n 1，需要開(kāi)long long，因?yàn)閚的范圍是1e9

#include<bits/stdc  .h>using namespace std;int main(){    int n;    scanf("%d",&n);    printf("%d\n",n 1);     return 0;}

B.吃桃

dp[i]表示i節(jié)點(diǎn)向子樹(shù)內(nèi)能延伸的最長(zhǎng)路徑

dep[i]表示i節(jié)點(diǎn)到k節(jié)點(diǎn)的距離，初始假定dep[k]=1

dfs記錄深度

redfs逆dp，輸出路徑

樣例：

#include<bits/stdc  .h>using namespace std;#define inf 0x3f3f3f3fconst int maxn=1e5 10;vector<int> vec[maxn];int dp[maxn],dep[maxn]; void dfs(int x){    int size=vec[x].size();    for(int i=0;i<size;i  )    {        int tmp=vec[x][i];        if(dep[tmp])continue;//不能只當(dāng)作vis來(lái)判斷是否出現(xiàn)過(guò),下面要用到dep         dep[tmp]=dep[x] 1;        dfs(tmp);        dp[x]=max(dp[x],dp[tmp]);    }    dp[x]  ;//加上x(chóng)點(diǎn)本身 } void redfs(int x){    printf("%d\n",x);    if(dp[x]==1)return;    int size=vec[x].size(),ans=inf;    for(int i=0;i<size;i  )    {        int tmp=vec[x][i];        if(dep[tmp]<dep[x])continue;        if(dp[tmp] 1==dp[x])ans=min(ans,tmp);//優(yōu)先選擇節(jié)點(diǎn)最小的     }    redfs(ans);} int main(){    int n,k;    scanf("%d%d",&n,&k);    for(int i=0;i<n-1;i  )    {        int u,v;        scanf("%d%d",&u,&v);        vec[u].push_back(v);        vec[v].push_back(u);    }    dep[k]=1;    dfs(k);    redfs(k);    /*     for(int i=1;i<=n;i  )    {        cout<<i<<" "<<dp[i]<<" "<<dep[i]<<endl;    }*/    return 0;}

C.背包問(wèn)題

代碼很簡(jiǎn)單但是我想了很久

范圍n<=200，V、v[i]<=1e6，w[i]<=200

題意：總體積不小于V的最小價(jià)值

轉(zhuǎn)換：總體積不大于Vall-V的最大價(jià)值（開(kāi)不了這么大的數(shù)組）

再次轉(zhuǎn)換：對(duì)價(jià)值進(jìn)行dp，dp[i]表示同價(jià)值最大體積，從價(jià)值1到最大價(jià)值，存在不小于V體積dp[i]，此時(shí)的價(jià)值i即為答案

#include<bits/stdc  .h>using namespace std;const int maxv=1e6 10;const int maxw=200 10;int v[maxw],w[maxw],dp[maxv];//dp[i]表示價(jià)值是i的情況下的最大體積int main(){    int n,V,sum=0;    scanf("%d%d",&n,&V);    for(int i=1;i<=n;i  )    {        scanf("%d%d",&v[i],&w[i]);        sum =w[i];    }     for(int i=1;i<=n;i  )    {        for(int j=sum;j>=w[i];j--)        {            dp[j]=max(dp[j],dp[j-w[i]] v[i]);        }    }     //找到第一個(gè)滿足體積不小于V的價(jià)值    for(int i=1;i<=sum;i  )    {        if(dp[i]>=V)        {            printf("%d\n",i);            break;        }    }    return 0;}

D.泡面

單調(diào)隊(duì)列g(shù)iao一下

加入了自己領(lǐng)悟的代碼

#include<bits/stdc  .h>using namespace std;const int maxn=1e5 10;pair<int,int> a[maxn];struct cmp{    bool operator()(int a,int b)    {        return a>b;    }};int main(){    int n,p;    long long ans[maxn]={0};    scanf("%d%d",&n,&p);    for(int i=1;i<=n;i  )    {        scanf("%d",&a[i].first);        a[i].second=i;    }    sort(a 1,a n 1);        priority_queue<int,vector<int>,cmp> q;//id小的優(yōu)先     //priority_queue<int,vector<int>,greater<int> > q;        long long cur=0;    for(int i=1;i<=n;i  )//保證Push n個(gè)數(shù)     {        while(!q.empty()&&cur<a[i].first)//如果打水隊(duì)列不空,而且還沒(méi)輪到a[i]打水(a[i]已經(jīng)為升序)         {            int id=q.top();//就不停地讓隊(duì)列里第一個(gè)人去打水             q.pop();                        //cout<<id<<" "<<cur<<" "<<a[i].first<<endl;            cur =p;            ans[id]=cur;         }        q.push(a[i].second);//a[i]排隊(duì)        if(cur<a[i].first)cur=a[i].first;        //如果a[i]前面的人都打過(guò)水了,cur還沒(méi)輪到a[i],cur之間變成a[i]的時(shí)間     }        //for一遍后n個(gè)人肯定都已經(jīng)排過(guò)隊(duì)了,把還沒(méi)打水的排一遍隊(duì)     while(!q.empty())    {        int id=q.top();        q.pop();        cur =p;        ans[id]=cur;    }    for(int i=1;i<=n;i  )    {        cout<<ans[i]<<" ";    }    return 0;}

E.偽直徑

在樹(shù)上找兩條不相同的路徑，使得兩路徑的交最長(zhǎng)

樹(shù)上最長(zhǎng)的路徑為直徑，該路徑少取一個(gè)節(jié)點(diǎn)后產(chǎn)生的新路徑，與直徑相交，長(zhǎng)度剛好為n-1

為啥不是n？

反證法：假設(shè)答案為n(直徑)，即樹(shù)上存在兩條不相同的路徑，他們的交為n，因?yàn)閮蓷l路不同，所以肯定有至少一條路在除了交的部分還有邊，那樹(shù)上最長(zhǎng)的路就大于n了，與原假設(shè)矛盾。

故答案不為n。

剩下就是怎么求樹(shù)的直徑了...

不學(xué)不知道，樹(shù)形dp原來(lái)so easy？：)

#include<bits/stdc  .h>using namespace std;const int maxn=2e5 10;vector<int> vec[maxn];int vis[maxn],dp[maxn],ans;//dp[i]為以i為起點(diǎn)的最長(zhǎng)鏈的長(zhǎng)度 void dfs(int u){    vis[u]=1;    int size=vec[u].size();    for(int i=0;i<size;i  )    {        int now=vec[u][i];        if(vis[now])continue;        dfs(now);        //cout<<u<<" "<<now<<endl;        ans=max(ans,dp[u] dp[now] 1);        //在u為根節(jié)點(diǎn)時(shí)，經(jīng)過(guò)u的最長(zhǎng)鏈長(zhǎng)度等于它的任意兩個(gè)子節(jié)點(diǎn)的d[i]之和的最大值 1        //每個(gè)u都會(huì)遍歷一遍，所以可以求出ans         dp[u]=max(dp[u],dp[now] 1);        }}int main(){    int n;    scanf("%d",&n);    for(int i=0;i<n-1;i  )    {        int u,v;        scanf("%d%d",&u,&v);        vec[u].push_back(v);        vec[v].push_back(u);    }    dfs(1);    cout<<ans-1<<endl;     return 0;}/* 7 1 22 62 33 43 55 7 */ 

F.最大最小差

先mark，有空了滾回來(lái)補(bǔ)題