【Educational Codeforces Round 58 (Rated for Div. 2)】A.B.C.D.E.F.G
89033 단어 개인 훈련 계획Codeforces
A. Minimum Integer
제목의 뜻
q번의 질문을 주고 매번 질문은 l,r,d를 주며 [l,r][l,r][l,r]에 없는 d의 최소 배수는 얼마입니까?
방법
1: l > d − > d l>d ->d l>d−>d 2: ( r d + 1 ) × d\left(\frac{r}{d}+1\right)\times d (dr+1)×d 코드#include
",c);
else printf("%lld
",1LL*(b/c+1)*c);
}
return 0;
}
B. Accordion
제목의 뜻
아코디언의 모양을'[:'+k*'|'+':]'로 정의하면 k는 어떠한 자연수도 될 수 있다.주어진 문자열은 일부 문자를 삭제한 후에 얻을 수 있는 가장 긴 아코디언의 길이를 묻는다
방법
왼쪽에서 오른쪽으로 첫 번째 "[다음"을 찾습니다. 찾을 수 없습니다. [또는 찾을 수 없습니다:, 되돌아오기-1 오른쪽에서 왼쪽으로 첫 번째 "]"그전"을 찾습니다. 찾을 수 없습니다. [또는 찾을 수 없습니다: 이전에 찾았던 것: 왼쪽, 되돌아오기-1두 개: 겹칠 때도 되돌아오기-1. 마지막 답은 4+ 두 짝퉁 사이의 | 개수입니다.
코드
#include
");
return 0;
}
int tt=0;
int cnt=0;
int pos1=-1,pos2=-1;
for(int i=0;i<len;i++)
{
if(tt==0&&str[i]=='[')
{
tt++;
cnt++;
}
else if(tt==1&&str[i]==':')
{
tt++;
cnt++;
pos1=i;
break;
}
}
if(pos1==-1)
{
printf("-1
");
return 0;
}
tt=0;
for(int i=len-1;i>=0;i--)
{
if(tt==0&&str[i]==']')
{
tt++;
cnt++;
}
else if(tt==1&&str[i]==':')
{
tt++;
cnt++;
pos2=i;
break;
}
}
if(tt==0||pos1>=pos2)
{
printf("-1
");
return 0;
}
int ans=4;
for(int i=pos1+1;i<=pos2-1;i++)
{
if(str[i]=='|') ans++;
}
printf("%d
",ans);
return 0;
}
C. Division and Union
제목의 뜻
n개의 라인을 드릴게요. 라인을 두 개의 집합으로 나눌 수 있냐고 물어보세요. 서로 다른 집합에서 온 라인이 교점이 없도록 하세요.
방법
첫 번째 단락에 틈이 생긴 라인을 꺼내서 첫 번째 집합에 넣고 나머지 라인은 두 번째 집합에 놓으면 된다.
코드
#include
");
continue;
}
for(int i=1;i<=n;i++)
{
printf("%d",ans[i]);
if(i==n) printf("
");
else printf(" ");
}
}
return 0;
}
제목의 뜻
n개의 점을 가진 트리를 드리겠습니다. i개의 점의 값은 a[i]입니다. 나무의 가장 긴 경로를 구하고 경로의 모든 점권을 만족시키는 gcd은 1이 아닙니다.1 < = n < = 2 ∗ 1 0 5 1<=n<=2*10^5 1<=n<=2∗105 1 < = a i < = 2 ∗ 1 0 5 1<=a_i<=2*10^5 1<=ai<=2∗105 방법
우선
gcd이 질인자면 충분하다는 것을 생각해야 한다. 즉, 가장 긴 경로의 공약수가 질수라는 것이 틀림없다.그 다음에 2 1 0 5 * 105 2 105보다 적은 수의 104591410개의 질인자가 가장 많이 존재하는 이유는 2\33877\877 11\8717 = 510> 2\8710 1 0 5 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * ∗17=510>2∗105 따라서 나무의 각 점에 대해 이 질인자가 가장 아래로 뻗을 수 있는 길이만 요구한다.우리는 7이 i를 기점으로 하는 i의 자수로 뻗은 dp[i][j]이 gcd의 제j개 질인자의 가장 긴 사슬의 길이이다.그러면 매번 a[i]을 갱신할 때마다 그의 어떤 아들도 이 질인자를 함유하고 있다. 우리가 dp[i][j]을 갱신하려면 이 질인자가 그의 아들의 몇 번째 질인자라는 것을 알아야 한다. 그래서 우리가 예처리할 때 dp[i][j]으로 저장한다. map은 map[pair]=k이 i에서 j의 질인자라고 한다.저장 질량 인자는 k으로 저장하고 vector은 i의 G[i][j]번째 질량 인자가 무엇인지 나타낸다.이렇게 하면 우리는 j의 이전 방정식을 갱신할 수 있다. 현재 방문한 결점은 dp[i][j]이고 이전할 질인자는 rt개이며 현재 방문한 아들은 j개이다. if(a[to]%G[rt][j]==0)
int pos=mp[pii(G[rt][j],to)];//rt j to pos
dp[rt][j]=max(dp[rt][j],dp[to][pos]+1);
to과 같이 우리는 모든 아들 중 갱신할 수 있는 아버지의 dp개 인자의 j값을 앞의 두 가지, 즉 dp을 뿌리로 하는 자수에서 rt은 gcd의 a[rt]의 j개 질인자의 가장 긴 경로를 찾았다.마지막으로 각 자수 안의 모든 질인자가 도달할 수 있는 가장 긴 경로에 대해 max을 취하는 것이 답이다.코드
#include
",ans);
return 0;
}
E. Polycarp’s New Job
제목의 뜻
모두 q회 조작이 있는데 매번 조작에는 두 가지 유형이 있다. 첫 번째 유형은
+ x y이고 x*y의 직사각형을 추가한다. 두 번째 유형은 ? h w이다. 현재 모든 직사각형을 중첩할 수 있다. h*w의 직사각형으로 앞의 좌우 직사각형을 덮을 수 있느냐방법
방법은 최소한 필요한 직사각형의 길이와 넓이를 유지하는 것이다.긴 maxh는 모든 덧붙인 직사각형의 긴 max 넓이 maxw는 모든 덧붙인 직사각형의 넓이 max 이후 검사할 각 직사각형에 대해 maxh<=max(h,w) & & & maxw<=min(h,w)만 있으면 YES 그렇지 않으면 NO
코드
#includeF. Ivan and Burgers
제목의 뜻
n개 도시가 x축에 있고 m대의 트럭이 있으며 트럭마다 네 가지 속성이 있다. 그것이 바로 시작 도시 s, 중지 도시 f, 킬로미터당 연료 연료 소모 c, 주유 가능 횟수 r이다.매번 주유 트럭의 유량이 가득 차면 트럭의 유량은 V이고 모든 트럭의 초기 유량은 가득 차 있다.모든 트럭이 기점에서 종점까지의 최소 유량 V를 구할 수 있도록 하세요.
2 < = n < = 400 , 1 < = m < = 250000 2<=n<=400,1<=m<=250000 2<=n<=400,1<=m<=250000 1 < = a i < = 1 0 9 , a i < a i + 1 1<=a_i<=10^9,a_i
#include
",ans);
return 0;
}
먼저 우리는 1차원을 스크롤할 수 있고 그 다음에 맥스 양(d p [i] [l] [k: 1], a [j] - a [l])\max\left(dp\left[i\right]\left[l\right]\left[l\right]\left[k-1\right], a\left[j\right] -a\left[l\right]\right] max (dp[i][i][l] [l]]]]][ik]]]]], [ja]a] [aaaaal[j\right]]]]], 이 단조로운 의사결정은 [단조로운 의사결정], [rightt[l[l]]]는 [단우리는 단조로운 대기열 유지보수만 하면 복잡도가 n3n^3n3로 변한다
코드
#include
",ans);
return 0;
}
G. (Zero XOR Subset)-less
제목의 뜻
문제는 길이가 n인 서열의 개수 크기가 a[i]인 당신에게 서열을 여러 개의 연속적인 단락으로 나누어 달라고 요구하는 것입니다. 그 단락이 다르거나 답이 0이 아니더라도 최대 몇 단락으로 나눌 수 있는지 물어보세요.
1 < = n < = 2 ∗ 1 0 5 1<=n<=2*10^5 1<=n<=2∗105 0 < = a i < = 1 0 9 0<=a_i<=10^9 0<=ai<=109 방법
우선 답안은 연속적인 단락을 요구하기 때문에 단락마다 다른 값이나 합이 하나의 값이다. 이 값은 두 개의 접두사 다른 값과 다른 값을 통해 얻을 수 있다. 그러면 단락의 값은 접두사 다른 값과 다른 값으로 전환된다. 그러면 문제는 n개의 값을 주고 그 중에서 가능한 한 많은 값을 골라서 이 값들이 임의로 조합되거나 합쳐지지 않도록 한다.이것은 선형기의 고전적인 문제가 된다.n개의 접두사가 다르거나 화합된 선형 기반을 직접 구성하고 기저의 개수가 바로 답이다.
코드
#include
");
return 0;
}
int ans=0;
for(int i=31;i>=0;i--) if(p[i]) ans++;
printf("%d
",ans);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Educational Codeforces Round 58 (Rated for Div. 2)】A.B.C.D.E.F.G제목의 뜻 q번의 질문을 주고 매번 질문은 l,r,d를 주며 [l,r][l,r][l,r]에 없는 d의 최소 배수는 얼마입니까? 제목의 뜻 제목의 뜻 제목의 뜻n개의 점을 가진 트리를 드리겠습니다. 제목의 뜻 제목의 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
