携程笔试 2023.09.07
第一题,一个next_permutation搞定
第二题,统计从左到右,从上到下的前缀和,然后四个方向求值
第三题,用两个优先队列来维护就好了
第四题,一个简单的贪心,不要把它想难了
#include <iostream> #include <algorithm> #include <vector> #include <cmath> #include <cstring> using namespace std; int k[15]; int sushu[20]; void init(){ memset(sushu,0,sizeof(sushu)); sushu[2]=1; sushu[3]=1; sushu[5]=1; sushu[7]=1; sushu[11]=1; sushu[13]=1; sushu[17]=1; sushu[19]=1; } int main(){ init(); int n;cin>>n; for(int i=1;i<=n;i++){ k[i]=i; } int ans=0; do{ int flag=0; for(int i=1;i<n;i++){ int u=k[i]+k[i+1]; if(sushu[u]==1){ flag=1; break; } } if(flag==0)ans++; }while(next_permutation(k+1,k+1+n)); cout<<ans<<endl; }
#include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <string> #define ll long long using namespace std; const int N = 1e3+5; int l2r[N][N][3]; int u2d[N][N][3]; int m,n; string s[N]; int main(){ ll ans=0; int n,m;cin>>n>>m; for(int i=0;i<n;i++)cin>>s[i]; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(s[i][j]=='y'){ if(j!=0){ l2r[i][j][0]=l2r[i][j-1][0]+1; l2r[i][j][1]=l2r[i][j-1][1]; l2r[i][j][2]=l2r[i][j-1][2]; }else{ l2r[i][j][0]=1; l2r[i][j][1]=0; l2r[i][j][2]=0; } }else if(s[i][j]=='o'){ if(j!=0){ l2r[i][j][0]=l2r[i][j-1][0]; l2r[i][j][1]=l2r[i][j-1][1]+1; l2r[i][j][2]=l2r[i][j-1][2]; }else{ l2r[i][j][0]=0; l2r[i][j][1]=1; l2r[i][j][2]=0; } }else if(s[i][j]=='u'){ if(j!=0){ l2r[i][j][0]=l2r[i][j-1][0]; l2r[i][j][1]=l2r[i][j-1][1]; l2r[i][j][2]=l2r[i][j-1][2]+1; }else{ l2r[i][j][0]=0; l2r[i][j][1]=0; l2r[i][j][2]=1; } }else{ if(j!=0){ l2r[i][j][0]=l2r[i][j-1][0]; l2r[i][j][1]=l2r[i][j-1][1]; l2r[i][j][2]=l2r[i][j-1][2]; }else{ l2r[i][j][0]=0; l2r[i][j][1]=0; l2r[i][j][2]=0; } } } } for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(s[j][i]=='y'){ if(j!=0){ u2d[j][i][0]=u2d[j-1][i][0]+1; u2d[j][i][1]=u2d[j-1][i][1]; u2d[j][i][2]=u2d[j-1][i][2]; }else{ u2d[j][i][0]=1; u2d[j][i][1]=0; u2d[j][i][2]=0; } }else if(s[j][i]=='o'){ if(j!=0){ u2d[j][i][0]=u2d[j-1][i][0]; u2d[j][i][1]=u2d[j-1][i][1]+1; u2d[j][i][2]=u2d[j-1][i][2]; }else{ u2d[j][i][0]=0; u2d[j][i][1]=1; u2d[j][i][2]=0; } }else if(s[j][i]=='u'){ if(j!=0){ u2d[j][i][0]=u2d[j-1][i][0]; u2d[j][i][1]=u2d[j-1][i][1]; u2d[j][i][2]=u2d[j-1][i][2]+1; }else{ u2d[j][i][0]=0; u2d[j][i][1]=0; u2d[j][i][2]=1; } }else{ if(j!=0){ u2d[j][i][0]=u2d[j-1][i][0]; u2d[j][i][1]=u2d[j-1][i][1]; u2d[j][i][2]=u2d[j-1][i][2]; }else{ u2d[j][i][0]=0; u2d[j][i][1]=0; u2d[j][i][2]=0; } } } } // for(int i=0;i<n;i++){ // for(int j=0;j<m;j++){ // for(int w=0;w<3;w++){ // cout<<l2r[i][j][w]; // }cout<<' '; // } // cout<<endl; // } // cout<<endl<<endl; // for(int i=0;i<n;i++){ // for(int j=0;j<m;j++){ // for(int w=0;w<3;w++){ // cout<<u2d[i][j][w]; // }cout<<' '; // } // cout<<endl; // } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(s[i][j]=='y'){ ll x1=u2d[i][j][1]; ll y1=l2r[i][j][2]; ans+=x1*y1; x1=u2d[i][j][2]; y1=l2r[i][j][1]; ans+=x1*y1; ll x2=l2r[i][m-1][1]-l2r[i][j][1]; ll y2=u2d[n-1][j][2]-u2d[i][j][2]; ans+=x2*y2; x2=l2r[i][m-1][2]-l2r[i][j][2]; y2=u2d[n-1][j][1]-u2d[i][j][1]; ans+=x2*y2; ll x3=u2d[i][j][1]; ll y3=l2r[i][m-1][2]-l2r[i][j][2]; ans+=x3*y3; x3=u2d[i][j][2]; y3=l2r[i][m-1][1]-l2r[i][j][1]; ans+=x3*y3; ll x4=l2r[i][j][1]; ll y4=u2d[n-1][j][2]-u2d[i][j][2]; ans+=x4*y4; x4=l2r[i][j][2]; y4=u2d[n-1][j][1]-u2d[i][j][1]; ans+=x4*y4; }else if(s[i][j]=='o'){ ll x1=u2d[i][j][0]; ll y1=l2r[i][j][2]; ans+=x1*y1; x1=u2d[i][j][2]; y1=l2r[i][j][0]; ans+=x1*y1; ll x2=l2r[i][m-1][0]-l2r[i][j][0]; ll y2=u2d[n-1][j][2]-u2d[i][j][2]; ans+=x2*y2; x2=l2r[i][m-1][2]-l2r[i][j][2]; y2=u2d[n-1][j][0]-u2d[i][j][0]; ans+=x2*y2; ll x3=u2d[i][j][0]; ll y3=l2r[i][m-1][2]-l2r[i][j][2]; ans+=x3*y3; x3=u2d[i][j][2]; y3=l2r[i][m-1][0]-l2r[i][j][0]; ans+=x3*y3; ll x4=l2r[i][j][0]; ll y4=u2d[n-1][j][2]-u2d[i][j][2]; ans+=x4*y4; x4=l2r[i][j][2]; y4=u2d[n-1][j][0]-u2d[i][j][0]; ans+=x4*y4; }else if(s[i][j]=='u'){ ll x1=u2d[i][j][1]; ll y1=l2r[i][j][0]; ans+=x1*y1; x1=u2d[i][j][0]; y1=l2r[i][j][1]; ans+=x1*y1; ll x2=l2r[i][m-1][1]-l2r[i][j][1]; ll y2=u2d[n-1][j][0]-u2d[i][j][0]; ans+=x2*y2; x2=l2r[i][m-1][0]-l2r[i][j][0]; y2=u2d[n-1][j][1]-u2d[i][j][1]; ans+=x2*y2; ll x3=u2d[i][j][1]; ll y3=l2r[i][m-1][0]-l2r[i][j][0]; ans+=x3*y3; x3=u2d[i][j][0]; y3=l2r[i][m-1][1]-l2r[i][j][1]; ans+=x3*y3; ll x4=l2r[i][j][1]; ll y4=u2d[n-1][j][0]-u2d[i][j][0]; ans+=x4*y4; x4=l2r[i][j][0]; y4=u2d[n-1][j][1]-u2d[i][j][1]; ans+=x4*y4; } // cout<<ans<<' '; } // cout<<endl; } cout<<ans<<endl; }
#include <iostream> #include <queue> #include <cmath> #define ll long long using namespace std; priority_queue<ll,vector<ll>,greater<ll> >p1; priority_queue<ll,vector<ll>,less<ll> >p2; priority_queue<ll,vector<ll>,greater<ll> >p3; priority_queue<ll,vector<ll>,less<ll> >p4; queue<ll>q3; int main(){ int t;cin>>t; while(t--){ while(!p1.empty()){ p1.pop(); } while(!p2.empty()){ p2.pop(); } while(!p3.empty()){ p3.pop(); } while(!p4.empty()){ p4.pop(); } while(!q3.empty()){ q3.pop(); } ll n,l,r; cin>>n>>l>>r; for(int i=0;i<n;i++){ ll w;cin>>w; if(w<l){ p1.push(w); }else if(w>r){ p2.push(w); }else{ q3.push(w); } } // while(!p1.empty()){ // cout<<p1.top()<<' '; // p1.pop(); // }cout<<endl; // while(!p2.empty()){ // cout<<p2.top()<<' '; // p2.pop(); // }cout<<endl; ll ans=0; while(1){ if(p1.empty()||p2.empty()){ break; } ll val1=p1.top(); ll val2=p2.top(); ll res1=l-val1; ll res2=val2-r; if(res1==res2){ ans+=res1; p1.pop(); p2.pop(); q3.push(l); q3.push(r); }else if(res1>res2){ ans+=res2; p2.pop(); q3.push(r); p1.pop(); p1.push(val1+res2); }else if(res1<res2){ ans+=res1; p1.pop(); q3.push(l); p2.pop(); p2.push(val2-res1); } } // if(!p1.empty()){ // cout<<"p1"<<endl; // } // if(!p2.empty()){ // cout<<"p2"<<endl; // } if(p1.empty()&&p2.empty()){ cout<<ans<<endl; }else if(!p1.empty()){ // cout<<123<<endl; ll all1=0; while(!p1.empty()){ all1+=l-p1.top(); p1.pop(); } ll all2=0; while(!q3.empty()){ all2+=q3.front()-l; q3.pop(); } if(all2<all1)cout<<-1<<endl; else{ ans+=all1; cout<<ans<<endl; } // cout<<all1<<' '<<all2<<endl; }else if(!p2.empty()){ ll all1=0; while(!p2.empty()){ all1+=p2.top()-r; p2.pop(); } ll all2=0; while(!q3.empty()){ all2+=r-q3.front(); q3.pop(); } if(all2<all1)cout<<-1<<endl; else{ ans+=all1; cout<<ans<<endl; } } } }
#include <iostream> #include <string> #include <cstring> #include <algorithm> #define ll long long using namespace std; int main(){ string str; cin>>str; ll res,count; res=count=0; for(int i=0;i<str.length();i++){ if(str[i]=='0'){ count+=1; }else{ count=max((ll)0,count-1); } res+=count; } cout<<res<<endl; }