?

5385: 樹的遍歷?

Time Limit(Common/Java):1000MS/3000MS ? ? Memory Limit:65536KByte
Total Submit: 22 ? ? ? ?? ? Accepted:16

Description

?

給定一棵二叉樹的后序遍歷和中序遍歷，請你輸出其層序遍歷的序列。這里假設(shè)鍵值都是互不相等的正整數(shù)。

?

Input

?

輸入第一行給出一個正整數(shù)N（<=30），是二叉樹中結(jié)點(diǎn)的個數(shù)。第二行給出其后序遍歷序列。第三行給出其中序遍歷序列。數(shù)字間以空格分隔。

?

Output

?

在一行中輸出該樹的層序遍歷的序列。數(shù)字間以1個空格分隔，行首尾不得有多余空格。

?

Sample Input

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

Sample Output

?4 1 6 3 5 7 2

如題意所述，我們可以直接得到其前序遍歷結(jié)果，所以hash一下就好了，特別大了而且成鏈就寫一個大數(shù)吧，hash一下就好的

#include <bits/stdc++.h> using namespace std; map<int,int>M; int s[31],c[31],l; void la(int l,int r,int st,int ed,int f) {if(l<=r&&st<=ed){M[f]=c[ed];for(int i=l; i<=r; i++)if(c[ed]==s[i]){la(l,i-1,st,st+i-1-l,2*f+1),la(i+1,r,st+i-l,ed-1,2*f+2);return ;}} } int main() {cin>>l;for(int i=0;i<l;i++)cin>>c[i];for(int i=0;i<l;i++)cin>>s[i];la(0,l-1,0,l-1,0);int f=0;for(auto X:M){if(f)cout<<" ";cout<<X.second,f=1;}return 0; }

taozi的隊(duì)列代碼

#include<bits/stdc++.h> using namespace std; int post[1000],in[1000],Left[1000],Right[1000]; int n; int build(int L1,int R1,int L2,int R2) {if(L1>R1)return 0;int root=post[R1];int pos=L2;while(in[pos]!=root)pos++;int cnt=pos-L2;Left[root]=build(L1,L1+cnt-1,L2,pos-1);Right[root]=build(L1+cnt,R1-1,pos+1,R2);return root; } void level() {queue<int>q;q.push(post[n]);int f=0;while(!q.empty()){int u=q.front();q.pop();if(!f)printf("%d",u),f=1;else printf(" %d",u);if(Left[u])q.push(Left[u]);if(Right[u])q.push(Right[u]);} } int main() {cin>>n;for(int i=1;i<=n;i++)cin>>post[i];for(int i=1;i<=n;i++)cin>>in[i];build(1,n,1,n);level();return 0; }

5445: 中位數(shù)?

時間限制(普通/Java):2000MS/6000MS ? ? 內(nèi)存限制:250000KByte
總提交: 15 ? ? ? ?? ? 測試通過:2

描述

?

?

給定兩個序列，都已經(jīng)從小到大排序，求兩個序列合并后的中位數(shù)。

所謂中位數(shù)是指：當(dāng)排序后的序列元素個數(shù)是奇數(shù)時取中間值，否則去中間兩個數(shù)的平均數(shù)。

你能想出O(log(m+n))復(fù)雜度的算法嗎？

?

?

輸入

?

?

多組數(shù)據(jù)。每組數(shù)據(jù)的：

第一行為兩個整數(shù)n和m，(1<=n, m<=10000000)。

第二行由n個從小到大排序的整數(shù)。

第三行由m個從小到大排序的整數(shù)。

以EOF結(jié)束。

?

?

輸出

?

?

輸出中位數(shù)，保留2位小數(shù)。

?

?

樣例輸入

?

2 1
1 3
2
2 2
1 2
3 4

樣例輸出

?

提示

?

因本題輸入數(shù)據(jù)規(guī)模較大，請使用類似以下代碼輸入一個整數(shù)（輸入掛）：

int Scan()

{

? ? int res = 0, ch, flag = 0;

? ? if((ch = getchar()) == '-')? ? ? ? ? ? ?//判斷正負(fù)

? ? ? ? flag = 1;

? ? else if(ch >= '0' && ch <= '9')? ? ? ? ? ?//得到完整的數(shù)

? ? ? ? res = ch - '0';

? ? while((ch = getchar()) >= '0' && ch <= '9' )

? ? ? ? res = res * 10 + ch - '0';

? ? return flag ? -res : res;

}

?枚舉pos看他是第幾個數(shù)，當(dāng)然也會相等，所以這個還是特判一下的

