今天依旧很惨...本来第二题可以A的,感觉很久没有碰数学,出现这样的低级错误,简直逗了...晚上的话打算找了书店,静下心来看点书进去吧
但是其他题目就不太好写了..我直接发题解好了
T1:贪心
其实贪心是最好写的,但是贪心特别考一个人的代码能力...哎..像我这样打代码打得不够多的人..
一遇到贪心,就很容易出现神马,模拟的时候呵呵啊..或是那个变量又打错的情况..TAT..
附上代码+注释:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long n,tot=0,sum=0,ans=0,k,l,ll,maxn,maxi;
int a[3001],b[3001];
int main(){
//freopen("game.in","r",stdin);freopen("game.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i],&b[i]);
if(b[i]>2*n){//因为最大的情况就是第二难度都可以过,所以最大值为2*n,如果B[I]>2*n,就不可能有解
printf("Too Bad\n");
return 0;
}
}
l=0;ll=0;//l表示过第二难度的数目,ll表示最少的游戏次数
while(l<n){
k=0;
tot=sum;//这是用来判断sum的值是否改变,如果sum的值没有改变,说明没有可以玩的游戏了,也就没有解了
for(int i=1;i<=n;i++){
if(b[i]!=-1 && sum>=b[i]){
sum+=2;
if (a[i]==-1) sum--;//如果第一难度有玩过,就减一..PS:审题!
a[i]=-1;//因为能力值只于当前的最高难度有关,所以如果玩过了第二难度,第一难度就没有必要玩了
b[i]=-1;//所以都记录为已经玩过了
l++;
ll++;
k=1;//记录已经有第二难度可以玩了
break;
}
}
maxn=0;
maxi=0;
for(int i=n;i>=1;i--){
if(k==1) break;//如果已被记录,则break..看看还有没有可以玩第二难度的游戏
if(a[i]<=sum && a[i]!=-1 && b[i]>maxn){//记录最大的即可...
maxn=b[i];
maxi=i;
}
}
if(maxi!=0){//玩第一难度的情况
a[maxi]=-1;
sum++;
ll++;
}
if(tot==sum){//sum的值不改变...
printf("Too Bad\n");
return 0;
}
}
printf("%d",ll);
return 0;
}
T2:应该算是数论吧...
keso...如此白痴的题目我居然写错了...你妹啊..直接判断某个点在不在那个范围之内不就得了..我个傻逼 当时居然去枚举...简直是有病!
#include <cstdio>
#include <algorithm>
using namespace std;
int n, a[2000][6], ans;
bool cover(int i, int j){
if (a[i][3] < a[j][0] || a[j][3] < a[i][0]) return 0;
if (a[i][4] < a[j][1] || a[j][4] < a[i][1]) return 0;
if (a[i][5] < a[j][2] || a[j][5] < a[i][2]) return 0;
return 1;
}
int main(){
freopen("prostor.in", "r", stdin);
freopen("prostor.out", "w", stdout);
scanf("%d", &n);
for (int i = 0; i < n; i++){
scanf("%d%d%d%d%d%d",
&a[i][0], &a[i][1], &a[i][2], &a[i][3], &a[i][4], &a[i][5]);
if (a[i][0] > a[i][3])
swap(a[i][0], a[i][3]);
if (a[i][1] > a[i][4])
swap(a[i][1], a[i][4]);
if (a[i][2] > a[i][5])
swap(a[i][2], a[i][5]);
}
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
ans += cover(i, j);
printf("%d\n", ans);
return 0;
}
T3:据某个大神说是两遍spfa..
var
first:array[1..20000] of longint;//模拟邻接表用到
h:array[1..200000] of longint;//队列
bo:array[1..200000] of boolean;//判断是否在队列中
w,en,next,start,cost,jiange,sum:array[0..20000] of longint;//数组模拟邻接表
b:array[1..2000] of longint;//存每个巴士的路线
n,m,qi,zhong,i,j,shumu,jian,totm,qikai,head,tail,temp,kaishi,tot,duo,tot1,tot2,total,last,c:longint;
dis:array[1..20000] of longint;//dis[i]表示到i所费的最短时间
procedure spfa(pre,suc,chu:longint);//pre是起点,suc是终点,chu代表初值
begin
fillchar(bo,sizeof(bo),false);
fillchar(dis,sizeof(dis),$7f div 3);
head:=0;tail:=1;h[1]:=pre;bo[pre]:=true;
dis[pre]:=chu;
while head<tail do//spfa部分我解释一下
begin
inc(head);
temp:=h[head];//取出队头
bo[temp]:=false;//这个队头元素不再存在于队列中
qikai:=first[temp];//到表头
while qikai<>0 do//如果不为空 在链表中可以表示为<>nil
begin
kaishi:=start[qikai];//start[i]表示到i这个点所花费的时间tot*k+x中的x k是间隔时间
tot:=0;
while kaishi+tot*jiange[qikai]<dis[temp] do inc(tot);//不断更新tot的值使得tot*k+x>=dis[temp] 这样它才能//坐到车
duo:=kaishi+tot*jiange[qikai]-dis[temp];//这是他要等的时间
if dis[temp]+w[qikai]+duo<dis[en[qikai]] then//按照三角不等式更新最短时间 ,en[k]是这个空间的出度元素
begin
dis[en[qikai]]:=dis[temp]+w[qikai]+duo;//更新!
if not bo[en[qikai]] then//如果不存在于队列中就入队
begin
bo[en[qikai]]:=true;
inc(tail);
h[tail]:=en[qikai];
end;
end;
qikai:=next[qikai];//下一个
end;
end;
tot1:=dis[suc];
end;
begin
assign(input,'water.in');
reset(input);
assign(output,'water.out');
rewrite(output);
totm:=0;
fillchar(first,sizeof(first),0);
readln(n,m,qi,zhong);
for i:=1 to m do
begin
read(shumu);
for j:=1 to shumu do read(b[j]);
readln;
read(jian);
last:=0;
for j:=1 to shumu-1 do//改变了一下方式直接存
begin
read(c);//读入巴士间隔
inc(totm);//增加节点
next[totm]:=first[b[j]];//链式存储
first[b[j]]:=totm;//串连起来
w[totm]:=c-last;//这是减去上一个,剩下的就是当前的信息了
start[totm]:=last;//这是这个我上述tot*k+x中的x(在累加)
jiange[totm]:=jian;//记录间隔
en[totm]:=b[j+1];//记录出度
last:=c;//方便下一个的存储
end;
readln;
end;
close(input);
spfa(qi,zhong,0);//从起点到终点的spfa,最后dis[zhong]记录在tot1中
spfa(zhong,qi,tot1);//从终点到起点的spfa,因为时间不能间断所以初值为tot1,最后dis[qi]记录在tot1中
writeln(tot1);//
close(output);
end.
T4:DP..
依旧不会TAT..