A.数三角形
题目：http://www.contesthunter.org/contest/CH%20Round%20%2348%20-%20Streaming%20%233%20(NOIP模拟赛Day1)/数三角形
题解：暴力枚举三元组，判断是否共线即可，用叉积
代码：
type cp=record
x,y:double;
end;
var a:array[..] of cp;
i,j,k,n,ans:longint;
function cross(a,b,c:cp):double;
begin
cross:=(b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
end;
procedure init;
begin
readln(n);
for i:= to n do readln(a[i].x,a[i].y);
end;
procedure main;
begin
ans:=;
for i:= to n do
for j:=i+ to n do
for k:=j+ to n do
begin
if cross(a[i],a[j],a[k])<> then inc(ans);
end;
writeln(ans);
end; begin
init;
main;
end.
B.4和7
题目：http://www.contesthunter.org/contest/CH%20Round%20%2348%20-%20Streaming%20%233%20(NOIP模拟赛Day1)/4和7
题解：这类似于vijosp1002过河，那题是当距离超过105时缩到105，但我取20也过了，现在也不知道为什么要压。。。
这一道题比较好做，因为只有4和7两个数，由裴蜀定理我们知道 （4，7）=1 所以仅有4和7是可以组合出所有的整数的，
但这题必须保证4和7的系数都必须是非负的。
所以我们从前面开始尝试，看看能发现什么规律。
发现前面有的可以4和7组合出来 比如15，但有的就组合不出来，如13
进一步我们又发现当x>=18时，就都可以组合出来了。我们详细的证明一下：
i） x mod 4=0 直接全用4即可
ii) x mod 4=1 我们可以用3个7，剩下的全用4，因为这样的数最小是21
iii）x mod 4=2 我们用2个7，剩下的全用4
iiii）x mod 4=3 我们用1个7，剩下的全用4
这样就可以了当相邻两个有药的位置距离相隔≥18时就将它看作18，这样是没有问题的。
考场上没有处理刚开始的边界情况，WA了30分
代码：
var v,a,b,c,f:array[-..] of int64;
i,n:longint;
ans,m,tmp:int64;
function max(x,y:int64):int64;
begin
if x>y then exit(x) else exit(y);
end;
procedure sort(l,r:longint);
var i,j,x,y:longint;
begin
i:=l;j:=r;x:=b[(i+j)>>];
repeat
while b[i]<x do inc(i);
while b[j]>x do dec(j);
if i<=j then
begin
y:=a[i];a[i]:=a[j];a[j]:=y;
y:=b[i];b[i]:=b[j];b[j]:=y;
inc(i);dec(j);
end;
until i>j;
if i<r then sort(i,r);
if j>l then sort(l,j);
end;
procedure init;
begin
readln(n,m);
for i:= to n do readln(a[i],b[i]);
sort(,n);
end;
procedure main;
begin
b[]:=;c[]:=;
for i:= to n do
if b[i]-b[i-]>= then c[i]:=c[i-]+
else c[i]:=c[i-]+b[i]-b[i-];
fillchar(v,sizeof(v),);
for i:= to n do inc(v[c[i]],a[i]);
f[]:=;
for i:= to c[n] do
begin
tmp:=max(f[i-],f[i-]);
if tmp= then continue;
f[i]:=tmp+v[i];
end;
ans:=;
for i:= to c[n] do ans:=max(ans,f[i]);
writeln(ans-);
end; begin
init;
main;
end.
C.反射镜
题目：http://www.contesthunter.org/contest/CH%20Round%20%2348%20-%20Streaming%20%233%20(NOIP模拟赛Day1)/反射镜
题解：考场上没想到什么好的算法，于是打了200行的暴力。。。幸亏没写跪，骗到60分，结果标程竟然那么短。。。
代码：
1.暴力
type cp=record
x,y,id,idx:longint;
z:char;
end;
var a,b:array[..] of cp;
now,dir,n,m,i,x,y,tmp:longint;
c:array[..] of longint;
dist,t:int64;
ans:cp; function cmp1(a,b:cp):boolean;
begin
if a.x=b.x then exit(a.y<b.y) else exit(a.x<b.x);
end;
function cmp2(a,b:cp):boolean;
begin
if a.y=b.y then exit(a.x<b.x) else exit(a.y<b.y);
end;
procedure sort1(l,r:longint);
var i,j:longint;x,y:cp;
begin
i:=l;j:=r;x:=a[(i+j)>>];
repeat
while cmp1(a[i],x) do inc(i);
while cmp1(x,a[j]) do dec(j);
if i<=j then
begin
y:=a[i];a[i]:=a[j];a[j]:=y;
inc(i);dec(j);
end;
until i>j;
if i<r then sort1(i,r);
if j>l then sort1(l,j);
end;
procedure sort2(l,r:longint);
var i,j:longint;x,y:cp;
begin
i:=l;j:=r;x:=b[(i+j)>>];
repeat
while cmp2(b[i],x) do inc(i);
while cmp2(x,b[j]) do dec(j);
if i<=j then
begin
y:=b[i];b[i]:=b[j];b[j]:=y;
inc(i);dec(j);
end;
until i>j;
if i<r then sort2(i,r);
if j>l then sort2(l,j);
end;
procedure init;
begin
readln(n,m,t);
for i:= to n do begin readln(a[i].x,a[i].y,a[i].z,a[i].z);a[i].id:=i;end;
for i:= to n do b[i]:=a[i];
sort1(,n);
sort2(,n);
for i:= to n do c[a[i].id]:=i;
for i:= to n do b[i].idx:=c[b[i].id];
for i:= to n do c[b[i].id]:=i;
for i:= to n do a[i].idx:=c[a[i].id];
a[n+].x:=maxlongint;a[n+].y:=maxlongint;
a[].x:=maxlongint;a[].y:=maxlongint;
b[n+]:=a[n+];b[]:=a[];
end;
procedure main;
begin
x:=;y:=;
for i:= to n do if (b[i].y=) and (b[i].x>) then begin now:=i;break;end;
if now= then
begin
writeln(t,' ',);exit;
end;
dir:=;dist:=b[now].x;ans:=b[now];
while true do
begin
if dir= then
begin
if b[now].z='/' then
begin
dir:=;
now:=b[now].idx;
tmp:=now+;
if a[tmp].x<>a[now].x then break;
if dist+abs(a[tmp].y-a[now].y)>t then break
else inc(dist,abs(a[tmp].y-a[now].y));
now:=tmp;ans:=a[now];
end
else
begin
dir:=;
now:=b[now].idx;
tmp:=now-;
if a[tmp].x<>a[tmp].x then break;
if dist+abs(a[tmp].y-a[now].y)>t then break
else inc(dist,abs(a[tmp].y-a[now].y));
now:=tmp;ans:=a[now];
end;
end;
if dir= then
begin
if a[now].z='/' then
begin
dir:=;
now:=a[now].idx;
tmp:=now+;
if b[tmp].y<>b[now].y then break;
if dist+abs(b[tmp].x-b[now].x)>t then break
else inc(dist,abs(b[tmp].x-b[now].x));
now:=tmp;ans:=b[now];
end
else
begin
dir:=;
now:=a[now].idx;
tmp:=now-;
if b[tmp].y<>b[now].y then break;
if dist+abs(b[tmp].x-b[now].x)>t then break
else inc(dist,abs(b[tmp].x-b[now].x));
now:=tmp;ans:=b[now];
end;
end;
if dir= then
begin
if b[now].z='/' then
begin
dir:=;
now:=b[now].idx;
tmp:=now-;
if a[tmp].x<>a[now].x then break;
if dist+abs(a[tmp].y-a[now].y)>t then break
else inc(dist,abs(a[tmp].y-a[now].y));
now:=tmp;ans:=a[now];
end
else
begin
dir:=;
now:=b[now].idx;
tmp:=now+;
if a[tmp].x<>a[now].x then break;
if dist+abs(a[tmp].y-a[now].y)>t then break
else inc(dist,abs(a[tmp].y-a[now].y));
now:=tmp;ans:=a[now];
end;
end;
if dir= then
begin
if a[now].z='/' then
begin
dir:=;
now:=a[now].idx;
tmp:=now-;
if b[tmp].y<>b[now].y then break;
if dist+abs(b[tmp].x-b[now].x)>t then break
else inc(dist,abs(b[tmp].x-b[now].x));
now:=tmp;ans:=b[now];
end
else
begin
dir:=;
now:=a[now].idx;
tmp:=now+;
if b[tmp].y<>b[now].y then break;
if dist+abs(b[tmp].x-b[now].x)>t then break
else inc(dist,abs(b[tmp].x-b[now].x));
now:=tmp;ans:=b[now];
end;
end;
end;
if dir= then writeln(ans.x-(t-dist),' ',ans.y);
if dir= then writeln(ans.x,' ',ans.y+(t-dist));
if dir= then writeln(ans.x+(t-dist),' ',ans.y);
if dir= then writeln(ans.x,' ',ans.y-(t-dist));
end;
procedure spj;
begin
if a[].y<> then writeln(t,' ',)
else if a[].x< then writeln(t,' ',)
else if a[].z='/' then writeln(a[].x,' ',t-a[].x)
else writeln(a[].x,' ',a[].x-t);
end; begin
init;
if n= then spj else main;
end.
2.正解
#include <cstdio>
#include <cstring>
#include <algorithm>
#define UU 0
#define LL 1
#define DD 2
#define RR 3
//LeftTurn = 1
//RightTurn = 3
const int dx[] = {, -, , };
const int dy[] = {, , -, };
#define f(x, y, z) for(int x = (y); x <= (z); ++x)
#define f2(x, y, z) for(int x = (y), asdf = (z); x <= asdf; ++x)
using std::min;
using std::abs; int N; long long T;
struct mir{int x, y; long long dr;} xm[], ym[];
inline bool byx(const mir &a, const mir &b){
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
inline bool byy(const mir &a, const mir &b){
return a.y < b.y || (a.y == b.y && a.x < b.x);
}
inline bool operator ==(const mir &a, const mir &b){
return a.x == b.x && a.y == b.y;
} inline mir *findxless(const mir a){
int l = , r = N + ;
while(l < r){
int m = ((l + r) >> ) + ;
if(xm[m] == a) return xm + m;
else if(byx(xm[m], a)) l = m; else r = m - ;
}
if(l < || l > N || xm[l].x != a.x) return NULL;
return xm + l;
}
inline mir *findxmore(const mir a){
int l = , r = N + ;
while(l < r){
int m = (l + r) >> ;
if(xm[m] == a) return xm + m;
else if(byx(a, xm[m])) r = m; else l = m + ;
}
if(l < || l > N || xm[l].x != a.x) return NULL;
return xm + l;
}
inline mir *findyless(const mir a){
int l = , r = N + ;
while(l < r){
int m = ((l + r) >> ) + ;
if(ym[m] == a) return ym + m;
else if(byy(ym[m], a)) l = m; else r = m - ;
}
if(l < || l > N || ym[l].y != a.y) return NULL;
return ym + l;
}
inline mir *findymore(const mir a){
int l = , r = N + ;
while(l < r){
int m = (l + r) >> ;
if(ym[m] == a) return ym + m;
else if(byy(a, ym[m])) r = m; else l = m + ;
}
if(l < || l > N || ym[l].y != a.y) return NULL;
return ym + l;
} int main(){
scanf("%d%*d%I64d", &N, &T); long long iT = T;
f(i, , N){
int cx, cy; char buf[];
scanf("%d%d%s", &cx, &cy, buf);
xm[i].x = ym[i].x = cx;
xm[i].y = ym[i].y = cy;
if(buf[] == '/'){
xm[i].dr = ; ym[i].dr = ;
}else{
xm[i].dr = ; ym[i].dr = ;
}
}
xm[] = (mir) {-, -, };
ym[] = (mir) {-, -, };
xm[N + ] = (mir) {, , };
ym[N + ] = (mir) {, , };
std::sort(xm + , xm + N + , byx);
std::sort(ym + , ym + N + , byy);
int cx = , cy = , cr = RR;
for(;;){
// printf("C %d %d = %d\n", cx, cy, cr);
mir *res;
if(cr == UU) res = findxmore((mir) {cx, cy + });
else if(cr == LL) res = findyless((mir) {cx - , cy});
else if(cr == DD) res = findxless((mir) {cx, cy - });
else res = findymore((mir) {cx + , cy});
if(res){
if(cy == && res->y == && cx < && res->x > ) T %= (iT - T - cx);
int dis = abs(res->x - cx) + abs(res->y - cy);
if(dis < T){
cx = res->x; cy = res->y; cr = (cr + res->dr) % ; T -= (long long) dis;
}else{
printf("%I64d %I64d\n", (long long) cx + T * (long long) dx[cr], (long long) cy + T * (long long) dy[cr]);
return ;
}
}else{
printf("%I64d %I64d\n", (long long) cx + T * (long long) dx[cr], (long long) cy + T * (long long) dy[cr]);
return ;
}
}
return ;
}