대학 1 학년 선발 전 Day 1

전송 문 hyflshhl
A, B, E, F 는 비교적 간단 하 다.
C, D 가 어려워 요.
 
A 문제: 정렬 에 주의 하 세 요. l 과 r 가 같 으 면 길이 가 작은 것 을 우선 삭제 합 니 다.비교적 간단 하 다.
B 문제: 아주 간단 한 확률 DP 입 니 다. 상태 이동 에 주의 하 세 요.
C 문제: 아래 에 상세 하 게 설명 한다.
D 문제: 아래 에 상세 하 게 설명 한다.
E 문제: 거꾸로 처리 하면 됩 니 다. 재 미 있 는 생각 이 있 습 니 다. 바로 알파벳 순 서 를 k 진수 로 본 다음 에 한 자리 에서 1, 진 위 를 추가 하 는 것 입 니 다. 실현 하기 가 귀 찮 습 니 다.
F 문제: 서열 을 하나의 고리 로 처리 할 수 있다. 절단 은 고 리 를 절단 하고 서열 을 두 배로 처리 하 는 길 이 는 고리 와 같다.
 
A 의 코드:

#include
#include
#include
#include
using namespace std;
struct hh {int l,r,len;}a[600001];
int n,ans,inf=2147483647;
int calc_r()
{
	int cnt=inf;
	for(int i=1;i<=n;i++) if(iy.l) return false;
	else if(x.len>y.len) return true;
	return false;
}

bool cmp2(hh x,hh y)
{
	if(x.r>y.r) return true;
	else if(x.ry.len) return true;
	return false;
}
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].l>>a[i].r,a[i].len=a[i].r-a[i].l;
	sort(a+1,a+n+1,cmp);
	ans=max(calc_r()-calc_l(),calc_r()-calc_l());
	sort(a+1,a+n+1,cmp2);
	ans=max(ans,calc_r()-calc_l());
	if(ans<0) ans=0;
	cout<

B 의 코드:

#include
#include
#include
#include
using namespace std;

int n,n1,n2,I;
double dp[2003][2002],ans,p;

void solve()
{
	cin>>n>>n1>>n2>>I>>p;
	p/=100;
	dp[0][0]=1,dp[1][0]=1-p,dp[1][1]=p;
	for(int i=2;i<=n;i++) dp[i][0]=dp[i-1][0]*(1-p);
	for(int i=2;i<=I;i++)
		for(int j=1;j<=n2 && j<=i;j++)
			dp[i][j]=dp[i-1][j-1]*p+dp[i-1][j]*(1-p);
	for(int j=0;j<=n2-1;j++) ans+=dp[I-1][j];
	printf("%.7lf",ans);
}

int main()
{
	solve();
	return 0;
}

C 의 코드:
하나의 더 미 를 유지 하고 모든 상태 (n 개의 숫자 선택) 의 확률 을 기록 합 니 다.
매번 최대 확률 로 답 에 추가 하고 다음 상 태 를 업데이트 합 니 다. 즉, 줄 마다 숫자의 머리 를 앞으로 이동 합 니 다.
cnt. head [i]: cnt 이 상태 에서 i 줄 숫자 헤드 의 위치;

#include
#include
#include
#include
#include
using namespace std;
const int MAXN=105;

double ma[MAXN][MAXN];
int n,m,k;
double ans;

struct hh {int head[MAXN];double sum;}cnt;
bool operator < (hh x,hh y) {return x.sum < y.sum;}
priority_queueq;


void solve()
{
	cin>>n>>m>>k;
	cnt.sum=1.0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			cin>>ma[i][j],ma[i][j]/=100;
		sort(ma[i]+1,ma[i]+m+1),cnt.head[i]=m,cnt.sum*=ma[i][m];
	}
	q.push(cnt);
	while(!q.empty() && k)
	{
		k--;
		cnt=q.top(),q.pop();
		ans+=cnt.sum;
		for(int i=1;i<=n;i++)
		{
			hh v=cnt;
			if(!ma[i][v.head[i]]) continue;
			v.head[i]--;
			v.sum=(v.sum/ma[i][v.head[i]+1])*ma[i][v.head[i]];
			q.push(v);
		}
	}
	printf("%.8lf ",ans);
	return;
}

