首页 > 代码库 > D12
D12
orz!=-=今天莫名爆人品..表示受到了惊吓..
一下子从rank20-30+,突然间蹦到了rank3..=-=可怕..
或许是因为T1有看过啊类似的啊..然后T3又被40指点了一下，T2打了个暴力神马的..
但是T4依旧不会写..
晚上的时间不想改T4了..打算补补队列的知识..
什么单调队列啊,优先队列啊，看看书，刷刷题，或是把之前没有发的题解补补啊..之类的
T1：类似于队列的模拟思想
首先需要用a数组存输入的数据，b数组存放i个城市有多少个人
还需要头指针 i 和尾指针 j
如果b[a[i]]>1或是区间大于规定的最大区间，就增加尾指针
记录下当前区间最大的城市数，以及区间长度
一个细节注意，如果城市数相同的情况下，记得比较区间的长度，更新
#include<cstdio>#include<cstring>using namespace std;const int INF=32768;int a[10000001],b[32768];int i=1,j=1,max=0,min=INF;int n,d,tot=0;int main(){ freopen("happy.in","r",stdin);freopen("happy.out","w",stdout); memset(b,0,sizeof(b)); scanf("%d%d",&n,&d); for (i=1;i<=n;i++){ scanf("%d",&a[i]); } i=1; while (i<=n) { b[a[i]]++; if (b[a[i]]==1) tot++; while ((b[a[j]]>1) || ((i-j+1)>d)) { b[a[j]]--; if (b[a[j]]==0) tot--; j++; } if (tot>max) { max=tot; min=i-j+1; } if ((tot==max)&& (min>i-j+1)) min=i-j+1; i++; } printf("%d %d",max,min); return 0;}PS:感觉这种题型是一种技巧类的题目吧
MARK一下..
T2:动规+一点点的贪心思想
很容易看出来是个DP题，但是如果用一个三维的数组，内存是不够的；
所以我们应该想想有没有更优的情况
比较会发现，红魔法师放在蓝绿法师后面的情况，必然是最优的；
所以，只要看蓝绿法师数就可以了..
这样就只需要用二维的数组即可，f[i][j]表示i个绿法师和i个蓝法师的伤害值
动规方程的话，其实理解题目意思了之后非常好理解
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(i+j<=n){
f[i][j] = max(f[i-1][j]+(i-1)*g*(j*b+t),f[i][j-1]+i*g*((j-1)*b+t));
}
}
PS:=-=别逗比忘了i+j<=n;
之后红法师就是n-i-j就可以了，不过不认真审题的童鞋注意一下，最后使用红法师的时候，蓝绿法师依旧会有伤害值..
附上代码
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int g,b,r,n,t;int ans=0;int f[1025][1025];int main(){ scanf("%d%d%d%d%d",&n,&r,&g,&b,&t); for(int i=1;i<=n;i++) f[0][i]=0; for(int i=1;i<=n;i++) f[i][0]=f[i-1][0]+g*t*(i-1); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ if(i+j<=n){ f[i][j] = max(f[i-1][j]+(i-1)*g*(j*b+t),f[i][j-1]+i*g*((j-1)*b+t)); } } for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) if(i+j<=n){ int k=n-i-j; ans=max(ans,f[i][j]+(r+i*g)*(j*b+t)*k); } printf("%d",ans); return 0;}
T3：数论或是搜索
其实这一题看起来是可以用数学方法解决的，之后经40大神指点，发现n*m/5就可以了..
那个傻逼程序就不附上了
不过DFS+剪枝的方法可以学习一下=-=
说一下题解上的剪枝的情况：
1最优化；2 每行每列每斜行的棋子数不超过这条边的长度a div 5+1；3 不可能出现连续的5个空白位置在行.列.斜行上。
=-=不过表示没有看懂std上的打法..
表示现在虽然对DFS有了很深的印象，不过对于剪枝还是很不会的..
晚上可以刷几题试试
附上DFS的代码:
program wuziqi;var i,j,k,n,zf,kw,ala,m,mm,nn,mn,minge:longint; a:array[-1001..1001]of longint; dx,dy:array[0..4,0..5]of longint; f:array[-1001..1001,0..9]of longint; z:array[-100..100,-100..100]of boolean; d:array[0..1001,0..8]of longint; hang,shu,zheng,fu,zl,fl,sl:array[-1001..1001]of longint;function min(q,w:longint):longint;begin if q<w then min:=q else min:=w;end;procedure dfs(step,sum,asd:longint);var zz,xx,cc,i,j,k,q,w:longint;begin if sum>=minge then exit; if (step>n*m) then begin for i:=1 to n do begin for j:=1 to m do if not z[i,j] then for k:=1 to 4 do begin for zz:=1 to 5 do if z[i+dx[k,zz],j+dy[k,zz]] then break; if not z[i+dx[k,zz],j+dy[k,zz]] then exit; end; end; minge:=sum; exit; end; q:=(step-1)div m+1; if step mod m=0 then w:=m else w:=step mod m; if (hang[q]<mm)and(shu[w]<nn) and(zheng[q+w]<mn)and(fu[q-w]<mn) and((n-q)div 5+shu[w]<nn)and((n-q)div 5+zheng[q+w]<mn) and((n-q)div 5+fu[q-w]<mn) then begin inc(zheng[q+w]); inc(hang[q]); inc(fu[q-w]); inc(shu[w]); z[q,w]:=true; zz:=sl[w]; xx:=zl[q+w]; cc:=fl[q-w]; zl[q+w]:=0; fl[q-w]:=0; sl[w]:=0; dfs(step+1,sum+1,0); zl[q+w]:=xx; fl[q-w]:=cc; sl[w]:=zz; z[q,w]:=false; dec(shu[w]); dec(hang[q]); dec(zheng[q+w]); dec(fu[q-w]); end; if (asd<4)and(sl[w]<4)and(zl[q+w]<4)and(fl[q+w]<4)then begin inc(sl[w]); inc(zl[q+w]); inc(fl[q-w]); if step mod m=0 then dfs(step+1,sum,0) else dfs(step+1,sum,asd+1); dec(sl[w]); dec(zl[q+w]); dec(fl[q-w]); end; end;beginassign(input,‘company.in‘);reset(input);assign(output,‘company.out‘);rewrite(output);readln(n,m);dx[1,1]:=-2;dx[1,2]:=-1;dx[1,3]:=1;dx[1,4]:=2;dy[2,1]:=-2;dy[2,2]:=-1;dy[2,3]:=1;dy[2,4]:=2;dx[3,1]:=-2;dx[3,2]:=-1;dx[3,3]:=1;dx[3,4]:=2;dy[3,1]:=-2;dy[3,2]:=-1;dy[3,3]:=1;dy[3,4]:=2;dx[4,1]:=-2;dx[4,2]:=-1;dx[4,3]:=1;dx[4,4]:=2;dy[4,1]:=2;dy[4,2]:=1;dy[4,3]:=-1;dy[4,4]:=-2;fillchar(z,sizeof(z),1);for i:=1 to n do for j:=1 to m do z[i,j]:=false;if n<m then zf:=nelse zf:=m;mm:=m div 5+1;nn:=n div 5+1;mn:=zf div 5+1;if m mod 5=0 then dec(mm);if n mod 5=0 then dec(nn);if zf mod 5=0 then dec(mn);minge:=n*m div 5+1 ;dfs(1,0,0);writeln(minge);close(input);close(output);end.
T4:单调队列+DP优化+二分答案
我表示对于二分啊，单调队列啊，还是没有什么很概念的理解，所以这一题暂且不究
晚上就好好学习一下基础的东西吧
嗯..明天继续加油
不想被笑尘黑啦...><