SRM 596 DIV 2
6982 단어 div
1. 250pt FoxAndSightseeing
제목의 뜻
n개의 도시의 위치를 드리겠습니다. 그들은 같은 직선에 있습니다. 그 중 어느 도시를 뛰어넘고 순서대로 다른 도시를 방문하여 거리의 최소치를 구하도록 요구합니다.
문제풀이
데이터 크기가 n<=50이므로 직접 일일이 열거하면 됩니다.
코드:class FoxAndSightseeing
{
public:
int getMin(vector <int> position)
{
int ans=INF;
for(int i=1;i<position.size()-1;i++)
{
int sum=0,pre=position[0];
for(int j=1;j<position.size();j++)
{
if(j==i) continue;
sum+=abs(position[j]-pre);
pre=position[j];
}
if(sum<ans) ans=sum;
}
return ans;
}
};
2. 500pt ColorfulRoa
제목의 뜻
n개의 점을 정하고 점마다 색깔이 있다(R, G, B는 각각 빨간색, 녹색, 파란색을 표시한다). 그 중 일부 점을 선택하여 총 비용을 최소화해야 한다.선택한 점 중 인접한 두 점 사이에 비용이 하나 있는데 i와 j를 선택했다고 가정하면 비용은 (i-j)*(i-j)이고 선택한 점의 색깔은 R, G, B, R, G, B...
문제풀이
물이 많은 DP, 방정식은 dp[i]=min(dp[i], dp[j]+(i-j)*(i-j)))((cr[j]='R'&&&cr[i]=='G')|(cr[j]='G'&&cr[i]='B')|(cr[j]='B'&&cr[i]='R')
코드:int dp[20];
bool check(char a,char b)
{
return (a=='R'&&b=='G')||(a=='G'&&b=='B')||(a=='B'&&b=='R');
}
class ColorfulRoad
{
public:
int getMin(string road)
{
int i,j;
memset(dp,INF,sizeof(dp));
dp[0]=0;
FOR(i,1,road.size()-1)
REP(j,i)
if(check(road[j],road[i]))
dp[i]=min(dp[i],dp[j]+(i-j)*(i-j));
return dp[road.size()-1]==INF?-1:dp[road.size()-1];
}
};
3. 1000pt SparseFactorialDiv2
제목의 대의.
정수 n에 대해 우리는 F (n) = (n - 0^2) * (n - 1^2) * (n - 2^2) * (n - 3^2) *... *(n-k^2), k는 n-k^2>0의 최대 정수입니다.로,hi, 그리고 p (소수) 를 정하면 로<=n<=hi에서 F (n) 를 디바이저에 의해 정제할 수 있는 n의 개수를 계산하십시오.
문제풀이
p는 소수이기 때문에 F (n) 가 p로 정제될 수 있다면 F (n) 의 어떤 인자 (n-i^2) 가 p로 정제될 수 있음을 의미한다
수학적으로 (n-i^2)%p==0으로 표시
n≡i^2(mod p)
n=i^2+x*p
그러면 i마다 x=(n-i^2)/p개가 상황에 부합되면 우리는 i를 일일이 들기만 하면 된다. 그러나 주의해야 할 것은 이렇게 중복 계산이 된다는 것이다. 따라서 i^2 ≡ j^2(modp)(i코드:map<LL,int>ms;
LL getAns(LL r,LL p)
{
ms.clear();
LL ans=0;
for(LL i=0; i*i<=r; i++)
{
if(ms[i*i%p]) continue;
ans+=(r-i*i)/p;
ms[i*i%p]++;
}
return ans;
}
class SparseFactorialDiv2
{
public:
LL getCount(LL lo, LL hi, LL divisor)
{
return getAns(hi,divisor)-getAns(lo-1,divisor);
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HTML] <div>와 <span>
웹 페이지에서 공간을 분할하는 것은 중요합니다.
문서 구조를 쉽게 파악할 뿐만 아니라, 문제가 생기면 해당 부분만 건드리면 되기 때문이죠.
또한 분할을 하면 태그를 관리하기가 쉬워집니다.
웹 페이지의 공간을 분할 한...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
class FoxAndSightseeing
{
public:
int getMin(vector <int> position)
{
int ans=INF;
for(int i=1;i<position.size()-1;i++)
{
int sum=0,pre=position[0];
for(int j=1;j<position.size();j++)
{
if(j==i) continue;
sum+=abs(position[j]-pre);
pre=position[j];
}
if(sum<ans) ans=sum;
}
return ans;
}
};제목의 뜻
n개의 점을 정하고 점마다 색깔이 있다(R, G, B는 각각 빨간색, 녹색, 파란색을 표시한다). 그 중 일부 점을 선택하여 총 비용을 최소화해야 한다.선택한 점 중 인접한 두 점 사이에 비용이 하나 있는데 i와 j를 선택했다고 가정하면 비용은 (i-j)*(i-j)이고 선택한 점의 색깔은 R, G, B, R, G, B...
문제풀이
물이 많은 DP, 방정식은 dp[i]=min(dp[i], dp[j]+(i-j)*(i-j)))((cr[j]='R'&&&cr[i]=='G')|(cr[j]='G'&&cr[i]='B')|(cr[j]='B'&&cr[i]='R')
코드:
int dp[20];
bool check(char a,char b)
{
return (a=='R'&&b=='G')||(a=='G'&&b=='B')||(a=='B'&&b=='R');
}
class ColorfulRoad
{
public:
int getMin(string road)
{
int i,j;
memset(dp,INF,sizeof(dp));
dp[0]=0;
FOR(i,1,road.size()-1)
REP(j,i)
if(check(road[j],road[i]))
dp[i]=min(dp[i],dp[j]+(i-j)*(i-j));
return dp[road.size()-1]==INF?-1:dp[road.size()-1];
}
};3. 1000pt SparseFactorialDiv2
제목의 대의.
정수 n에 대해 우리는 F (n) = (n - 0^2) * (n - 1^2) * (n - 2^2) * (n - 3^2) *... *(n-k^2), k는 n-k^2>0의 최대 정수입니다.로,hi, 그리고 p (소수) 를 정하면 로<=n<=hi에서 F (n) 를 디바이저에 의해 정제할 수 있는 n의 개수를 계산하십시오.
문제풀이
p는 소수이기 때문에 F (n) 가 p로 정제될 수 있다면 F (n) 의 어떤 인자 (n-i^2) 가 p로 정제될 수 있음을 의미한다
수학적으로 (n-i^2)%p==0으로 표시
n≡i^2(mod p)
n=i^2+x*p
그러면 i마다 x=(n-i^2)/p개가 상황에 부합되면 우리는 i를 일일이 들기만 하면 된다. 그러나 주의해야 할 것은 이렇게 중복 계산이 된다는 것이다. 따라서 i^2 ≡ j^2(modp)(i코드:map<LL,int>ms;
LL getAns(LL r,LL p)
{
ms.clear();
LL ans=0;
for(LL i=0; i*i<=r; i++)
{
if(ms[i*i%p]) continue;
ans+=(r-i*i)/p;
ms[i*i%p]++;
}
return ans;
}
class SparseFactorialDiv2
{
public:
LL getCount(LL lo, LL hi, LL divisor)
{
return getAns(hi,divisor)-getAns(lo-1,divisor);
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HTML] <div>와 <span>
웹 페이지에서 공간을 분할하는 것은 중요합니다.
문서 구조를 쉽게 파악할 뿐만 아니라, 문제가 생기면 해당 부분만 건드리면 되기 때문이죠.
또한 분할을 하면 태그를 관리하기가 쉬워집니다.
웹 페이지의 공간을 분할 한...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
map<LL,int>ms;
LL getAns(LL r,LL p)
{
ms.clear();
LL ans=0;
for(LL i=0; i*i<=r; i++)
{
if(ms[i*i%p]) continue;
ans+=(r-i*i)/p;
ms[i*i%p]++;
}
return ans;
}
class SparseFactorialDiv2
{
public:
LL getCount(LL lo, LL hi, LL divisor)
{
return getAns(hi,divisor)-getAns(lo-1,divisor);
}
};이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HTML] <div>와 <span>웹 페이지에서 공간을 분할하는 것은 중요합니다. 문서 구조를 쉽게 파악할 뿐만 아니라, 문제가 생기면 해당 부분만 건드리면 되기 때문이죠. 또한 분할을 하면 태그를 관리하기가 쉬워집니다. 웹 페이지의 공간을 분할 한...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
