|
|
今天做的还可以，当然，对我来说。唯一的缺点是别人当水题做的D我没做出来。简单的BFS，我愣是不会。哎，还是要把基础打好啊。最后A掉3道，还有一道线段树的没有过，过些时间补上。我该抓紧时间复习了...  A - River Pollution
线段树，求面积的并，很基础的线段树+离散化+扫描线，但我就是不会~
B - Middle number
今天这个是第一个过的，如果这个不过我相信后边会更加艰难。给定一个数的序列，然后不断的插入数字并保持递增，最后询问中间的数是多少。如果
数的个数是偶数，输出中间两个中小的。数据很大，时间是5s，我冒了个险，第一次先排序，每次二分找到要插入的位置，然后顺序修改后边的序列，过了！
二分的效率啊!!我看到后边这个题无数人TLE到死。。。这个题给了我很大信心，不然。。。
现在知道了，正解是用两个堆，一个大顶堆，一个小顶堆，大顶堆只能和小顶堆元素个数相同或者正好多一个。开始时将小的一般给大顶堆，大的一半给小顶堆，插入时和堆顶元素比一下，若大于大顶堆的堆顶元素，则插给小堆，否则给了大堆。询问时只需输出大堆的堆顶元素就可以了。
C - Game of Stones
JL出的题，乍一看很难，但是后来才知道简单的要命：两个人A和B玩游戏，有两堆石子M和N，每次两个人都至少从两堆中任意一堆拿至少一个石子，直到两堆石子都为空最后一个拿的人WIN。，A总是第一个拿，给定M和N，问A能否获胜。( 0 < M , N < 10^50 )
答案：如果M==N，A输，否则，A赢。我考虑到奇偶上了，结果WA了5次，哎。。。
D - The longest athletic track
给定N个点，和一棵生成树（N-1条边），最后问最长的一条路是多少。
上图的答案是80。
求树的直径，两次BFS，第一次任选起点，则终点一定是直径的一个端点。然后再来一次BFS就可以了。
E - Buy Car
Brent喜欢骑摩托，现在有N个城市，Brent 想把所有城市逛一遍，但是他怕油不够。每升油可以跑10km，他可以在任何一个城市加油。给出M条边，
最后问Brent的摩托的容量最小是多少，如果不能逛完所有城市，输出-1。
简单的最小生成树(正是Brent讲座讲的~)，找出最小生成树最小的一条边长度为A。如果A%10==0，答案是A/10;否则答案是A/10+1;
最后排名大概是10名？(除去老队员和admin大概是7,8名的样子)，问题应该不大了。嘻嘻，加油吧~ 可恶的BFS。。。一定搞定它。
这道题用到了一个我不知道的定理，Pick定理。意思是格子面上的多边形的边的点的个数on和内部点的个数in的关系式Area = on / 2 + in - 1; 求Area可以用叉乘法。注意最后那个Area/=2.0。 Code：
  /**//*TOJ 1011 Area
 pick theory */
 #include<stdio.h>
