AtCoder Beginner Contest 236补题报告

AtCoder Beginner Contest 236补题报告

D:Dance

题解：DFS，数据只有8，很小，所以dfs爆搜就可以。

主要是dfs的部分不好写，可以从线性来考虑，一共2*n个数，要配对成n对，然后每对进行异或，最后搞在一起注意要判断这个走过没有，如果用过，那肯定不能再用了，vis[i]就是判断第i个人是否选过。

#include 
#include 
#include 
#include 
#define int long long
using namespace std;
const int N = 1e6+10;
int arr[20][20];

int ans;
bool vis[20];
int n;
//dfs爆搜判断每种情况
void dfs(int u,int v)
{
	if(u==2*n){
		ans = max(ans,v);
		return;
	}
	if(vis[u]){
		dfs(u+1,v);
		return ;
	}
	for(int i=u+1;i<=2*n;i++)
	{
		if(vis[i]) continue;
		vis[i]=true;
		dfs(u+1,v^arr[u][i]);
		vis[i]=false;
	}
}


signed main() {
	scanf("%lld",&n);
	for(int i=1;i<=2*n-1;i++){
		for(int j=i+1;j<=2*n;j++){
			scanf("%lld",&arr[i][j]);
		}
	}
	dfs(1,0);
	printf("%lld",ans);
	return 0;
}

E:E - Average and Median

题解：

//题目是说让我们选出最大的平均值，以及最大的中值。
//此处使用两个判断函数与二分函数
//判断函数可以用来判断二分中的条件
#include 

using namespace std;

#define N 100001
#define eps 1e-3

int read(){
	int p=0,flag=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')
			flag=-1;
		c=getchar();
	}
	while(isdigit(c)){
		p=(p<<3)+(p<<1)+(c^48);
		c=getchar();
	}
	return p*flag;
}
int n,a[N];
double dp[N];
int get(int a,int b){
	return a>=b?1:-1;
}
//使用DP记录要存的数
//然后精度的细节处理
bool check1(double x){
	dp[1]=a[1]-x;
	for(int i=2;i<=n;i++){
		dp[i]=max(dp[i-1],dp[i-2])+a[i]-x;
	}
	return dp[n]>-eps||dp[n-1]>-eps;
}

bool check2(int x){
	dp[1]=get(a[1],x);
	for(int i=2;i<=n;i++){
		dp[i]=max(dp[i-1],dp[i-2])+get(a[i],x);
	}
	return dp[n]>0||dp[n-1]>0;
}


double ans1()
{
	double l = 0, r = 1e9;
	while(r-l>eps){
		double mid = (l+r)/2.0;
		if(check1(mid)) l = mid;
		else r = mid;
	}
	return r;
}

int ans2()
{
	int l = 0,r = 1e9;
	while(l<=r){
		int mid = (l+r)>>1;
		if(check2(mid)) l = mid+1;
		else r = mid -1;
	}
	return l-1;
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	printf("%lfn%d",ans1(),ans2());
	return 0;
}