為什么這樣是可以的呢，因?yàn)槟忝總€數(shù)在兩個數(shù)組均會有一個位置的，我只要遍歷每個數(shù)組就可以找到

mi代表當(dāng)前位置，其實(shí)個數(shù)是mi+1

pos-1代表可以插入到的位置，前一個可能是相等，也可能是不等

#include<bits/stdc++.h> using namespace std; const int N=10000005; int a[N],b[N],n,m; long long L,R,zws; int la() {while(L<=R){int mi=(L+R)>>1;int pos=upper_bound(a,a+n,b[mi])-a;if(pos&&a[pos-1]==b[mi]){if(mi+pos==zws)return mi;}if(mi+pos+1<zws){if(mi==m-1)return -1;L=mi+1;}else if(mi+pos+1>zws){if(mi==0)return -1;R=mi-1;}else {return mi;}}return -1; } int lb() {while(L<=R){int mi=(L+R)>>1;int pos=upper_bound(b,b+m,a[mi])-b;if(pos&&b[pos-1]==a[mi]){if(mi+pos==zws)return mi;}if(mi+pos+1<zws){if(mi==n-1)return -1;L=mi+1;}else if(mi+pos+1>zws){if(mi==0)return -1;R=mi-1;}else {return mi;}}return -1; } int Scan() {int res = 0, ch, flag = 0;if((ch = getchar()) == '-') flag = 1;else if(ch >= '0' && ch <= '9') res = ch - '0';while((ch = getchar()) >= '0' && ch <= '9' )res = res * 10 + ch - '0';return flag ? -res : res;}int main() {while(~scanf("%d%d",&n,&m)){for(int i=0; i<n; i++)a[i]=Scan();for(int i=0; i<m; i++)b[i]=Scan();L=0,R=m-1,zws=(n+m+1)/2;int t=la();if(t==-1)L=0,R=n-1,t=lb(),t=a[t];else t=b[t];if((n+m)%2==0){zws++;L=0,R=m-1;int t1=la();if(t1==-1)L=0,R=n-1,t1=lb(),t1=a[t1];else t1=b[t1];t+=t1;}else t+=t;printf("%.2f\n",t/2.);}return 0; }

?

5201: 數(shù)字游戲?

Time Limit(Common/Java):1000MS/3000MS ? ? Memory Limit:65536KByte
Total Submit: 125 ? ? ? ?? ? Accepted:17

Description

?

?

棟棟正在和同學(xué)們玩一個數(shù)字游戲。
游戲的規(guī)則是這樣的：棟棟和同學(xué)們一共n個人圍坐在一圈。棟棟首先說出數(shù)字1。接下來，坐在棟棟左手邊的同學(xué)要說下一個數(shù)字2。再下面的一個同學(xué)要從上一個同學(xué)說的數(shù)字往下數(shù)兩個數(shù)說出來，也就是說4。下一個同學(xué)要往下數(shù)三個數(shù)，說7。依次類推。
為了使數(shù)字不至于太大，棟棟和同學(xué)們約定，當(dāng)在心中數(shù)到 k-1 時，下一個數(shù)字從0開始數(shù)。例如，當(dāng)k=13時，棟棟和同學(xué)們報(bào)出的前幾個數(shù)依次為：
　　1, 2, 4, 7, 11, 3, 9, 3, 11, 7。
游戲進(jìn)行了一會兒，棟棟想知道，到目前為止，他所有說出的數(shù)字的總和是多少。

?

?

Input

?

輸入的第一行包含三個整數(shù) n,k,T，其中 n 和 k 的意義如上面所述，T 表示到目前為止棟棟一共說出的數(shù)字個數(shù)。

?

Output

?

輸出一行，包含一個整數(shù)，表示棟棟說出所有數(shù)的和。

?

Sample Input

?

Sample Output

?3 13 3

Hint

?17

樣例說明

　　棟棟說出的數(shù)依次為1, 7, 9，和為17。

數(shù)據(jù)規(guī)模和約定

　　1 < n,k,T < 1,000,000；

可以枚舉要加的值

#include<bits/stdc++.h> using namespace std;int main() {long long n,k,T,res=0,last=1;cin>>n>>k>>T;for(int i=1;i<T;i++){res+=(last+(2*i*n-n+1)*n/2)%k;last=(last+(2*i*n-n+1)*n/2)%k;}cout<<res+1;return 0; }

5202: 網(wǎng)絡(luò)尋路?

時間限制(普通/Java):1000MS/3000MS ? ? 內(nèi)存限制:65536KByte
總提交: 1 ? ? ? ?? ? 測試通過:1

描述

?

?

