Need help in problems from Timus

Правка ru3, от Felix_Mate, 2018-03-09 11:12:49

Хотелось бы узнать решения задач 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):

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; }

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru8 Русский Felix_Mate 2018-03-09 11:48:16 136 Мелкая правка: 'я задач \nhttp://a' -> 'я задач \n\nhttp://a' (опубликовано)
ru7 Русский Felix_Mate 2018-03-09 11:42:05 8
ru6 Русский Felix_Mate 2018-03-09 11:40:09 37
ru5 Русский Felix_Mate 2018-03-09 11:37:47 13647
ru4 Русский Felix_Mate 2018-03-09 11:33:00 34 Мелкая правка: 'од(WA2):\n#include' -> 'од(WA2):\nhttps://ideone.com/fork/hprg2R\n\n#include'
ru3 Русский Felix_Mate 2018-03-09 11:12:49 3909
ru2 Русский Felix_Mate 2018-03-09 11:05:17 980
ru1 Русский Felix_Mate 2018-03-09 10:52:51 10316 Первая редакция (сохранено в черновиках)