好久没写总结了
这几天都是上午下午连着考
所以貌似没时间
直接进入正题
【正题之前：这套题TM真的是NOIP模拟？】
Day1
1.rho
首先密度最大的时候肯定是一条边两个点
证明一下
假设有三个点两条边（肯定比三条边优吧）
那么密度为
显然总能找到其中一条边两个点使
（当且仅当v1=v2=v3=0时等号成立（也许吧））
所以枚举每一条边就可以了
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
// <rho.cpp> - 10/28/15 08:19:18 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> #include <ctime> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } int dq[10001]; double ans; int main(){ freopen("rho.in","r",stdin); freopen("rho.out","w",stdout); int n=getint(),m=getint(); for(int i=0;i<n;i++)dq[i]=getint(); for(int i=0;i<m;i++){ int u=getint()-1,v=getint()-1,w=getint(); ans=max(ans,double(dq[u]+dq[v])/double(w)); } printf("%.6lf",ans); return 0; } |
2.light
没A不写了
反正是最短路
3.permutation
没A不写了
反正不会主席树
Day2
1.triangle
先找规律
发现第n行第m列为
然后就可以做了
先预处理出1到100000的阶乘
然后用费马小定理+快速幂 每次求逆元就好了
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
// <triangle.cpp> - 10/29/15 08:33:15 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; const int mod=1000000009; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } lol pow(lol a,int b){ lol ans=1; while(b!=0){ if(b&1)ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } lol ans,jc[100001]; int main(){ freopen("triangle.in","r",stdin); freopen("triangle.out","w",stdout); jc[0]=1; for(int i=1;i<=100000;i++)jc[i]=(jc[i-1]*i)%mod; int T=getint(); while(T--){ int a=getint(),b=getint(),n=getint(),m=getint(); ans=pow((lol)a,n-m)*pow((lol)b,m-1)%mod; ans=ans*jc[n-1]%mod*pow((lol)jc[m-1],mod-2)%mod*pow((lol)jc[n-m],mod-2)%mod; cout<<ans<<endl; } return 0; } |
2.interval
我做的是非正解n方算法
枚举每一个k，向两边扩展
用m[i]记录向左扩展到i时区间最长值
可以发现从k到k扩展到的最右端点之间是不可能存在比k更优的结果的
于是搜完k直接从扩展到的最右端点+1处再扩展就好了
于是就能骗过了
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
// <interval.cpp> - 10/29/15 08:33:15 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } int a[500001]; int m[500001]; int main(){ freopen("interval.in","r",stdin); freopen("interval.out","w",stdout); int n=getint(),MAX=0; for(int i=0;i<n;i++){ a[i]=getint(); if(a[i]==1){cout<<n-1<<" "<<1<<endl<<1;return 0;} } for(int i=0;i<n;i++){ int l=0; int k; for(k=i+1;k<n&&a[k]%a[i]==0;k++)l++; for(k=i-1;k>=0&&a[k]%a[i]==0;k--)l++; m[k+1]=max(m[k+1],l); MAX=max(MAX,m[k+1]); } int sum=0; for(int i=0;i<n;i++)if(m[i]==MAX)sum++; cout<<MAX<<" "<<sum<<endl; for(int i=0;i<n;i++)if(m[i]==MAX)cout<<i+1<<" "; return 0; } |
3.bwg
这道题直接暴力 加一点剪枝就能过了【数据太水】
然而我不想写了
那就END了XD
说点什么