X 國的一個網(wǎng)絡(luò)使用若干條線路連接若干個節(jié)點(diǎn)。節(jié)點(diǎn)間的通信是雙向的。某重要數(shù)據(jù)包，為了安全起見，必須恰好被轉(zhuǎn)發(fā)兩次到達(dá)目的地。該包可能在任意一個節(jié)點(diǎn)產(chǎn)生，我們需要知道該網(wǎng)絡(luò)中一共有多少種不同的轉(zhuǎn)發(fā)路徑。

源地址和目標(biāo)地址可以相同，但中間節(jié)點(diǎn)必須不同。

如下圖所示的網(wǎng)絡(luò)。

1 -> 2 -> 3 -> 1 是允許的

1 -> 2 -> 1 -> 2 或者 1 -> 2 -> 3 -> 2 都是非法的。

?

?

?

輸入

?

?

輸入數(shù)據(jù)的第一行為兩個整數(shù)N M，分別表示節(jié)點(diǎn)個數(shù)和連接線路的條數(shù)(1<=N<=10000; 0<=M<=100000)。

接下去有M行，每行為兩個整數(shù) u 和 v，表示節(jié)點(diǎn)u 和 v 聯(lián)通(1<=u,v<=N , u!=v)。

輸入數(shù)據(jù)保證任意兩點(diǎn)最多只有一條邊連接，并且沒有自己連自己的邊，即不存在重邊和自環(huán)。

?

?

?

輸出

?

?

輸出一個整數(shù)，表示滿足要求的路徑條數(shù)。

?

?

樣例輸入

?

3 3
1 2
2 3
1 3

樣例輸出

?

6

提示

?

樣例輸入2

4 4
1 2
2 3
3 1
1 4

樣例輸出2

10?

可以dfs去枚舉，也就是去枚舉兩邊的點(diǎn)讓他們不形成環(huán)

但是注意目的地可以和源地址相同，那么合法的就有以下兩種情況

case1

case2

和當(dāng)前節(jié)點(diǎn)的度有關(guān)，即這條邊除了這條路帶來的度的乘積

#include<bits/stdc++.h> using namespace std; const int N=100005; int d[N],u[N],v[N],n,m; int main() {long long ans=0;scanf("%d%d",&n,&m);for(int i=0; i<m; i++)scanf("%d%d",&u[i],&v[i]),d[u[i]]++,d[v[i]]++;for(int i=0; i<m; i++)if(d[u[i]]>1&&d[v[i]]>1)ans+=(d[u[i]]-1)*1LL*(d[v[i]]-1)*2;printf("%I64d\n",ans);return 0; }

5204: 小朋友排隊(duì)?

Time Limit(Common/Java):1000MS/3000MS ? ? Memory Limit:65536KByte
Total Submit: 18 ? ? ? ?? ? Accepted:2

Description

?

n 個小朋友站成一排。現(xiàn)在要把他們按身高從低到高的順序排列，但是每次只能交換位置相鄰的兩個小朋友。
每個小朋友都有一個不高興的程度。開始的時候，所有小朋友的不高興程度都是0。
如果某個小朋友第一次被要求交換，則他的不高興程度增加1，如果第二次要求他交換，則他的不高興程度增加2（即不高興程度為3），依次類推。當(dāng)要求某個小朋友第k次交換時，他的不高興程度增加k。
請問，要讓所有小朋友按從低到高排隊(duì)，他們的不高興程度之和最小是多少。
如果有兩個小朋友身高一樣，則他們誰站在誰前面是沒有關(guān)系的。

?

Input

?

輸入的第一行包含一個整數(shù)n，表示小朋友的個數(shù)。
第二行包含 n 個整數(shù) H1 H2 … Hn，分別表示每個小朋友的身高。

?

Output

?

輸出一行，包含一個整數(shù)，表示小朋友的不高興程度和的最小值。

?

Sample Input

?

3
3 2 1

Sample Output

?9

Hint

樣例說明

　　首先交換身高為3和2的小朋友，再交換身高為3和1的小朋友，再交換身高為2和1的小朋友，每個小朋友的不高興程度都是3，總和為9。

數(shù)據(jù)規(guī)模和約定

　　對于10%的數(shù)據(jù)， 1<=n<=10；
　　對于30%的數(shù)據(jù)， 1<=n<=1000；
　　對于50%的數(shù)據(jù)， 1<=n<=10000；
　　對于100%的數(shù)據(jù)，1<=n<=100000，0<=Hi<=1000000。

?前置技能逆序?qū)?#xff0c;即交換相鄰兩個數(shù)字的最小次數(shù)

再考慮這個問題，就是問你一個數(shù)要交換幾次，這個自己可以推一下

