第一题 大天使之剑 大意：
有n个怪，每个怪的ph 为 h[i],有三种攻击方式，普通攻击：一次打一个怪一滴血；重击（消耗1魔法值）：一次打一个怪两滴血；群体攻击（消耗1魔法值）：一次打所有怪一滴血。你有无数血，m个魔法值，每攻击一次怪后，还存活的所有怪会各攻击你一滴血。问你打完所有怪你最少被打了多少滴血。
解：
看到这道题，首先想到的是搜索，一种一种的搜，把所有情况都搜出来找最小。在草稿纸上再列一些数据就会发现，其实是个贪心。在有魔法值的时候，尽量全用于群体攻击更划算，然后没有了就普通攻击。那重击呢？由于我的数据比较特殊，所以我判重击的条件是还剩两个偶数滴血的怪，但其实，不管它的血量是偶数还是奇数，重击都更划算。还有一些杂七杂八的减没减过sum的问题等，让我调试了一个下午。看来以后静态查错很重要，少犯小错误。代码写得丑。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 100005 6 #define ll long long 7 using namespace std; 8 ll n,m,ph[maxn],ans,sum,cur=1; 9 bool jian[maxn]; 10 void print() 11 { 12 printf("%I64d",ans); 13 return ; 14 } 15 int main() 16 { 17 freopen("zhijian.in","r",stdin); 18 freopen("zhijian.out","w",stdout); 19 cin>>n>>m; 20 for (int i=1;i<=n;i++) 21 scanf("%d",&ph[i]); 22 sort(ph+1,ph+1+n); 23 while (m) 24 { 25 if (n-cur+1<=2){//改用重击 26 for (int i=cur;i<=n;i++) 27 if (!jian[i]) ph[i]-=sum; 28 while(m){ 29 if (cur>n) { 30 print();return 0; 31 } 32 if (ph[cur]<=2){ 33 ans+=n-cur; 34 cur++;continue; 35 } 36 ph[cur]-=2; 37 ans+=n-cur+1; 38 m--; 39 } 40 while (cur<=n){ 41 if (ph[cur]){ 42 int ci=ph[cur]-1; 43 ans+=(n-cur+1)*ci; 44 } 45 ans+=n-cur; 46 cur++; 47 } 48 print(); 49 return 0; 50 } 51 sum++; 52 ph[cur]--;int h=cur; 53 jian[cur]=true; 54 ans+=n-cur+1; 55 while (ph[cur]<=0){ 56 ans--; 57 cur++; 58 ph[cur]-=sum; 59 jian[cur]=true;//判断 60 } 61 m--; 62 } 63 while (cur<=n){ 64 if (!jian[cur]) ph[cur]-=sum;//直接减会多减 65 if (ph[cur]){ 66 int ci=ph[cur]-1; 67 ans+=(n-cur+1)*ci; 68 } 69 ans+=n-cur; 70 cur++; 71 } 72 printf("%I64d",ans); 73 return 0; 74 }
第二题 保卫萝卜 大意：
一个很大的矩阵，起点在正中心的方格。数据有向上下左右四个方向走的记录，输出走过的方格及所围的方格数。
解：
有两种大体思路。一个是直接正着算面积，还有反着算走不到的点。我用的后者。但有一个问题，就是存矩阵。我把它走过的地方的最左边上面下面和右边记录下来，然后在这个包含它走的所有路的方格中从0,0开始遍历dfs，到不了的地方vis=false，即为ans++。注意要在搜索范围中再加一圈，因为可能走过的路把这个范围隔开了，就搜索不到。但这是60分的做法，100分做法要用离散化坐标的思想，先放一下。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 2005 6 using namespace std; 7 const int zl[2][4]={{0,0,1,-1},{1,-1,0,0}}; 8 int n,xi,yi,idx,sum,ans; 9 bool mp[maxn][maxn],vis[maxn][maxn]; 10 int uup,don,le,ri,stx,sty; 11 struct pp{ 12 int x,y; 13 }; 14 pp tur[1005]; 15 char c[1005]; 16 void dfs(int xx,int yy) 17 { 18 for (int i=0;i<=3;i++) 19 { 20 int ki=xx+zl[0][i],kj=yy+zl[1][i]; 21 if (ki>=0&&kj>=0&&ki<=ri&&kj<=uup&&!vis[ki][kj]&&!mp[ki][kj]) 22 { 23 vis[ki][kj]=true; 24 sum++;dfs(ki,kj); 25 } 26 } 27 } 28 int main() 29 { 30 freopen("luobo.in","r",stdin); 31 freopen("luobo.out","w",stdout); 32 cin>>n; 33 getchar(); 34 for (int i=1;i<=n;i++) 35 { 36 c[i]=getchar(); 37 getchar();int a; 38 scanf("%d",&a); 39 if (c[i]=='L') {stx-=a;if (stx<le) le=stx;} 40 else if (c[i]=='R'){stx+=a;if (stx>ri) ri=stx;} 41 else if (c[i]=='U') {sty+=a;if (sty>uup) uup=sty;} 42 else if (c[i]=='D'){sty-=a;if (sty<don) don=sty;} 43 tur[++idx].x=stx;tur[idx].y=sty; 44 getchar(); 45 } 46 xi=-le+1;yi=-don+1;uup+=-don+2;ri+=-le+2; 47 mp[xi][yi]=true; 48 for (int i=1;i<=idx;i++) 49 { 50 tur[i].x+=-le+1;tur[i].y+=-don+1; 51 int a=min(xi,tur[i].x),b=max(xi,tur[i].x),ci=min(yi,tur[i].y),d=max(yi,tur[i].y); 52 for (int j=a;j<=b;j++) 53 for (int k=ci;k<=d;k++) 54 mp[j][k]=true; 55 xi=tur[i].x;yi=tur[i].y; 56 } 57 dfs(0,0); 58 for (int i=0;i<=ri;i++) 59 for (int j=0;j<=uup;j++) 60 if (!vis[i][j]) ans++; 61 printf("%d",ans); 62 return 0; 63 }
第三题 打地鼠 大意：
（没错怎么都是游戏的名字）打地鼠，打的这个地鼠的肥胖值一定要比上一个打的大。地鼠最多出现t次，问最多能打多少地鼠。
解：
看起来是个简单的最长上升序列。但是有一个t次，所以直接扫描加一个循环t就可以了，是不影响的。然后LIS 的nlogn的算法才能过这道题。具体的解释我觉得这个博客讲的就很清楚。http://blog.csdn.net/shuangde800/article/details/7474903
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 100005 6 using namespace std; 7 int n,maxx,k,t,a[maxn],d[maxn],ans; 8 int main() 9 { 10 freopen("dishu.in","r",stdin); 11 freopen("dishu.out","w",stdout); 12 cin>>k>>n>>maxx>>t; 13 while (k--) 14 { 15 memset(d,0,sizeof(d)); 16 int idx;ans=0; 17 for (int i=1;i<=n;i++) 18 scanf("%d",&a[i]); 19 d[1]=a[1];ans=1; 20 for(int i=1;i<=t;i++) 21 for (int j=1;j<=n;j++) 22 { 23 if (a[j]>d[ans]) d[++ans]=a[j]; 24 else { 25 int pos=lower_bound(d+1,d+1+ans,a[j])-d;//-d not -d-1 ? 26 d[pos]=a[j]; 27 } 28 } 29 printf("%d ",ans); 30 } 31 return 0; 32 }
好好睡一觉，明天联考加油，不要有压力。