Yoh

1032

xiaoling
Kenshin

Yoh
2天前

# include[HTML_REMOVED]

using namespace std;

const int N = 1e6+10;

int q[N];

int n;

void quick_sort(int q[],int l,int r){

if(l>=r) return;

int x=q[l] ,i=l-1,j=r+1;

while(i<j){

do i++; while(q[i]<x);
do j--; while(q[j]>x);
if(i<j) swap(q[i],q[j]);
}

quick_sort(q,l,j);
quick_sort(q,j+1,r);


}

int main(){
cin>>n;

for(int i=0;i<n;i++){
cin>>q[i];
}

quick_sort(q,0,n-1);

for(int i=0;i<n;i++){
cout<<q[i];
}

return 0;


}

Yoh
5个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 1000;
int mp[N][N];
int a[N][N];
int m, n;
int dir[4][2] = {0,1,1,0,-1,0,0,-1};
int dfs(int x, int y){
if(mp[x][y] != -1) return mp[x][y];
mp[x][y] = 1;
for(int i = 0; i < 4; i ++){
int nx = x + dir[i][0], ny = y + dir[i][1];
if(nx > 0 && nx <= m && ny > 0 && ny <= n){
if(a[nx][ny] < a[x][y]) mp[x][y] = max(dfs(nx, ny) + 1, mp[x][y]);
}
}

return mp[x][y];
}
int main(){
memset(mp, -1, sizeof(mp));
cin >> m >> n;
for(int i = 1; i <= m; i ++){
for(int j = 1; j <= n; j ++){
cin >> a[i][j];
}
}

int res = 0;
for(int i = 1; i <= m; i ++){
for(int j = 1; j <= n; j ++){
res = max(res, dfs(i, j));
//cout << mp[i][j] << " ";
}
//cout << endl;
}
cout << res << endl;
return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


Yoh
6个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 10010;

int ne[N], e[N], h[N], idx;
int hp[N];
int dp[N][2];
bool fat[N];

void init(){
memset(fat, false, sizeof(fat));
idx = 0;
memset(h, -1, sizeof(h));
}

e[idx] = b, ne[idx] = h[a], h[a] = idx, idx ++;
}

void dfs(int u){
dp[u][1] = hp[u];

for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
dfs(j);

dp[u][1] += dp[j][0];
dp[u][0] += max(dp[j][0], dp[j][1]);
}
}

int main(){
init();
int n;
cin >> n;
for(int i = 1; i <= n; i ++) {
cin >> hp[i];
//cout << i << hp[i] << endl;
}
int a, b;
for(int i = 0; i < n - 1; i ++){
cin >> a >> b;
fat[a] = true;
}

int root = 1;
while(fat[root]) root ++;
//cout << root << endl;
dfs(root);

cout << max(dp[root][0], dp[root][1]);

return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


Yoh
6个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int e[2 * N], ne[2 * N], h[N], idx, n;
int ans = N;
bool st[N];
void init(){
idx = 0;
memset(h, -1, sizeof(h));
memset(st, false, sizeof(st));
}

e[idx] = b, ne[idx] = h[a], h[a] = idx, idx ++;
}

int dfs(int u){
st[u] = true;
int sum = 0, res = 0;
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if(st[j]) continue;

int s = dfs(j);
res = max(s, res);
sum += s;
}

res = max(res, n - sum - 1);
ans = min(res, ans);

return (sum + 1);
}

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

int a, b;
for(int i = 0; i < n - 1; i ++){
scanf("%d %d", &a, &b);
}

dfs(1);

cout << ans << endl;

return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


Yoh
6个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
void init(){
idx = 0;
}
e[idx] = x;
idx ++;
}

void insert(int k, int x){
ne[idx] = ne[k];
ne[k] = idx;
e[idx] = x;
idx ++;
}