其實(shí)就是把數(shù)倒過來正序?qū)Φ膫€數(shù)比如 3 2 1逆序?qū)ω暙I(xiàn)是0 1 2

倒過來1 2 3正序?qū)ω暙I(xiàn)0 1 2，即0+2 1+1 2+0所求次數(shù)

他卡我其他求逆序?qū)Φ姆绞?#xff0c;只能歸并排序過的

#include <stdio.h> #include <bits/stdc++.h> using namespace std; const int N=100005; int w[N],sum[N],n; struct T {int x,num; } a[N],T[N]; void la(int l,int r) {if(r-l==1)return;int m=l+r>>1,tm=l+r>>1,tl=l,i=l;la(l,m),la(m,r);while(tl<m||tm<r){if(tm>=r||(tl<m&&a[tl].x<=a[tm].x))T[i++]=a[tl++],T[i-1].num+=tm-m;elseT[i++]=a[tm++],T[i-1].num+=m-tl;}for(int i=l; i<r; i++)a[i]=T[i]; } int main() {scanf("%d",&n);for(int i=0; i<n; i++)scanf("%d",&a[i].x),a[i].num=0;la(0,n);__int64 ans=0;for(int i=0; i<n; i++)ans+=a[i].num*1LL*(a[i].num+1)/2;printf("%I64d",ans);return 0; }

5205: 最大子陣?

Time Limit(Common/Java):4000MS/12000MS ? ? Memory Limit:65536KByte
Total Submit: 21 ? ? ? ?? ? Accepted:8

Description

?

?

給定一個n*m的矩陣A，求A中的一個非空子矩陣，使這個子矩陣中的元素和最大。
其中，A的子矩陣指在A中行和列均連續(xù)的一塊。

?

?

Input

?

?

輸入的第一行包含兩個整數(shù)n, m，分別表示矩陣A的行數(shù)和列數(shù)。
接下來n行，每行m個整數(shù)，表示矩陣A。

?

?

Output

?

?

輸出一行，包含一個整數(shù)，表示A中最大的子矩陣中的元素和。

?

?

Sample Input

?

3 3
-1 -4 3
3 4 -1
-5 -2 8

Sample Output

?10

Hint

?

樣例說明

　　取最后一列，和為10。

數(shù)據(jù)規(guī)模和約定

　　對于50%的數(shù)據(jù)，1<=n, m<=50；
　　對于100%的數(shù)據(jù)，1<=n, m<=500，A中每個元素的絕對值不超過5000。

想起來了要用最大字段和，但是這個dp過程還是不好想的

你可以對行或列做下前綴和，然后再求下最大字段和

基于行的dp

#include<stdio.h> const int N=505; int r[N][N]; int main() {int n,m,x;scanf("%d%d",&n,&m);for(int i=1; i<=n; i++)for(int j=1; j<=m; j++)scanf("%d",&x),r[i][j]=r[i-1][j]+x;int ma=x,t;for(int i=1; i<=n; i++)for(int j=i; j<=n; j++){t=0;for(int k=1; k<=m; k++){t+=r[j][k]-r[i-1][k];if(t>ma)ma=t;if(t<0)t=0;}}printf("%d",ma);return 0; }

數(shù)據(jù)分布不均勻，基于列的dp跑起來比較慢

#include<stdio.h> const int N=505; int r[N][N]; int main() {int n,m,x;scanf("%d%d",&n,&m);for(int i=1; i<=n; i++)for(int j=1; j<=m; j++)scanf("%d",&x),r[i][j]=r[i][j-1]+x;int ma=x,t;for(int i=1; i<=m; i++)for(int j=i; j<=m; j++){t=0;for(int k=1; k<=n; k++){t+=r[k][j]-r[k][i-1];if(t>ma)ma=t;if(t<0)t=0;}}printf("%d",ma);return 0; }

5206: 約數(shù)倍數(shù)選卡片?

Time Limit(Common/Java):1000MS/3000MS ? ? Memory Limit:65536KByte
Total Submit: 1 ? ? ? ?? ? Accepted:1

Description

?

閑暇時，福爾摩斯和華生玩一個游戲：
在N張卡片上寫有N個整數(shù)。兩人輪流拿走一張卡片。要求下一個人拿的數(shù)字一定是前一個人拿的數(shù)字的約數(shù)或倍數(shù)。例如，某次福爾摩斯拿走的卡片上寫著數(shù)字“6”，則接下來華生可以拿的數(shù)字包括：
　　1，2，3, 6，12，18，24 ....
當(dāng)輪到某一方拿卡片時，沒有滿足要求的卡片可選，則該方為輸方。
請你利用計(jì)算機(jī)的優(yōu)勢計(jì)算一下，在已知所有卡片上的數(shù)字和可選哪些數(shù)字的條件下，怎樣選擇才能保證必勝！
當(dāng)選多個數(shù)字都可以必勝時，輸出其中最小的數(shù)字。如果無論如何都會輸，則輸出-1。

