#include<cstring>
using namespace std;
class MyString {
public:
// 构造函数
MyString() : length(0), data(nullptr){}
MyString(int n, char d);
MyString(const char* d);
// 拷贝构造函数
MyString(const MyString& str);
// 拷贝赋值函数
MyString& operator=(const MyString& other);
// 移动构造函数
MyString(MyString&& other) noexcept;
// 移动赋值函数
String& operator=(String&& other) noexcept;
// 析构函数
~MyString()
{
delete[] data;
}
// 常用成员函数
int size() const {
return length;
}
char& operator[](int n){
return *(data + n);
}
private:
int length;
char* data;
};// 构造函数
MyString::MyString(int n, char d){
char* temp=new char[n+1];
length=n;
for(int i=0;i<n;i++){
temp[i]=d;
}
temp[n]='\0';
}
MyString::MyString(const char* t){
if(t){
length=strlen(t);
data=new char[length+1];
strcpy(data,t);
}else{
length=0;
data=nullptr;
}
}
// 拷贝构造函数
MyString::MyString(const MyString& str){
if(str.data){
length=str.length;
data=new char[length+1];
strcpy(data,str.data);
}else{
length=0;
data=nullptr;
}
}
// 拷贝赋值运算符
MyString& MyString::operator=(const MyString& rhs){
if(this==&rhs){
return *this
}
delete [] data;
length=strlen(rhs.data);
data=new char[length+1];
strcpy(data, rhs.data);
return *this;
}
// 移动构造函数
MyString::MyString(MyString&& str){
data=str.data;
length=str.length;
str.data=nullptr;
str.length=0;
}
// 移动赋值运算符
MyString& MyString::operator=(MyString&& str){
if(this==&str){
return *this;
}
delete data[];
data=str.data;
length=str.length;
str.length=0;
str.data=nullptr;
return *this;
}void* memset(void* ptr, int value, size_t num) {
unsigned char* p = static_cast<unsigned char*>(ptr);
unsigned char v = static_cast<unsigned char>(value);
for (size_t i = 0; i < num; i++) {
*(p + i) = v;
}
return p;
}void* memcpy(void* dest,const void* src,size_t n){
char* t=dest;
const char* s=src;
while(n--){
*t=*s;
t++;
s++;
}
return dest;
}void* memmove(void* dest,const void* src,size_t n){
char* t;
const char* s;
if(dest<=src){
t=dest;
s=src;
while(n--){
*t=*s;
t++;
s++;
}
}else{
t=dest+n;
s=src+n;
while(n--){
--t;
--s;
*t=*s;
}
}
return dest;
}void insert_sor(vector<int>& arr){
int n=arr.size();
if(n==1) return;
for(int i=1;i<n;i++){
int key=arr[i];
int j=i-1;
while(j>=0 && key<arr[j]){
arr[j+1]=arr[j];
j--;
}
arr[j+1]=key;
}
}class Solution {
public:
void mysort(vector<int>& nums, int begin,int end){
if(begin>=end) return;
int x = rand() % (end - begin + 1) + begin; // 基于随机的原则
swap(nums[begin], nums[x]);
int base=nums[begin];
int left=begin,right=end;
while(left<right){
while(left<right && nums[right]>=base) right--;
if(left<right) nums[left]=nums[right];
while(left<right && nums[left]<=base) left++;
if(left<right) nums[right]=nums[left];
}
nums[left]=base;
mysort(nums,begin,left-1);
mysort(nums,left+1,end);
}
vector<int> sortArray(vector<int>& nums) {
mysort(nums,0,nums.size()-1);
return nums;
}
};class Solution {
public:
void adjustheap(vector<int>& nums, int top, int len){
int left=top*2;
int right=top*2+1;
int large=top;
if(left<len && nums[left]>nums[large]){
large=left;
}
if(right<len && nums[right]>nums[large]){
large=right;
}
if(large!=top){
swap(nums[top],nums[large]);
adjustheap(nums,large,len);
}
}
void buildheap(vector<int>& nums){
int n=nums.size();
for(int i=n/2;i>=0;i--){
adjustheap(nums,i,n);
}
}
void heapsort(vector<int>& nums){
int n=nums.size();
buildheap(nums);
for(int i=0;i<n-1;i++){
swap(nums[0],nums[n-1-i]);
adjustheap(nums,0,n-1-i);
}
}
vector<int> sortArray(vector<int>& nums) {
heapsort(nums);
return nums;
}
};class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> ans;
TreeNode* now=root;
// prev等于出栈的元素
TreeNode* prev=nullptr;
while(now||!st.empty()){
while(now){
st.emplace(now);
now=now->left;
}
TreeNode* temp=st.top();
st.pop();
if(temp->right==nullptr||temp->right==prev){
prev=temp;
ans.push_back(temp->val);
now=nullptr;
}else{
st.push(temp);
now=temp->right;
}
}
return ans;
}
};vector<int> inorder(TreeNode* root){
stack<TreeNode*> st;
vector<int> ans;
while(root || !st.empty()){
while(root){
st.push(root);
root=root->left;
}
TreeNode* temp=st.top();
st.pop();
ans.push_back(temp->val);
root=temp->right;
}
return ans;
}n个人，差别值为能力值和性格值之差的和，差别值不超过L的两个人必然在一个组里，所有人至少能分成k个非空小组，规定的差别值上限是多少。
#include<vector>
#include<iostream>
#define ll long long
using namespace std;
int n, k;
vector<ll> a;
vector<ll> b;
ll g[501][501];
int father[501];
ll dis(int i, int j) { return abs(a[i] - a[j]) + abs(b[i] - b[j]); }
void init() {
for (int i = 0; i <= n; i++) {
father[i] = i;
}
}
int find(int x) {
if (x != father[x]) {
father[x] = find(father[x]);
}
return father[x];
}
void merge(int x, int y) {
int fx = find(x);
int fy = find(y);
if (fx != fy) {
father[fx] = fy;
}
}
bool check(ll x) {
init();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (g[i][j] <= x) {
merge(i, j);
}
}
}
vector<bool> vis(n, false);
for (int i = 0; i < n; i++) {
vis[find(i)] = true;
}
int cur = 0;
for (int i = 0; i < n; i++) {
if (vis[i]) {
cur++;
}
}
return cur >= k;
}
int main() {
cin >> n >> k;
a.resize(n, 0);
b.resize(n, 0);
ll MIN = 1000000000;
ll MAX = 0;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
ll d = dis(i, j);
g[i][j] = d;
g[j][i] = d;
MIN = min(MIN, d);
MAX = max(MAX, d);
}
}
// 差别值越大，分的小组越少
// 差别值越小，分的小组越多
ll l = MIN, r = MAX + 1;
while (l < r) {
int mid = (l + r) / 2;
if (check(mid)) {
l = mid + 1;
}
else {
r = mid;
}
}
cout << l - 1;
return 0;
}
/*
3 2
1 9 3
2 7 8
*/#include <bits/stdc++.h>
using namespace std;
// string转化为vector<int>，倒序存储
// “123” = 321 个位放到vector的前面
vector<int> s2i(string& s) {
vector<int> x;
int idx = 0, n = s.size();
for (; idx < n; ++idx) {
if (s[idx] != '0') break;
}
if (idx == n) idx = n - 1;
for (int i = n-1; i >= idx; --i) {
x.push_back(s[i]-'0');
}
return x;
}
// a进制下x%b，x倒序存储
// a是进制，b是求余的数
int mod(vector<int>& x, int a, int b) {
int n = x.size(), q = 0;
for (int i = n-1; i >= 0; --i) {
q = (q * a + x[i]) % b;
}
return q;
}
// a进制下x/b，x倒序存储
// a是进制,b是要除的数
void div(vector<int>& x, int a, int b) {
int n = x.size(), q = 0;
for (int i = n-1; i >= 0; --i) {
x[i] += q * a;
q = x[i] % b;
x[i] = x[i] / b;
}
for (int i = n-1; i > 0; --i) {
if (x[i]) break;
x.pop_back();
}
}
// a进制下s转化为b进制string
string convert(string s, int a, int b) {
// 转换成大数在高位
vector<int> x = s2i(s);
int n = x.size();
vector<int> y;
while (n > 0) {
// x是a进制数，用b求余
y.push_back(mod(x, a, b));
// x是a进制数，用b求商
div(x, a, b);
n = x.size();
if (n == 1 && !x[0]) break;
}
int m = y.size();
string res = "";
for (int i = m-1; i >= 0; --i) {
res += '0' + y[i];
}
return res;
}
int main() {
int T;
cin >> T;
string x;
for (int t = 0; t < T; ++t) {
cin >> x;
string x2 = convert(x, 10, 2);
reverse(x2.begin(), x2.end());
string res = convert(x2, 2, 10);
cout << "case #" << t << ":" << endl;
cout << res << endl;
}
return 0;
}给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
class Solution {
private:
unordered_map<int,int> mp;
public:
int dp(int k,int n){
if(mp.find(n*100+k)==mp.end()){
int ans;
if(n==0){
ans=0;
}else if(k==1){
ans=n;
}else{
int left=1,right=n;
while(left+1<right){
int mid=(right+left)/2;
// 鸡蛋没碎
int f1=dp(k,n-mid);
// 鸡蛋碎了
int f2=dp(k-1,mid-1);
if(f1<f2){
right=mid;
}else if(f1>f2){
left=mid;
}else{
left=mid;
right=mid;
}
}
ans=1+min(max(dp(k,n-left),dp(k-1,left-1)), max(dp(k,n-right),dp(k-1,right-1)));
}
mp[n*100+k]=ans;
}
return mp[n*100+k];
}
int superEggDrop(int k, int n) {
return dp(k,n);
}
};#include<iostream>
#include<vector>
#include<cstring>
#include<stack>
#include<sstream>
using namespace std;
string get(string& s) {
// 返回的字符串
string ret="";
// 符号栈
stack<char> st;
int n = s.size();
int index = 0;
while(index<n) {
while (isdigit(s[index])) {
ret.push_back(s[index]);
index++;
}
ret.push_back(' ');
if (s[index] == '+' || s[index] == '-') {
while (!st.empty() && (st.top() == '+' || st.top() == '-' || st.top() == '*' || st.top() == '/')) {
ret.push_back(st.top());
ret.push_back(' ');
st.pop();
}
st.push(s[index]);
}
else if (s[index] == '*' || s[index] == '/') {
while (!st.empty() && (st.top() == '*' || st.top() == '/')) {
ret.push_back(st.top());
ret.push_back(' ');
st.pop();
}
st.push(s[index]);
}
else if (s[index] == '(') {
st.push('(');
}
else if (s[index] == ')') {
while (!st.empty() && st.top() != '(') {
ret.push_back(st.top());
ret.push_back(' ');
st.pop();
}
st.pop();
}
index++;
}
while (!st.empty()) {
ret.push_back(st.top());
ret.push_back(' ');
st.pop();
}
return ret;
}
int cal(string& str) {
stringstream ss(str);
string s;
stack<int> st;
int ret=0;
while (ss >> s) {
//cout << s << endl;
if (isdigit(s[0])) {
st.push(stoi(s));
continue;
}
if (s[0] == '+') {
int a = st.top();
st.pop();
int b = st.top();
st.pop();
ret = a + b;
st.push(ret);
}
else if (s[0] == '-') {
int a = st.top();
st.pop();
int b = st.top();
st.pop();
ret = b - a;
st.push(ret);
}
else if (s[0] == '*') {
int a = st.top();
st.pop();
int b = st.top();
st.pop();
ret = a * b;
st.push(ret);
}
else {
int a = st.top();
st.pop();
int b = st.top();
st.pop();
ret = b / a;
st.push(ret);
}
}
return ret;
}
int main() {
string s;
getline(cin, s);
string ret = get(s);
// cout << ret << endl;
int ans = cal(ret);
cout << ans << endl;
return 0;
}