The game link
B
Train of thought
Calculate the geometry problem. The first step is to determine that there must be only five different endpoints legally, and you can maintain this feature with set. Based on this, find two lines with common endpoints, namely the waist of the letter ‘A’, find their lengths, and determine whether their Angle is legal according to the Pythagorean theorem.
For the third side, if we want to determine whether the endpoint C on AB, whether can use AC and BC slope equal and whether ordinate with number (because want to consider the case of C on AB extension) to judge, in the process can also be conveniently calculate than the length of the short and long while, to plug it into a convenient in the check function calls in the future.
code
#include<bits/stdc++.h>
#definerep(i,st,ed) for(int i=st; i<=ed; ++i)
#definebl(u,i) for(int i=head[u]; i; i=e[i].nxt)
#define LLM LONG_LONG_MAX
#define LLm LONG_LONG_MIN
#define pii pair<ll,ll>
typedef long long ll;
typedef long double db;
using namespace std;
const ll INF=0x3f3f3f3f;
void read(a) {}
void say(a) {}
void say_(a) {}
template <typename T, typename. T2>inline void read(T &_, T2 &... oth)
{
int__ =0; _ =0;
char ch=getchar(a);while(!isdigit(ch))
{
if(ch==The '-') __ =1;
ch=getchar(a); }while(isdigit(ch))
{
_=_*10+ch- 48;
ch=getchar(a); } _ = __? - _ : _;read(oth...) ; }template <typename T>
void Out(T _)
{
if(_ <0)
{
putchar(The '-'); _ = - _; }if(_ > =10)
Out(_ /10);
putchar(_ %10+'0');
}
template <typename T, typename. T2>inline void say(T _, T2... oth)
{
Out(_).putchar('\n');
say(oth...) ; }template <typename T, typename. T2>inline void say_(T _, T2... oth)
{
Out(_).putchar(' ');
say_(oth...) ; }/ * # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # * /
ll cnt;
db eps=0.25;
pii a[10];
set<pii> had;
struct seg
{
ll x1,y1,x2,y2,len;
void print(a)
{
say_(x1,y1,x2,y2,len);
puts("");
}
}b[5];
ll G_dis(ll x1,ll y1,ll x2,ll y2)
{
return pow(x1-x2,2) +pow(y1-y2,2);
}
pii check(ll x1,ll y1,ll x2,ll y2,ll x3,ll y3)
{
// say_(x1,y1,x2,y2,x3,y3);
// puts("");
pii ret=make_pair(- 1.- 1);
if(x1==x3 || x2==x3)
{
if(x1==x3 && x2==x3 && db(min(abs(y1-y3),abs(y2-y3)))/db(max(abs(y1-y3),abs(y2-y3)))>=0.25)
ret=make_pair(1.1);
return ret;
}
db k1=db((y1-y3))/db((x1-x3)),k2=db((y2-y3))/db((x2-x3));
// cout<
if(k1! =k2 || (y1-y3)*(y2-y3)>=0)
return ret;
db first=sqrt(min(G_dis(x1,y1,x3,y3),G_dis(x2,y2,x3,y3)));
db second=sqrt(max(G_dis(x1,y1,x3,y3),G_dis(x2,y2,x3,y3)));
// printf("%.0Lf %.0Lf %.4Lf\n",first,second,first/second);
if(first/second<eps)
return ret=make_pair(- 1.- 1);
else
return ret=make_pair(first,second);
}
void solve(a)
{
++cnt;
had.clear(a); ll p;rep(i,1.6)
{
read(a[i].first,a[i].second);
if(had.find(a[i])! =had.end())
p=i;
had.insert(a[i]);
}
rep(i,2.6)
{
a[i].first-=a[1].first;
a[i].second-=a[1].second;
}
a[1].first=0;
a[1].second=0;
/ / rep (I, 1, 6)
/ / {
// say_(a[i].first,a[i].second);
// puts("");
// }
// if(cnt==35)
/ / {
/ / rep (I, 1, 6)
/ / {
// say_(a[i].first,a[i].second);
// puts("");
// }
// }
if(had.size()! =5)
{
puts("NO");
return;
}
ll sum=0;
seg fir,sec,thr;
fir.x1=LLm;
rep(i,1.3)
{
ll tmp=i<<1;
b[i]=seg({a[tmp- 1].first,a[tmp- 1].second,a[tmp].first,a[tmp].second});
b[i].len=G_dis(b[i].x1,b[i].y1,b[i].x2,b[i].y2);
if(a[tmp]! =a[p] && a[tmp- 1]! =a[p]) { thr=b[i]; }else
{
if(fir.x1! =LLm) sec=b[i];else
fir=b[i];
sum+=b[i].len;
}
}
pii tmpa,tmpb;
if(make_pair(fir.x1,fir.y1)! =a[p]) tmpa=make_pair(fir.x1,fir.y1);
else
tmpa=make_pair(fir.x2,fir.y2);
if(make_pair(sec.x1,sec.y1)! =a[p]) tmpb=make_pair(sec.x1,sec.y1);
else
tmpb=make_pair(sec.x2,sec.y2);
// say_(tmpa.first,tmpa.second,tmpb.first,tmpb.second);
// puts("");
// say(sum);
/ / say (G_dis 8 0, (23902806178358) + G_dis (8, 23902806178358-82089596559 (1));
// say(G_dis(tmpa.first,tmpa.second,tmpb.first,tmpb.second));
if(sum<G_dis(tmpa.first,tmpa.second,tmpb.first,tmpb.second))
{
puts("NO");
return;
}
// say(sum);
// fir.print();
// sec.print();
// thr.print();
// puts("::::::");
// pii cur=check(fir.x1,fir.y1,fir.x2,fir.y2,thr.x1,thr.y1);
// cout<<cur.first<<" [][][][][][]"<<cur.second<<endl;
if(check(fir.x1,fir.y1,fir.x2,fir.y2,thr.x1,thr.y1).first==- 1)
{
if(check(fir.x1,fir.y1,fir.x2,fir.y2,thr.x2,thr.y2).first==- 1)
{
puts("NO");
return;
}
if(check(sec.x1,sec.y1,sec.x2,sec.y2,thr.x1,thr.y1).first==- 1)
{
// cout<<"???????" <
puts("NO");
return;
}
puts("YES");
return;
}
// cout<<"::::::::::::"<<endl;
// cur=check(sec.x1,sec.y1,sec.x2,sec.y2,thr.x1,thr.y1);
// cout<<cur.first<<">>> "<<cur.second<<endl;
// puts("::::::::::::::::::");
if(check(sec.x1,sec.y1,sec.x2,sec.y2,thr.x2,thr.y2).first==- 1)
{
puts("NO");
return;
}
puts("YES");
}
int main(a)
{
int _;
cin>>_;
while(_ --) {solve();
}
}
Copy the codeC
Train of thought
Dp. Where an element goes down in size, for a smaller element, it must be the element to the left or the element to the right. Therefore, the elements in the final sequence must have occurred in the original sequence.
Set the sequence of the original sequence sorted for BBB, and set f [I] [j] [I] [j] f f [I] [j] to the current element iii drab not decline, and a [I] < = b [j] a [I] < = b [j] a [I] < = b needs at least steps when [j]. From the previous conclusions, can know a [I] = b [j] a [I] [j] a [I] = = b b [j] or [I] < = b [j] – 1 (j > 1) a [I] < = b [1] (m > 1) a [I] < = b [j] – 1 (j > 1), so F [I] [j] = min (f [I – 1) [j] + abs (a – b [j] [I]), f [I] [j] – 1) f [I] [j] = min (f [j] [I – 1] + abs (a – b [j] [I]), f [I] [1]) f [I] [j] = min (f [I – 1) [j] + abs ( [I] – b [j]), f [I] [j – 1]). Rolling array optimization can be reduced to one dimensional space.
code
#include<bits/stdc++.h>
#definerep(i,st,ed) for(int i=st; i<=ed; ++i)
#definebl(u,i) for(int i=head[u]; i; i=e[i].nxt)
#define LLM LONG_LONG_MAX
#define LLm LONG_LONG_MIN
#define pii pair<ll,ll>
typedef long long ll;
typedef double db;
using namespace std;
const ll INF=0x3f3f3f3f;
void read(a) {}
void say(a) {}
void say_(a) {}
template <typename T, typename. T2>inline void read(T &_, T2 &... oth)
{
int__ =0; _ =0;
char ch=getchar(a);while(!isdigit(ch))
{
if(ch==The '-') __ =1;
ch=getchar(a); }while(isdigit(ch))
{
_=_*10+ch- 48;
ch=getchar(a); } _ = __? - _ : _;read(oth...) ; }template <typename T>
void Out(T _)
{
if(_ <0)
{
putchar(The '-'); _ = - _; }if(_ > =10)
Out(_ /10);
putchar(_ %10+'0');
}
template <typename T, typename. T2>inline void say(T _, T2... oth)
{
Out(_).putchar('\n');
say(oth...) ; }template <typename T, typename. T2>inline void say_(T _, T2... oth)
{
Out(_).putchar(' ');
say_(oth...) ; }/ * # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # * /
const ll N=5005;
ll n;
ll a[N],b[N],f[N];
int main(a)
{
read(n);
rep(i,1,n)
{
read(a[i]);
b[i]=a[i];
}
sort(b+1,b+n+1);
rep(i,1,n)
{
rep(j,1,n)
{
f[j]+=abs(a[i]-b[j]);
if(j>1)
f[j]=min(f[j- 1],f[j]); }}say(f[n]);
}
Copy the codeE
Train of thought
Violent jump over the inevitable time, so to break up, a piece of jump.
The number of steps needed to jump from the third point to the end of its block and its position when it arrives at the end are preprocessed. When the XXX point is updated every time, the information of the points following XXX will not be affected. Therefore, only the points in the same block to the left of XXX are updated, and the complexity is O(n)O(\ SQRT n)O(n). Query, directly jump to the last point in the block one step, then jump to the next block, repeat the above process until jumping out of the bounds, the complexity is also O(n)O(\ SQRT n)O(n). So the total complexity is O(nn)O(n\ SQRT n)O(nn).
code
#include<bits/stdc++.h>
#definerep(i,st,ed) for(int i=st; i<=ed; ++i)
#definebl(u,i) for(int i=head[u]; i; i=e[i].nxt)
#define LLM LONG_LONG_MAX
#define LLm LONG_LONG_MIN
#define pii pair<ll,ll>
typedef int ll;
typedef double db;
using namespace std;
const ll INF=0x3f3f3f3f;
void read(a) {}
void say(a) {}
void say_(a) {}
template <typename T, typename. T2>inline void read(T &_, T2 &... oth)
{
int__ =0; _ =0;
char ch=getchar(a);while(!isdigit(ch))
{
if(ch==The '-') __ =1;
ch=getchar(a); }while(isdigit(ch))
{
_=_*10+ch- 48;
ch=getchar(a); } _ = __? - _ : _;read(oth...) ; }template <typename T>
void Out(T _)
{
if(_ <0)
{
putchar(The '-'); _ = - _; }if(_ > =10)
Out(_ /10);
putchar(_ %10+'0');
}
template <typename T, typename. T2>inline void say(T _, T2... oth)
{
Out(_).putchar('\n');
say(oth...) ; }template <typename T, typename. T2>inline void say_(T _, T2... oth)
{
Out(_).putchar(' ');
say_(oth...) ; }/ * # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # * /
const ll N=1E5+10;
ll n,m,unit;
ll a[N],lst[N],cnt[N],block[N];
void print(a)
{
rep(i,1,n)
say_(lst[i]);
puts("");
rep(i,1,n)
say_(cnt[i]);
puts("");
}
void update(ll x,ll val)
{
a[x]=val;
for(inti=x; block[i]==block[x]; --i) { ll nxt=i+a[i];if(block[i]! =block[nxt]) { cnt[i]=0;
lst[i]=i;
continue;
}
cnt[i]=cnt[nxt]+1; lst[i]=lst[nxt]; }}void query(ll x)
{
ll cur=x,tot=1;
while(cur<=n)
{
tot+=cnt[cur];
cur=lst[cur];
if(cur+a[cur]<=n)
{
cur+=a[cur];
++tot;
}
else
break;
}
printf("%d %d\n",cur,tot);
}
int main(a)
{
read(n,m);
unit=ceil(sqrt(n));
rep(i,1,n)
block[i]=(i- 1)/unit+1;
rep(i,1,n)
read(a[i]);
for(inti=n; i>=1; --i) { ll nxt=i+a[i];if(block[i]! =block[nxt]) { lst[i]=i;continue;
}
cnt[i]=cnt[nxt]+1;
lst[i]=lst[nxt];
}
ll ty,x,y;
// print();
while(m--)
{
read(ty);
if(ty==0)
{
read(x,y);
update(x,y);
}
else
{
read(x);
query(x); }}// print();
}
Copy the code