摄影网站的需求分析,甘肃网站建设哪家好,中国营销策划第一人,中国最好的室内设计公司滑稽树 (huajitree.pas/c/cpp) 【问题描述】 JZYZ的湖畔边有一棵滑稽树#xff0c;每年的冬天滑稽树上都会长出很多个滑稽果。我们用一个二维平面N,M描述每个滑稽果所能落下的位置#xff0c;即每个滑稽果不可能落到我们所描述的二维平面之外。 滑稽大师cdc钟爱于收集滑稽… 滑稽树 (huajitree.pas/c/cpp) 【问题描述】 JZYZ的湖畔边有一棵滑稽树每年的冬天滑稽树上都会长出很多个滑稽果。我们用一个二维平面N,M描述每个滑稽果所能落下的位置即每个滑稽果不可能落到我们所描述的二维平面之外。 滑稽大师cdc钟爱于收集滑稽果但是他只有一个篮子篮子只能放在一个点上即一个篮子最多收集一个滑稽果。现在滑稽大师cdc想知道他收集到滑稽果的期望值是多少。cdc放的篮子在任意位置的概率相同 为了zao方shu便ju起fang见bian我们用一个数S描述这个二维平面。 例如 S32(100000)2 ,N2,M3 其对应的二维平面为: 100 000 其中1表示滑稽果所落下的位置即有一个滑稽果落在坐标为1,1的位置。 那么这个数据的答案就是 1*(1/(2*3))1/6 例如 S33(100001)2 ,N2,M3 其对应的二维平面为: 100 001 其中1表示滑稽果所落下的位置即有一个滑稽果落在坐标为1,1的位置,有一个在坐标为(2,3)的位置。 那么这个数据的答案就是 1*(2/(2*3))1/3. 【输入】 输入仅为1行三个正整数分别为N,M,S 【输出】 输出仅一行为期望值的既约分数。即输出为a/b的形式其中gcd(a,b)1 如果期望值为0输出0即可如果为1输出1/1 【输入输出样例1】 huajitree.in huajitree.out 2 3 32 1/6 【数据范围】 对于70%的数据 N*M31 S2^31 对于 100%的数据 N*M63 S2^63 这题就是把一个数转化为二进制找里面有多少个1然后用 个数/n*m 再找 gcd个数n*m 然后 “个数 /gcd” “/” “n*m/gcd”。 1 #includeiostream2 #includecstdio3 using namespace std;4 long long s;5 int n,m,sum0,t;6 int gcd(int a,int b)7 {8 if(b0) return a;9 return gcd(b,a%b);
10 }
11 int main()
12 {
13 freopen(huajitree.in,r,stdin);
14 freopen(huajitree.out,w,stdout);
15 cinnms;
16 while(s)
17 {
18 if(s%21) sum;
19 s/2;
20 }
21 tgcd(n*m,sum);
22 if(sum0) cout0endl;
23 else
24 coutsum/t/n*m/tendl;
25 fclose(stdin); fclose(stdout);
26 return 0;
27 } 背包 (pack.pas/c/cpp) 【问题描述】 滑稽大师cdc依靠每天的辛勤努力终于收集到了足够多的滑稽每个滑稽有两个属性分别是滑稽值h和体积v他要把所有的滑稽带走但是cdc只有一个固定容积的背包。怎么才能带走尽可能多的滑稽值呢 因为cdc是神犇所以他很轻松的解决了这个问题。现在cdc来到了滑稽工厂他要把所有的滑稽打包发给各个滑稽销售点但是每次打包cdc都要付出一定的代价。 我们把滑稽工厂打包滑稽的生产线看作一个一维线段每个滑稽都是线段上的一个点且每个滑稽的顺序不可改变。 且每次打包滑稽只能是一段连续的区间定义这个线段上从左到右第i个点的滑稽值为hi,体积为vi,设每次打包的区间为[i,j]则每次打包的代价为,现在cdc想知道他需要支付的最小代价为多少。他需要支付的代价为打包所有滑稽的代价和。 【输入】 第一行为一个正整数N,表示N个滑稽 接下来的N行每行两个正整数v,h,分别表示体积与滑稽值 【输出】 输出仅一行表示cdc可能需要支付的最小代价 【输入输出样例1】 pack.in pack.out 4 1 4 2 3 3 2 4 1 85 /*分组为{1}{2}{3}{4} 854*1(43)*2(432)*3(4321)*4 */ 【数据范围】 对于60%的数据 N1000 对于100%的数据 N1000000 hi,vi500 保证答案在long long 范围内 看着题目超级高大上然而…小弱渣飘过 大暴力估计是题目没出好把 Sumvi*sumhi 1 #includeiostream2 #includecstdio3 #includestring4 #includecmath5 #includealgorithm6 #includectime7 using namespace std;8 long long a,x[1000000],y[1000000],z,w,h0,sum0,num0;9 string s;
10 int main()
11 {
12 freopen(pack.in,r,stdin);
13 freopen(pack.out,w,stdout);
14 cina;
15
16 for(int i1;ia;i)
17 {
18 cinx[i]y[i];
19 sumy[i];
20 numsum*x[i];
21 }
22 coutnumendl;
23 return 0;
24 } 街区运输 block(.pas/c/cpp) 【问题描述】 好的现在你们已经完美的解决了打包的问题了现在需要把这些滑稽分发给各个滑稽销售点 滑稽大师cdc想要把所有的滑稽分发出去但是每个街区之间的道路有时候会因为各种原因而封闭掉,导致无法运输cdc可以通过膜法瞬间知道哪些道路封闭了或那些道路又重新开放了注一个道路可能会封闭好几次但是每次开放与之前封闭了几次无关。他想知道从一个街区到另一个街区是否有可以到达的道路。 每个街区分布在NxM的二维平面上同时保证N2,也就是说这个二维平面只有两行M列其中每个焦点代表一个街区。同时保证每次封闭和重新开放的道路一定在两个相邻的城市之间在开始时所有的道路都是封闭的。 【输入】 第一行为正整数M,代表这是一个2*M的二维平面。 接下来的若干行分别有4种形式. Exit:结束输入Open x1 y1 x2 y2 开放(x1,y1)至(x2,y2)的道路Close x1 y1 x2 y2 封闭(x1,y1)至(x2,y2)的道路//数据保证以上所有的(x1,y1) (x2,y2)在平面上相邻 Ask x1 y1 x2 y2 询问(x1,y1) (x2,y2)是否存在通路【输出】 对于每个询问输出1行如果存在请输出Y,如果不存在请输出N 【输入输出样例1】 block.in block.out 2 Open 1 1 1 2 Open 1 2 2 2 Ask 1 1 2 2 Ask 2 1 2 2 Exit Y N 【数据范围】 对于100%的数据保证N1e5 所有信息小于1e5 对于30%的数据保证N100 对于另外30%的数据保证N10000 我简单废话一下本题所需要的数据结构就是线段树简单的说就是用线段树维护连通性高二的各位神犇你们说良心不良心呀。 怎么用线段树维护连通性呢 反正我是用一个线段树里维护6个值分别是 左上到左下的连通性 左上到右下的连通性 左上到右上的连通性 左下到右下的连通性 左下到右上的连通性 右上到右下的连通性 维护四个值好像也没什么问题具体的自己思考 然后合并什么的就很好ma搞fan了 具体的实现可以参考我180行的代码虽然写的很丑.. 当然本题没有强制在线分块并查集随便搞搞也可以过 COGS上有一个神犇90行就解决了你们也可以去看看他的代码 1 //BZOJ 10182 //by Cydiater3 //2016.8.244 #include iostream5 #include cstring6 #include cstdio7 #include cstdlib8 #include string9 #include ctime10 #include cmath11 #include queue12 #include map13 #include iomanip14 #include algorithm15 using namespace std;16 #define FILE block17 #define ll long long18 #define up(i,j,n) for(int ij;in;i)19 #define down(i,j,n) for(int ij;in;i--)20 const int MAXN1e55;21 const int oo0x3f3f3f3f;22 inline int read(){23 char chgetchar();int x0,f1;24 while(ch9||ch0){if(ch-)f-1;chgetchar();}25 while(ch0ch9){xx*10ch-0;chgetchar();}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[MAXN4];36 bool toright[2][MAXN],pipe[MAXN];37 int N,r1,c1,r2,c2,k,v,limleft,limright,cnt0;38 char s[20];39 namespace solution{40 Tree reload(Tree a,Tree b,bool upedge,bool downedge){41 Tree c;42 c.lulda.luld;c.rurdb.rurd;43 c.luru(a.luruupedgeb.luru)|(a.lurddownedgeb.ldru);44 c.ldrd(a.ldrddownedgeb.ldrd)|(a.ldruupedgeb.lurd);45 c.lurd(c.luruc.rurd)|(c.luldc.ldrd)|(a.luruupedgeb.lurd)|(a.lurddownedgeb.ldrd);46 c.ldru(c.ldrdc.rurd)|(c.luldc.luru)|(a.ldrddownedgeb.ldru)|(a.ldruupedgeb.luru);47 c.luldc.luld|(c.lurdc.ldrd)|(c.ldruc.luru)|(a.luruupedgeb.lulddownedgea.ldrd);48 c.rurdc.rurd|(c.lurdc.luru)|(c.ldruc.ldrd)|(b.luruupedgea.rurddownedgeb.ldrd);49 return c;50 }51 void build(int leftt,int rightt,int root){52 if(lefttrightt){53 t[root].lurut[root].ldrd1;54 t[root].lurdt[root].ldrut[root].luldt[root].rurd0;55 return;56 }57 int mid(lefttrightt)1;58 t[root].lurut[root].ldrdt[root].lurdt[root].ldrut[root].luldt[root].rurd0;59 build(leftt,mid,root1);60 build(mid1,rightt,root1|1);61 }62 void updata1(int leftt,int rightt,int root){63 if(lefttk||righttk) return;64 if(lefttkrighttk){65 t[root].luldt[root].rurdt[root].lurdt[root].ldruv;66 return;67 }68 int mid(lefttrightt)1;69 updata1(leftt,mid,root1);70 updata1(mid1,rightt,root1|1);71 t[root]reload(t[root1],t[root1|1],toright[0][mid],toright[1][mid]);72 }73 void updata2(int leftt,int rightt,int root){74 if(lefttk||righttk) return;75 if(lefttkrighttk) return;76 int mid(lefttrightt)1;77 updata2(leftt,mid,root1);78 updata2(mid1,rightt,root1|1);79 t[root]reload(t[root1],t[root1|1],toright[0][mid],toright[1][mid]);80 }81 Tree get(int leftt,int rightt,int root){82 Tree a,b,c;83 if(lefttlimleftrighttlimright) return t[root];84 int mid(lefttrightt)1;85 if(mid1limleft) return get(mid1,rightt,root1|1);86 else if(limrightmid) return get(leftt,mid,root1);87 else{88 aget(leftt,mid,root1);89 bget(mid1,rightt,root1|1);90 creload(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 c1read();r1read();c2read();r2read();
100 if(r1r2c1!c2){
101 kr1;v1;pipe[k]1;
102 updata1(1,N,1);
103 }
104 if(r1!r2c1c2){
105 r1min(r1,r2);kr1;
106 toright[c1-1][r1]1;
107 updata2(1,N,1);
108 }
109 }
110 if(s[0]C){
111 c1read();r1read();c2read();r2read();
112 if(r1r2){
113 swap(r1,r2);
114 swap(c1,c2);
115 }/*make sure that r1r2*/
116 if(r1r2c1!c2){
117 kr1;v0;pipe[k]0;
118 updata1(1,N,1);
119 }
120 if(r1!r2c1c2){
121 r1min(r1,r2);
122 toright[c1-1][r1]0;kr1;
123 updata2(1,N,1);
124 }
125 }
126 if(s[0]A){
127 c1read();r1read();c2read();r2read();
128 if(c1c2r1r2){puts(Y);continue;}
129 if(r1r2){
130 swap(r1,r2);
131 swap(c1,c2);
132 }/*make sure that r1r2*/
133 limleft1;limrightr1;Tree go_leftget(1,N,1);
134 limleftr1;limrightr2;Tree go_midget(1,N,1);
135 limleftr2;limrightN;Tree go_rightget(1,N,1);
136 if(r1r2c1!c2){
137 if(go_left.rurd||go_right.luld||go_mid.luld)puts(Y);
138 else puts(N);
139 }
140 if(r1!r2c1c2){
141 if(c11){
142 if((go_left.rurdgo_mid.ldrdgo_right.luld)||go_mid.luru||(go_left.rurdgo_mid.ldru)||(go_right.luldgo_mid.lurd))puts(Y);
143 else puts(N);
144 }else{
145 if((go_left.rurdgo_mid.lurugo_right.luld)||go_mid.ldrd||(go_left.rurdgo_mid.lurd)||(go_right.luldgo_mid.ldru))puts(Y);
146 else puts(N);
147 }
148 }
149 if(r1!r2c1!c2){
150 if(c11){/*left up to right down*/
151 if((go_left.rurdgo_mid.ldrd)||go_mid.lurd||(go_left.rurdgo_mid.ldrugo_right.luld)||(go_mid.lurugo_right.luld))puts(Y);
152 else puts(N);
153 }else{/*left down to right up*/
154 if((go_left.rurdgo_mid.luru)||go_mid.ldru||(go_left.rurdgo_mid.lurdgo_right.luld)||(go_mid.ldrdgo_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 Nread();
167 build(1,N,1);
168 slove();
169 return 0;
170 } 转载于:https://www.cnblogs.com/Kaike/p/5861568.html