void remove(int k){
ne[k] = ne[ne[k]];
}
int main(){
int n;
cin >> n;
init();

while(n --){
char ch;
cin >> ch;
if(ch == 'H'){
int x;
cin >> x;
}
else if(ch == 'I'){
int k, x;
cin >> k >> x;
insert(k - 1, x);
}
else{
int k;
cin >> k;
else remove(k - 1);
}
}

for(int i = head; i != -1; i = ne[i]) cout << e[i] << " ";

return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


Yoh
6个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int son[31 * N][2], idx, a[N];

void insert(int x){
int p = 0;
for(int i = 30; i >= 0; i --){
int u = (x >> i) & 1;
if(!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
}

int query(int x){
int p = 0, res = 0;
for(int i = 30; ~i ; i --){
int u = (x >> i) & 1;
if(son[p][!u]){
res += 1 << i;
p = son[p][!u];
}
else{
p = son[p][u];
}
}

return res;
}

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

int res = 0;
for(int i = 0; i < n; i ++){
res = max(res, query(a[i]));
insert(a[i]);
}

cout << res << endl;
return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


Yoh
6个月前
#include<bits/stdc++.h>
using namespace std;

int a[1000010], b[1000010], mp[1000010];
int main(){
int n;
cin >> n;

for(int i = 1; i <= n; i ++){
scanf("%d", &a[i]);
mp[a[i]] = i;
}
for(int i = 1; i <= n; i ++) {
scanf("%d", &b[i]);
if(mp[b[i]]) b[i] = mp[b[i]];
else b[i] = 0;
//cout << b[i] << " ";
}

vector<int> aa;
for(int i = 1; i <= n; i++){
if(b[i] == 0) continue;
if(aa.size() == 0 || b[i] > aa.back()) aa.push_back(b[i]);
int idx = lower_bound(aa.begin(), aa.end(), b[i]) - aa.begin();
aa[idx] = b[i];
}

cout << aa.size() << endl;
return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


Yoh
6个月前
#include<bits/stdc++.h>
using namespace std;
vector<int> v;
int x[400010],c[400010];
int r[400010],l[400010];
int sum[400010];

int find(int num){
return lower_bound(v.begin(), v.end(), num) - v.begin();
}

int main(){
int n, m;
cin >> n >> m;
for(int i = 0; i < n ; i ++){
cin >> x[i] >> c[i];
v.push_back(x[i]);
}
for(int i = 0; i < m; i ++){
cin >> l[i] >> r[i];
v.push_back(l[i]);
v.push_back(r[i]);
}
v.push_back(-2e9);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

for(int i = 0; i < n ; i++) sum[find(x[i])] += c[i];

int len = v.size();
for(int i = 1; i <= len; i ++) sum[i] += sum[i - 1];

for(int i = 0; i < m; i ++) cout << sum[find(r[i])] - sum[find(l[i]) - 1] << endl;

return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


Yoh
6个月前
#include<bits/stdc++.h>
using namespace std;

int a[310], s[310], dp[310][310];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i ++) {
cin >> a[i];
s[i] = s[i - 1] + a[i];
}

for(int len = 2; len <= n ; len ++){
for(int i = 1; i + len - 1 <= n; i ++){
int j = i + len - 1;
dp[i][j] = 1e8;
for(int k = i; k <= j; k ++){
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + s[j] - s[i - 1]);
}
}
}

cout << dp[1][n] << endl;

return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


Yoh
6个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;

int son[N][26], cnt[N], idx;

void insert(char str[]){
int p = 0;
for(int i = 0; str[i]; i ++){
int u = str[i] - 'a';
if(!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}

cnt[p] ++;
}

int query(char str[]){
int p = 0;
for(int i = 0; str[i]; i ++){
int u = str[i] - 'a';
if(!son[p][u]) return 0;
p = son[p][u];
}

return cnt[p];
}

char str[N];
int main(){
int qnum;
cin >> qnum;
while(qnum --){
char ch[2];
scanf("%s%s",ch,str);
if(ch[0] == 'I'){
insert(str);
}
else cout << query(str) << endl;
}

return 0;
}

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~