숙제

문서 목록

A-필수문제-1

제목:

Input:

Output:

Sample Input:

Sample Output:

제목 분석:

코드:

B-필수문제-2

제목:

Input:

Output:

Sample Input

Sample Output:

제목 분석:

코드:

C-필수문제 -3

제목:

Input:

Output:

Sample Input:

Sample Output:

Hint

제목 분석:

코드:

A-필수문제-1

제목:

n개수를 주세요. zjm은 최소한(n+1)/2번의 숫자를 찾아내려고 합니다. 지금 이 숫자가 얼마인지 찾아주세요.

Input：

이 문제는 여러 그룹의 데이터를 포함합니다. 한 그룹의 데이터는 두 줄을 포함합니다.첫 번째 줄에 하나의 숫자 N(1<=N<=9999), N이 홀수임을 보증합니다.두 번째 비헤이비어 N은 공백으로 구분된 정수입니다.데이터는 EOF로 끝납니다.

Output：

모든 그룹의 데이터에 대해 당신이 찾은 유일한 수를 출력해야 합니다.

Sample Input：

5
1 3 2 3 3
11
1 1 1 1 1 5 5 5 5 5 5
7
1 1 1 1 1 1 1

Sample Output：

3
5
1

제목 분석:

간단하게 제목의 뜻에 따라 각 그룹의 데이터의 N 개수에 나타난 개수를 기록하고 그룹 cnt로 저장하며 데이터 범위의minn과maxx를 기록한 다음minn-maxx의 수를 반복하여 cnt[i]>=(n+1)/2를 찾을 때까지 출력에 대응하는 i를 찾으면 된다.
그러나 이 문제는 시간과 공간의 복잡도 카드에 대한 문제가 비교적 엄격하기 때문에 주의해야 한다. 입력한 n개수에 대해 하나의 수조로 저장할 필요가 없다. 직접 변수만 있으면 된다. 그렇지 않으면runtimeerror에 보고하고 데이터 범위에 주의할 것이다. (나처럼 6개의 0을 보고 7개의 0의 공간을 열지 마라.Memory Limit Exceed!)

코드:

#include
#include
#include
#include
using namespace std;
const int inf=1e8+8;
const int maxn=1000010;
int cnt[maxn];
int main()
{
	int n;int a;
	while(scanf("%d",&n)!=EOF)
	{
		int maxx=0;int minn=inf;
		memset(cnt,0,sizeof(cnt));
		for(int i=0;i<n;i++)
		{
			cin>>a;
			maxx=max(maxx,a);
			minn=min(minn,a);
			cnt[a]++; 
		} 	
		for(int i=minn;i<=maxx;i++)
		{
			if(cnt[i]>=(n+1)/2)
			{
				cout<<i<<endl;
				break;
			}
		}	
	}
	return 0;
} 

B-필수문제-2

제목:

zjm은 3차원 공간에 갇혔습니다. 지금 가장 짧은 경로를 찾아서 탈출해야 합니다!공간은 입방체 단위로 구성되어 있다.zjm는 매번 위아래 전후 좌우로 한 단위를 이동하는 데 1분이 걸리고 zjm는 대각선으로 이동할 수 없다.공간의 사방이 폐쇄되다.zjm의 목표는 공간의 출구로 가는 것이다.생천에서 탈출할 가능성이 존재하는가?존재한다면 얼마나 걸립니까?

Input：

첫 번째 줄을 입력하는 것은 공간의 수를 표시합니다.각 공간에 대해 설명하는 첫 번째 비헤이비어 L, R 및 C(30을 초과하지 않음).L은 공간의 높이를 나타내고 R과 C는 각 층의 공간의 행과 열의 크기를 나타낸다.그런 다음 L 레이어, 각 레이어 R 행, 각 행 C 자각 문자는 공간의 셀을 나타냅니다.'#'단원을 통과할 수 없음을 나타낸다.공백 단원을 나타낸다.zjm의 시작 위치는'S'이고 출구는'E'이다.각 층의 공간 뒤에 모두 빈 줄이 있다.L, R 및 C가 0이면 끝을 입력합니다.

Output：

모든 공간은 한 줄의 출력에 대응한다.탈출이 가능하다면 다음과 같이 Escaped in x minute(s)를 내보냅니다.x는 가장 짧은 이탈 시간이다.탈출이 불가능한 경우 아래 Trapped를 출력합니다!

Sample Input

3 4 5
S….
.###.
.##..
###.#
#####
#####
##.##
##…
#####
#####
#.###
####E
1 3 3
S##
#E#
###
0 0 0

Sample Output：

Escaped in 11 minute(s).
Trapped!

제목 분석:

이 문제는 이전의 미로 문제와 비슷하지만 2차원에서 3차원으로 바뀌었다.여전히 bfs의 방법으로 먼저 기점을 입대시킨 다음에 밖으로 나가는 모든 방식을 두루 훑어보고 갈 수 있는 모든 방안을 찾고 걸음수 +1을 기억한다.끝까지 갈 때까지 끝까지 갈 수 있다면 출력 형식에 따라 출력할 수 있는 시간이 길어야 합니다. 그렇지 않으면 탈출할 수 없습니다. 출력 형식에 따라 Trapped를 출력합니다!
(나는 내가 최근에 정말 눈이 멀었나 봐.vis[next.x][next.y][next.z]를vis[next.x][next.y][next.x]]로 써서 잘못 보고한 Time Limit Exceed! 밤새도록 잘못 찾아서 질식했다)

