Codeforces Beta Round #9 (Div. 2 Only)

从此醉

浏览: 1055093 次
性别:
来自: US

最近访客更多访客>>

billyhhzh

u012363178

devcang

宝帅啊啊啊

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

点击打开链接cf#9

思路：求gcd然后化简

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int gcd(int a ,int b){
   return b == 0 ? a : gcd(b , a%b);
}

int main(){
   int a , b;
   while(scanf("%d%d" , &a , &b) != EOF){
       int tmp = max(a , b);
       tmp = 6-tmp+1;
       int x = gcd(tmp , 6);
       if(x != 1){
         tmp = tmp/x;
         int y = 6/x;
         printf("%d/%d\n", tmp , y);
       }
       else
         printf("%d/6\n" , tmp);
   }
   return 0;
}

思路：暴力枚举每一个点
分析：
1 题目要求找到时间最少的那个点，如果有多个找到距离学校最近的点。
2 题目的数据n最大100，而且数据不超10^5，那么我们暴力完全是可以的。
3 注意浮点数的比较问题：#define eps 1e-9 , 现在有两个浮点数a , b
如果if(a-b > eps) a > b ，不可以利用if(b - a < eps) 来判断a > b，只能是第一种
如果if(fabs(a-b) < eps) ，则认为是a = b。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

#define MAXN 110
#define eps 1e-19

int n , Vb , Vs;
int num[MAXN];
int x , y;

double Dis(int x1 , int y1 , int x2 , int y2){
    return sqrt(1.0*(x1-x2)*(x1-x2)+1.0*(y1-y2)*(y1-y2));
}

int main(){
   while(scanf("%d%d%d" , &n , &Vb , &Vs) != EOF){
       for(int i = 1 ; i <= n ; i++)
          scanf("%d" , &num[i]);
       scanf("%d%d" , &x , &y);
       
       double min = 0x7fffffff;
       int ans;
       double dis;
       for(int i = 2 ; i <= n ; i++){
          double t;
          t = 1.0*num[i]/Vb+Dis(num[i],0,x,y)/Vs;
          if(min - t > eps){/*大于的时候*/
            min = t;
            ans = i;
            dis = Dis(num[i] , 0 , x , y);
          } 
          else if(fabs(t-min) < eps){/*相等*/
            if(dis - Dis(num[i] , 0 , x , y) > eps){
               dis = Dis(num[i] , 0 , x , y);
               ans = i;
            }
          }
       }
       printf("%d\n" , ans);
   }
   return 0;
}

思路：1 递归生成数据判断是否大于n 2 打表法
分析：
1 由题目我们可以知道数据有如下规律
1
10 11
100 101 110 111
1000 1001 1010 1011 1100 1101 1110 1111
......
那么我们只要不断的递归生成这些数，直到当前生成的数假设为x ，x>n的时候就return，否则加加ans这样就可以求出个数。

2 打表的话，我们去分析数据就可以得到如下规律
1-9 1个 2^0
10-99 2个 2^1
100-999 4个 2^2
1000-9999 8个 2^3
.......
10^9-999999999 n个 2^9

我们知道2^9不超过1000，那么我们只要利用这些规律把数据保存到一个二维数组即可。假设我们用num[20][1010]来保存，那么就有
num[1][0] = 1;
num[2][0] = 10 , num[2][1] = 11;
num[3][0] = 100 , num[3][1] = 101 , num[3][2] = 110 , num[3][3] = 111;
......
然后对于每一个n，我们只要进行查找即可

3 注意c库函数的pow函数少用，一般自己写pow函数。

代码：

/*递归*/
#include<iostream>
#include<cstdio>
using namespace std;

int n , ans;

void solve(int x){
   if(x > n)
     return;
   ans++;
   solve(x*10);
   solve(x*10+1);
}

int main(){
  while(scanf("%d" , &n) != EOF){
     ans = 0;
     solve(1);
     printf("%d\n" , ans);
  }
  return 0;
}

/*打表*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define MAXN 10010

int n;
long long num[20][MAXN];
int vis[20];

/*pow函数*/
int Pow(int x , int y){
   int sum = 1;
   for(int i = 1 ; i <= y ; i++)
      sum *= x;
   return sum;
}

void init(){
    memset(num , 0 , sizeof(num));
    memset(vis , 0 , sizeof(vis));

    for(int i = 1 ; i <= 10 ; i++){
       int k = Pow(2 , i-1);
       vis[i] = vis[i-1] + k;
       int pos = 0;
       
       for(int j = k ; j <= vis[i] ; j++){
          int tmp = 0;
          int cnt = 0;
          int tmpSum = j;/*用tmpSum来代替j运算*/
          while(tmpSum){
             int x = tmpSum%2;
             tmp = x*Pow(10,cnt)+tmp;
             cnt++;
             tmpSum /= 2;
          }
          num[i][pos++] = tmp;
       }
    }
}

