Codeforces Round #Pi (Div. 2)(A,B,C,D)

分类：CodeForces

A题：题目地址： Lineland Mail

using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const double pi= acos(-1.0);const double esp=1e-6;const int maxn=1e5+10;struct node{int id;int value;int Max;int Min;}q[maxn];int cmp(struct node a,struct node b){return a.value<b.value;}int cmp1(struct node a,struct node b){return a.id<b.id;}int main(){int n,i;while(~scanf(“%d”,&n)){for(i=1;i<=n;i++){scanf(“%d”,&q[i].value);q[i].id=i;q[q[i].id].Max=0;q[q[i].id].Min=0;}sort(q+1,q+n+1,cmp);for(i=1;i<=n;i++){if(i==1){q[i].Min=abs(q[1].value-q[2].value);q[i].Max=abs(q[n].value-q[1].value);}else if(i==n){q[i].Min=abs(q[n].value-q[n-1].value);q[i].Max=abs(q[n].value-q[1].value);}else{q[i].Min=min(abs(q[i].value-q[i-1].value),abs(q[i+1].value-q[i].value));q[i].Max=max(abs(q[i].value-q[1].value),abs(q[n].value-q[i].value));}}sort(q+1,q+1+n,cmp);for(i=1;i<=n;i++){printf(“%d %d\n”,q[i].Min,q[i].Max);}}return 0;}

B题：题目地址：Berland National Library

;LL;const int inf=0x3f3f3f3f;const double pi= acos(-1.0);const double esp=1e-6;const int maxn=110;const int maxn1=1e6+10;char str[10];int a;int vis[maxn1];int main(){int n;int cnt1,cnt2;while(~scanf(“%d”,&n)){memset(vis,0,sizeof(vis));cnt1=cnt2=0;for(int i=0;i<n;i++){scanf(“%s %d”,&str,&a);if(str[0]==’+’){cnt1++;vis[a]=1;cnt2=max(cnt1,cnt2);}else{if(!vis[a]){cnt2++;}else{vis[a]=0;cnt1–;}}}printf(“%d\n”,cnt2);}return 0;}

C题：题目地址：Geometric Progression 题意：求一个序列中形成以k为公比，项数为3的等比数列的种类数。思路：在这里我用map开了一个dp[i][j]数组，记录长度为i的以j结尾的数字有多少种，所以我们很容易得出dp[i][j]+=dp[i-1][j/k]，dp[1][j]=1。因为我在程序中是用x%k维护的，所以要倒推。因为数据问题map不要开map

;LL;const int inf=0x3f3f3f3f;const double pi= acos(-1.0);const double esp=1e-6;const int maxn=200010;LL a[maxn];int main(){map<LL,LL> dp[4];int n,k,i;LL ans;while(~scanf(“%d %d”,&n,&k)){ans=0;for(i=0;i<4;i++)dp[i].clear();for(i=1;i<=n;i++)scanf(“%lld”,&a[i]);for (i=1;i<=n;i++){if(a[i]%k==0){dp[3][a[i]]+=dp[2][a[i]/k];dp[2][a[i]]+=dp[1][a[i]/k];}dp[1][a[i]]++;}map<LL,LL>::iterator it;for (it=dp[3].begin();it!=dp[3].end();it++)ans+=it->second;printf(“%lld\n”,ans);}return 0;}

D题：题目地址：One-Dimensional Battle Ships 题意：给定一个区间，每次除去一个点，要求在剩下的空白里能放下，k个长为a的区间(a区间不能相离)。如果能放下，则输出-1，否则的话输出在去处第几个点的时候不能放下。思路：区间[l,r]每次去除一个点x，则当前剩下的区间为[l,x-1]，[x+1,r]。然后找每个区间可以放下的船数：(区间长度+1)/(船的长度+1)｛因为船和船之间相离，所以除以的是船的长度+1｝。二分答案去找第几个点让放的船数不足k。

;LL;const int inf=0x3f3f3f3f;const double pi= acos(-1.0);const double esp=1e-6;const int maxn=200010;int x[maxn];int x1[maxn];int n,k,a,m;int cnt;int Find(int m){for(int i=1;i<=m;i++)x1[i]=x[i];sort(x1+1,×1+m+1);int len=0;cnt=0;for(int i=1;i<=m;i++){cnt+=(x1[i]-len)/(a+1);len=x1[i];}cnt+=(n+1-len)/(a+1);if(cnt>=k)return 1;;}int main(){scanf(“%d %d %d”,&n,&k,&a);scanf(“%d”,&m);for(int i=1;i<=m;i++)scanf(“%d”,&x[i]);int l=1,r=m;int mid;int res=inf;while(l<=r){mid=(l+r)>>1;if(Find(mid)) l=mid+1;else {r=mid-1;res=min(res,mid);}}(l>m)puts(“-1”);elseprintf(“%d\n”,res);}

上一篇HDU 5349(2015多校5)-MZL's simple problem(优先队列)

顶1踩0

一遍一遍的……你突然明白自己还活着，

相关文章：

你感兴趣的文章：

标签云：