[NOIP 2015 시 뮬 레이 션 11.3] IOIOI 카드 점
네가 본 제목 처럼 지금 은 A 개의 I 가 있 고 B 개의 O 에 이 어 C 개의 I 에 이 어 D 개의 O 에 이 어 E 개의 I 에 이 어 한 줄 로 서 있다.당신 은 지금 N 가지 조작 이 있 습 니 다. i 번 째 조작 이 있 습 니 다. li 번 째 문자 부터 ri 번 째 문자 까지 이 구간 의 문자, I 는 O, O 는 I 가 되 고 시간 은 ri - li + 1 입 니 다.모든 문 자 를 I 의 최소 시간 으로 바 꿔 주세요.풀 리 지 않 으 면 출력 - 1.A,B,C,D,E,N<=10^5
Solution
신기 한 문제.먼저%% 출제 자, 이런 생각 을 누가 얻 고 싶 어 요 ~ Japanese... 우선, 우 리 는 새로운 서열 b, bi = ai ^ ai + 1 을 만 들 었 습 니 다. 이렇게 b 중 에 0 이 쌓 였 고 중간 에 4 개 1 이 있 습 니 다.그렇다면 한 번 의 조작 은 무엇 에 해당 합 니까?bl - 1 과 br 를 반대 하 는 것 과 같 습 니 다!(왜 그런 지 생각해 보 세 요) 그러면 우 리 는 l - 1 에서 r 로 길 이 를 r - l + 1 의 변 으로 연결 할 수 있 습 니 다.그리고 우리 의 임 무 는 b 서열 을 0 으로 바 꾸 는 것 이 되 었 다.(왜 그런 지 생각해 보 세 요) 그러면 우 리 는 spfa / 디 제 스 트 라 만 때 리 면 됩 니 다.하지만 동 나리 의 테스트 를 통 해 디 제 스 트 라 는 넘 지 못 할 것 같 습 니 다.
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a) for(int i=last[a];i;i=next[i])
#define N 500005
#define ll long long
using namespace std;
int n,tot,g[3][4]={0,1,2,3,0,2,1,3,0,3,1,2};
int t[N*2],next[N*2],last[N],a[5],d[N*2];
ll dis[N],v[N*2],ans,l,r;
bool bz[N];
void add(int x,int y,ll z){
t[++tot]=y;v[tot]=z;next[tot]=last[x];last[x]=tot;
}
ll spfa(int S,int T) {
memset(dis,127,sizeof(dis));
ll mx=dis[S];dis[S]=0;
memset(bz,0,sizeof(bz));bz[S]=1;
int i=0,j=1;d[1]=S;
while (i<j) {
rep(k,d[++i]) if (dis[t[k]]>dis[d[i]]+v[k]) {
dis[t[k]]=dis[d[i]]+v[k];
if (!bz[t[k]]) bz[t[k]]=1,d[++j]=t[k];
}
bz[d[i]]=0;
}
if (dis[T]==mx) return -1;else return dis[T];
}
int main() {
freopen("card.in","r",stdin);
freopen("card.out","w",stdout);
fo(i,0,4) scanf("%d",&a[i]),a[i]+=a[i-1];
scanf("%d",&n);ans=100000000000;
fo(i,1,n) scanf("%lld%lld",&l,&r),add(l-1,r,r-l+1),add(r,l-1,r-l+1);
fo(i,0,2) {
ll x=spfa(a[g[i][0]],a[g[i][1]]),y=spfa(a[g[i][2]],a[g[i][3]]);
if (x==-1||y==-1) continue;
ans=min(ans,x+y);
}
if (ans==100000000000) printf("-1");else printf("%lld",ans);
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
hdu 1233 또는 원활 한 공정 최소 생 성 트 리 (prim 알고리즘 + kruskal 알고리즘)그럼 이 연결 서브 맵 은 G 의 최소 생 성 트 리 입 니 다.최소 생 성 트 리 를 구 하 는 흔 한 알고리즘 은 Prim 알고리즘 입 니 다. 욕심 전략 을 사용 하기 때문에 집합 S 에 새로운 정점 을 추가 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
