目錄

• 3485. 最大異或和 【難度：中 / 知識點: trie樹】
• 3493. 最大的和 【難度: 一般 / 知識點: 前綴和 滑動窗口】
• 3499. 序列最大收益 【難度: 中等 / 知識點: DP】
• 3502. 不同路徑數 【難度: 簡單 / 知識點: dfs】
• 3489. 星期幾 【難度: 一般 / 知識點: 日期模擬】
• 3481. 階乘的和 【難度: 一般 / 知識點: 二進制枚舉】

3485. 最大異或和 【難度：中 / 知識點: trie樹】

題目詳解

#include<bits/stdc++.h> using namespace std; const int N=1e5*31+10,M=1e5+10; int s[M],son[N][2],idx,n,m,cnt[N]; void insert(int x,int v)// v是表示trie的該結點否存在的次數 {int p=0;for(int i=30;i>=0;i--){int u=x>>i&1;if(!son[p][u]) son[p][u]=++idx;p=son[p][u];cnt[p]+=v;} } int query(int x) {int p=0,res=0;for(int i=30;i>=0;i--){int u=x>>i&1;if(cnt[son[p][!u]]) p=son[p][!u],res=res*2+1;else p=son[p][u],res*=2;}return res; } int main(void) {cin>>n>>m;for(int i=1;i<=n;i++) cin>>s[i],s[i]^=s[i-1];insert(s[0],1);//求前綴和需要s[0]int res=0;for(int i=1;i<=n;i++){if(i>m) insert(s[i-m-1],-1) ;//-1 表示去掉這個點res=max(res,query(s[i]));insert(s[i],1);//1表示加入這個點}cout<<res;return 0; }

3493. 最大的和 【難度: 一般 / 知識點: 前綴和 滑動窗口】

題目詳解

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; long long int a[N],b[N],s[N],n,k; int main(void) {cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++){cin>>b[i];if(b[i]) s[i]=s[i-1]+a[i];else s[i]=s[i-1];} long long int ans=0,sum=0;for(int i=1;i<=n;i++){if(i>k&&!b[i-k]) sum-=a[i-k];sum+=a[i];ans=max(ans,sum+s[n]-s[i]);}cout<<ans;return 0; }

3499. 序列最大收益 【難度: 中等 / 知識點: DP】

題目詳解

#include<bits/stdc++.h> using namespace std; const int N=210; int n,m,k; int f[N][N],a[N],w[N][N],ans; int main(void) {cin>>n>>k>>m;for(int i=1;i<=m;i++) cin>>a[i];for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>w[i][j];memset(f,-0x3f,sizeof f);f[1][0]=0;for(int i=2;i<=m;i++)for(int j=0;j<=k;j++)for(int u=1;u<i;u++) if(j>=i-1-u) f[i][j]=max(f[i][j],f[u][j-(i-1-u)]+w[a[u]][a[i]]);for(int i=0;i<=k;i++) ans=max(ans,f[m][i]);cout<<ans;return 0; }

3502. 不同路徑數 【難度: 簡單 / 知識點: dfs】

#include<bits/stdc++.h> using namespace std; set<int>st; int n,m,k,a[15][15]; int dx[4]={-1,0,1,0}; int dy[4]={0,1,0,-1}; void dfs(int x,int y,int sum,int index) {if(index==k){st.insert(sum);return;}for(int i=0;i<4;i++){int tempx=x+dx[i];int tempy=y+dy[i];if(tempx>=1&&tempx<=n&&tempy>=1&&tempy<=m) dfs(tempx,tempy,sum*10+a[tempx][tempy],index+1);} } int main(void) {cin>>n>>m>>k;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) cin>>a[i][j];for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dfs(i,j,a[i][j],0);cout<<st.size()<<endl;return 0; }

3489. 星期幾 【難度: 一般 / 知識點: 日期模擬】

詳細題解

#include<bits/stdc++.h> using namespace std; int m[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; int a,b,c; string month; map<string,int>mp1; map<int,string>mp2; bool check(int year) {if(year%400==0||(year%4==0&&year%100!=0)) return true;else return false; } int main(void) {mp1["January"]=1,mp1["February"]=2,mp1["March"]=3;mp1["April"]=4,mp1["May"]=5,mp1["June"]=6;mp1["July"]=7,mp1["August"]=8,mp1["September"]=9;mp1["October"]=10,mp1["November"]=11,mp1["December"]=12;mp2[1]="Monday",mp2[2]="Tuesday",mp2[3]="Wednesday";mp2[4]="Thursday",mp2[5]="Friday",mp2[6]="Saturday",mp2[7]="Sunday";while(cin>>a>>month>>c){int sum=1+365*(c-1);//+1 是因為1.1b=mp1[month];for(int i=1;i<c;i++) if(check(i)) sum++;if(check(c)) m[2]=29;int s1=1,s2=1;while(s1!=b||s2!=a){s2++,sum++;if(s2>m[s1]) s1++,s2=1;}if(sum%7) cout<<mp2[sum%7]<<endl;else cout<<mp2[7]<<endl;m[2]=28;}return 0; }

3481. 階乘的和 【難度: 一般 / 知識點: 二進制枚舉】

題目詳解

#include<bits/stdc++.h> using namespace std; int n; int s[15]={1,1,2,6,24,120,720,5040,40320,362880}; int main(void) {while(cin>>n,n>=0){bool flag=false;for(int k=0;k<(1<<10);k++){int x=0;for(int i=9;i>=0;i--){if(k>>i&1) x+=s[i];if(x==n) flag=true;}}if(flag&&n) puts("YES");else puts("NO");}return 0; } 《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的2021夏季每日一题 【week1 未完结】的全部內容，希望文章能夠幫你解決所遇到的問題。

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