?

?

Input

?

輸入數(shù)據(jù)為2行。第一行是若干空格分開的整數(shù)（每個整數(shù)介于1~100間），表示當(dāng)前剩余的所有卡片。
第二行也是若干空格分開的整數(shù)，表示可以選的數(shù)字。當(dāng)然，第二行的數(shù)字必須完全包含在第一行的數(shù)字中。

?

Output

?

程序則輸出必勝的招法！！

?

Sample Input

?

2 3 6
3 6

Sample Output

?3

Hint

樣例輸入2

1 2 2 3 3 4 5
3 4 5

樣例輸出2

4

博弈題目，但是題目數(shù)據(jù)應(yīng)該不是很多，直接dfs就過了

大概思路是這樣的，因?yàn)槲乙x擇必勝，即某個選擇可以導(dǎo)致對手出現(xiàn)必?cái)B(tài)

還要輸出最小的數(shù)字，所以需要對b數(shù)組進(jìn)行排序

然后需要預(yù)處理一下一個數(shù)的約數(shù)和倍數(shù)，假如這個數(shù)量級很大了，貌似就很難過了，倍數(shù)還有約數(shù)要很好的處理下，可以把有些數(shù)組直接賦值過去

#include<bits/stdc++.h> using namespace std; #define dbg(x) cout<<#x<<" = "<< (x)<< endl const int N=105; int num[N]; vector<int> b,f[N]; int dfs(int x) {for(int i=f[x].size()-1; i>=0; i--){int pp=f[x][i],t;if(num[pp]){num[pp]--,t=dfs(pp),num[pp]++;if(t)return 0;}}return 1; } void la() {for(auto X:b){if(num[X]){num[X]--;if(dfs(X)){cout<<X;return;}num[X]++;}}cout<<-1; } int main() {int x;string s;getline(cin,s);stringstream ss(s);while(ss>>x)num[x]++;getline(cin,s);stringstream st(s);while(st>>x)b.push_back(x);sort(b.begin(),b.end());for(int i=1; i<N ; i++)if(num[i])for(int j=1; j<N ; j++)if(num[j]&&(i%j==0||j%i==0))f[i].push_back(j);la();return 0; }

5200: 買不到的數(shù)目?

Time Limit(Common/Java):1000MS/3000MS ? ? Memory Limit:65536KByte
Total Submit: 57 ? ? ? ?? ? Accepted:43

Description

?

?

小明開了一家糖果店。他別出心裁：把水果糖包成4顆一包和7顆一包的兩種。糖果不能拆包賣。

小朋友來買糖的時候，他就用這兩種包裝來組合。當(dāng)然有些糖果數(shù)目是無法組合出來的，比如要買 10 顆糖。

你可以用計(jì)算機(jī)測試一下，在這種包裝情況下，最大不能買到的數(shù)量是17。大于17的任何數(shù)字都可以用4和7組合出來。

本題的要求就是在已知兩個包裝的數(shù)量時，求最大不能組合出的數(shù)字。

?

?

Input

?

?

兩個正整數(shù)，表示每種包裝中糖的顆數(shù)(都不多于1000)

?

?

Output

?

?

一個正整數(shù)，表示最大不能買到的糖數(shù)。

如果這個數(shù)不存在，則輸出-1。

?

?

Sample Input

?4 7

Sample Output

?17

Hint

?

樣例輸入2

3 5

樣例輸出2

7

題目不嚴(yán)謹(jǐn)，因?yàn)橛?的時候是不存在這個數(shù)的，而且你很快會發(fā)現(xiàn)只有互質(zhì)的時候才存在，否則是不存在的

但是是一個很好的數(shù)論

證明以下2個命題
1.?(x-1)(y-1)-1?不能被表示為?ax+by的形式
2.?大于等于(x-1)(y-1)都能被表示為?ax+by的形式 當(dāng)時題目數(shù)據(jù)是滿足?x>1,y>1,gcd（x，y）==1的，現(xiàn)在可能改了hhh #include <stdio.h> int main() {int a,b;scanf("%d%d",&a,&b);printf("%d",a*b-a-b); }

?

轉(zhuǎn)載于:https://www.cnblogs.com/BobHuang/p/8980104.html

總結(jié)

以上是生活随笔為你收集整理的2018集训队日常训练1的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。