2019.03.09【NOIP提高組】模拟 B組

解題報告

• JZOJ 4742 單峰
• • 題目
  • 分析
  • 代碼
• JZOJ 4743 積木
• • 題目
  • 分析
  • 代碼
• JZOJ 4745 看電影
• • 題目
  • 分析
  • 代碼

JZOJ 4742 單峰

題目

問 1 ∼ n 1\sim n 1∼n的排列中有多少個單峰排列

分析

對于 n − 1 n-1 n−1， n n n的位置隻能在 n − 1 n-1 n−1的左右，是以也就是 2 n − 1 2^{n-1} 2n−1

代碼

#include <cstdio>
#define rr register
using namespace std;
typedef long long ll;
const ll WYC=1000000007;
inline ll modd(ll ans,ll mod){
	rr int f=1;
	if (ans<0) ans=-ans,f=-f;
	if (ans>=(mod<<4)) ans=(ans-(mod<<4))%mod;
	else{
		ans-=(ans>=(mod<<3))*(mod<<3);
		ans-=(ans>=(mod<<2))*(mod<<2);
		ans-=(ans>=(mod<<1))*(mod<<1);
		ans-=(ans>=(mod<<0))*(mod<<0);
	}
	return ans*f;
}
inline ll ksm(ll x,ll y){
	rr ll ans=1;
	for (;y;y>>=1,x=modd(x*x,WYC))
	    if (y&1) ans=modd(ans*x,WYC);
	return ans;
}
signed main(){
	rr ll n; scanf("%lld",&n);
	printf("%lld",ksm(2,modd(n-1,WYC-1)));
	return 0;
}
           

JZOJ 4743 積木

題目

搭積木必須讓上一層底面對于該層完全覆寫（沒有凸出來的），問最多搭多高

分析

狀壓dp，設 d p [ i ] [ n ] [ 0 ∼ 3 ] dp[i][n][0\sim 3] dp[i][n][0∼3]表示目前層用的是第 n n n塊積木哪一個面朝上時的最大高度，轉移時用未在集合内的積木。

代碼

#include <cstdio>
#include <cctype>
#define rr register
#define max(a,b) ((a)>(b)?(a):(b))
#define check(xx1,yy1,xx2,yy2) ((xx1>=xx2&&yy1>=yy2)||(xx1>=yy2&&yy1>=xx2))
using namespace std;
struct rec{int x,y,z;}a[16];
int n,all,k,dp[32768][16][3],ans;
inline signed iut(){
	rr int ans=0; rr char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans;
}
signed main(){
	all=1<<(n=iut());
	for (rr int i=0;i<n;++i) a[i]=(rec){iut(),iut(),iut()};
	for (rr int i=0;i<all;++i)
	for (rr int j=0;j<n;++j){
		if (i&(1<<j)) continue;
		rr int now=i|(1<<j);
		for (rr int p=0;p<n;++p)
		for (rr int t=0,ch,ku;t<3;++t){
		    if (!t) ch=a[p].x,ku=a[p].y;
		    else if (t&1) ch=a[p].x,ku=a[p].z;
		        else ch=a[p].y,ku=a[p].z;
		    if (check(a[j].x,a[j].y,ch,ku)) dp[now][j][0]=max(dp[now][j][0],dp[i][p][t]+a[j].z);
		    if (check(a[j].x,a[j].z,ch,ku)) dp[now][j][1]=max(dp[now][j][1],dp[i][p][t]+a[j].y);
		    if (check(a[j].y,a[j].z,ch,ku)) dp[now][j][2]=max(dp[now][j][2],dp[i][p][t]+a[j].x);	    
		}
	}
	for (rr int i=0;i<=n;++i)
	for (rr int t=0;t<3;++t) ans=max(ans,dp[all-1][i][t]);
	return !printf("%d",ans);
} 
           

JZOJ 4745 看電影

題目

N N N個人排成一圈，按順時針順序标号為 1 ∼ N 1\sim N 1∼N，每次随機一個 1 ∼ N 1\sim N 1∼N的編号，假設随機到的編号是 X X X，如果編号為 X X X人還未踢出，則将這個人踢出，否則看編号為 X X X m o d mod mod N + 1 N+1 N+1（即順時針順序下一個編号）的人是否存活，如果還未踢出則将他踢出，否則繼續看編号 ( X + 1 ) (X+1) (X+1) m o d mod mod N + 1 N +1 N+1的人，如果已被踢出看順時針的下一個，以此類推，直到踢出一個人為止。重複上述操作，直到剩下 K K K個人。

已知小S的編号是 I d Id Id，問按照小S的方法來他有多少的機率可以不被踢出，成功得到看電影的機會。

分析

由于這個東西是随機的，通過一些玄學的打表東西可以發現每個人的機率應該是一樣的，是以就是 k n \frac{k}{n} nk​

代碼

#include <cstdio>
#define rr register
using namespace std;
int n,k,t;
inline signed gcd(int a,int b){return b?gcd(b,a%b):a;}
signed main(){
	scanf("%d%d%*d",&n,&k);
	if (!k) printf("0/1");
	    else t=gcd(k,n),printf("%d/%d",k/t,n/t);
	return 0;
}