欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

D6

程序员文章站 2022-04-27 23:42:28
...

今天依旧很惨...本来第二题可以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..