Tie

Tie
1个月前
// Time Limit Exceeded

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
int n;
int a[N];

int partition(int a[], int l, int r) {
int p = a[l]; // 把最左边的点设为pivot
int m = l; //更新m为最左边的点，m是S1和S2的分界点，位于S1末尾
// 比pivot小的点放到S1里面去，比pivot大的点放到S2里面去，最开始两者皆为空
for (int k = m + 1; k <= r; k ++ ) { //遍历数组
if (a[k] < p) { // 找到数组中小于pivot的值
m ++ ; // 更新m，让S1区间多1
swap(a[k], a[m]); // 把小于pivot的值放到S1区间里面
}
}
swap(a[l], a[m]); // 把pivot的值和m交换，使pivot分隔S1和S2
return m;

}

void quickSort(int a[], int l, int r) {
if (l < r) {
int m = partition(a, l, r);
quickSort(a, l, m - 1); // 递归地将左子阵列排序
quickSort(a, m + 1, r); // 然后将右子阵列排序
}
}

int main() {
cin >> n;
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
quickSort(a, 0, n - 1);
for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);

return 0;
}


Tie
1个月前
if __name__ == '__main__':
n = int(input())
array = list(map(int, input().split()))
res = quicksort(array)
for i in res:
print(i, end=' ')


Tie
1个月前
class Solution {
public:
int getMaxValue(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<int>> f(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
f[i][j] = max(f[i - 1][j], f[i][j - 1]) + grid[i - 1][j - 1];
return f[n][m];
}
};


Tie
1个月前
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:

// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string res;
dfs_s(root, res);
return res;
}

void dfs_s(TreeNode *root, string &res)
{
if (!root) {
res += "null ";
return;
}
res += to_string(root->val) + ' ';
dfs_s(root->left, res);
dfs_s(root->right, res);
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
int u = 0;
return dfs_d(data, u);
}

TreeNode* dfs_d(string data, int &u)
{
//if (u == data.size()) return NULL;
int k = u;
while (data[k] != ' ') k ++ ;
if (data[u] == 'n') {
u = k + 1;
return NULL;
}
int val = 0, sign = 1;
if (u < k && data[u] == '-') sign = -1, u ++ ;
for (int i = u; i < k; i ++ ) val = val * 10 + data[i] - '0';
val *= sign;
u = k + 1;
auto root = new TreeNode(val);
root->left = dfs_d(data, u);
root->right = dfs_d(data, u);
return root;
}
};


Tie
1个月前
#include <iostream>

using namespace std;

const int N = 1010, MOD = 1e9 + 7;
typedef long long LL;

int n;
int f[N];

int main() {
cin >> n;

f[0] = 1;
for (int i = 1; i <= n; i ++ )
for (int j = 0; j < i; j ++ )
f[i] = (f[i]  + (LL)f[j] * f[i - 1 - j]) % MOD;
cout << f[n] << endl;

return 0;
}


Tie
1个月前
/**
* Definition for singly-linked list with a random pointer.
* struct ListNode {
*     int val;
*     ListNode *next, *random;
*     ListNode(int x) : val(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
unordered_map<ListNode*, ListNode*> pos; // 定义hash表来存映射，从一个指针映射到另一个指针

pos[NULL] = NULL; // 空节点映射到空节点
for (auto p = head; p; p = p->next)  // 遍历原链表
pos[p] = new ListNode(p->val); // 先给每个点做个影分身

for (auto p = head; p; p = p->next) {
pos[p]->next = pos[p->next];  //
pos[p]->random = pos[p->random];
}

}
};


Tie
1个月前
#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int l[N];

bool check(double length) {
int s = 0;
for (int i = 0; i < n; i ++ ) {
s += l[i] / length;
if (s >= m) return true;
}

return false;
}

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

double l = 0, r = 1e9;
while (r - l > 1e-4) {
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}

printf("%.2lf\n", r);

return 0;
}


Tie
1个月前
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> get_val(vector<TreeNode*> level)
{
vector<int> res;
for (auto &u : level)
res.push_back(u->val);
return res;
}

vector<vector<int>> printFromTopToBottom(TreeNode* root) {
vector<vector<int>>res;
if (!root) return res;
vector<TreeNode*>level;
level.push_back(root);
res.push_back(get_val(level));
bool zigzag = true;
while (true)
{
vector<TreeNode*> newLevel;
for (auto &u : level)
{
if (u->left) newLevel.push_back(u->left);
if (u->right) newLevel.push_back(u->right);
}
if (newLevel.size())
{
vector<int>temp = get_val(newLevel);
if (zigzag)
reverse(temp.begin(), temp.end());
res.push_back(temp);
level = newLevel;
}
else break;
zigzag = !zigzag;
}
return res;
}
};


Tie
1个月前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 20;

int n;
int w[N][N];
int f[1 << N][N]; // f[i][j]表示已经走遍i中所有城市，并且停留在j城市的所有方案集合；花费最小值
// 状态i化为二进制后，里面为1的位置表示走过了的城市， i <= (1 << n) - 1
// 101010101表示走过了5个城市

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

memset(f, 0x3f, sizeof f);
f[1][0] = 0;

for (int i = 1; i < 1 << n; i += 2)
for (int j = 0; j < n; j ++ )
if (i >> j && 1)
for (int k = 0; k < n; k ++ )
if (i - (1 << j) >> k & 1)
f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);

int res = 0x3f3f3f3f;
for (int i = 1; i < n; i ++ ) res = min(res, f[(1 << n) - 1][i] + w[i][0]);

cout << res << endl;

return 0;
}


Tie
1个月前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 70;

int n;
int sticks[N];
bool st[N];
int sum, length;

bool dfs(int u, int cur, int start) { // 木棒数量，当前木棒长度，木棍开始位置
if (u * length == sum) return true;
if (cur == length) return dfs(u + 1, 0, 0);

for (int i = start; i < n; i ++ ) {
if (st[i]) continue;
int l = sticks[i];
if (cur + l <= length) {
st[i] = true;
if (dfs(u, cur + l, i + 1)) return true;
st[i] = false;
}

if (!cur || cur + l == length) return false;

int j = i + 1;
while (j < n && sticks[j] == l) j ++ ;
i = j - 1;
}

return false;
}

int main() {
while (cin >> n, n) {
sum = length = 0;
for (int i = 0; i < n; i ++ ) {
int l;
cin >> l;
sticks[i] = l;
sum += l;
length = max(length, l);
}

sort(sticks, sticks + n, greater<int>());

memset(st, 0, sizeof st);
while(true) {
if (sum % length == 0 && dfs(0, 0, 0)) {
cout << length << endl;
break;
}
length ++ ;
}
}

return 0;
}