int main()
{
	solve();
	return 0;
}

D 의 코드:
참고:https://blog.csdn.net/Code92007/article/details/101350037
Dijkstra 는 최 단 로 를 두 번 처리 하고 모든 점 이 최 단 로 를 지나 간 횟수 를 기록 합 니 다.
배열 2 차원 에서 0 은 1 을 기점 으로 하고 1 은 n 을 기점 으로 한다.
dis [i] [0 / 1]: 출발점 에서 i 점 까지 의 최 단 길이;
num [i] [0 / 1]: 출발점 에서 종점 까지 의 최 단 로 는 1 / n 을 기점 으로 i 점 을 통과 하 는 횟수;
i 점 이 지나 갈 확률 은 (num [i] [1] * num [i] [0]) / 최 단 로 총 갯 수 입 니 다.
꽈배기 그림 에 대해 서 는 2 ^ 100000 개의 최 단 길이 존재 할 수 있 습 니 다.
따라서 ln 을 베이스 로, e ^ a + e ^ b = e ^ (a + ln (1 + e ^ (b - a))) 
WA 는 16 번 을 했 는데 처음에는 특수 그림 의 존 재 를 알 아차 리 지 못 했 기 때문이다.
나중에 롱 롱 을 안 켜 서?두 번 째 야..

#include
#include
#include
#include
#include
#include
#include
using namespace std;

typedef long long ll;
const ll MAXN=300001;
const ll inf=2e18;
ll fst[MAXN<<1],nxt[MAXN<<1];
ll dis[MAXN][2];
ll n,m,tot;
bool vis[MAXN];
double cnt[MAXN][2];

struct hh {ll f,t;ll c;}ma[MAXN<<1];
struct sh {ll num;ll d;};
bool operator < (sh x,sh y){return x.d>y.d;}
priority_queueq;

void build(ll f,ll t,ll c)
{
	ma[++tot]=(hh){f,t,c};
	nxt[tot]=fst[f];
	fst[f]=tot;
	return;
}

double calc(double x,double y)
{
	if(xdis[x][st]+ma[i].c)
			{
				cnt[v][st]=cnt[x][st];
				dis[v][st]=dis[x][st]+ma[i].c;
				q.push((sh){v,dis[v][st]});
			}
			else if(dis[v][st]==dis[x][st]+ma[i].c)
				cnt[v][st]=calc(cnt[v][st],cnt[x][st]);
		}
	}
	return;
}

void solve()
{
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=m;i++)
	{
		ll f,t,c;
		scanf("%lld%lld%lld",&f,&t,&c);
		build(f,t,c),build(t,f,c);
	}
	Dijkstra(1,0),Dijkstra(n,1);
	for(ll i=1;i<=n;i++)
	{
		double ans=0;
		if(dis[i][0]+dis[i][1]==dis[n][0])
			ans=exp(cnt[i][0]+cnt[i][1]-cnt[n][0]);
		printf("%.8lf ",ans*2.0);
	}
	return;
}

int main()
{
	solve();
	return 0;
}

E 의 코드:

#include
#include
#include
#include
#include
using namespace std;
const int MAXN=200001;
char a[MAXN];
int vis[MAXN];
int n,m;
string s;
int maxx=-1,minn=214748444,cnt;
int f(int x)
{
	for(int i=(int)a[x]+1;i<=126;i++)
	if(vis[i])  return i;
	return 0;
}
void solve()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		vis[a[i]]++;
		minn=min(minn,(int)a[i]);
	}
	if(n=1;i--)
	{
		int flag=f(i);
		if(flag)
		{
			for(int j=1;j<=i-1;j++)
			cout<

F 의 코드:

#include
#include
#include
#include
#include
using namespace std;

string s;
int a[600001];
int ans=-1,cnt,n,last;
void solve()
{
	cin>>s;
	for(int i=0;i