搜索

标签云

分类

声明

文章若未特別註明，皆採用

請自覺遵守

鏈。。。

存档

匆匆过客

83585

功能

自記初習Qt

RQNOJ-43·飞翔·乱解

人云E云 posted @ 2011年10月20日 03:17 in 信息技術 with tags 解题报告 RQNOJ , 1276 阅读

昨天有人问我RQNOJ的第43题，，，就是那道飞翔，当时没思路，晚上回家的时候想到了方案，今天早上给打了出来，A掉了……//其实我今天早上打的跟昨晚想的不太一样，我昨晚想的那个是个 k^3 的做法，，不过早上发现更优方案了

题目嘛，我感觉有些描述不清{我白痴嘛}……后来问了下，才明白从第三行起的东西是可以走对角线的正方形的左下角坐标

N×M，明显爆了。而k只有1000，这就给题弄出了一个切入点：把所有的特殊的正方形列出来，到某个正方形为止的所有走的对角线个数是该正方形左下角的所有正方形中走的对角线数的最大值。

在这里，可以直接将正方形当作点看，，以下“点”全是指这些特殊正方形

不过要注意，不要总是枚举它最近的点，这样是错误的，，反例自己就可以举出来。

于是，可以对所有的特殊点进行排序{对X或者对Y皆可}{我用X的小到大}，之后在循环中对这些点之前的点进行枚举，找出最大的个数x，那么经过该点之后的个数便是x+1

若设读取的点坐标记录为map[*][1] map[*][2]，走过的对角线个数记为num[*]，伪代码可以如下写

FOR i = 1 TO k {

FOR j = i-1 TO 0

IF map[j,1]<map[i,1] AND map[j,2]<map[i,2] THEN x = num[j]

num[i] = x+1

}

附上我的PASCAL代码……

var
 point:array[0..1000,1..2] of longint;//就是正文中的map
 line:array[0..1000] of longint;//就是正文中的num
 n,m,mm,i,j,x,y,z:longint;//mm就是题中的k
 Procedure change(i,j:longint);//交换数据
 Var
  x:longint;
 Begin
  x:=point[i,1]; point[i,1]:=point[j,1]; point[j,1]:=x;
  x:=point[j,2]; point[j,2]:=point[i,2]; point[i,2]:=x;
 End;
 Procedure qsort(l,r:longint);
 Var
  i,j,x,y:longint;
 Begin
  i:=l;
  j:=r;
  x:=point[(l+r) shr 1,1];
  y:=point[(l+r) shr 1,2];
   while i<=j do
    begin
      while (point[i,1]<x) or ((point[i,1]=x) and (point[i,2]<y)) do
       inc(i);
      while (point[j,1]>x) or ((point[j,1]=x) and (point[j,2]>y)) do
       dec(j);
      if i<=j then
       begin
        change(i,j);
        inc(i);
        dec(j);
        end;
     end;
   if i<r then
    qsort(i,r);
   if j>l then
    qsort(l,j);
 End;
begin
 readln(n,m);
 readln(mm);
 z:=0;
  for i:=1 to mm do
   begin
    readln(x,y);
    point[i,1]:=x;
    point[i,2]:=y;
    end;//这里我本来想离散化的，后来发现不需要{而且我也不会……}
 qsort1(1,mm);
 point[0,1]:=0;
 point[0,2]:=0;
 line[0]:=0;//赋一下初值
  for i:=1 to mm do
   begin
    z:=0;
     for j:=i-1 downto 0 do
      if (point[j,1]<point[i,1]) and (point[j,2]<point[i,2]) then
       if z<line[j] then
        z:=line[j];
    line[i]:=z+1;
    end;//见上文伪代码
 x:=0;
  for i:=1 to mm do
   if x<line[i] then
    x:=line[i];//求最大对角线个数
 z:=(n+m-x-x)*100+round(sqrt(20000)*x);
 writeln(z);
end.

后，，不会写伪代码……求教各位大牛……

无匹配

[回复]

AIMS Portal Indian R 说:
2022年8月02日 09:28

AIMS is referred as Accounting Information and Management System which is a department of Indian Railways, and it is the world’s 4th large railway network employing to 13 lakhs of total employees, where the employee of Indian Railway works round the clock to serve the Indian National people. AIMS Portal Indian Railway Hope you know that AIMS department of Indian Railways services with Employee Self Service or HRMS providing their monthly Pay Slip, Tax Forms, Form 16, Paying bills, career development searches, Provident Fund, Loans & Advances, Income Tax details, and more.

[回复]

Service.vivocloud.co 说:
2022年11月13日 09:39

VIVO is a famous electronic brand with great smartphone devices and software. The brand has gained traction globally through introducing smart innovations to suit all users. Service.vivocloud.com VIVO goes beyond smartphone development and offers secure software facilities such as Vivo Cloud. The app is compatible with Vivo phones and provides a wide range of benefits.However, to access Vivo Cloud storage, one needs to register a Vivo account.

[回复]

Pay Tj Maxx Credit C 说:
2023年1月20日 08:36

TJ Maxx also well known as TJMaxx or TJX, is a superstore chain in the United State of America that is famous for selling products at lower prices compared to other superstore chains in the market. Pay Tj Maxx Credit Card In order to increase their customer intent they have launched a special credit card called TJMaxx credit card. This may be used in any of their stores. Upon using these cards customers will earn loyalty and bonus points. These loyalty and bonus points are used in order to redeem through special offers.

[回复]

ekalyan-epass.in 说:
2023年5月17日 06:39

Ekalyan-epass strives to provide better service in a variety of ways, however aside from the public information you choose to share, we do not sell or otherwise distribute your personal information.We are very aware of email spam and make every effort to protect every email. Your letter may occasionally ekalyan-epass.in be seen by the public.strives to provide better service in several ways, and we don't sell or give away your personal information unless you voluntarily make it public. We are very aware of email spam and make every effort to protect every email. Your mail might occasionally be visible to the public.