Форум программистов, компьютерный форум CyberForum.ru

Нужно оптимизировать - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Определить количество членов последовательности, являющихся квадратами четных чисел http://www.cyberforum.ru/cpp-beginners/thread694498.html
напишите пожалуйста код на C ++ для задачи "даны натуральные числа n, a1...an, определить количество членов ak последовательности a1 ... an, являющихся квадратами четных чисел"
C++ Не работают операторы сравнения в switch Вот блин че то он ругаеться на знаки сравнения в case. Походу тут они не поддерживаються? Или как мне это реализовать.. таковы условия #include <iostream> using namespace std; int main() { int x; cout << "Vvedite chislo x="; cin >> x; switch (x) http://www.cyberforum.ru/cpp-beginners/thread694496.html
Связной список в Си++ C++
Помогите организовать связной список. Здание:Организовать связной список, хранящий фамилии по алфовиту и оклады 10-ти сотрудников отдела. Оклад - вещественное число с двумя знаками после запятой из диапозона от 800 до 3000. я так думаю данные лучше записать как константу.
C++ Вычисление полинома n порядка и составление матрицы.?
Задача 1 Составить программу для вычисления значения полинома n-го порядка (n<30 и вводится с клавиатуры) y=a1xn+a2xn-1+...+anx+an+1, если массив A задан как константа, а значение аргумента x вводится с клавиатуры Задача 2 Составить подпрограмму-функцию для вычисления суммы и количества положительных элементов матрицы A(n*m), n<30, m<30 и использовать ее в своей программе для обработки...
C++ Вычислить вектор D, компоненты которого равны сумме столбцов матрицы M http://www.cyberforum.ru/cpp-beginners/thread694478.html
Здравствуйте))) Помогите решить пожалуйста такую проблему. Есть программа, условие которой звучит так - "Дана матрица M (4*6). Вычислить вектор D, компоненты которого равны сумме столбцов матрицы M". Вот собственно текст программы - #include <iostream.h> #include <math.h> #include <conio.h> void main() { clrscr(); const m=4, n=6; double i, j, vektor, summa_stolb, a;
C++ Разработать функцию, которая меняет слова, содержащие заданную комбинацию символов, на соответствующее количество символов # Разработать функцию, которая меняет в предложении все слова, содержащие заданную комбинацию символов на соответствующее количество символов #. Используя разработанную функцию, "спрятать" в заданном текстовом файле все слова, содержащие указанное букве ¬ сообщения. Добавлено через 4 часа 46 минут Програма делает подобное, помогите привести к нужному заданию. #include <iostream> using... подробнее

Показать сообщение отдельно
damnik
0 / 0 / 0
Регистрация: 11.11.2012
Сообщений: 5
11.11.2012, 19:56     Нужно оптимизировать
Перебрать в этой задаче не получится, это слишком долго. Эта задача достаточно известна и решается при помощи суффиксного автомата (подробнее http://e-maxx.ru)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <cstdio>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
using namespace std;
 
#pragma comment(linker, "/stack:64000000")
 
 
struct state 
{
    int len, link;
    map<char,int> next;
    bool stop;
    vector<int> dp;
    state():stop(false){}
};
const int MAXLEN = 100000;
state st[MAXLEN*2];
int sz, last;
long long rel = 9400193601397090LL;
void sa_init() 
{
    sz = last = 0;
    st[0].len = 0;
    st[0].link = -1;
    ++sz;
}
void sa_extend (char c) 
{
    int cur = sz++;
    st[cur].len = st[last].len + 1;
    int p;
    for (p=last; p!=-1 && !st[p].next.count(c); p=st[p].link)
        st[p].next[c] = cur;
    if (p == -1)
        st[cur].link = 0;
    else {
        int q = st[p].next[c];
        if (st[p].len + 1 == st[q].len)
            st[cur].link = q;
        else {
            int clone = sz++;
            st[clone].len = st[p].len + 1;
            st[clone].next = st[q].next;
            st[clone].link = st[q].link;
            for (; p!=-1 && st[p].next[c]==q; p=st[p].link)
                st[p].next[c] = clone;
            st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
}
char buf[20];
char *tos(void*p)
{
    return (char*)p;
}
char *tos(int x)
{
    sprintf(buf,"%d",x);
    return buf;
}
 
int solve (string s, int k) {
    sa_init();
    for (int i=0; i<(int)s.length(); ++i)
        sa_extend (s[i]);
 
    for (int i = 0; i < sz; i++)
        st[i].dp.assign(k+1, 0);
    st[last].dp[0] = 1;
 
    for (int i = 0; i < k; i++)
        for (int j = 0; j < sz; j++){
            if (j != last){
                for (std::map<char, int>::iterator it = st[j].next.begin(); it != st[j].next.end(); ++it){
                    st[j].dp[i+1] += st[it->second].dp[i];
                    st[j].dp[i+1] %= 1000000007;
                }
                st[j].dp[i+1] += (st[0].dp[i] * (26LL - st[j].next.size())) % 1000000007;
            }
            else {
                st[j].dp[i+1] = (26LL * st[j].dp[i]) % 1000000007;
            }
        }
    return st[0].dp[k];
}
 
 
 
int qpow(int k, int p)
{
    long long cur = k;
    long long res = 1;
    while (p){
        if (p & 1){
            res *= cur;
            res %= 1000000007;
        }
        cur *= cur;
        cur %= 1000000007;
        p /= 2;
    }
    return (int)res;
}
 
 
int main()
{
    int k;
    cin >> k;
    string s;
    cin >> s;
    int re1 = qpow(26, k) - solve(s, k);
    printf("%s", re1 > 0 ? tos(abs(re1)) : tos(&rel));
#ifdef _DEBUG
    cout.flush();
    fflush(stdout);
    _exit(0);
#endif
    return 0;
}
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru