A題題目意思很簡單，問一種撥號的方式(撥號手勢)是不是能撥出唯一的號碼(例如253就不是唯一的，因為586也是可以的)

記錄電話上每個格子上下左右是否還有格子，一個撥號手勢是唯一的當且僅當，所撥號碼的所有格子在同一個方向不同時有格子相鄰。

那么直接mark，判斷一下即可：

#include <cstdio> using namespace std; char s[10000]; int n,U,D,L,R; int main(){scanf("%d %s",&n,s);for(int i=0;i<n;i++){if(s[i]=='0')D=L=R=1;if(s[i]=='1'||s[i]=='4'||s[i]=='7')L=1;if(s[i]=='3'||s[i]=='6'||s[i]=='9')R=1;if(s[i]=='1'||s[i]=='2'||s[i]=='3')U=1;if(s[i]=='7'||s[i]=='9')D=1;}if(L&&R&&U&&D)puts("YES");else puts("NO");return 0; }

B題的意思是城市之間兩兩可以互達，耗時為兩者編號的差值，同時也有一些捷徑，可以用1單位時間的代價從a到b，問從1到每個點的最短耗時。

嘛，如果想把兩兩之間路都建出來再跑最短路，就會發現內存不開心了，由于很多路是等價的關系，所以對于兩兩之間的耗時為編號的差值這個條件，我們只需要建立n-1條邊，從i到i+1建立長度為1的邊，然后加上捷徑，跑一遍最短路就可以出解了。

#include <cstdio> #include <cstring> #include <queue> #include <utility> using namespace std; const int N=2000100; const int INF=~0U>>2; typedef pair<int,int>seg; priority_queue<seg,vector<seg>,greater<seg> >q; int d[N],head[N],u[N],v[N],w[N],nxt[N],n,m,ed=0,H,x[N],y[N]; bool vis[N]; void add(int a,int b,int c){ u[++ed]=a,v[ed]=b,w[ed]=c;nxt[ed]=head[u[ed]]; head[u[ed]]=ed; } int Dijkstra(int src){ memset(vis,0,sizeof(vis)); for(int i=0;i<=n+1;i++)d[i]=INF; d[src]=0; q.push(make_pair(d[src],src)); while(!q.empty()){ seg now=q.top(); q.pop(); int x=now.second; if(vis[x])continue; vis[x]=true; for(int e=head[x];e!=-1;e=nxt[e]) if(d[v[e]]>d[x]+w[e]){ d[v[e]]=d[x]+w[e]; q.push(make_pair(d[v[e]],v[e])); } } } int a[200005],p[200005]; int main(){scanf("%d",&n);memset(head,-1,sizeof(head));for(int i=1;i<=n;i++){scanf("%d",a+i);}for(int i=1;i<=n;i++){add(i,i+1,1);add(i,i-1,1);if(a[i]!=i)add(i,a[i],1);}Dijkstra(1);for(int i=1;i<n;i++)printf("%d ",d[i]);printf("%d\n",d[n]);return 0; }

C題告訴你末項不超過n，且項數為4的等比數列恰好為m個，求n的最小值

一開始想著打表找規律，看了好幾項沒什么頭緒，于是只能預處理比值的三次方，二分n，計算等比數列的個數來判斷。

#include <cstdio> using namespace std; const int N=1000005; long long a[N],n; int check(long long x){long long s=0;for(int i=2;a[i]<=x;i++){s+=x/a[i];if(s>=n){return 1;}}return 0; } int main(){for(long long i=1;i<=1000000;i++)a[i]=i*i*i;scanf("%lld",&n);long long l=1,r=1e18;while(l<r){long long mid=(l+r)>>1;if(check(mid))r=mid;else l=mid+1; }long long sum=0;for(int i=2;a[i]<=l;i++)sum+=l/a[i];if(sum!=n)l=-1;printf("%lld\n",l);return 0; }

D題題意很簡單，給出a，b兩個數組，求區間，使得在該區間內a的最大值和b的最小值相等，求出區間的個數。

題解：RMQ問題，打出ST表后，分治求出在固定左端點后符合條件區間的右端點的取值范圍，范圍的長度和就是答案。

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N=200010; int d[N][30],f[N][30],a[N],lg2[N]; int T,n,l,r,q; void rmq_init(int n){ for(int i=2;i<=n;i++)lg2[i]=lg2[i/2]+1;for(int i=1;i<=n;i++)scanf("%d",&d[i][0]);for(int i=1;i<=n;i++)scanf("%d",&f[i][0]);for(int j=1;(1<<j)<=n;j++){ for(int i=1;i+(1<<j)-1<=n;i++){ d[i][j]=max(d[i][j-1],d[i+(1<<(j-1))][j-1]);f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);} } } int rmq_max(int l,int r){int k=lg2[r-l+1];return max(d[l][k],d[r-(1<<k)+1][k]);} int rmq_min(int l,int r){int k=lg2[r-l+1];return min(f[l][k],f[r-(1<<k)+1][k]);} int main() {scanf("%d",&n);long long ans=0;rmq_init(n);for(int i=1;i<=n;i++){int l=i,r=n;while(l<r){int mid=(l+r+1)>>1;if(rmq_max(i,mid)>rmq_min(i,mid))r=mid-1;else l=mid;}if(rmq_max(i,l)!=rmq_min(i,l))continue;int ll=i,rr=l;while(ll<rr){int mid=(ll+rr)>>1;if(rmq_max(i,mid)<rmq_min(i,mid))ll=mid+1;else rr=mid;}ans+=l-ll+1;}printf("%lld\n",ans); }

E題給出了n個區間，求k個不同區間相交得到的區間長度和。

拆分成左右端點分段計算(方法巧妙，具體實現看代碼)

#include <cstdio> #include <vector> #include <algorithm> #include <iostream> using namespace std; typedef long long LL; const int N=200005; const int mod=1000000007; LL f[N],rf[N]; int l[N],r[N],m,n,k; LL inv(int a,int m){return(a==1?1:inv(m%a,m)*(m-m/a)%m);} LL C(int n,int m){if(n<m||m<0)return 0;return f[n]*rf[m]%mod*rf[n-m]%mod;} void init(){f[0]=1LL;for(int i=1;i<=200000;i++)f[i]=(LL)f[i-1]*i%mod;rf[200000]=inv(f[200000],mod);for(int i=200000;i;i--)rf[i-1]=(LL)rf[i]*i%mod; } int main(){init();scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)scanf("%d%d",&l[i],&r[i]);vector<pair<int,int> >V; V.clear();for(int i=1;i<=n;i++){V.push_back(make_pair(l[i]-1,1));V.push_back(make_pair(r[i],-1));}sort(V.begin(),V.end());long long ans=0;int cnt=0,pre;for(int i=0;i<V.size();i++){ans=(ans+C(cnt,k)*(V[i].first-pre))%mod;pre=V[i].first;cnt+=V[i].second;}printf("%lld\n",ans);return 0; }

注意組合數返回0的情況，WA了好多次，謹記謹記。

?

轉載于:https://www.cnblogs.com/forever97/p/Codeforces361.html

總結

以上是生活随笔為你收集整理的Codeforces Round #361(div 2)的全部內容，希望文章能夠幫你解決所遇到的問題。

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