題目地址：?http://codeforces.com/contest/332

第一題：題目又臭又長，讀了好長時間才讀懂。

n個人，你是0號，從0開始到n-1循環做動作，只要你前面三個人動作一樣，你就喝一杯橙汁，問你能喝多少杯，

模擬

?

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cstdlib> #include <cmath> #include <vector> #include <list> #include <deque> #include <queue> #include <iterator> #include <stack> #include <map> #include <set> #include <algorithm> #include <cctype> using namespace std;typedef __int64 LL; const int N=20005; const LL II=1000000007; const int INF=0x3f3f3f3f; const double PI=acos(-1.0);char s[N];int main() {int i,j,n;while(cin>>n){scanf("%s",s);int len=strlen(s),sum=0;for(i=0;i<len;){if((i+n)<len){i=i+n;if(s[i-1]==s[i-2]&&s[i-2]==s[i-3]){sum++;}}elsebreak;}cout<<sum<<endl;}return 0; }

?

第二題：給你n個數，要你求一個k使得[a;?a + k - 1]?與[b;?b + k - 1]的和最大，保證這兩個集合不想交。

1、相當于兩個dp吧

?

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cstdlib> #include <cmath> #include <vector> #include <list> #include <deque> #include <queue> #include <iterator> #include <stack> #include <map> #include <set> #include <algorithm> #include <cctype> using namespace std;typedef __int64 LL; const int N=200005; const LL II=1000000007; const int INF=0x3f3f3f3f; const double PI=acos(-1.0);LL x[N]; LL dp[N];int main() {LL i,j,n,k;while(scanf("%I64d%I64d",&n,&k)!=EOF){for(i=1;i<=n;i++)scanf("%I64d",&x[i]);memset(dp,0,sizeof(dp));for(i=1;i<=k;i++)dp[1]+=x[i];for(i=2;i<=n-k+1;i++)dp[i]=dp[i-1]-x[i-1]+x[i+k-1];LL max1=dp[1],Max=0;int t1,t2,te=1;for(i=1+k;i<=n-k+1;i++){if((dp[i]+max1)>Max){Max=dp[i]+max1;t1=te; t2=i;}if(max1<dp[i-k+1]){max1=dp[i-k+1];te=i-k+1;}}printf("%d %d\n",t1,t2);}return 0; }

?

2、RMQ算法

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cstdlib> #include <cmath> #include <vector> #include <list> #include <deque> #include <queue> #include <iterator> #include <stack> #include <map> #include <set> #include <algorithm> #include <cctype> using namespace std;typedef __int64 LL; const int N=200005; const LL II=1000000007; const int INF=0x3f3f3f3f; const double PI=acos(-1.0);LL x[N]; LL dp[N]; LL d[N][20];LL RMQ(int l,int r) {int k=0;while((1<<(k+1))<=(r-l+1))k++;return max(d[l][k],d[r-(1<<k)+1][k]); }int main() {int i,j,n,k;while(scanf("%d%d",&n,&k)!=EOF){for(i=0;i<n;i++)scanf("%I64d",&x[i]);memset(dp,0,sizeof(dp));for(i=0;i<k;i++)dp[0]+=x[i];int p=n-k+1;for(i=1;i<p;i++)dp[i]=dp[i-1]-x[i-1]+x[i+k-1];for(i=0;i<p;i++)d[i][0]=dp[i];for(j=1;(1<<j)<=p;j++)for(i=0;i+(1<<j)-1<p;i++)d[i][j]=max(d[i][j-1],d[i+(1<<(j-1))][j-1]);LL Max=0,tmp,kk;int t1,t2;for(i=0;i<p;i++){if((i+k)<p){LL s=dp[i]+(tmp=RMQ(i+k,p-1));if(Max<s){Max=s; kk=tmp;t1=i; t2=i+k;}}}for(j=t2;j<p;j++)if(dp[j]==kk){t2=j;break;}printf("%d %d\n",t1+1,t2+1);}return 0; }

?

?

轉載于:https://www.cnblogs.com/jiangu66/p/3214928.html

總結

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

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