블 루 브리지 컵 온라인 테스트 문제 풀이(2)
제목 주소:http://lx.lanqiao.org/index.page
지난번 에는 너무 길 어서 저장 이 느 려 서 한 편 을 더 쓰기 로 했 습 니 다.
블 루 브리지 컵 온라인 테스트 문제 풀이(1)http://blog.csdn.net/murmured/article/details/18908567(초보 자 추천,다 물 문제)
알고리즘 트 레이 닝-젖소 위로
문제 설명
Farmer John 은 매우 게 을 러 져 서 더 이상 젖소 들 사이 에서 통행 할 수 있 는 길 을 지 키 고 싶 지 않 았 다.도 로 는 N 개의 목장 을 연결 하 는 데 사용 되 고 목장 은 1 부터 N 까지 연속 으로 번 호 를 매 긴 다.모든 목장 은 젖소 의 집 이다.FJ 는 P 개 도로 중 가능 한 한 많은 도 로 를 제외 하고 목장 간 연계 성 을 유지 할 계획 이다.너 는 우선 그 도로 들 이 보존 해 야 할 N-1 도로 라 는 것 을 결정 해 야 한다.제 j 조 양 방향 도 로 는 목장 Sj 와 Ej(1<=Sj)를 연결 했다. <= N; 1 <= Ej <= N; Sj != Ej)그리고 가 려 면 Lj 의 시간 이 필요 합 니 다.한 길 이상 의 도로 로 연 결 된 목장 은 두 군데 도 없다.젖소 들 은 교통 시스템 이 삭감 되 었 기 때문에 매우 상심 했다.너 는 모든 젖소 의 거처 로 가서 그들 을 위로 해 야 한다.당신 이 제 i 목장 에 도착 할 때마다(당신 이 이미 도 착 했 더 라 도)당신 은 Ci 에 가서 젖소 와 이 야 기 를 나 누 어야 합 니 다.젖소 들 이 슬픔 에서 정신 을 차 릴 때 까지 밤마다 같은 목장 에서 밤 을 지 낸다.아침 에 일어나 서 저녁 에 돌아 가서 잘 때 는 당신 이 자 는 목장 에 있 는 젖소 와 이 야 기 를 해 야 합 니 다.이렇게 해야만 너 는 너의 대화 임 무 를 완성 할 수 있다.만약 Farmer John 이 당신 의 건 의 를 받 아 들 였 다 고 가정 하면 모든 젖소 가 위 로 받 을 수 있 는 최소한 의 시간 을 계산 해 보 세 요.
입력 형식
첫 번 째 줄 은 두 개의 정수 N 과 P 를 포함한다.
다음 N 줄 은 줄 마다 정수 Ci 를 포함 합 니 다.
다음 P 줄 은 각 줄 에 세 개의 정수 Sj,Ej 와 Lj 를 포함한다.
출력 형식
하나의 정 수 를 출력 하 는 데 필요 한 총 시간(당신 이 있 는 목장 에 있 는 젖소 와 의 두 번 의 대화 시간 포함).
샘플 입력
5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6
샘플 출력
176
데이터 규모 와 약정
5 <= N <= 10000，N-1 <= P <= 100000，0 <= Lj <= 1000，1 <= Ci <= 1,000。
문제 의 테스트 샘플 이 잘못 되 었 습 니 다.(P 가 7 인 데 왜 6 조 입 니까?나 는 문제 의 7 을 6 으로 고 쳤 다.답 은 178 이다)
5 6 10 10 20 6 30 1 2 5 2 3 5 2 4 12 3 4 17 2 5 15 3 5 6
생각:
직접 변 의 가중치 w(u,v)를 2*w(u,v)+cost[u]+cost[v]로 바 꾸 고 MST 를 구 합 니 다.why?
종이 에 이 데 이 터 를 그 려 라(정 답 43)
3 2 5
6
7
1 2 3 2 3 4
그리고 그 는 밤 을 지 낼 곳 을 찾 아야 하기 때문에 조금 더 많은 대 화 를 하고 가장 작은 곳 을 찾 아 밤 을 지 냈 으 면 좋 겠 다~히히~
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=10000+10;
const int MAXM=100000+10;
const int INF=100000;
int cost[MAXN],fa[MAXN];
int find(int cur)
{
return cur==fa[cur]? cur:fa[cur]=find(fa[cur]);
}
struct edge
{
int from,to,val;
bool operator <(const edge& x)const{
return val<x.val;
}
}e[MAXM];
int main()
{
int mini=INF,index;
int n,p;
scanf("%d%d",&n,&p);
for(int i=1;i<=n;i++)
{
scanf("%d",&cost[i]);
mini=min(cost[i],mini);
fa[i]=i;
}
for(int i=0;i<p;i++)
{
scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].val);
e[i].val=(e[i].val<<1)+cost[ e[i].from ] + cost [ e[i].to ];
}
sort(e,e+p);
int ans=0;
for(int i=0;i<p;i++)
{
int x=e[i].from,y=e[i].to;
int root_x=find(x),root_y=find(y);
if(root_x==root_y) continue;
fa[root_x]=root_y;
ans+=e[i].val;
}
printf("%d
",ans+mini);
return 0;
}
알고리즘 트 레이 닝-최 단 길
문제 설명
n 개의 정점 을 지정 합 니 다.m 개의 변 에 방향 그림 이 있 습 니 다.(그 중 일부 변 권 은 마이너스 일 수 있 지만 마이너스 고리 가 없 음 을 보증 합 니 다)1 번 점 에서 다른 점 까지 의 최 단 로 를 계산 하 세 요.
입력 형식
첫 줄 두 개의 정수 n,m.
다음 m 줄 은 줄 마다 세 개의 정수 u,v,l 이 있 는데 u 에서 v 까지 길이 가 l 인 변 이 있 음 을 나타 낸다.
출력 형식
모두 n-1 줄 이 고 i 줄 은 1 번 점 에서 i+1 번 점 까지 의 최 단 로 를 나타 낸다.
샘플 입력
3 3
1 2 -1
2 3 -1
3 1 2
샘플 출력
-1
-2
데이터 규모 와 약정
10%의 데이터 에 대해 n=2,m=2.
30%의 데이터 에 대해 n<=5,m<=10.
100%의 데이터 에 대하 여 1<=n<=20000,1<=m<=20000,-1000<=l<=10000,임의의 정점 에서 다른 모든 정점 에 도달 할 수 있 도록 보장 합 니 다.
직접 SPFA,직접 100 점.
금 낭 을 열 어 최 적 화 된 dijkstra 를 쌓 아 라...제목 은 마이너스 야!너 는 이것 이 임 시직 이 쓴 것 이 아니 라 고 확신 하 니?아니면 내 수준 이 한계 가 있 는 거 야?가르침 을 바 랍 니 다.
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN=20000+10;
const int MAXM=200000+10;
const int INF=100000;
int head[MAXN],len,dis[MAXN],n,m;
bool vis[MAXN];
struct edge
{
int to,val,next;
}e[MAXM];
void add(int from,int to,int val)
{
e[len].to=to;
e[len].val=val;
e[len].next=head[from];
head[from]=len++;
}
queue<int> q;
void spfa()
{
for(int i=1;i<=n;i++)
dis[i]=INF;
memset(vis,0,sizeof(vis));
q.push(1);
vis[1]=true;
dis[1]=0;
while(!q.empty())
{
int cur=q.front();
q.pop();
vis[cur]=false;
for(int i=head[cur];i!=-1;i=e[i].next)
{
int id=e[i].to;
if(dis[id] > dis[cur] + e[i].val)
{
dis[id] = dis[cur] + e[i].val;
if(!vis[id])
{
vis[id]=true;
q.push(id);
}
}
}
}
}
int main()
{
memset(head,-1,sizeof(head));
len=0;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
int from,to,val;
scanf("%d%d%d",&from,&to,&val);
add(from,to,val);
}
spfa();
for(int i=2;i<=n;i++)
printf("%d
",dis[i]);
return 0;
}
알고리즘 훈련-구간 k 대수 조회
문제 설명
시퀀스 를 지정 합 니 다.매번 질문 시퀀스 의 l 번 째 숫자 에서 r 번 째 숫자 에서 K 번 째 로 큰 숫자 는 무엇 입 니까?
입력 형식
첫 번 째 줄 은 n 을 포함 하여 시퀀스 의 길 이 를 표시 합 니 다.
두 번 째 줄 은 n 개의 정 수 를 포함 하고 주어진 서열 을 표시 합 니 다.
세 번 째 는 정수 m 를 포함 하여 질문 개 수 를 나타 낸다.
다음 m 줄,각 줄 의 세 번 째 수 l,r,K 는 질문 서열 이 왼쪽 에서 오른쪽으로 l 번 째 수 에서 r 번 째 수 까지 크 고 작은 K 번 째 큰 수 는 어느 것 인지 나타 낸다.시퀀스 요 소 는 1 부터 레이 블 을 시작 합 니 다.
출력 형식
총 m 줄 을 출력 하고 줄 마다 숫자 를 입력 하여 질문 의 답 을 표시 합 니 다.
샘플 입력
5
1 2 3 4 5
2
1 5 2
2 3 2
샘플 출력
4
2
데이터 규모 와 약정
30%의 데이터 에 대해 n,m<=100;
100%의 데이터 에 대해 n,m<=1000;
보증 k<=(r-l+1),서열 중의 수<=106.
제목 을 처음 보고 나 무 를 나 누 자!놀 라 서 오줌 을 쌌 다.규 모 를 보 니...1000.。정렬 할 게 요.
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1000+10;
int a[MAXN];
bool cmp(int x,int y)
{
return x>y;
}
int main()
{
int n,m;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
scanf("%d",&m);
while(m--)
{
int temp[MAXN],len=0;
int from,to,k;
scanf("%d%d%d",&from,&to,&k);
for(int i=from;i<=to;i++)
temp[len++]=a[i];
sort(temp,temp+len,cmp);
printf("%d
",temp[k-1]);
}
return 0;
}
알고리즘 트 레이 닝.-K 스트라이크.
문제 설명
만약 자연수 N 의 K 진법 이 임의의 인접 한 두 사람 이 모두 인접 한 숫자 가 아니 라 는 것 을 나타 낸다 면 우 리 는 이 숫자 가 K 의 좋 은 숫자 라 고 말 할 것 이다.L 비트 K 진수 중 K 의 좋 은 수 를 구하 세 요.예 를 들 어 K=4,L=2 일 때 모든 K 호 수 는 11,13,20,22,30,31,33 총 7 개 였 다.이 숫자 가 매우 많 기 때문에 1000000007 모델 을 추출 한 후의 값 을 출력 해 주 십시오.
입력 형식
두 개의 정수,K 와 L 을 포함 하 는 것 을 입력 하 십시오.
출력 형식
하나의 정 수 를 출력 하여 1000000007 에 대한 정 답 을 표시 합 니 다.
샘플 입력
4 2
샘플 출력
7
데이터 규모 와 약정
30%의 데이터 에 대해 KL <= 106；
50%의 데이터 에 대해 K<=16,L<=10;
100%의 데이터 에 대해 1<=K,L<=100.
#include<cstdio>
const int MAXN=100+10;
const int mod=1000000007;
__int64 dp[MAXN][MAXN];
int main()
{
// dp[i][j] j i k
int k,L;
scanf("%d%d",&k,&L);
for(int i=1;i<k;i++)
dp[1][i]=1;
for(int i=2;i<=L;i++)
for(int j=0;j<k;j++)
for(int x=0;x<k;x++)
if(x!=j-1 && x!=j+1)
dp[i][j]=(dp[i][j]+dp[i-1][x])%mod;
__int64 ans=0;
// L 0~k-1 k
for(int i=0;i<k;i++)
ans=(ans+dp[L][i])%mod;
printf("%I64d
",ans);
return 0;
}알고리즘 트 레이 닝-조작 칸
문제 설명
n 개의 칸 이 있 는데 왼쪽 에서 오른쪽으로 한 줄 로 놓 고 번 호 는 1-n 입 니 다.
모두 m 회 조작 이 있 고 3 가지 조작 유형 이 있 습 니 다.
1.칸 의 가중치 수정,
2.한 단락 의 격자 값 과,
3.칸 의 최대 치 를 연속 으로 구 합 니 다.
2,3 동작 마다 원 하 는 결 과 를 출력 합 니 다.
입력 형식
첫 줄 두 개의 정수 n,m.
다음 줄 n 개의 정 수 는 n 개의 칸 의 초기 값 을 표시 합 니 다.
다음 m 줄 은 줄 당 3 개의 정수 p,x,y,p 는 조작 유형 을 나타 내 고 p=1 시 에는 격자 x 의 가중치 가 y 이 고 p=2 시 에는 구간[x,y]내 격자 의 가중치 와,p=3 시 에는 구간[x,y]내 격자 의 가장 큰 가중치 를 나타 낸다.
출력 형식
몇 줄 이 있 는데,줄 수 는 p=2 또는 3 의 조작 총수 와 같다.
줄 당 1 개의 정 수 는 p=2 또는 3 작업 의 결과 에 대응 합 니 다.
샘플 입력
4 3
1 2 3 4
2 1 3
1 4 3
3 1 4
샘플 출력
6
3
데이터 규모 와 약정
20%의 데이터 n<=100,m<=200.
50%의 데이터 n<=5000,m<=5000.
100%의 데이터 에 대해 1<=n<=100000,m<=100000,0<=격자 값<=10000.
선분 나무 물 판~
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=100000+10;
int a[MAXN],maxv[MAXN<<2],sum[MAXN<<2];
void build(int k,int L,int R)
{
if(L==R) {
sum[k]=maxv[k]=a[L];
}
else
{
int m=(L+R)>>1;
build(k<<1,L,m);
build((k<<1)+1,m+1,R);
sum[k]=sum[k<<1]+sum[(k<<1)+1];
maxv[k]=max(maxv[k<<1],maxv[(k<<1)+1]);
}
}
void update(int k,int L,int R,int p,int v)
{
if(L==R){
sum[k]=maxv[k]=v;
}
else
{
int m=(L+R)>>1;
if(p<=m) update(k<<1,L,m,p,v);
if(m<p) update((k<<1)+1,m+1,R,p,v);
sum[k]=sum[k<<1]+sum[(k<<1)+1];
maxv[k]=max(maxv[k<<1],maxv[(k<<1)+1]);
}
}
int getsum(int k,int L,int R,int a,int b)
{
if(a<=L && R<=b)
return sum[k];
else
{
int res=0,m=(L+R)>>1;
if(a<=m) res+=getsum(k<<1,L,m,a,b);
if(m<b) res+=getsum((k<<1)+1,m+1,R,a,b);
return res;
}
}
int getmax(int k,int L,int R,int a,int b)
{
if(a<=L && R<=b)
return maxv[k];
else
{
int res=-0x7ffffff,m=(L+R)>>1;
if(a<=m) res=max(res,getmax(k<<1,L,m,a,b));
if(m<b) res=max(res,getmax((k<<1)+1,m+1,R,a,b));
return res;
}
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,1,n);
for(int i=0;i<m;i++)
{
int cmd,a,b;
scanf("%d%d%d",&cmd,&a,&b);
if(cmd==1)
{
update(1,1,n,a,b);
}
else if(cmd==2)
{
printf("%d
",getsum(1,1,n,a,b));
}
else
{
printf("%d
",getmax(1,1,n,a,b));
}
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
