기말 복습 노트 | PTA 데이터 구조상 문제(지속적인 업데이트)

앞에 적으세요: 이것은 누더기집이라고 할 수 있죠. 참고할 의미도 없이 단순히 자신에게 씁니다.간단한 문제라도 약간의 착오가 발생할 수 있기 때문에 동료는 작은 일로 큰 실수를 하고 싶지 않다는 생각으로 이런 착오를 기록하여 나중에 다시 발생하지 않도록 한다.(훗날 반드시 다시 발생할 것이다(안개)
1: 간단한 dp로 서열의 최대 자단과 dp[i]를 i로 끝나는 최대 자단으로 정의하고 전이 방정식을 열거하면 됩니다.

#include
#include
#include
using namespace std;

const int maxn = 1e5 + 9;
int a[maxn],dp[maxn];

int main()
{
	int K;
	scanf("%d",&K);
	for(int i = 0;i < K;i++)
	{
		scanf("%d",&a[i]);
	}
	dp[0] = a[0];
	for(int i = 1;i < K;i++)
	{
		dp[i] = max(dp[i-1] + a[i],a[i]);
 	}
	int maxx = 0;
	for(int i = 0;i < K;i++)
	{
		maxx = max(maxx ,dp[ i ]);
	}
	printf("%d
",maxx);
	return 0;
} 

2:1원 다항식의 덧셈과 곱셈은 정말 사유 수준이 없는 시뮬레이션 문제이다. 그러나 나는 오랫동안 (주로 debug) 썼고 자신의 코드 수준이 통과되지 않는 잔인한 사실을 다시 한 번 반영했다.그러나 이 원본 코드는 길어 보이지만 인터넷에서 천편일률적인 해법보다 공간을 더 절약할 수 있다(하고 나서 블로그 10편을 봤는데 똑같은 해법이라고 투덜대지 않을 수 없다).
뭐랄까: 시뮬레이션 문제를 쓰기 전에 모든 상황을 최대한 고려해야 한다. 그렇지 않으면 마지막에 debug가 패치를 보완하는 것처럼 코드를 읽을 수 없게 된다.이 문제는 체인 테이블로 쓰는 것이 더 간단할지 모르겠지만, 나는 내가 사용하는 더 숙련된 수조qwq를 선택했다.

#include
#include
using namespace std;

const int maxn = 1e5 + 9;

struct node
{
	int xi;
	int eps;
};
bool cmp(node a,node b)
{
	return a.eps > b.eps;
}

node eq1[maxn];
node eq2[maxn];
node jia[maxn];
node cheng[maxn];
node ch[maxn];

int main()
{
	//freopen("input.txt","r",stdin);
	int num1,num2;
	scanf("%d",&num1);
	for(int i = 0;i < num1; i++)
	{
		scanf("%d%d",&eq1[i].xi,&eq1[i].eps);
	}
	scanf("%d",&num2);
	for(int i = 0;i < num2;i++)
	{
		scanf("%d%d",&eq2[i].xi,&eq2[i].eps);
		jia[i].xi = eq2[i].xi;
		jia[i].eps = eq2[i].eps;
		
	}
	//---------------------------------------------
	int ct = 0;
	for(int i=0;i<num1;i++)
	{
		for(int j=0;j<num2;j++)
		{
			cheng[ct].xi = eq1[i].xi * eq2[j].xi;
			cheng[ct].eps = eq1[i].eps + eq2[j].eps;
			ct++;
		}
	}
	sort(cheng,cheng+ct,cmp);
	//printf("---%d
",ct);
	int temp = 0;
	ch[0].xi  = cheng[0].xi;
	ch[0].eps = cheng[0].eps;
	for(int i=1;i<ct;i++)
	{
		while(cheng[i].eps == ch[temp].eps)
		{
			ch[temp].xi += cheng[i].xi;
			i++;
		}
		temp++;
		ch[temp].xi = cheng[i].xi;
		ch[temp].eps = cheng[i].eps;
	}
	int cnt_0 = 0;
	for(int i = 0 ;i <= temp;i++)
	{
		if(ch[i].xi == 0) cnt_0++;
	}
	if(cnt_0 == temp + 1) 
	{
		printf("0 0
");
	}
	else
	 {
		for(int i = 0;i <= temp;i++)
		{
		if(i != temp)
		{
			if(ch[i].xi!=0)
			{
				if(i!=0) printf(" ");
				printf("%d %d",ch[i].xi,ch[i].eps);
			}
			
		}
		else
		{
			if(ch[i].xi!=0)
			{
				if(i!=0) printf(" ");
				printf("%d %d",ch[i].xi,ch[i].eps);
			}
			
		}
	}
	printf("
");
	}

	//------------------------------------------------------
	int cnt_jia = num2;
	int cnt = num2;
	for(int j = 0;j < num1;j++)
	{
		int flag = 0;
		for(int i = 0;i < cnt_jia;i++)
		{
			if(jia[i].eps == eq1[j].eps)
			{
				jia[i].xi = jia[i].xi + eq1[j].xi;
				flag = 1;
			}
		}
		if(flag == 0)
		{
			jia[cnt].xi = eq1[j].xi;
			jia[cnt].eps = eq1[j].eps;
			cnt++;
		}
	}
	sort(jia,jia + cnt,cmp);
	/*printf("----------
"); 
	for(int i=0;i
	// remember to take all 0 into consideration
	int count = 0;
	for(int i=0;i<cnt;i++)
	{
		if(jia[i].xi == 0)
		count++;
	}
	if(count == cnt)
	{
		printf("0 0
");
		return 0;
	}
	for(int i = 0;i < cnt ;i++)
	{
		if(i != cnt-1)
		{
			if(jia[i].xi !=0 )
			{
				if(i!=0) printf(" ");
				printf("%d %d",jia[i].xi,jia[i].eps);
			}
			
		}
		else
		{
			if(jia[i].xi !=0 )
			{
				if(i!=0) printf(" ");
				printf("%d %d",jia[i].xi,jia[i].eps);
			}
				
		}
	}
	return 0;
}


/*    ：
    ，                     ，    bug */

7:6 도 분리 한 도론 문제 가 하나 있다. 만약에 제목 에 따라 주어진 데이터 범위 를 n <=1e3 은 전혀 플로이드 를 뛸 수 없다. 그리고 그 의 변 이 많지 않기 때문에 표지 거리 는 각 점 마다 한 번 더 뛰어 최적화된 dij 이다.그런데 문제가 생겼어요. 제가 좀 게으르기 때문에 Floyd를 하나 써서 큰 tle를 보려고 했는데 단념했어요. 결국, AC???n3이 천 개가 넘으면 광속 측정기일까 봐 하하.

#include
#include
#include
using namespace std;
 
 
const int maxn = 1e3 + 9;
 
int maze[maxn][maxn] = { 0 };

int n,m;

int main()
{
	scanf("%d%d",&n,&m);	
	memset(maze,0x3f3f3f,sizeof(maze));
	while(m--)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		maze[a][b] = 1;
		maze[b][a] = 1;
	}

	for(int k =1;k <= n;k++)
	{
		for(int i = 1;i <= n;i++)
		{
			for(int j = 1;j <= n;j++)
			{
				maze[i][j] = min(maze[i][j],maze[i][k] + maze[k][j]);
			}
		}
	}
	
	int cnt[maxn];
	memset(cnt,0,sizeof cnt);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(maze[i][j] <= 6)
			{
				cnt[i]++;
				cnt[j]++;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		printf("%d: %.2f%
",i,100.0*cnt[i]/(2.0*n));
	}
	return 0;
}