#include<stdlib.h>
#include<math.h>
int px[100],py[100];
int gcd(int a,int b) {
 int temp;
  while(b!=0){
temp=b;
b=a%b;
a=temp;
 }
return a;
}
int main(void)
{
int cas,dx,dy,on,in,i,j,n;
double area;
scanf("%d",&cas);
for(j=1;j<=cas;j++){
scanf("%d",&n);
px[0]=py[0]=dx=dy=area=on=0;
for(i=1;i<=n;i++){
scanf("%d%d",&dx,&dy);
on+=gcd(abs(dx),abs(dy));
px[i]=px[i-1]+dx;
py[i]=py[i-1]+dy;
area+=(px[i-1]*py[i]-px[i]*py[i-1]);
}
area=area/2.0;
in=area+1-on/2;
printf("Scenario #%d:\n%d %d %.1lf\n\n",j,in,on,area);
}
}
简单的DP，大意是给出N场比赛球队的输，平，赢的场数，最后问M场比赛至少拿S分的概率。赢一场3分，平一场1分，输0分。 dp[i][j]表示 i 场比赛得 j 分的概率。则有转移方程dp[i][j]=dp[i-1][j-3]*r1+dp[i-1][j-1]*r2+dp[i-1][j]*r3;(r1,r2,r3分别表示每一场赢，平，输的概率) Code：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
double dp[90][270];
int main()
{
int i,j,k,n,m;
double r1,r2,r3,sum;
while(scanf("%d%d",&n,&m),n+m){
scanf("%d%d%d",&i,&j,&k);
r1=i*1.0/(i+j+k);
r2=j*1.0/(i+j+k);
r3=k*1.0/(i+j+k);
memset(dp,0,sizeof(dp));
dp[1][0]=r3;dp[1][1]=r2;dp[1][3]=r1;
for(i=2;i<=n;i++)
for(j=0;j<=3*i;j++){
if(j<=0) // 防止数组下标出现负数
dp[i][j]=dp[i-1][j]*r3;
else if(j<=1) //同上
dp[i][j]=dp[i-1][j]*r3+dp[i-1][j-1]*r2;
else
dp[i][j]=dp[i-1][j]*r3+dp[i-1][j-1]*r2+dp[i-1][j-3]*r1;
}
sum=0.0;
for(i=m;i<=3*n;i++)
sum+=dp[n][i];
printf("%.1lf\n",sum*100);
}
}
一个结论很简单的问题，对于任意两个数a,b(a,b>=2)
1)如果gcd (a,b)==1，则最大的不能由a，b线性表示的数为a*b-a-b；
2)否则这个数时无穷大
至于证明，期待大牛给出，我还是不懂，一开始往拓展欧几里得想的，但后来也没什么结论。
哪位神牛知道证明给点提示，不胜感谢~
Code略去(太水了)
一个求逆序对的题，N个数，N<=500000，问排成递增序列需要相邻的数交换多少次。一开始没有仔细看题，上来就做，后来才发现数的范围是999999999。因为最多500000个数，所以数和数之间的间隔很大，可以处理一下，使数的间隔变小，然后使用树状数组统计某个数前边的比它大的数的个数。将所有的数放到一个结构体里，称作num，并增加一个成员id，然后按num递增排列，再另开一个数组给每个数重新编号，使数的范围都在N以内。然后就可以很自然的用树状数组做了。时间500ms。据说归并排序比这个要快。 Code：
1 #include<iostream>
2 #include<algorithm>
3 #define M 500001
4 using namespace std;
5 int c[M],aa[M],n; //aa数组为排序后重新编号用
6 struct digit
7 {
8 int num,id;
9 }a[M]; //num为数的大小
10 bool cmp(digit a,digit b){
11 return a.num<b.num;
12 }
13 int lowbit(int t){
14 return t&(t^(t-1));
15 }
16 int sum(int t){
17 int total=0;
18 while(t>0){
19 total+=c[t];
20 t-=lowbit(t);
21 }
22 return total;
23 }
24 void update(int t,int key){
25 while(t<=n){
26 c[t]+=key;
27 t+=lowbit(t);
28 }
29 }
30 int main()
31 {
32 int i,j;
33 long long ans;
34 while(scanf("%d",&n),n){
35 memset(c,0,sizeof(c));
36 ans=0;
37 for(i=1;i<=n;i++){
38 scanf("%d",&a[i].num);
39 a[i].id=i;
40 }
41 sort(a+1,a+n+1,cmp);
42 aa[a[1].id]=1; //最小的数编号为1
43 for(i=2;i<=n;++i){
44 if(a[a[i].id].num!=a[a[i-1].id].num) //如果前后两个数不等，则编号为下标
45 aa[a[i].id]=i;
46 else
47 aa[a[i].id]=aa[a[i-1].id]; //否则编号与前一个相同
48 }
49 //for(i=1;i<=n;i++) printf("%d ",aa[i]);
50 for(i=1;i<=n;++i){
51 update(aa[i],1);
52 ans+=(sum(n)-sum(aa[i])); //每次累加该数前边比它大的数的个数
53 }
54 printf("%lld\n",ans);
55 }
56 }
简单的二维树状数组，求一个矩形区域内的和，因为要随时增减，而且可能减的数比原来都大，所以需要保留原来的数组。 在求矩形区域和的时候，只要用最大的矩形减去两个小的，再加上那个多减的最小的，就OK了。1y~~ Code：
1 #include<iostream>
2 #define M 1300
3 int c[M][M],a[M][M],n;
4 int lowbit(int t){
5 return t&(t^(t-1));
6 }
7 int sum(int p,int q){
8 int x=p,y,total=0;
9 while(x>0){
10 y=q;
11 while(y>0){
12 total+=c[x][y];
13 y-=lowbit(y);
14 }
15 x-=lowbit(x);
16 }
17 return total;
18 }
19 void modify(int p,int q,int key){
20 int x=p,y;
21 while(x<=n){
22 y=q;
23 while(y<=n){
24 c[x][y]+=key;
25 y+=lowbit(y);
26 }
27 x+=lowbit(x);
28 }
29 }
30 int main()
31 {
32 int i,j,k,jj,kk,m,order,ans;
33 scanf("%d%d",&i,&n);
34 memset(c,0,sizeof(c));
35 memset(a,0,sizeof(a));
36 while(scanf("%d",&order)!=EOF){
37 if(order==3) break;
38 else if(order==1){
39 scanf("%d%d%d",&j,&k,&m);
40 ++j; ++k;
41 if(m<0&&m*(-1)>a[j][k]){
42 m=(-1)*a[j][k];
43 modify(j,k,m);
44 a[j][k]=0;
45 }
46 else{
47 modify(j,k,m);
48 a[j][k]+=m;
49 }
50 }
51 else if(order==2){
52 scanf("%d%d%d%d",&j,&jj,&k,&kk);
53 ++j; ++jj; ++k; ++kk;
54 //printf("%d ",sum(n,n));
55 ans=sum(k,kk)+sum(j-1,jj-1)-sum(k,jj-1)-sum(j-1,kk);
56 printf("%d\n",ans);
57 }
58 }
59 }
今天联系树状数组，但是我发现我真的很笨，做了好几道了还是不熟。这个题和前边的也没什么分别，是说每个牛有一个区间[s,e],两个牛[s1,e1], [s2,e2]，当s1<=s2并且e1>=e2并且e1-s1>e2-s2时，我们说牛1比牛2强，给N个牛的区间，对于每个牛，输出比这个牛强的牛的个数。 还是需要预处理，先对每个牛的e进行降序排序，e相同时对s进行升序排列，这样循环时可以保证后边的牛绝对不比前边的牛强。在循环时，只需找出比当前牛s小的牛的个数。如果遇到特殊情况，即两个牛区间完全一样，赋值就可以了。哎，加油吧~ Code：
1 #include<iostream>
2 #include<algorithm>
3 #include<map>
4 #define MAX 100002
5 using namespace std;
6 int c[MAX],ans[MAX],n,imax;
7 struct cow
8 {
9 int l,r,id;
10 }a[MAX];
11 bool cmp(cow a,cow b){
12 if(a.r==b.r) //如果两个牛区间右边界相同，按左边界的升序排列
13 return a.l<b.l;
14 return a.r>b.r; //按右边界的降序排列
15 }
16 int lowbit(int t){
17 return t&(t^(t-1));
18 }
19 int sum(int t){
20 int total=0;
21 while(t>0){
22 total+=c[t];
23 t-=lowbit(t);
24 }
25 return total;
26 }
27 void modify(int posi,int key){
28 while(posi<=imax){
29 c[posi]+=key;
30 posi+=lowbit(posi);
31 }
32 }
33 int main()
34 {
35 int i,j,k,n;
36 while(scanf("%d",&n),n){
37 memset(c,0,sizeof(c));
38 imax=0;
39 for(i=1;i<=n;i++){
40 scanf("%d%d",&a[i].l,&a[i].r);
41 a[i].id=i; //每个牛有个id防止排序完顺序变乱
42 ++a[i].l; ++a[i].r;
43 if(imax<a[i].l) imax=a[i].l; //用imax表示右边界最大值，即求和时的边界
44 }
45 sort(a+1,a+n+1,cmp);
46 for(i=1;i<=n;++i){
47 if(i==1){
48 ans[a[i].id]=sum(a[i].l); //这里注意是ans[a[i].id]而不是ans[i]
49 modify(a[i].l,1);
50 }
51 else{
52 if(a[i].l==a[i-1].l&&a[i].r==a[i-1].r) //如果两个牛完全相同，直接赋值
53 ans[a[i].id]=ans[a[i-1].id];
54 else
55 ans[a[i].id]=sum(a[i].l); //否则找出左边界l比这个牛小的
56 modify(a[i].l,1);
57 }
58 }
59 for(i=1;i<n;++i)
60 printf("%d ",ans[i]);
61 printf("%d\n",ans[i]);
62 }
63 }
64
这道题和那道Star如出一辙，可我还是做了很长时间 ...太菜了...有K条连接东西两个城市的路，东西方向每个城市都有一个编号M,N，从北到南，最后问共有多少个十字路都，即有多少个交点。 先预处理，用结构体表示每条边，对结构体按N进行从小到大的排序，如果N相同，按M从小到大排序。接下来就和Star一样了，唯一不同的是Star那道题是每次求出当前星星前边的个数，而这个是求当前点后边的个数。用c[]表示树状数组，sum(n)求出的是N编号小于等于n的city的个数，只需每次拿出一个city，求出N编号大于它的city的个数，然后更新数组就可以了。 关键代码：
1 long long ans=0;
2 for(i=1;i<=K;i++){ //K表示边的个数
3 ans+=sum(max)-sum(a[i].east); //east即为N编号
4 modify(a[i].east,1); //将a[i].east插入到当前数组
5 }
6
解决了这一步，其余就是套路了，很简单。 Code：
1 #include<iostream>
2 #include<algorithm>
3 #define MAX 10005 //最大的city个数
4 using namespace std;
5 int c[MAX],n,N,M,K,omax;
6 struct road
7 {
8 int west,east;
9 }a[MAX*MAX]; //MAX*MAX为最多的边的个数
10 bool cmp(road a,road b){
11 if(a.west==b.west)
12 return a.east<b.east;
13 return a.west<b.west;
14 }
15 int lowbit(int t){
16 return t&(t^(t-1));
17 }
18 int sum(int t){
19 int total=0;
20 while(t>0){
21 total+=c[t];
22 t-=lowbit(t);
23 }
24 return total;
25 }
26 void modify(int posi,int key){
27 while(posi<=omax){
28 c[posi]+=key;
29 posi+=lowbit(posi);
30 }
31 }
32 int main()
33 {
34 int i,j,k,m,cas;
35 long long ans;
36 scanf("%d",&cas);
37 for(i=1;i<=cas;++i){
38 omax=0; //用omax表示所有east的最大值，以确定求和区间
39 memset(c,0,sizeof(c));
40 scanf("%d%d%d",&N,&M,&K);
41 for(j=1;j<=K;++j){
42 scanf("%d%d",&a[j].east,&a[j].west);
43 if(a[j].east>omax)
44 omax=a[j].east;
45 }
46 sort(a+1,a+1+K,cmp);
47 ans=0;
48 for(j=1;j<=K;++j){ //key code
49 ans+=(sum(omax)-sum(a[j].east));
50 modify(a[j].east,1);
51 }
52 printf("Test case %d: %lld\n",i,ans);
53 }
54 }
55
大意是N个星星，规定每个星星的等级为在它左下方星星的数量（包括某个坐标相等），N范围是15000，输入按y坐标的升序给出，如果两个星星y坐标相等，按x坐标升序给出。 用树状数组，不用管y坐标（因为已经是升序，后边的星星不影响前边星星的等级），用sum(n)来统计x坐标为n以前的星星个数，但是千万注意树状数组需要数组以1为首项，由于坐标有0，所以每次需要给x坐标+1。另外，通过这个题，我发现++i果然比i++快。两者一个420ms，一个360ms。还是差不少的，以后尽量用++i了:D Code：
1 #include<stdio.h>
2 #include<string.h>
3 #define M 32006 //坐标范围是32000
4 int c[M],ans[M/2]; //c为树状数组，ans[i]表示level为i的星星个数
5 int lowbit(int t){
6 return t&(t^(t-1));
7 }
8 int sum(int m){
9 int total=0;
10 while(m>0){
11 total+=c[m];
12 m-=lowbit(m);
13 }
14 return total;
15 }
16 void modify(int position){
17 while(position<=32002){
18 ++c[position];
19 position+=lowbit(position);
20 }
21 }
22 int main()
23 {
24 int x,y,i,j,n;
25 scanf("%d",&n);
26 j=n;
27 memset(c,0,sizeof(c));
28 memset(ans,0,sizeof(ans));
29 while(n--){
30 scanf("%d%d",&x,&y);
31 ++ans[sum(x+1)];
32 modify(x+1);
33 }
34 for(i=0;i<j;++i)
35 printf("%d\n",ans[i]);
36 }
TOJ有道题，大意是有N个位置，每个位置有若干瓶子，Mike很淘气，他每次会增加或减少位置i的瓶子数，然后有M次询问，求位置A到B的瓶子数的和。最开始，我一直用最直观的做法，但是由于是O(n)的复杂度，所以一直超时。今天看了BIT的相关东西，才发现那个题其实是典型的BIT题目，而且是最基础的，但是就和RMQ问题一样，高效的算法背后深刻的数学理论还是不能很透彻的理解，这个只有靠以后熟练的慢慢来了：D
先来看一下树状数组的概念：树状数组是一种静态树状数据结构，它的首要作用是维护前缀和，即改变数组中某一元素a[i]的值，若要询问前N项的和，树状数组便可完美解决。时间复杂度O(logn)。
先来直观看一下树状数组的结构（图片来自http://fqq11679.blog.hexun.com/21722866_d.html#）
在上图中，红色的数组c[]便是树状数组。改变数组a的某一个元素i，则需要相应的改变数组c，若要询问前N项和，只需累加相应的c，而这当中一个核心的问题便是相应的数组c的下标问题。可以用位操作lowbit解决。c[i]=a[i-2^k+1]到a[i]的和，k是指i用二进制表示时末位0的个数，即将i表示成幂方和后最小的指数。利用位运算，我们可以得知2^k=i&(i^(i-1));
相应的代码为：
1 int lowbit(int n)
2 {
3 return n&(n^(n-1));
4 }
这样，当a[i]改变时，我们只需从c[i]开始一直向上回溯，改变路上相应的数组c的值，若要求前N项和，只需求N以前所有最大子树c[]的和。然后我们来看相应下标的操作：
修改a[i],则修改一路的父节点c[p], p=i-bit(i);
若要前i项求和，只需一路找子节点c[p], p=i-lowbit(i);
求前N项和：
1 int sum(int n)
2 {
3 int total=0;
4 while(n>0){
5 total+=c[n];
6 n-=lowbit(n);
7 }
8 return total;
9 }
TOJ 3505 Naughty mike Code：
1 /*TOJ 3505 Naughty mike*/
2 #include<stdio.h> //注意在使用树状数组时下标一定不能从0开始
3 #include<string.h>
4 #define M 100002
5 int a[M],n;
6 int c[M];
7 int lowbit(int t) //关键的位操作确定数组下标
8 {
9 return t&(t^(t-1));
10 }
11 int sum(int end) //求前end项和的函数，通过不断累加最大子树得到
12 {
13 int i;
14 int total=0;
15 while(end>0){
16 total+=c[end];
17 end-=lowbit(end);
18 }
19 return total;
20 }
21 void modify(int t,int key) //对数组某一项进行修改时，只需沿该项一直向上回溯修改相应的数组c
22 {
23 while(t<=n){
24 c[t]+=key;
25 t+=lowbit(t);
26 }
27 }
28 int main()
29 {
30 int i,j,k,m,cas;
31 char e[50];
32 scanf("%d",&cas);
33 while(cas--){
34 scanf("%d",&n);
35 memset(c,0,sizeof(c));
36 for(i=1;i<=n;i++){
37 scanf("%d",&a[i]);
38 modify(i,a[i]);
39 }
40 scanf("%d",&m);
41 while(m--){
42 scanf("%s%d%d",e,&i,&j);
43 if(e[0]=='A'){
44 modify(i,j);
45 a[i]+=j;
46 }
47 else if(e[0]=='D'){
48 if(j>=a[i]) j=(-1)*a[i]; //由于可能删除的比现有的还多，需要分开考虑
49 else j*=(-1);
50 modify(i,j);
51 a[i]+=j;
52 }
53 else
54 printf("%d\n",sum(j)-sum(i-1)); //区间[i,j]的和
55 }
56 }
57 }
58
|