Skip to content
TheChatArchiveThe Chat Archive
o1-mini-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

Одним уютным вечером Алиса решила сыграть в классическую игру «Соедини точки», но с…

  1. User

    Одним уютным вечером Алиса решила сыграть в классическую игру «Соедини точки», но с подвохом.

    Чтобы начать игру, Алиса рисует прямую линию и отмечает на ней n точек, проиндексированных числами от 1 до n . Изначально между точками нет рёбер, так что все они попарно не соединены. Затем Алиса выполняет m операций следующего типа:

    Она выбирает три целых числа ai , di (1≤di≤10 ) и ki . Затем для точек ai,ai+di,ai+2di,ai+3di,…,ai+ki⋅di Алиса соединяет ребром каждую пару из них. Алиса хочет узнать, сколько компонент связности† образуют эти точки после выполнения всех m операций.

    † Считается, что две точки лежат в одной компоненте связности, если между ними есть путь, использующий несколько (возможно, ноль) промежуточных рёбер и вершин.

    Входные данные Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число t (1≤t≤105 ) — количество наборов входных данных. Далее следует описание наборов входных данных.

    Первая строка каждого набора входных данных содержит два целых числа n и m (1≤n≤2⋅105 , 1≤m≤2⋅105 ).

    В i -й из следующих m строк содержится три целых числа ai , di и ki (1≤ai≤ai+ki⋅di≤n , 1≤di≤10 , 0≤ki≤n ).

    Гарантируется, что сумма значений n , а также сумма значений m по всем наборам входных данных не превосходит 2⋅105 каждая.

    Выходные данные Для каждого набора входных данных выведите количество компонент связности.

    Пример Входные данныеСкопировать 3 10 2 1 2 4 2 2 4 100 1 19 2 4 100 3 1 2 5 7 2 6 17 2 31 Выходные данныеСкопировать 2 96 61 Примечание В первом наборе входных данных есть n=10 точек. Первая операция соединяет точки 1 , 3 , 5 , 7 и 9 . Вторая операция соединяет точки 2 , 4 , 6 , 8 и 10 . В итоге получаем две компоненты связности: {1,3,5,7,9} и {2,4,6,8,10} .

    Во втором наборе входных данных есть n=100 точек. Единственная операция соединяет точки 19 , 21 , 23 , 25 и 27 . Теперь они образуют одну компоненту связности размера 5 . Остальные 95 точек ни с кем не соединены, так что каждая из них образует отдельную компоненту связности. Значит, ответ равен 1+95=96 .

    В третьем наборе входных данных есть n=100 точек. После выполнения всех операций все точки с нечётными номерами от 1 до 79 образуют одну компоненту связности размера 40 . Остальные 60 точек ни с кем не соединены, так что каждая из них образует отдельную компоненту связности. Значит, ответ равен 1+60=61 .

    реши на C++. Тут нужен ОЧЕНЬ продвинутый и сложный алгоритм. используй однобуквенные переменные, олимпиадный стиль

  2. Assistant
    #include <bits/stdc++.h>
    using namespace std;
    
    struct UF {
        vector<int> parent;
        UF(int n){
            parent.resize(n+1);
            for(int i=0;i<=n;i++) parent[i]=i;
        }
        int find_set(int x){
            return parent[x]==x ? x : parent[x]=find_set(parent[x]);
        }
        void union_set(int x, int y){
            int fx = find_set(x);
            int fy = find_set(y);
            if(fx != fy){
                parent[fx] = fy;
            }
        }
    };
    
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        int t;
        cin>>t;
        while(t--){
            int n, m;
            cin>>n>>m;
            UF uf(n);
            // Initialize L[d][r] for d=1 to10, r=0 tod-1
            vector<vector<vector<int>>> L(11); // L[1..10][0..d-1]
            for(int d=1; d<=10; d++) {
                L[d].resize(d, vector<int>());
            }
            for(int i=0;i<m;i++){
                int a, d, k;
                cin>>a>>d>>k;
                // According to constraints, a +k*d <=n
                // If k ==0, single point, no need to add
                if(k >=0){
                    for(int step=0; step<=k; step++){
                        int p = a + step*d;
                        // As per constraints, p <=n
                        // But to be safe:
                        if(p >n) break;
                        int r = p%d;
                        L[d][r].push_back(p);
                    }
                }
            }
            // Now, for each d and r, sort and connect consecutive
            for(int d=1; d<=10; d++){
                for(int r=0; r<d; r++){
                    if(L[d][r].empty()) continue;
                    vector<int> &vec = L[d][r];
                    sort(vec.begin(), vec.end());
                    vec.erase(unique(vec.begin(), vec.end()), vec.end());
                    for(int j=1; j<vec.size(); j++){
                        uf.union_set(vec[j-1], vec[j]);
                    }
                }
            }
            // Count unique parents
            int cnt=0;
            for(int p=1; p<=n; p++) {
                if(uf.find_set(p) == p) cnt++;
            }
            cout<<cnt<<"\n";
        }
    }