houghstc

1.5万

#include <iostream>
#include <unordered_set>

using namespace std;

int main()
{
int n, m;
cin >> n >> m;

unordered_set<int> set;
int v1 = 1e9, v2;
for(int i = 0; i < n; ++i)
{
int a;
cin >> a;
int b = m - a;
if(set.count(b))
{
if(a > b) swap(a, b);
if(a < v1) v1 = a, v2 = b;
}
set.insert(a);
}
if(v1 == 1e9)
cout << "No Solution\n";
else
cout << v1 << ' ' << v2 << '\n';
return 0;
}


houghstc
10天前
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 50010, M = 1000010;

int primes[N], cnt;
bool is_prime[N];
int l, r;
bool is_prime2[M];

void get_primes(int n)
{
fill(is_prime, is_prime+N, true);

for(int i = 2; i <= n; ++i)
{
if(is_prime[i]) primes[cnt++] = i;
for(int j = 0; primes[j] * i <= n; ++j)
{
is_prime[primes[j]*i] = false;
if(i % primes[j] == 0) break;
}
}
}

int main()
{
get_primes(50000);

while(cin >> l >> r)
{
fill(is_prime2, is_prime2+M, true);
for(int i = 0; i < cnt; ++i)
{
// p0 = first multiple of p greater or equal to l
// p0 = ceil(l/p) = (l+p-1)/p
ll p = primes[i];
for(ll j = max(2*p, (l+p-1)/p*p); j <= r; j += p)
{
is_prime2[j-l] = false;
}
}

int mi_a = 0, mi_b = 1e9, mx_a = -1, mx_b = -1;
for(ll i = l, j = -1; i <= r; ++i) // i要定义成ll 类型，不然i = r之后++i会爆int
{
if(i >= 2 && is_prime2[i-l])  // i必须要大于2
{
if(j != -1)
{
if(i-j < mi_b-mi_a)
{
mi_a = j, mi_b = i;
}
if(i-j > mx_b-mx_a)
{
mx_a = j, mx_b = i;
}
}
j = i;
}
}
if(mi_a != 0)
{
cout << mi_a << ',' << mi_b << " are closest, " << mx_a << ',' << mx_b << " are most distant.\n";
}
else
{
cout << "There are no adjacent primes.\n";
}

}
return 0;
}


houghstc
10天前
#include <iostream>
#include <string>

using namespace std;

int main()
{
string s, t;
cin >> s >> t;
int n = s.size();
int cnt = 0;
for(int i = 0, j = -1; i < n; ++i)
{
if(s[i] != t[i])
{
if(j == -1)
j = i;
else
{
cnt += (i-j);
j = -1;
}
}
}
cout << cnt << '\n';

return 0;
}


houghstc
10天前
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Data
{
int id;
int a;
int b;
int c;
int sum;
};

int main()
{
int n;
cin >> n;
vector<Data> d(n+1);
for(int i = 1; i <= n; ++i)
{
cin >> d[i].a >> d[i].b >> d[i].c;
d[i].id = i;
d[i].sum = d[i].a + d[i].b + d[i].c;
}

sort(d.begin()+1, d.end(), [](const auto &d1, const auto &d2) {
if(d1.sum != d2.sum)
return d1.sum > d2.sum;
else if(d1.a != d2.a)
return d1.a > d2.a;
else
return d1.id < d2.id;
});

for(int i = 1; i <= 5; ++i)
cout << d[i].id << ' ' << d[i].sum << '\n';

return 0;
}


houghstc
10天前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int primes[N], cnt, n;
bool is_prime[N];

void get_primes(int n)
{
fill(is_prime, is_prime+N, true);
for(int i = 2; i <= n; ++i)
{
if(is_prime[i]) primes[cnt++] = i;
for(int j = 0; primes[j]*i <= n; ++j)
{
is_prime[primes[j]*i] = false;
if(i % primes[j] == 0)
break;
}
}
}

int main()
{
cin >> n;
get_primes(n+1);

if(n <= 2) puts("1");
else puts("2");

for(int i = 2; i <= n+1; ++i)
{
if(is_prime[i])
cout << "1 ";
else
cout << "2 ";
}
cout << '\n';

return 0;
}


houghstc
11天前
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 1e6;

bool is_prime[N+10];
vector<int> primes;
int cnt;

void get_primes()
{
primes.reserve(N);
memset(is_prime, true, sizeof is_prime);
for(int i = 2; i <= N; ++i)
{
if(is_prime[i]) primes.push_back(i);
for(int j = 0; primes[j]*i <= N; ++j)
{
is_prime[primes[j] * i] = false;
// cout << "set false to: " << primes[j] * i << endl;
if(i % primes[j] == 0) break;
}
}
}

void solve(int x)
{
for(int i = 1; i < primes.size() && primes[i] <= x/2; ++i)
{
auto it = lower_bound(primes.begin(), primes.end(), x-primes[i]);
if(it != primes.end() && *it == x-primes[i])
{
cout << x << " = " << primes[i] << " + " << *it << '\n';
return;
}
}
}

int main()
{
get_primes();
int x;
while(cin >> x, x)
{
solve(x);
}
return 0;
}


houghstc
12天前
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef pair<int, int> pii;

int main()
{
int l, m;
cin >> l >> m;
vector<pii> ranges(m);
for(int i = 0; i < m; ++i)
cin >> ranges[i].first >> ranges[i].second;

sort(ranges.begin(), ranges.end(), [](const pii p1, const pii p2) { return p1.first < p2.first; });

vector<pii> merged;
pii curr = ranges[0];
for(int i = 1; i < m; ++i)
{
if(ranges[i].first > curr.second)
{
merged.push_back(curr);
curr = ranges[i];
}
else
{
if(ranges[i].second > curr.second)
{
curr.second = ranges[i].second;
}
}
}
merged.push_back(curr);

int cnt = 0;
for(auto p: merged)
cnt += (p.second-p.first+1);

cout << l+1-cnt << '\n';

return 0;
}


houghstc
12天前
#include <iostream>

using namespace std;

typedef pair<int, int> pii;

const int N = 100010;
pii arr[N];
int n, k;

bool check(int len)
{
int cnt = 0;
for(int i = 0; i < n; ++i)
{
auto [a, b] = arr[i];
cnt += (a / len) * (b / len);
}
return cnt >= k;
}

int main()
{
cin >> n >> k;

int max_len = 0;
for(int i = 0; i < n; ++i)
{
int a, b;
cin >> a >> b;
arr[i] = {a, b};
max_len = max(max_len, min(a, b));
}

int l = 1, r = max_len;
while(l < r)
{
int mid = (l+r+1)/2;
if(check(mid))
l = mid;
else
r = mid - 1;
}

cout << l << '\n';
return 0;
}


houghstc
12天前
#include <iostream>
#include <iomanip>

using namespace std;

const int N = 100010;
int arr[N];
int n, m;

bool check(double len)
{
int cnt = 0;
for(int i = 0; i < n; ++i)
{
cnt += (arr[i]/len);
if(cnt >= m)
return true;
}
return false;
}

int main()
{
cin >> n >> m;
for(int i = 0; i < n; ++i)
cin >> arr[i];

double l = 0, r = 1e9;
while(r-l > 1e-4)
{
double mid = (r+l)/2;
if(check(mid))
l = mid;
else
r = mid;
}
cout << fixed << setprecision(2) << l << '\n';

return 0;
}


houghstc
12天前
#include <iostream>
#include <string>
#include <cmath>

const int N = 18;
int base[N];
int n;

using namespace std;

char to_char(int x)
{
if(x <= 9)
return '0' + x;
else
return 'A' + (x-10);
}

bool is_palindrome(const string &s)
{
int n = s.size();
for(int i = 0; i < n/2; ++i)
{
if(s[i] != s[n-1-i])
return false;
}
return true;
}

string to_base_b(int x)
{
string s;
for(int j = n; j >= 0; --j)
{
int y = x / base[j];
s.push_back(to_char(y));
x = x % base[j];
}

// remove prefix '0'
int j = 0;
for(; j < s.size(); ++j)
{
if(s[j] != '0')
break;
}
s = s.substr(j);
return s;
}

int main()
{
int B;
cin >> B;
n = log2(90000)/log2(B) + 1;

base[0] = 1;
for(int i = 1; i <= n; ++i)
{
base[i] = base[i-1] * B;
}

for(int i = 1; i <= 300; ++i)
{
int x = i * i;
string s = to_base_b(x);

// check palindrome
if(is_palindrome(s))
cout << to_base_b(i) << ' ' << s << '\n';
}
return 0;
}