코드:

#include
#include
#include
#include
#include
using namespace std;
const int maxn=32;
struct point//     
{
	int x;
	int y;
	int z;
	int step;
}; 
char a[maxn][maxn][maxn];
bool vis[maxn][maxn][maxn];

int dx[]={0,0,1,-1,0,0};
int dy[]={1,-1,0,0,0,0};
int dz[]={0,0,0,0,1,-1};

point start;point end;
int l,r,c;

bool flag=false;
queue<point> q;//   

void bfs()
{
	while(q.size()) q.pop();
	memset(vis,false,sizeof(vis));//    flase  
	q.push(start);
	vis[start.x][start.y][start.z]=true;
	while(!q.empty())//        
	{
		point temp=q.front();//       
		q.pop();	
		if(temp.x==end.x && temp.y==end.y && temp.z==end.z)//     
		{
			flag=true;
			cout<<"Escaped in "<<temp.step<<" minute(s)."<<endl;
			return ;
		}
		for(int i=0;i<6;i++)	//    
		{
			point next;
			next.x=temp.x+dx[i];
			next.y=temp.y+dy[i];
			next.z=temp.z+dz[i];
			if( next.x>=0&&next.x<l && next.y>=0&&next.y<r && next.z>=0&&next.z<c 
			&&!vis[next.x][next.y][next.z] && a[next.x][next.y][next.z]!='#')
			{
				vis[next.x][next.y][next.z]=true;//        
				next.step=temp.step+1;
				q.push(next); 
			}		
		} 
	}
}
int main()
{
	while(cin>>l>>r>>c)//L       ，R C               
	{
		if(l==0&&r==0&&c==0)
		{
			break;
		}
		for(int i=0;i<l;i++)
		{
			for(int j=0;j<r;j++)
			{
				for(int k=0;k<c;k++)
				{
					cin>>a[i][j][k];
					if(a[i][j][k]=='S')
					{
						start.x=i;
						start.y=j;
						start.z=k;
						start.step=0;
					}
					if(a[i][j][k]=='E')
					{
						end.x=i;
						end.y=j;
						end.z=k;
						end.step=0;
					}
				}
			}
		}	
		flag=false;
		bfs();	
		if(!flag)
		{
			cout<<"Trapped!"<<endl;	
		} 
	}
	return 0;
}

C. - 필수. - 3.

제목:

동동은 매 학기 침실에 가서 건물 청소 임무를 받고 침실마다 인원수를 점검한다.각 침실에ai사람(1<=i<=n)이 있습니다.i부터 j까지 기숙사는 모두sum(i,j)=a[i]+...+a[j]개인입니다.이것은 기숙사 아주머니를 매우 즐겁게 하고 동쪽에서 m번을 청소하며 매번 i번부터 j번 기숙사sum(i,j)까지 청소하게 한다.문제는sum(i1,j1)+...+sum(im,jm)의 최대치를 찾는 것이다.또한ix<=iy<=jx와ix<=jy<=jx의 경우 허용되지 않습니다.그러니까 m단도 교차할 수 없다는 거야.
주: 1≤i≤n≤1e6, -32768≤ai≤32767 인원수는 마이너스...(1<=n<=1000000)

Input:

m 을 입력하고 n 을 입력합니다.뒤에 n개ai를 입력하세요.

Output:

최대 및 를 출력합니다.

Sample Input:

1 3 1 2 3
2 6 -1 4 -2 3 -2 3

Sample Output:

6
8 

Hint

데이터량이 매우 많기 때문에scanf 읽기와 dp 처리가 필요합니다.

제목 분석:

이 문제는 마이너스가 존재하고 데이터량이 많기 때문에 동적 기획의 사상이 필요하다.
전이 방정식은 dp[i][j]=max(dp[i][j-1]+a[j], dp[i-1][k]+a[j])로 전자는 이전 구간을 연장하고 j구간을 더하면 후자는 새로운 구간을 만들고 j구간을 시작 구간으로 한다.
최적화: dp[i-1][k]는 dp[i][j]의 업데이트에서만 나타나기 때문에 스크롤 그룹 1차원 형식으로 최적화할 수 있고 다른 그룹pre로 이전 상태의 dp 최대치를 표시할 수 있다.전이 방정식은 dp[j]=max(dp[j-1]+a[j],pre[j-1]+a[j])로 바뀌었다.여기pre는 다음 dp에 사용할 업데이트입니다. 현재 dp에 영향을 주지 않기 때문에 위치는 dp 업데이트 후에야 합니다.

코드:

#include
#include
#include
using namespace std;
const int maxn=1e6+5;
const int inf=1e8+8;
int dp[maxn];//i-j     
int pre[maxn];//       dp    
int main()
{
	int m,n;
	while(scanf("%d%d",&m,&n)!=EOF)
	{
		int *a=new int[n];
		int ans=-inf;
		for(int i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
		}
		for(int i=0;i<n;i++)
		{
			dp[i]=0;
			pre[i]=0;
		}
		for(int i=0;i<m;i++)
		{
			ans=-inf;
			for(int j=i;j<n;j++)
			{
				dp[j]=max(dp[j-1]+a[j],pre[j-1]+a[j]);
				pre[j-1]=ans;
				ans=max(ans,dp[j]);
			}
		} 
		cout<<ans<<endl;
	}
	return 0;
 }