Codeforces Round #193 (Div. 2)
5585 단어 codeforces
첫 번 째 문제: 문 제 는 구리 고 길 어서 오랫동안 읽 고 나 서 야 읽 었 다.
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++;
}
}
else
break;
}
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
",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
",t1+1,t2+1);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces Round #715 Div. 2C The Sports Festival: 구간 DP전형구간 DP의 초전형. 이하, 0-indexed. 입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다. 우선, 입력을 소트하여 n개의 요소를 $...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.