Хотелось бы узнать решения задач http://acm.timus.ru/problem.aspx?space=1&num=1890 http://acm.timus.ru/problem.aspx?space=1&num=1839 http://acm.timus.ru/problem.aspx?space=1&num=2022 http://acm.timus.ru/problem.aspx?space=1&num=1655
везде имею WA 1890 решаю так: строю HLD; имею 2 дерева отрезков: для суммы прибавок в департаментах (до корня) (с запросами изменить значение элемента и найти сумму на отрезке) и для суммы всех индивидуальных прибавок сотрудникам в корне с заданной вершиной (с запросами найти суммарную прибавку в элементе и прибавить значение на отрезок). есть подозрения, что плохо считываю данные или имею переполнение типов
код(WA2): https://ideone.com/fork/hprg2R
include
pragma comment(linker, "/STACK:46777216")
include
using namespace std;
define ll unsigned long long
const int MAXN = 50005;
struct SegmentTree_Dep { ll * dep;
int size;
void init(int sz)
{
dep = new ll[4 * sz];
memset(dep, (ll)0, 4 * sz * sizeof(ll));
size = sz;
}
ll getSum(int v, int tl, int tr, int l, int r)
{
if(tl == l && tr == r) return dep[v];
int mid = (tl + tr) >> 1, u=(v<<1);
if(r<=mid) return getSum(u, tl, mid, l, r);
if(l>mid) return getSum(u + 1, mid+1, tr, l, r);
return getSum(u, tl, mid, l, mid) + getSum(u + 1, mid+1, tr, mid+1, r);
}
ll getSum(int l, int r) {return getSum(1, 1, size, l, r);}
void update(int v, int tl, int tr, int pos, ll val)
{
if(tl == tr) dep[v]+=val;
else
{
int mid = (tl + tr) / 2, u=(v<<1);
if(pos<=mid) update(u, tl, mid, pos, val);
else update(u + 1, mid + 1, tr, pos, val);
dep[v] = dep[u] + dep[u + 1];
}
}
void update(int pos, ll val) {update(1, 1, size, pos, val);}};
struct SegmentTree_Sum { ll * sum; int size;
void init(int sz)
{
sum = new ll[4 * sz];
memset(sum, (ll)0, 4 * sz * sizeof(ll));
size = sz;
}
ll getVal(int v, int tl, int tr, int pos)
{
if(tl == tr) return sum[v];
int mid = (tl + tr) >> 1, u=(v<<1);
if(pos<=mid) return sum[v]+getVal(u, tl, mid, pos);
else return sum[v]+getVal(u + 1, mid+1, tr, pos);
}
ll getVal(int pos) {return getVal(1, 1, size, pos);}
void update(int v, int tl, int tr, int l, int r, ll val)
{
if(tl ==l && tr==r) sum[v]+=val;
else
{
int mid = (tl + tr) >> 1, u=(v<<1);
if(r<=mid) update(u, tl, mid, l, r, val);
else
{
if(l>mid) return update(u+1, mid+1, tr, l, r, val);
else update(u, tl, mid, l, mid, val), update(u+1, mid+1, tr, mid+1, r, val);
}
}
}
void update(int l, int r, ll val) {update(1, 1, size, l, r, val);}};
int n, q, x, chainNum; ll y, z, sz[MAXN], s[MAXN], val[MAXN]; char c[15]; vector g[MAXN]; int p[MAXN], chain[MAXN], chainRoot[MAXN], chainSize[MAXN], chainPos[MAXN]; SegmentTree_Dep dep[MAXN]; SegmentTree_Sum sum[MAXN];
bool isHeavy(int from, int to) {return sz[to] * (ll)2 >= sz[from];}
void dfs(int v, int par = -1) { p[v] = par, sz[v] = (ll)1; for (int i = 0; i < (int) g[v].size(); i++) { int to = g[v][i]; if (to == par) continue; dfs(to, v); sz[v] += sz[to]; s[v] += s[to]; } }
int newChain(int root) { chainNum++; chainRoot[chainNum] = root; return chainNum; }
void buildHLD(int v, int curChain) { chain[v] = curChain; chainSize[curChain]++; chainPos[v] = chainSize[curChain];
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
if (to == p[v]) continue;
if (isHeavy(v, to)) buildHLD(to, curChain);
else buildHLD(to, newChain(to));
}}
int main() { scanf("%d %d %lld", &n, &q, &val[1]); s[1]=val[1]; for (int i = 2; i <= n; i++) { scanf("%d %lld\n", &x, &val[i]); s[i]=val[i]; x++; g[x].push_back(i); g[i].push_back(x); }
dfs(1);
chainNum = 0;
buildHLD(1, newChain(1));
for (int i = 1; i <= chainNum; i++)
{
dep[i].init(chainSize[i]);
sum[i].init(chainSize[i]);
}
for (int i = 1; i <= q; i++)
{
scanf("%s ",&c);
if (c[0] == 'e')
{
scanf("%d %lld %lld\n", &x, &y, &z);
x++;
int v=x;
ll salary=val[v];
while(v!=-1)
{
int curChain=chain[v];
salary+=dep[curChain].getSum(1, chainPos[v]);
v = p[chainRoot[curChain]];
}
if(salary<y)
{
val[x]+=z;
while(x!=-1)
{
int curChain=chain[x];
sum[curChain].update(1, chainPos[x], z);
x = p[chainRoot[curChain]];
}
}
}
else
{
scanf("%d %lld %lld\n", &x, &y, &z);
x++;
int v=x;
ll departament=s[v], all=(ll)0;
while(v!=-1)
{
int curChain=chain[v];
all+=dep[curChain].getSum(1, chainPos[v]);
v = p[chainRoot[curChain]];
}
departament+=all*sz[x] + sum[chain[x]].getVal(chainPos[x]);
if(departament<y*sz[x]) dep[chain[x]].update(chainPos[x], z);
}
}
for(int i=1;i<=n;i++)
{
int v=i;
ll salary=val[v];
while(v!=-1)
{
int curChain=chain[v];
salary+=dep[curChain].getSum(1, chainPos[v]);
v = p[chainRoot[curChain]];
}
printf("%lld", salary);
if(i<n) printf("\n");
}
return 0;}
1839 решаю так: перебираю дуги и для каждой ищу рожицы: во-первых отсеим все неподходящие точки без условия 4); получим претендентов Pret; теперь проблема только с условием 4). Рассмотрим очередную точку Х из Pret; для неё нужно найти все такие Y из Pret, что cos(YRP)<cos(XRP) и cos(YPR)>cos(XPR); это можно сделать за логарифм для каждой точки Х с помощью ДО.
Код(WA3):
define _CRT_SECURE_NO_WARNINGS
include
include
include
include
using namespace std;
struct Point { double x, y; bool operator > (Point Q){return x>Q.x;} bool operator < (Point Q){return x<Q.x;} };
const double eps = 0.0000001; const int nmax = 105; const int mmax = 10005;
Point P[nmax], Q[nmax], R[nmax], T[mmax]; long long n, m, r, ans; Point Ang[mmax]; int Tree[4*mmax];
double min(double x, double y){return x<y?x:y;}
void Create(int v, int tl, int tr) { if(tl==tr) Tree[v]=0; else { int m=(tl+tr)/2; Create(2*v,tl,m); Create(2*v+1,m+1,tr); } }
void Update(int v, int tl, int tr, int i) { if(tl==tr) Tree[v]++; else { int m=(tl+tr)/2; if(i<=m) Update(2*v, tl, m, i); else Update(2*v+1, m+1, tr, i); Tree[v]++; } }
int Sum(int v, int tl, int tr, int l, int r) { if(tl==tr) return Tree[v]; else { int m=(tl+tr)/2; if(r<=m) return Sum(2*v, tl, m, l, r); if(l>m) return Sum(2*v+1, m+1, tr, l, r); return Sum(2*v, tl, m, l, m)+Sum(2*v+1, m+1, tr, m+1,r); } }
double Scalar(Point P, Point Q) { return P.x*Q.x+P.y*Q.y; }
double Dist(Point A, Point B) { double dx=A.x-B.x, dy=A.y-B.y; return sqrt(dx*dx+dy*dy); }
bool GoodPoint(Point A, Point P, Point Q, Point R) { double a=R.y-P.y, b=P.x-R.x, c=R.x*P.y-P.x*R.y; double la=a*A.x+b*A.y+c, lq=a*Q.x+b*Q.y+c; Point PA, PR, RA, RP; PA.x=A.x-P.x, A.y-P.y; PR.x=R.x-P.x, R.y-P.y; RA.x=A.x-R.x, A.y-R.y; RP.x=P.x-R.x, P.y-R.y; return la*lq<0 && Scalar(PA,PR)>0 && Scalar(RA,RP)>0 && la<2.0*Dist(P,R)*sqrt(a*a+b*b); }
void QSort(Point A[], int L, int R) { int i=L, j=R; Point X=A[(L+R)/2], Y; while(i<=j) { while(A[i]<X) i++; while(A[j]>X) j--; if(i<=j) { Y=A[i], A[i]=A[j], A[j]=Y; i++, j--; } } if(L<j) QSort(A, L, j); if(i<R) QSort(A, i, R); }
double Cos(Point A, Point B) { double d1=sqrt(A.x*A.x+A.y*A.y); double d2=sqrt(B.x*B.x+B.y*B.y); return Scalar(A,B)/(d1*d2); }
int main() { scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lf%lf%lf%lf%lf%lf",&P[i].x,&P[i].y,&Q[i].x,&Q[i].y,&R[i].x,&R[i].y);
for(int j=1;j<=m;j++) scanf("%lf%lf",&T[j].x,&T[j].y);
ans=0;
for(int i=1;i<=n;i++) { r=0; for(int j=1;j<=m;j++) { if(GoodPoint(T[j], P[i], Q[i], R[i])) { Point RP, RT, PR, PT; RP.x=P[i].x-R[i].x, RP.y=P[i].y-R[i].y; RT.x=T[j].x-R[i].x, RT.y=T[j].y-R[i].y; PR.x=R[i].x-P[i].x, PR.y=R[i].y-P[i].y; PT.x=T[j].x-P[i].x, PT.y=T[j].y-P[i].y; r++; Ang[r].x=Cos(RP, RT); Ang[r].y=Cos(PR, PT); } } if(r>0) { QSort(Ang, 1, r); int N=0; map<double,int> Map; set Set; for(int j=1;j<=r;j++) Set.insert(Ang[j].y); Create(1, 1, Set.size()); for(set::iterator it=Set.begin();it!=Set.end();it++) { N++; Map.insert(make_pair(*it,N)); } int k=1; long long bad=0; ans+=r*(r-1)/2; for(int j=1;j<=r;j++) { while(k<=r && fabs(Ang[j].y-Ang[k].y)<eps) { map<double,int>::iterator it=Map.find(Ang[k].y); Update(1, 1, N, it->second); k++; } map<double,int>::iterator it=Map.find(Ang[j].y); ans-=(Sum(1, 1, N, 1, it->second)-1); } } }
printf("%lld",ans);
return 0; }
2022 решаю так:пусть T-момент прыжка; до него движение описывается так: x(t)=vx * t y(t)=vy * t — g*t*t/2; чтобы прыжок можно было совершить, необходимы условия: x(T)<L, y(T)>0, T>0, откуда получаем интервал для T; далее полёт описывается так: x(t')=x(T) + (vx+ux) * t', y(t')=y(T) + (vy-g*T+uy)*t' — g*t'*t'/2; теперь необходимые условия пролёта через дырку выглядят так: в момент пролёта t1 через стену (т.е. когда x(t1)=x(T)+(vx+ux)*t1=L) в т. L нужно h<y(t1)<h+d, в момент пролёта t2 через стену (т.е. когда x(t2)=x(T)+(vx+ux)*t2=L+l) в т. L нужно h<y(t2)<h+d, (3) а также если максимальная высота ф-ии y(t') достигается на [t1, t2], то max(t')<h+d. В итоге получаем некоторые интервалы решений (возникающие при решении неравенств), их пересекаем; потом (если выполняется (3), то некоторые из них обрезаем. Ответ=середина интервала длины не меньше 0.000001
Код(WA3) : писать не буду, т.к. сдавал без (3), а с (3) даже инпут не прохожу.
1655 решаю так: пишу ДП: dp[i][j][0]-минимальное время уничтожения кораблей на [i,j], если мы находимся в позиции i (где находится i корабль), dp[i][j][1]-минимальное время уничтожения кораблей на [i,j], если мы находимся в позиции j (где находится j корабль). Особо пояснять нечего.
Код (WA8):
define _CRT_SECURE_NO_WARNINGS
include
using namespace std;
const double inf=12345678901234567890; const int nmax=555;
double dp[nmax][nmax][2], b[nmax], t[nmax], mint[nmax][nmax]; double a, w, d, v; int n, ind[nmax], list[nmax], r, s[nmax][nmax][2][3]; bool used[nmax][nmax][2];
double min(double x, double y){return x<y?x:y;} void Solve(int i, int j, int k); double Time(double x, double y); void Update(double &oldv, double newv, int i, int j, int k, int i1, int j1, int k1);
int main() { cin>>a>>w>>n;
for(int i=1;i<=n;i++) { cin>>b[i]>>d>>v; ind[i]=i; b[i]-=a; if(b[i]<0) b[i]+=360.0; t[i]=(d-1.0)*60.0*(360.0*w); }
for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(b[j]<b[i]) { double c; c=b[i], b[i]=b[j], b[j]=c; c=t[i], t[i]=t[j], t[j]=c; int q; q=ind[i], ind[i]=ind[j], ind[j]=q; }
for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) { used[i][j][0]=used[i][j][1]=false; mint[i][j]=t[i]; for(int k=i+1;k<=j;k++) mint[i][j]=min(mint[i][j], t[k]); }
for(int i=1;i<=n;i++) { Solve(i,i,0); Solve(i,i,1); }
int i=1, j=1, k=0; double ans=dp[1][1][0]; for(j=2;j<=n;j++) if(ans>dp[j][j][0]) ans=dp[j][j][0], i=j;
if(ans==inf) cout<<"Impossible"; else { printf("%.5lf",ans/(v*(360.0*w))); r=1, list[r]=ind[i], j=i; while(i>1 || j<n) { int i1=s[i][j][k][0]; int j1=s[i][j][k][1]; int k1=s[i][j][k][2]; if(i1!=i) list[++r]=ind[i1]; else list[++r]=ind[j1]; i=i1, j=j1, k=k1; } for(int i=n;i>=1;i--) cout<<endl<<list[i]; }
return 0; }
void Solve(int i, int j, int k) { if(i==1 && j==n) { dp[i][j][k]=inf, used[i][j][k]=true; if(k==0) { if(Time(0,b[1])<=mint[1][n]) dp[i][j][k]=Time(0,b[1]); } else { if(Time(0,b[n])<=mint[1][n]) dp[i][j][k]=Time(0,b[n]); } return; } //1<i || j<n if(k==0) { dp[i][j][k]=inf, used[i][j][k]=true; if(i>1) { if(!used[i-1][j][0]) Solve(i-1,j,0); if(dp[i-1][j][0]<inf && dp[i-1][j][0]+Time(b[i-1],b[i])<=mint[i][j]) Update(dp[i][j][k], dp[i-1][j][0]+Time(b[i-1],b[i]), i,j,k,i-1,j,0); } if(j<n) { if(!used[i][j+1][1]) Solve(i,j+1,1); if(dp[i][j+1][1]<inf && dp[i][j+1][1]+Time(b[j+1],b[i])<=mint[i][j]) Update(dp[i][j][k], dp[i][j+1][1]+Time(b[j+1],b[i]), i,j,k,i,j+1,1); } } else { dp[i][j][k]=inf, used[i][j][k]=true; if(i>1) { if(!used[i-1][j][0]) Solve(i-1,j,0); if(dp[i-1][j][0]<inf && dp[i-1][j][0]+Time(b[i-1],b[j])<=mint[i][j]) Update(dp[i][j][k], dp[i-1][j][0]+Time(b[i-1],b[j]), i,j,k,i-1,j,0); } if(j<n) { if(!used[i][j+1][1]) Solve(i,j+1,1); if(dp[i][j+1][1]<inf && dp[i][j+1][1]+Time(b[j+1],b[j])<=mint[i][j]) Update(dp[i][j][k], dp[i][j+1][1]+Time(b[j+1],b[j]), i,j,k,i,j+1,1); } } }
double Time(double x, double y) { if(x>y) return Time(y,x); else return min(x+360.0-y,y-x)*v; }
void Update(double &oldv, double newv, int i, int j, int k, int i1, int j1, int k1) { if(oldv>newv) oldv=newv, s[i][j][k][0]=i1, s[i][j][k][1]=j1, s[i][j][k][2]=k1; }
