第四屆“傳智杯”全國大學(xué)生IT技能大賽（決賽B組）

• A. 小智的疑惑
• B. 三元組
• C. 排排隊
• D. 背單詞的小智
• E. 游戲
• F1. 生活在樹上（easy version）

A. 小智的疑惑

題目描述

傳智專修學(xué)院給了小智一個僅包含小寫字母的字符串 s，他想知道，里面出現(xiàn)了多少次子串 chuanzhi 呢。
我們稱一個字符串 t 是 s 的子串，當(dāng)且僅當(dāng)將 s 的開頭若干個（可以為 0 個）連續(xù)字符和結(jié)尾若干個（可以為 0 個）連續(xù)字符刪去后，剩下的字符串和 t 相同。例如，我們稱 ab 是 abc 的子串，但 ac 不是 abc 的子串。

解題思路： 直接開python，快速方便。

print (input().count('chuanzhi'))

B. 三元組

題目描述
給定一個長度為 n 的數(shù)列 a，對于一個有序整數(shù)三元組 (i,j,k)，若其滿足 1≤i≤j≤k≤n 并且 ai+aj=ak?，則我們稱這個三元組是「傳智的」。
現(xiàn)在請你計算，有多少有序整數(shù)三元組是傳智的。

解題思路： 暴力循環(huán)。

#include<bits/stdc++.h> using namespace std; int a[105],n,b[105],ans,t; int main() {cin>>t;while(t--){for(int i=0;i<105;i++)b[i]=0;ans=0;cin>>n;for(int i=0;i<n;i++)cin>>a[i];for(int i=0;i<n;i++){for(int j=i;j<n;j++){for(int k=j;k<n;k++){if(a[i]+a[j]==a[k])ans++;}}}cout<<ans<<endl;}return 0; }

C. 排排隊

題目描述
在傳智專修學(xué)院中，每個人都有一個身高 ai?，并且只有相鄰的兩個人可以交換位置。小智帶領(lǐng)的隊伍有 n 個人,他現(xiàn)在要給大家排隊形。

給定一個長度為 n 的序列 b，一個隊形被認(rèn)為美觀，當(dāng)且僅當(dāng)對于所有的 i=1,2,3,…n，ai=bi。小智想知道，他能否讓大家的隊形變得美觀，并且交換相鄰兩個人的次數(shù)不超過 n^2 次。這個問題把小智難住了，請你幫他來解決這個問題，如果存在合法的交換方案，輸出 YES，并給出一組方案；否則，輸出 NO。

解題思路： 重新對a進(jìn)行排序然后交換位置，假設(shè)a={1,2,2,3},b={3,2,2,1},給多一個數(shù)組對當(dāng)前的a確認(rèn)位置num={4,2,3,1}代表最終要去到的位置，對num數(shù)字進(jìn)行冒泡排序交換i和j的值最后變成{1,2,3,4}就可以了。

#include<bits/stdc++.h> using namespace std; const int N=1010; int t,n,a[N],b[N],num[N],flag; int main() {cin>>t;while(t--){flag=0;memset(num,0,sizeof num);cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)cin>>b[i];for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(a[j]==b[i]&&num[j]==0)//確保每個都有對應(yīng){num[j]=i;break;}}}for(int i=1;i<=n;i++)if(num[i]==0)flag=1;if(flag)//數(shù)量對不上直接輸出no{cout<<"NO"<<endl;continue;}cout<<"YES"<<endl;for(int i=1;i<n;i++){for(int j=1;j<n;j++){if(num[j]>num[j+1]){cout<<j<<" "<<j+1<<endl;swap(num[j],num[j+1]);}}}cout<<"0 0"<<endl;}return 0; }

D. 背單詞的小智

題目描述
大概意思就是，n個單詞分成k個區(qū)間，確保最大的區(qū)間價值最小。
對于樣例二，分成兩個區(qū)間，代價分別是1+4+9=14和16，最大價值為16是最優(yōu)解。
解題思路： 二分最大值。

#include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,k,a[100005],x; bool pd(ll num) {ll ans=0,sum=0;for(int i=1;i<=n;i++){sum+=a[i];if(sum+a[i+1]>num)sum=0,ans++;}if(sum>0)ans++;if(ans>k)return false;return true; } int main() {ll l=1,r=1e18;cin>>n>>k;for(int i=1;i<=n;i++){cin>>x,a[i]=x*x;l=max(l,a[i]);}while(l<r){ll mid=l+r>>1;if(pd(mid))r=mid;else l=mid+1;}cout<<l<<endl;return 0; }

E. 游戲

寫不出來555

F1. 生活在樹上（easy version）

題目描述
給出n個節(jié)點和m個查詢，查詢兩個城市之間的權(quán)值異或和是否等于k。
題目確保了城市是一棵最小生成樹。

解題思路： 首先我們要知道異或的性質(zhì)
交換律： a ^ b ^ c = a ^ c ^ b
任何數(shù)于0異或為任何數(shù) ：0 ^ n = n
相同的數(shù)異或為0:n ^ n = 0
接著看樣例一的圖

城市1到城市4的其中一種異或就是1-3異或4-3，結(jié)果就是8 ^ 2 ^ 6 ^ 6,相當(dāng)于城市1直接異或到城市4，也就是8 ^ 2，所以我們只需要判斷最短路徑上的異或是否等于k然后輸出就好了。

#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; const int N=500005; int n,m,a[N],x,y,nex[N*2],en[N*2],ans; ull w[N*2],num[N],val; bool pd[N]; void add(int x,int y,ull val) {en[ans]=y;w[ans]=val;nex[ans]=a[x];a[x]=ans++; } void dfs(int cnt) {for(int i=a[cnt];i!=-1;i=nex[i]){int j=en[i];if(!pd[j]){num[j]=num[cnt]^w[i];pd[j]=1;dfs(j);pd[j]=0;}} } int main() {std::ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m;for(int i=1;i<=n;i++)a[i]=-1;for(int i=1;i<n;i++){cin>>x>>y>>val;add(x,y,val);add(y,x,val);}pd[1]=1;for(int i=a[1];i!=-1;i=nex[i]){num[en[i]]=w[i];dfs(en[i]);}while(m--){ull u,v;cin>>u>>v>>val;if(n==1){cout<<"NO"<<endl;continue;}if(u!=1&&v!=1){if((num[u]^num[v])==val)cout<<"YES"<<endl;else cout<<"NO"<<endl;}else{if(u==1){if(num[v]==val)cout<<"YES"<<endl;else cout<<"NO"<<endl;}else{if(num[u]==val)cout<<"YES"<<endl;else cout<<"NO"<<endl;}}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的第四届“传智杯”全国大学生IT技能大赛（决赛B组）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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