int main(){
   init();
   num[11][0] = 1e10;
   
   while(scanf("%d" , &n) != EOF){
     int ans = 0; 

     for(int i = 1 ; i <= 11 ; i++){
         if(n < num[i][0]){
           ans = vis[i-2];
           int j;
           
           for(j = 0 ; j < Pow(2 , i-2); j++){
              if(num[i-1][j] >= n){
                ans += j;
                if(num[i-1][j] == n)
                  ans++;
                break;
              }
           }
           if(j == Pow(2 , i-2))
             ans += Pow(2 , i-2);
           printf("%d\n" , ans);
           break;
         }
      }
   }
   return 0;
}

思路；dp

分析：

1 给定n和h表示n个节点和高度不低于h的二叉搜索树的个数

2 dp[i][j]表示i个节点最大高度为j的二叉搜索树的个数，枚举节点数i和高度j以及左子树的节点数k

dp[i][j] += dp[k][j-1]*dp[i-k-1][j];

3 初始化dp[0][i] = 1;

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long int64;
const int N = 40;

int n , h;
int64 dp[N][N]; 

void init(){
	for(int i = 0 ; i < N ; i++)
		dp[0][i] = 1;

	for(int i = 1 ; i < N ; i++)
		for(int j = 1 ; j < N ; j++)
			for(int k = 0 ; k < i ; k++)
				dp[i][j] += dp[k][j-1]*dp[i-k-1][j-1];
}

int main(){
	init();
	while(~scanf("%d%d" , &n , &h))
		cout<<(dp[n][n]-dp[n][h-1])<<endl;
	return 0;
}

思路：暴力+并查集

分析：

1 题目的意思是给定n个点和m条已知的边的无向图，要求添加最少的边使得这个无向图是一个interesting graph

2 题目定义interesting graph是指每个点只能属于某一个环，并且是一个funny ring。而funny ring则是一个环通过所有的点一次

3 经过1和2两点的分析，我们知道题目最后要求就是给定n个点和m条已知的边，使得添加最少的边得到一个funny ring。

4 求出每个点的度数，然后暴力枚举即可

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 55;
const int MAXN = 2510;

int n , m;
int degree[N];
int father[N];

struct Edge{
	int x;
	int y;
};
Edge e[MAXN];

void init(){
	for(int i = 1 ; i <= n ; i++)
		father[i] = i;
}

int find(int x){
	if(x != father[x])
		father[x] = find(father[x]);
	return father[x];
}

bool unionSet(int x , int y , int ans){
	int fx = find(x);
	int fy = find(y);
	if(fx != fy){
		father[fx] = fy;
		return true;
	}
	return ans+m+1 == n;
}

bool check(){
	int root = find(1);
	for(int i = 1 ; i <= n ; i++)
		if(degree[i] != 2 || find(i) != root)
			return false;
	return true;
}

void solve(){
	if(n == 1){
		if(m == 0) printf("YES\n1\n1 1\n");
		else printf("YES\n0\n"); 
		return;
	}
	int ans = 0;

	for(int i = 1 ; i <= n ; i++){
		for(int j = 1 ; degree[i] < 2 && j <= n ; j++){
			if(i != j && degree[j] < 2){
				if(unionSet(i , j , ans) == false)
					continue;
				degree[i]++ ; degree[j]++;
				e[ans].x = i; e[ans++].y = j;
			}
		}
	}
	if(!check()){
		puts("NO");
		return;
	}
	puts("YES");
	printf("%d\n" , ans);
    for(int i = 0 ; i < ans ; i++)
		printf("%d %d\n" , min(e[i].x,e[i].y) , max(e[i].x , e[i].y));
}

int main(){
	bool isOk;
	int x , y;
	while(scanf("%d%d" , &n , &m) != EOF){
		isOk = true;
		init();
		memset(degree , 0 , sizeof(degree));
		for(int i = 0 ; i < m ; i++){
			scanf("%d%d" , &x , &y);
			if(x > y) swap(x , y);
			unionSet(x , y , 0);
			degree[x]++ ; degree[y]++;
			if(degree[x] > 2 || degree[y] > 2)
				isOk = false;
		}
		if(isOk)
			solve();
		else
			puts("NO");
	}
    return 0;
}

分享到：