1 #include<cassert> 2 #include<cstdio> 3 #include<vector> 4 using namespace std; 5 const int maxm=500005,maxt=200005,maxn=100005; 6 int seq[maxm]; 7 int cnt[maxt]; 8 vector<int> to[maxn]; 9 int n,T; 10 int vis[maxn],timer=0; 11 int ext[maxn]; 12 bool flag; 13 void dfs(int x){ 14 vis[x]=timer; 15 for(vector<int>::iterator pt=to[x].begin();pt!=to[x].end();++pt){ 16 if(vis[*pt]!=timer){ 17 dfs(*pt);; 18 }else if(ext[*pt]!=timer)flag=false; 19 } 20 ext[x]=timer; 21 } 22 bool toposort(){ 23 ++timer;flag=true; 24 for(int i=1;i<=n;++i){ 25 if(vis[i]!=timer)dfs(i); 26 } 27 return flag; 28 } 29 bool check(int x){ 30 if(x==0)return true; 31 for(int i=1;i<=n;++i)to[i].clear(); 32 for(int i=1;i<=x;++i){ 33 for(int j=cnt[i-1]+1;j<cnt[i];++j){ 34 to[seq[j]].push_back(seq[j+1]); 35 } 36 } 37 return toposort(); 38 } 39 int main(){ 40 freopen("dandelion.in","r",stdin); 41 freopen("dandelion.out","w",stdout); 42 scanf("%d%d",&n,&T); 43 for(int i=1;i<=T;++i){ 44 scanf("%d",cnt+i); 45 cnt[i]+=cnt[i-1];if(cnt[i]>maxm)assert(0); 46 for(int j=cnt[i-1]+1;j<=cnt[i];++j){ 47 scanf("%d",seq+j); 48 } 49 } 50 int l=0,r=T; 51 while(l<=r){ 52 int mid=(l+r)>>1; 53 if(check(mid))l=mid+1; 54 else r=mid-1; 55 } 56 assert(cnt[T]<=500000); 57 printf("%d ",l-1); 58 //printf("%d ",cnt[T]); 59 return 0; 60 }
1 #include<cstdio> 2 #include<cstring> 3 #include<cassert> 4 #include<vector> 5 using namespace std; 6 const int maxn=100005; 7 vector<int> to[maxn]; 8 int deg[maxn]; 9 int vis[maxn];int timer=0; 10 int cntodd=0; 11 void dfs(int x){ 12 vis[x]=timer; 13 if(deg[x]&1)cntodd++; 14 for(vector<int>::iterator pt=to[x].begin();pt!=to[x].end();++pt){ 15 if(vis[*pt]!=timer)dfs(*pt); 16 } 17 } 18 int sumN=0,sumM=0; 19 void work(){ 20 int n,m;scanf("%d%d",&n,&m);sumN+=n;sumM+=m; 21 //assert(n<=m);//printf("%d %d ",n,m); 22 for(int i=0;i<=n;++i)deg[i]=0; 23 int a,b; 24 for(int i=1;i<=m;++i){ 25 scanf("%d%d",&a,&b);deg[a]++;deg[b]++; 26 to[a].push_back(b);to[b].push_back(a); 27 } 28 // assert(deg[0]==0); 29 ++timer; 30 int cntblock=0; 31 int ans=0; 32 int cntodd0=0; 33 for(int i=0;i<=n;++i){ 34 if(deg[i]!=0&&vis[i]!=timer){ 35 cntblock++; 36 cntodd=0;dfs(i); 37 if(cntodd>2)ans+=(cntodd-2)/2; 38 if(i==0)cntodd0=cntodd; 39 } 40 }// assert(cntblock==1); 41 if(cntblock==0)printf("0 "); 42 else if(cntblock==1){ 43 if(deg[0]==0){ 44 printf("%d ",2+ans); 45 }else{ 46 printf("%d ",cntodd0/2); 47 } 48 }else{ 49 if(deg[0]==0)printf("%d ",cntblock+ans+1); 50 else printf("%d ",cntblock+ans); 51 } 52 for(int i=0;i<=n;++i)to[i].clear(); 53 } 54 int main(){ 55 freopen("vine.in","r",stdin); 56 freopen("vine.out","w",stdout); 57 int T;scanf("%d",&T); 58 while(T--){ 59 work(); 60 } 61 assert(sumN<=100000);assert(sumM<=500000); 62 return 0; 63 }
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 using namespace std; 5 const int maxn=100005; 6 int w[maxn],v[maxn]; 7 int n,L,R; 8 double seq[maxn]; 9 bool check(double x){ 10 for(int i=1;i<=n;++i){ 11 seq[i]=v[i]-x*w[i]; 12 } 13 sort(seq+1,seq+n+1); 14 double sum=0; 15 for(int i=1;i<=L;++i)sum+=seq[n+1-i]; 16 return sum>=0.0; 17 } 18 int C(int n,int m){//printf("%d %d ",n,m); 19 if(n-m<m)m=n-m; 20 long long ans=1; 21 for(int i=0;i<m;++i){ 22 ans=ans*(n-i);//printf("%lld ",ans); 23 } 24 for(int i=1;i<=m;++i)ans=ans/i; 25 return (int)ans; 26 } 27 int calc(double ans){ 28 for(int i=1;i<=n;++i)seq[i]=v[i]-ans*w[i]; 29 sort(seq+1,seq+n+1); 30 for(int i=1;i<n+1-i;++i)swap(seq[i],seq[n+1-i]); 31 // for(int i=1;i<=n;++i)printf("%.7f ",seq[i]); 32 int hi=L,lo=L; 33 while(hi<n&&abs(seq[hi]-seq[hi+1])<1e-5)++hi; 34 while(lo>1&&abs(seq[lo]-seq[lo-1])<1e-5)--lo; 35 //printf("%.5f %.5f ",ans,seq[L]); 36 // printf("%d %d ",lo,hi); 37 if(abs(seq[L])<1e-5){ 38 int ans=0; 39 for(int i=L;i<=R&&i<=hi;++i)ans+=C(hi,i); 40 return ans; 41 }else{ 42 return C(hi-lo+1,L-lo+1); 43 } 44 } 45 int main(){ 46 freopen("white.in","r",stdin); 47 freopen("white.out","w",stdout); 48 scanf("%d%d%d",&n,&L,&R); 49 for(int i=1;i<=n;++i)scanf("%d%d",w+i,v+i); 50 double l=0.1,r=10; 51 while(r-l>1e-6){ 52 double mid=(l+r)/2.0; 53 if(check(mid))l=mid; 54 else r=mid; 55 } 56 printf("%.3f ",(l+r)/2.0); 57 printf("%d ",calc((l+r)/2.0)); 58 return 0; 59 }
1 #include<cstdio> 2 //#include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #include<cassert> 8 #define INF 0x3f3f3f3f 9 #define re register 10 #define Ii inline int 11 #define Il inline long long 12 #define Iv inline void 13 #define Ib inline bool 14 #define Id inline double 15 #define ll long long 16 #define Fill(a,b) memset(a,b,sizeof(a)) 17 #define R(a,b,c) for(register int a=b;a<=c;++a) 18 #define nR(a,b,c) for(register int a=b;a>=c;--a) 19 #define Min(a,b) ((a)<(b)?(a):(b)) 20 #define Max(a,b) ((a)>(b)?(a):(b)) 21 #define Cmin(a,b) ((a)=(a)<(b)?(a):(b)) 22 #define Cmax(a,b) ((a)=(a)>(b)?(a):(b)) 23 #define abs(a) ((a)>0?(a):-(a)) 24 #define D_e(x) printf("&__ %d __& ",x) 25 #define D_e_Line printf("----------------- ") 26 #define Pause system("pause"); 27 using namespace std; 28 const int N=100001; 29 Ii read(){ 30 int s=0,f=1;char c; 31 for(c=getchar();c>'9'||c<'0';c=getchar())if(c=='-')f=-1; 32 while(c>='0'&&c<='9')s=s*10+(c^'0'),c=getchar(); 33 return s*f; 34 } 35 Iv print(int x){ 36 if(x<0)putchar('-'),x=-x; 37 if(x>9)print(x/10); 38 putchar(x%10^'0'); 39 } 40 vector<int>V[N]; 41 int deg[N],vis[N],tim,sum_odd; 42 Iv dfs(int x){ 43 vis[x]=tim; 44 if(deg[x]&1)++sum_odd; 45 for(vector<int>::iterator it=V[x].begin();it!=V[x].end();++it) 46 if(vis[*it]!=tim) 47 dfs(*it); 48 } 49 int main(){ 50 freopen("vine.in","r",stdin),freopen("vine.out","w",stdout); 51 int T=read(); 52 while(T--){ 53 int n=read(),m=read(),tag=0,ans=0,odd_0=0;; 54 R(i,0,n)deg[i]=0,vector<int>().swap(V[i]); 55 R(i,1,m){ 56 int u=read(),v=read(); 57 ++deg[u],++deg[v], 58 V[u].push_back(v),V[v].push_back(u); 59 } 60 ++tim; 61 R(i,0,n) 62 if(deg[i]&&vis[i]!=tim){ 63 ++tag, 64 sum_odd=0, 65 dfs(i); 66 if(sum_odd>2)ans+=(sum_odd-2)>>1; 67 if(i==0)odd_0=sum_odd; 68 } 69 if(tag==0) 70 printf("0 "); 71 else if(tag==1){ 72 deg[0]? 73 printf("%d ",odd_0>>1): 74 printf("%d ",2+ans); 75 } 76 else 77 printf("%d ",tag+ans+(deg[0]==0)); 78 } 79 return 0; 80 }
模拟题 day1
出题人: liu_runda
题目名称 山藤 蒲公英 白蛇相簿
源程序文件名 vine.cpp dandelion.cpp white.cpp
输入文件名 vine.in dandelion.in white.in
输出文件名 vine.out dandelion.out white.out
每个测试点时限 1s 1s 1s
内存限制 512MB 512MB 512MB
测试点数目 10 10 10
每个测试点分值 10 10 10
是否打开O2 优化 是 是 是
在windows 下用lemon 进行测试.
山藤(vine)
【题目描述】
许宣生性好动.在山中,要想快速移动,就需要借助山间一根根藤蔓.
每根藤蔓的两端,要么在地面,要么连在一块石头上.藤蔓不会两端都在地面,也不会
两端都在同一块石头上,但是有可能两端各在一块石头上.两个地点之间可能有多条藤蔓.
许宣可以沿着藤蔓攀爬,从藤蔓一端攀爬到另一端,由于藤蔓脆弱,一条藤蔓只能经过
一次,之后就会断掉.
一共有n 块石头,m 条藤蔓.石头编号从1 到n,地面编号为0.
许宣现在想从地面出发,攀爬经过所有藤蔓之后,回到地面.许宣拥有一种特殊道具,
飞爪,可以让他从一个地点到达另外任意一个地点,但是他想尽量少使用飞爪.请问许宣最
少需要使用多少次飞爪?
【输入格式】
多组数据,第一行一个数字T 表示数据组数.
接下来T 组数据,对于每一组数据:
第一行两个整数n,m
接下来m 行,每行两个数字,表示一条藤蔓的两个端点
【输出格式】
一行一个数字,表示使用飞爪的最少次数
【样例输入1】
1
3 1
1 2
【样例输出1】
2
【样例输入2】
1
3 1
0 1
【样例输出2】
1
【数据范围】
第1 个测试点,m=1
第2 个测试点,n<=5,m<=5
第3 个测试点,n<=7,m<=7
第4,6 个测试点,从地面出发至少有一条藤蔓
第5,7 个测试点,从地面出发没有藤蔓
第6,7,8 个测试点,所有的藤蔓都是连通的.也就是说,如果x 和y 两个地点都连接了至
少一条藤蔓,就存在一条路径沿着藤蔓从x 爬到y.
对每个测试点,T 组数据的n 之和<=105,T 组数据的m 之和<=5*105
注意T 可能很大,请注意避免因为初始化的用时过多而超时.
蒲公英(dandelion)
【题目描述】
“人生迫不得已的事情太多,何不只记住那些美好的片段,比如,那片山坡上的蒲公英”
许宣喜欢观赏蒲公英.山坡上有n 株蒲公英.通过目测,许宣给每个蒲公英都估计了一
个正整数作为美学价值.每天,许宣都会走上山坡,依次观赏一些蒲公英.许宣对同一株蒲
公英在每一天估计的美学价值都是一样的.
第X 天观赏蒲公英的时候,许宣要求自己按顺序观赏的下一株蒲公英至少比前一株
的美学价值多X,而第一株蒲公英没有要求.例如,第一天的时候,这个要求相当于观赏的蒲
公英美学价值严格递增.
现在,小白得到了许宣在T 天中观赏的记录.但是她发现,这个记录或许会有差错.具体
来说,如果这T 天的记录都是真的,而许宣又一直保持”第X 天,每株美学价值至少比前一
株多X”的规则,就不存在一种美学价值的赋值方式,使得每天的美学价值估计都一样.
小白又觉得,只考虑前Q 天的观赏记录,还是能够给蒲公英合理的美学价值.
现在小白想知道Q 最大是多少.也就是说,最多考虑前多少天的观赏记录时能够不产
生矛盾?如果第一天就产生矛盾,答案为0.如果到最后一天也没产生差错,答案为Q
【输入格式】
第一行两个整数n,T,分别表示蒲公英的数目和许宣游览的天数.
接下来T 行,第x 行表示许仙第x 天的观赏记录,第一个数字是cnt[x],表示第x 天观赏
的蒲公英数目,接下来x 个数字(1 到n 之间,且不会重复),表示许仙这一天的观赏路线.
【输出格式】
一行一个整数Q,表示不产生矛盾的最大天数
【样例输入】
5 3
4 1 5 4 2
1 5
3 5 2 4
【样例输出】
2
【数据范围】
第1,2,3 个测试点,n<=10,T<=20,cnt[x]之和不超过100
第4,5,6 个测试点,n<=200,T<=200,cnt[x]之和不超过1200
第7,8,9,10 个测试点,n<=105,T<=2*105,cnt[x]之和<=5*105
白蛇相簿(white)
【题目描述】
“又到了,白色相簿的季节呢”
白蛇:缘起 是一部非常优秀的国产动画电影,现在liu_runda 想要将电影中的精彩画
面制成一部<白蛇相簿>.
现在liu_runda 手里已经有了n 张精彩相片,存储在电脑上.每张相片都有两个属性,一
个是文件大小,我们假设相片的大小都是整数.另一个属性是精彩程度,也是一个正整数.
liu_runda 希望在最终的白蛇相簿中,平均每个kb 的精彩程度尽量大.也就是说,每张
相片的文件大小加起来得到一个数字sumDaXiao,每张相片的精彩程度加起来得到一个
数字sumJingCai, liu_runda 希望sumJingCai/sumDaXiao 的比值尽量大.
当然,liu_runda 希望白蛇相簿的相片张数不要太多,也不要太少,恰好在L 张到R 张之
间.
同时,liu_runda 还想知道,选择L 张到R 张相片取得最大比值的相片的方案数是多少.
保证这个方案数可以用int 表示.
【输入格式】
第一行3 个整数n,L,R 表示已有的相片张数和相簿中希望选取的相片数的范围.
接下来n 行,第i 行两个数字,依次表示第i 张相片的文件大小w[i]和精彩程度v[i]
【输出格式】
第一行一个四舍五入保留小数点后三位的浮点数,表示最大比值.
第二行一个正整数,表示取到最大比值的方案数.(某个方案取到最大比值,是指这个
方案的比值精确值等于最大比值的精确值,而不是四舍五入后相等.两个方案不同,当且仅
当存在一张相片在一个方案中被选择却在另一个方案中未被选择)
【样例输入】
7 3 5
1 2
4 3
10 1
6 9
3 3
1 5
9 8
【样例输出】
2.000
2
【数据范围】
第1 个测试点,n=3
第2 个测试点,n=5
第3 个测试点,n=15,
第4,5 个测试点,n<=100, 所有的物品的w[i]/v[i]都相同,且L=R
第6,7 个测试点,方案数为1
对所有测试点,n<=105,1<=w[i]<=10,1<=v[i]<=10
保证使用double 编写正确的程序不会遇到精度问题.