首页 > 代码库 > NOIp 0904 出题报告
NOIp 0904 出题报告
T1 huajitree
纯模拟，把S拆成二进制查一下有多少个1，然后把这个数和N*M求一下gcd,除一下输出就好了。说求期望值可能对新高一不太友好….
1 //huajitree 2 //2016.8.22 3 //by Cydiater 4 #include <iostream> 5 #include <cstdio> 6 #include <cstdlib> 7 #include <queue> 8 #include <map> 9 #include <cstring>10 #include <string>11 #include <algorithm>12 #include <cmath>13 #include <ctime>14 #include <iomanip>15 using namespace std;16 #define FILE "huajitree"17 #define ll long long18 #define up(i,j,n) for(int i=j;i<=n;i++)19 #define down(i,j,n) for(int i=j;i>=n;i--)20 const int oo=0x3f3f3f3f;21 inline ll read(){22 char ch=getchar();ll x=0,f=1;23 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}24 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}25 return x*f;26 }27 ll S,ans=0,N,M;28 namespace solution{29 inline ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}30 void init(){31 N=read();M=read();S=read();32 ans=0;33 }34 void slove(){35 while(S>0){ans+=S%2;S/=2;}36 }37 void output(){38 ll d=gcd(ans,N*M);39 if(ans>0)cout<<ans/d<<‘/‘<<N*M/d;40 else puts("0");41 }42 }43 int main(){44 freopen(FILE".in","r",stdin);45 freopen(FILE".out","w",stdout);46 using namespace solution;47 init();48 slove();49 output();50 return 0;51 }
T2 pack
起名叫pack是为了衔接剧情QAQ，60分裸的DP，会DP就应该会，如果学过DP这个的60分没写出来就应该考虑补一下DP了。
所有数据都是随机的..所以加上一些奇淫技巧也许能暴力A掉？
给出状态转移方程：
首先把h和v的前缀和都搞出来
1 //NOIp by Cydiater right 2 //by Cydiater 3 //2016.8.24 4 #include <iostream> 5 #include <cstdio> 6 #include <cstring> 7 #include <string> 8 #include <algorithm> 9 #include <queue>10 #include <map>11 #include <ctime>12 #include <cstdlib>13 #include <iomanip>14 #include <cmath>15 using namespace std;16 #define ll long long17 #define up(i,j,n) for(int i=j;i<=n;i++)18 #define down(i,j,n) for(int i=j;i>=n;i--)19 #define FILE "pack"20 const int MAXN=1e6+5;21 const int oo=0x3f3f3f3f;22 inline ll read(){23 char ch=getchar();int x=0,f=1;24 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}25 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}26 return x*f;27 }28 ll N,sum[MAXN],h[MAXN],q[MAXN],head,tail,f[MAXN];29 namespace solution{30 void init(){31 N=read();32 memset(sum,0,sizeof(sum));33 memset(h,0,sizeof(h));34 memset(f,0,sizeof(f));35 up(i,1,N){36 sum[i]=sum[i-1]+read();37 h[i]=h[i-1]+read();38 }39 }40 inline double col(int x,int y){41 double t1=f[y]-f[x];42 double t2=sum[y]-sum[x];43 return t1/t2;44 }45 void slove(){46 head=1;tail=0;q[++tail]=0;47 up(i,1,N){48 while(head<tail&&col(q[head],q[head+1])<h[i])head++;49 f[i]=f[q[head]]+(sum[i]-sum[q[head]])*h[i];50 while(head<tail&&col(q[tail-1],q[tail])>col(q[tail],i))tail--;51 q[++tail]=i;52 }53 }54 void output(){55 cout<<f[N]<<endl;56 }57 }58 int main(){59 freopen(FILE".in","r",stdin);60 freopen(FILE".out","w",stdout);61 using namespace solution;62 init();63 slove();64 output();65 return 0;66 }
T3 block
我太弱啦出不了第三题，这是BZOJ上的一道题，所以说这个的题解你随便一搜成片的都是，我简单废话一下，本题所需要的数据结构就是线段树，简单的说就是用线段树维护连通性，高二的各位神犇你们说良心不良心呀。
怎么用线段树维护连通性呢？
反正我是用一个线段树里维护6个值，分别是
左上到左下的连通性
左上到右下的连通性
左上到右上的连通性
左下到右下的连通性
左下到右上的连通性
右上到右下的连通性
维护四个值好像也没什么问题，具体的自己思考
然后合并什么的就很好（ma）搞（fan）了
具体的实现可以参考我180行的代码，虽然写的很丑..
COGS上有一个神犇90行就解决了，你们也可以去看看他的代码
1 //BZOJ 1018 2 //by Cydiater 3 //2016.8.24 4 #include <iostream> 5 #include <cstring> 6 #include <cstdio> 7 #include <cstdlib> 8 #include <string> 9 #include <ctime> 10 #include <cmath> 11 #include <queue> 12 #include <map> 13 #include <iomanip> 14 #include <algorithm> 15 using namespace std; 16 #define FILE "block" 17 #define ll long long 18 #define up(i,j,n) for(int i=j;i<=n;i++) 19 #define down(i,j,n) for(int i=j;i>=n;i--) 20 const int MAXN=1e5+5; 21 const int oo=0x3f3f3f3f; 22 inline int read(){ 23 char ch=getchar();int x=0,f=1; 24 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} 25 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 26 return x*f; 27 } 28 struct Tree{ 29 bool luru;/*left up to right up*/ 30 bool ldrd;/*left down to right down*/ 31 bool lurd;/*left up to right down*/ 32 bool ldru;/*left down to right up*/ 33 bool luld;/*left up ro left down*/ 34 bool rurd;/*right up to right down*/ 35 }t[MAXN<<4]; 36 bool toright[2][MAXN],pipe[MAXN]; 37 int N,r1,c1,r2,c2,k,v,limleft,limright,cnt=0; 38 char s[20]; 39 namespace solution{ 40 Tree reload(Tree a,Tree b,bool upedge,bool downedge){ 41 Tree c; 42 c.luld=a.luld;c.rurd=b.rurd; 43 c.luru=(a.luru&upedge&b.luru)|(a.lurd&downedge&b.ldru); 44 c.ldrd=(a.ldrd&downedge&b.ldrd)|(a.ldru&upedge&b.lurd); 45 c.lurd=(c.luru&c.rurd)|(c.luld&c.ldrd)|(a.luru&upedge&b.lurd)|(a.lurd&downedge&b.ldrd); 46 c.ldru=(c.ldrd&c.rurd)|(c.luld&c.luru)|(a.ldrd&downedge&b.ldru)|(a.ldru&upedge&b.luru); 47 c.luld=c.luld|(c.lurd&c.ldrd)|(c.ldru&c.luru)|(a.luru&upedge&b.luld&downedge&a.ldrd); 48 c.rurd=c.rurd|(c.lurd&c.luru)|(c.ldru&c.ldrd)|(b.luru&upedge&a.rurd&downedge&b.ldrd); 49 return c; 50 } 51 void build(int leftt,int rightt,int root){ 52 if(leftt==rightt){ 53 t[root].luru=t[root].ldrd=1; 54 t[root].lurd=t[root].ldru=t[root].luld=t[root].rurd=0; 55 return; 56 } 57 int mid=(leftt+rightt)>>1; 58 t[root].luru=t[root].ldrd=t[root].lurd=t[root].ldru=t[root].luld=t[root].rurd=0; 59 build(leftt,mid,root<<1); 60 build(mid+1,rightt,root<<1|1); 61 } 62 void updata1(int leftt,int rightt,int root){ 63 if(leftt>k||rightt<k) return; 64 if(leftt==k&&rightt==k){ 65 t[root].luld=t[root].rurd=t[root].lurd=t[root].ldru=v; 66 return; 67 } 68 int mid=(leftt+rightt)>>1; 69 updata1(leftt,mid,root<<1); 70 updata1(mid+1,rightt,root<<1|1); 71 t[root]=reload(t[root<<1],t[root<<1|1],toright[0][mid],toright[1][mid]); 72 } 73 void updata2(int leftt,int rightt,int root){ 74 if(leftt>k||rightt<k) return; 75 if(leftt==k&&rightt==k) return; 76 int mid=(leftt+rightt)>>1; 77 updata2(leftt,mid,root<<1); 78 updata2(mid+1,rightt,root<<1|1); 79 t[root]=reload(t[root<<1],t[root<<1|1],toright[0][mid],toright[1][mid]); 80 } 81 Tree get(int leftt,int rightt,int root){ 82 Tree a,b,c; 83 if(leftt>=limleft&&rightt<=limright) return t[root]; 84 int mid=(leftt+rightt)>>1; 85 if(mid+1<=limleft) return get(mid+1,rightt,root<<1|1); 86 else if(limright<=mid) return get(leftt,mid,root<<1); 87 else{ 88 a=get(leftt,mid,root<<1); 89 b=get(mid+1,rightt,root<<1|1); 90 c=reload(a,b,toright[0][mid],toright[1][mid]); 91 } 92 return c; 93 } 94 void slove(){ 95 memset(toright,0,sizeof(toright)); 96 while(scanf("%s",s)!=EOF){ 97 if(s[0]==‘E‘)break; 98 if(s[0]==‘O‘){ 99 c1=read();r1=read();c2=read();r2=read();100 if(r1==r2&&c1!=c2){101 k=r1;v=1;pipe[k]=1;102 updata1(1,N,1);103 }104 if(r1!=r2&&c1==c2){105 r1=min(r1,r2);k=r1;106 toright[c1-1][r1]=1;107 updata2(1,N,1);108 }109 }110 if(s[0]==‘C‘){111 c1=read();r1=read();c2=read();r2=read();112 if(r1>r2){113 swap(r1,r2);114 swap(c1,c2);115 }/*make sure that r1<=r2*/116 if(r1==r2&&c1!=c2){117 k=r1;v=0;pipe[k]=0;118 updata1(1,N,1);119 }120 if(r1!=r2&&c1==c2){121 r1=min(r1,r2);122 toright[c1-1][r1]=0;k=r1;123 updata2(1,N,1);124 }125 }126 if(s[0]==‘A‘){127 c1=read();r1=read();c2=read();r2=read();128 if(c1==c2&&r1==r2){puts("Y");continue;}129 if(r1>r2){130 swap(r1,r2);131 swap(c1,c2);132 }/*make sure that r1<=r2*/133 limleft=1;limright=r1;Tree go_left=get(1,N,1);134 limleft=r1;limright=r2;Tree go_mid=get(1,N,1);135 limleft=r2;limright=N;Tree go_right=get(1,N,1);136 if(r1==r2&&c1!=c2){137 if(go_left.rurd||go_right.luld||go_mid.luld)puts("Y");138 else puts("N");139 }140 if(r1!=r2&&c1==c2){141 if(c1==1){142 if((go_left.rurd&go_mid.ldrd&go_right.luld)||go_mid.luru||(go_left.rurd&go_mid.ldru)||(go_right.luld&go_mid.lurd))puts("Y");143 else puts("N");144 }else{145 if((go_left.rurd&go_mid.luru&go_right.luld)||go_mid.ldrd||(go_left.rurd&go_mid.lurd)||(go_right.luld&go_mid.ldru))puts("Y");146 else puts("N");147 }148 }149 if(r1!=r2&&c1!=c2){150 if(c1==1){/*left up to right down*/151 if((go_left.rurd&go_mid.ldrd)||go_mid.lurd||(go_left.rurd&go_mid.ldru&go_right.luld)||(go_mid.luru&go_right.luld))puts("Y");152 else puts("N");153 }else{/*left down to right up*/154 if((go_left.rurd&go_mid.luru)||go_mid.ldru||(go_left.rurd&go_mid.lurd&go_right.luld)||(go_mid.ldrd&go_right.luld))puts("Y");155 else puts("N");156 }157 }158 }159 }160 }161 }162 int main(){163 freopen(FILE".in","r",stdin);164 freopen(FILE".out","w",stdout);165 using namespace solution;166 N=read();167 build(1,N,1);168 slove();169 return 0;170 }
小结
这套题对新高一可能不太友好，但是这些知识点全都是在NOIp范围内的，可能一些比较偏？但是一些零碎的东西还是要学的。个人以为NOIp2016想进top5这套题应该要拿到230分以上吧..
没什么可说的了，感谢滑稽大师cdc友情出演。
NOIp 0904 出题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。