T1:標題統計

---

題目大意

輸入一個字符串，求字符串除了空格的字符個數

---

解題思路

這種考你會不會編程的題不會？

---

code

#include<cstdio> #include<string> #include<iostream> using namespace std; int ans; string c; int main() {getline(cin,c);int l=c.size();for(int i=0;i<l;i++)ans+=(c[i]!=' '&&c[i]!='\n');printf("%d",ans); }

---

T2:龍虎斗

---

題目大意

一個長度為n序列，被中間點m分成兩半，m左邊和m右邊。
左邊戰斗力為
$$\sum _{i=1}^{m?1}(m?i)?a_i$$
$$\sum _{i=m+1}^n(i?m)?a_i$$
找到一個數值加$s2$，使兩邊的戰斗力之差最小

---

解題思路

先處理好兩邊戰斗力
暴力枚舉位置。注意要用longlong

---

code

#include<cstdio> #include<algorithm> #define N 100010 #define lls long long using namespace std; lls n,c[N],m,p1,s1,s2,ans1,ans2,mins,mark; int main() {scanf("%lld",&n);for(lls i=1;i<=n;i++)scanf("%lld",&c[i]);scanf("%lld%lld%lld%lld",&m,&p1,&s1,&s2);c[p1]+=s1;for(lls i=1;i<m;i++)ans1+=c[i]*(m-i);for(lls i=m+1;i<=n;i++)ans2+=c[i]*(i-m);mark=0;mins=1e19;for(lls i=1;i<m;i++){if(abs(ans1+s2*(m-i)-ans2)<mins){mark=i;mins=abs(ans1+s2*(m-i)-ans2);}}for(lls i=m+1;i<=n;i++){if(abs(ans1-ans2-s2*(i-m))<mins){mark=i;mins=abs(ans1-ans2-s2*(i-m));}}if((mins==abs(ans1-ans2)&&mark<m)||mins<abs(ans1-ans2)) printf("%lld",mark);else printf("%lld",m); }

---

T3:擺渡車

---

題目大意

n個人，有不同的到達時間。一輛車，來回一次要$mmin$。安排一個來回時間，使所有人等待時間之和最小。

---

解題思路

我們可以發現m很小可是t卻很大。所有我們不一定要從t入手。因為一個人會影響到他的只有之前的$m?1min$。
用$f_{i,j}$表示第i個人等了j的等待時間總數。然后我們枚舉i和枚舉上一班車的最后一個人j。之后枚舉那個人等了多久k。我們就可以計算出這個人上車最少等待時間
$$t_j+k+m?t_i$$
然后我們可以更新$f_{i,w}$
$$f_{i,w}=min\{f_{i,w},f_{j,k}+s_{j+1,i}+(i?j)?w\}$$
其中用$s_{i,j}$表示i到j的人都等第j個人上車需要的時間

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define N 510 #define M 210 using namespace std; int n,m,t[N],s[N][N],f[N][M],ans; int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&t[i]);sort(t+1,t+1+n);for(int i=1;i<n;i++)//預處理sfor(int j=i+1;j<=n;j++)for(int k=i;k<j;k++)s[i][j]+=t[j]-t[k];memset(f,0x3f3f3f3f,sizeof(f));t[0]=-2e9;for(int i=0;i<=m;i++)//初始化{f[0][i]=0;f[1][i]=i;}for(int i=2;i<=n;i++)//dpfor(int j=0;j<i;j++)for(int k=0;k<=m;k++){int w=t[j]+k+m-t[i];if(w>0)f[i][w]=min(f[i][w],f[j][k]+s[j+1][i]+(i-j)*w);else//特判防越界f[i][0]=min(f[i][0],f[j][k]+s[j+1][i]);}ans=2e9;for(int i=0;i<=m;i++)ans=min(ans,f[n][i]);printf("%d\n",ans); }

---

T4:對稱二叉樹

---

題目大意

一棵n個點的二叉樹，每個點有不同的權值。一棵樹對稱就是整棵樹的左右子節點互換之和長的和之前一樣。求這棵樹上最大的一顆對稱二叉樹。

---

解題思路

對于每個點我們給他兩個特征值
$$z{1}_i=lso{n}_i?2+rso{n}_i+w_i?4$$
$$z{2}_i=lso{n}_i+rso{n}_i?2+w_i?4$$
lson:這個點有沒有左子節點
rson:這個點有沒有右子節點
然后先左后右的跑一邊，記錄跑到的點的z1和這顆子樹包含的范圍。
再先右后左的跑一邊，記錄跑到的點的z2和這顆子樹包含的范圍。
之后對于每個節點用字符串hash判斷一下z1對于范圍是否和z2對應范圍相等，如果相等那么這棵子樹就是一顆對稱二叉樹。

時間負責度:$O(n)$

---

code

#include<cstdio> #include<algorithm> #define N 1000010 #define p 10007 #define ull unsigned long long using namespace std; int sz[N],a1[N],b1[N],e1[N],a2[N],b2[N],e2[N],z[N],f[N]; int maxs,n,tot,ls[N],rs[N],w[N]; ull hash1[N],hash2[N],pows[N]; void read(int &x) {char c;bool flag=false;while(c=getchar())if((c>='0'&&c<='9')||c=='-') break;if(c!='-')x=c-48;else flag=true;while(c=getchar())if(c>='0'&&c<='9') x=x*10+c-48;else break;if(flag) x=-x; } void dfs1(int x) {sz[x]=1;a1[++tot]=z[x];b1[x]=tot;if(ls[x]!=-1)dfs1(ls[x]);if(rs[x]!=-1)dfs1(rs[x]);sz[x]+=sz[ls[x]]+sz[rs[x]];e1[x]=tot; } void dfs2(int x) {if(x==-1) return;a2[++tot]=f[x];b2[x]=tot;if(rs[x]!=-1)dfs2(rs[x]);if(ls[x]!=-1)dfs2(ls[x]);e2[x]=tot; } ull hash1z(int l,int r) {return hash1[r]-hash1[l-1]*pows[r-l+1];} ull hash2z(int l,int r) {return hash2[r]-hash2[l-1]*pows[r-l+1];} bool check(int x) {if(sz[ls[x]]!=sz[rs[x]]) return false;int l1=b1[x],r1=e1[x],l2=b2[x],r2=e2[x];if(hash1z(l1,r1)==hash2z(l2,r2)) return true;return false; } int main() {read(n);for(int i=1;i<=n;i++)read(w[i]);for(int i=1;i<=n;i++){read(ls[i]);read(rs[i]);//fa[ls[i]]=fa[rs[i]]=i;z[i]=((ls[i]!=-1)<<1)+(rs[i]!=-1)+w[i]*4;f[i]=((rs[i]!=-1)<<1)+(ls[i]!=-1)+w[i]*4;//計算特征值}dfs1(1);//正搜tot=0;dfs2(1);//反搜pows[0]=1;for(int i=1;i<=n;i++){pows[i]=pows[i-1]*p;hash1[i]=hash1[i-1]*p+a1[i];hash2[i]=hash2[i-1]*p+a2[i];}//字符串哈希for(int i=1;i<=n;i++)//枚舉節點if(check(i))//判斷相等maxs=max(maxs,sz[i]);printf("%d",maxs); }

總結

以上是生活随笔為你收集整理的NOIP2018普及组复赛解析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。