Всем привет, прошу помочь с задачей.
Пробовал с начало перевести в двоичную систему потом делать операцию “и”, работает слишком долго
https://acmp.ru/index.asp?main=task&id_task=67
На каком языке, написал? Можешь скинуть код, или более подробно рассказать что ты делаешь?
Скорее всего ты хранил двоичное число в явном виде из 0 и 1, и делал операцию “и” вручную. Для того чтобы решение проходило по тлу нужно хранить числа в виде числа, и использовать встроенные логические операции.
1 симпатия
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
string ekibit(string x)
{
string res, common;
long long san = 0;
long long step = 1;
for(int i = x.length() - 1; i >= 0; i--)
{
if(x[i] == '.')
{
step = 1;
while(san != 0)
{
if(san % 2 == 1)
{
res = res + '1';
san--;
san /= 2;
}
else
{
res = res + '0';
san /= 2;
}
}
if(res.length() < 8)
{
while(res.length()!= 8)
{
res = res + '0';
}
}
common = common + res;
res = "";
san = 0;
step = 1;
}
else
{
san += ((x[i] - 48)*step);
step *= 10;
}
}
reverse(common.begin(), common.end());
return common;
}
int main()
{
vector <string> mask;
vector <string> set1;
vector <string> set2;
string x,y;
long long n,m;
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> x;
x = '.' + x ;
mask.push_back(ekibit(x));
}
cout << endl;
cin >> m;
for(int i = 0; i < m; i++)
{
cin >> x >> y;
x = '.' + x;
set1.push_back(ekibit(x));
y = '.' + y;
set2.push_back(ekibit(y));
}
for(int i = 0; i < m; i++)
{
int count = 0;
for(int j = 0; j < n; j++)
{
string p,o;
for(int q = 0; q < 32; q++)
{
if(set1[i][q] == '0' || mask[j][q] == '0')
{p = p + '0';}
else{p= p +'1';}
if(set2[i][q] == '0' || mask[j][q] == '0')
{o = o + '0';}
else{o = o + '1';}
}
if(p == o)
{
count++;
}
}
cout << count << endl;
}
}
блин, не особо понял по части хранения. как можно хранить эти числа?
Ну давайте заметим что любое двоичное число представимо в виде десятичного, пусть у нас есть число 234 = 2^7 + 2^6 + 2^5 +2^3 + 2^2 = 11101100_2. И если у вас есть двоичное число то вы можете хранить его в виде десятичного.
Но как работать с “и”?
В c++ есть битовые операции и операция “и” это &. И если у вас есть число x и y, то применяя между ними операцию & (т.е. x&y) :
- Числа x и y переводятся в двоичный вид.
- Применяется операция “и” между ними
- Возвращается результат этой операции в виде этого числа.
(Я не про то как работает это на самом деле, а про то как можно представить как это работает).
6 симпатий
понял, рахмет!