Понеділок, 18.12.2017, 02:32
Головна Реєстрація Вхід
Вітаю Вас, Гість · RSS
Меню сайту
Статистика

Онлайн всього: 1
Гостей: 1
Користувачів: 0
Форма входу
 Розбір задач
Задача А
Ідея зрозуміла із формули: K=((k-5)/(m-1))*(n-1)+5;
(Якщо ми перебуваємо на к –ому поверсі, то під нами к-1 поверх.)

#include<iostream>
using namespace std;
int main()
{
    unsigned long long m,n,k,K;
    cin>>m>>n>>k;
    if((m==1)&&(k!=1)) cout<<"-1";
        else
            {
                K=((k-5)/(m-1))*(n-1)+5;
                cout<<K;
            }   
}

Задача  B
Ідея: зміна рахунку на табло – це послідовні числа від 0 до n . Сума цих чисел – сума арифметичної прогресії S=n*(n-1)/2.   Звідси отримуємо: n=((int)sqrt(8*S+1)-1)/2;

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    long long n, S;
    cin>>S;
    n=((int)sqrt(8*S+1)-1)/2;
    cout<<n;
}
Задача С
Задача на алгоритм Евкліда.

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    long long  a,b;
    cin>>a>>b;
    while(b)
        {
            a%=b;
            swap(a,b);
        }
    cout<<a;       
}

Задача D
У даному алгоритмі використаний метод включення –викключення.

#include<iostream>
 #include<cstdio>
 using namespace std;
 int main()
 {
 freopen("prosto.in","r",stdin);
 long long sum = 0,a,b;
 int n, p[10];
 cin>>a>>b>>n;
 for(int i=0;i<n;i++) cin>>p[i];
    for (int i = 0; i < (1 << n); i++) {
      int f = 1;
      long q = 1;
      for (int j = 0; j < n; j++)
        if ((i & (1 << j)) > 0) {
          f *= -1;
          q *= p[j];
        };
      sum += f * (b / q - (a - 1) / q);
    };
    cout<<sum;
  }
 
3адача  E
Ідея: скануюча пряма:
Проходимо  сканпрямою і маємо події двох видів --- прямокутник  починається  або закінчився.
Ці запити = +-1 на відрізку прямої. А відповідь на задачу це максимум на всій прямій.

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#include <vector>
#define MAXN 524288
#define MAXC 200000
#define INFINITy 1000000000
struct tseg{
    int miny, maxy, d,x;
    tseg(){}
    tseg(int p, int q, int b, int a){
        miny = p;
        maxy = q;
        d = b;
        x = a;
    }
    friend bool operator <(const tseg &a, const tseg &b){
        if (a.x!=b.x) return a.x<b.x;
        if (a.d!=b.d) return a.d>b.d;
        return false;
    }
};   
int max(int a, int b){
    return (a>b?a:b);
}
struct window{
    int x1,y1,x2,y2;
};
struct tree{
    int a[MAXN*2+2];
    int d[MAXN*2+2];
    tree(){
        for (int i = 0; i < MAXN*2+2; i++){a[i]=0;d[i]=0;}
    }
    void add(int l, int r, int D, int v, int nL, int nR){                             
        if ((nR<l)||(nL>r)) return;
        if ((nL>=l)&&(nR<=r)){
            d[v] += D;
            return;
        }
        d[v*2+1] += d[v];
        d[v*2+2] += d[v];
        d[v] = 0;
        add(l,r,D,v*2+1,nL,((nL+nR)>>1));
        add(l,r,D,v*2+2,((nL+nR)>>1)+1,nR);
        a[v] = max(a[v*2+1]+d[v*2+1],a[v*2+2]+d[v*2+2]);
    }
    pair<int,int> getmax(){
        int v = 0;
        int l = 0;
        int r = MAXC*2+1;
        while (l!=r){
            d[v*2+1] += d[v];
            d[v*2+2] += d[v];
            d[v] = 0;
            a[v] = max(a[v*2+1]+d[v*2+1],a[v*2+2]+d[v*2+2]);
            if (a[v*2+1]+d[v*2+1]>a[v*2+2]+d[v*2+2]){
                v = v*2+1;
                r = (l+r)>>1;
            }else{
                v = v*2+2;
                l = ((l+r)>>1)+1;
            }
        }
        a[v] += d[v];
        d[v] = 0;               
        return make_pair(a[v],l);
    }
};
vector<tseg> v;
tree t;
window w[50000];
int n;
int main(){
    freopen("windows.in", "rt", stdin);
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        int x1,y1,x2,y2;
        scanf("%d%d%d%d", &x1,&y1,&x2,&y2);
        w[i].x1=x1;w[i].x2=x2;w[i].y1=y1;w[i].y2=y2;
        x1 += MAXC; y1 += MAXC; x2 += MAXC; y2 += MAXC;
        v.push_back(tseg(y1,y2,1,x1));
        v.push_back(tseg(y1,y2,-1,x2));
    }
    sort(v.begin(),v.end());
    int omax = 0;
    int _x = 0;
    int _y = 0;
    for (int i = 0; i < n*2; i++){
        t.add(v[i].miny, v[i].maxy, v[i].d, 0, 0, MAXC*2+1);
        pair<int, int> tmp = t.getmax();
        if (tmp.first>omax){
            omax = tmp.first;
            _x = v[i].x;
            _y = tmp.second;
        }
    }
    printf("%d\n", omax);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

3адача F
Ідея:  вставляємо зірочку між кожними  символами і для кожної позиції рахуємо найбільший паліндром з центром в даній позиції.
Хеш-функція з використанням бінарного пошуку.

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
#define mlen 200010
int n, len, num[mlen], sum[mlen];
char s[mlen], s1[mlen], t[mlen];
int p[mlen], code[mlen], q[mlen], ncode[mlen];
int tr[mlen * 2];
int TGet( int l, int r )
{
  if (l > r) swap(l, r);
  r--;
  l += n, r += n;
  int mi = (int)1e9;
  while (l <= r)
  {
    if (l & 1) mi = min(mi, tr[l++]);
    if (!(r & 1)) mi = min(tr[r--], mi);
    if (l > r) break;
    l >>= 1, r >>= 1;
  }
  return mi;
}
int main( void )
{
  int i, k;
  freopen("palind.in", "rt", stdin);
  gets(s);
  len = strlen(s);
  for (i = 0; i < len; i++)
    s1[i] = s[len - i - 1];
  s1[len] = 0;
  sprintf(t, "$%s#%s!", s, s1);
  n = strlen(t);
  memset(num, 0, sizeof(num));
  for (i = 0; i < n; i++)
    num[(int)t[i]]++;
  sum[0] = 0;
  for (i = 0; i < mlen; i++)
    sum[i + 1] = sum[i] + num[i];
  for (i = 0; i < n; i++)
    p[sum[(int)t[i]]++] = i, code[i] =(int)t[i];
  for (k = 1; k < n; k *= 2)
  {
    memset(num, 0, sizeof(num));
    for (i = 0; i < n; i++)
      num[code[i]]++;
    sum[0] = 0;
    for (i = 0; i < max(n, 256); i++)
      sum[i + 1] = sum[i] + num[i];
    for (i = 0; i < n; i++)
      q[sum[code[(p[i] - k + n) % n]]++] = p[i];
    int cc = 0;
    for (i = 0; i < n; i++)
    {
      if (i && (code[q[i]] != code[q[i - 1]] || code[(q[i] - k + n) % n] != code[(q[i - 1] - k + n) % n])) cc++;
      ncode[i] = cc;
    }
    for (i = 0; i < n; i++)
      p[i] = q[i], code[p[i]] = ncode[i];
  }
  for (i = 0; i < n; i++)
    p[i] = (p[i] - k + 1 + n * 2) % n;
  for (i = 0; i < n; i++)
    q[p[i]] = i;
  for (i = 1; i < n; i <<= 1);
  for (k = i = 0; i < n; i++)
  {
    if (k) k--;
    if (q[i] < n)
      while (k < n && t[i + k] == t[p[q[i] + 1] + k])
        k++;
    tr[n + q[i]] = k;
  }
  for (i = n - 1; i > 0; i--)
    tr[i] = min(tr[i + i], tr[i + i + 1]);
  long long ans = 0;
  for (i = 0; i < len; i++)
    ans += max(0, TGet(q[i + 1], q[len * 2 - i + 1]) - 1);
  for (i = 0; i < len - 1; i++)
    ans += TGet(q[i + 2], q[len * 2 - i + 1]);
  cout << ans;
  return 0;
}
Copyright MyCorp © 2017
Пошук
Календар
«  Грудень 2017  »
ПнВтСрЧтПтСбНд
    123
45678910
11121314151617
18192021222324
25262728293031
Архів записів
Друзі сайту
Обдаровані діти

Хмельницькі олімпіади

НМЦ ІКТ і ДН

Портал ХОІППО

Безкоштовний конструктор сайтів - uCoz