2015 Multi-University Training Contest 3

2015 Multi-University Training Contest 3

【比赛链接】：​​click here~~​​

5326 ：Work

【题意】：

It’s an interesting experience to move from ICPC to work, end my college life and start a brand new journey in company.As is known to all, every stuff in a company has a title, everyone except the boss has a direct leader, and all the relationship forms a tree. If A’s title is higher than B(A is the direct or indirect leader of B), we call it A manages B.Now, give you the relation of a company, can you calculate how many people manage k people.

代码：

#pragma comment(linker,"/STACK:1024000000,1024000000")#ifndef _GLIBCXX_NO_ASSERT#include #endif#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include // C++#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include

5317：RGCDQ

【题目大意】：

Mr. Hdu is interested in Greatest Common Divisor (GCD). He wants to find more and more interesting things about GCD. Today He comes up with Range Greatest Common Divisor Query (RGCDQ). What’s RGCDQ? Please let me explain it to you gradually. For a positive integer x, F(x) indicates the number of kind of prime factor of x. For example F(2)=1. F(10)=2, because 10=2*5. F(12)=2, because 12=2*2*3, there are two kinds of prime factor. For each query, we will get an interval [L, R], Hdu wants to know maxGCD(F(i),F(j)) (L≤i

给你 n和m，定义F(x)为的素因子种类个数，求maxGCD(F(i),F(j)) (L≤i

【思路】：我们发现其实F（x）的范围很小，最大：2*3*5*7*11*13*17*19>10^6,因此用sum[i][j]表示前i个数中素因子个数种类为j 的数有多少个

代码：

/--------------5317------------------/#include using namespace std;const int N=1e6+10;typedef long long LL;inline LL read(){ int c=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();} return c*f;}int sum[N][8];/// 用sum[i][j]记录前 i 个数字中的有 j 个不同素因子的数字的个数int num[8];int pos[N];bool vis[N];void init() ///统计每个数有多少个不同种类的素因子{ for(int i=2; i<=N; ++i){ if(!vis[i]){ for(int j=i; j<=N; j+=i){ vis[j]=true,pos[j]++; } } }}void solve(){ memset(sum,0,sizeof(sum)); init(); for(int i=2; i<=N; ++i){ for(int j=1; j<=7; ++j){ if(pos[i]%j==0){ sum[i][j]=1; } } } for(int i=2; i<=N; ++i){ ///前缀和累加 for(int j=1; j<=7; ++j){ sum[i][j]+=sum[i-1][j]; } }}int t,l,r,res;int main(){ solve(); t=read(); while(t--){ l=read(); r=read(); for(int j=7; j>=1; --j){ if(sum[r][j]-sum[l-1][j]>=2){ printf("%d\n",j); break; } } } return 0;}

5323： Solve this interesting problem

【题目大意】：

给定区间[l,r]，用线段树的递归建树方式build(1, n)，问最小的n是多少，使得build(1,n) 中能直接建出区间[l,r] 【思路】： 从底向上搜就好了 用线段树方式建树 [ 0, n] 已知[ l, r] 结点 求n 若 建一个[0, 2*r] 的线段树 ,左子树！=右子树，[0, r]  在左子树里 则n最大为2*r 若 建一个[0, 2*r+1] 的线段树 ，左子树==右子树，[0, r]  在左子树里 这时则 [0, r] 就可以建树 搜的时候超出2*r 就直接return

注意往上dfs顺序，否则会RE！

ps:说到底，还是英文是硬伤！han!

代码：

/***************hdu 5323******************************#pragma comment(linker, "/STACK:1024000000,1024000000")// C#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include // C++#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。