更新时间:2022-08-12 16:31:35
思路:求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; }
B
思路:暴力枚举每一个点
分析:
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; }
C
思路: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; }
D
思路;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; }
E
思路:暴力+并查集
分析:
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; }
Codeforces Round #409 (rated, Div. 2, based on VK Cup 2017 Round 2)(A.思维题,B.思维题)
Codeforces 400 A. Inna and Choose Options 【Codeforces Round #234 (Div. 2)】
Codeforces Round #277(Div. 2) (A Calculating Function, B OR in Matrix, C Palindrome Transformation)
Codeforces Round #326 (Div. 2) B. Pasha and Phone C. Duff and Weight Lifting
codeforces Round #320 (Div. 2) C. A Problem about Polyline(数学) D. "Or" Game(暴力,数学)