mx

6911

mx
2个月前
#include <iostream>

using namespace std;

bool is_prime(int n){
if(n <= 1) return false;
for(int i = 2; i <= n / i; i++){
if(n % i == 0) return false;
}
return true;
}

int main(){
int n;
cin >> n;
for(int i = 0; i < n ; i ++){
int a;
cin >> a;
cout << (is_prime(a) ? "Yes" : "No") << endl;
}
return 0;
}


mx
3个月前
#include <iostream>

using namespace std;

const int N = 100010, M = N * 31;

int n, idx, a[N], son[M][2];

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

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

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

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

cout << res << endl;
return 0;
}



mx
3个月前
#include <iostream>
#include <cstring>

using namespace std;
const int N = 100010;
int m;
int e[N], l[N], r[N], idx;

void init(){
r[0] = 1;
l[1] = 0;
idx = 2;
}

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

void del(int k){
r[l[k]] = r[k];
l[r[k]] = l[k];
}

int main(){
cin >> m;
init();
while(m --){
string op;
int k, x;
cin >> op;
if(op == "L"){
cin >> x;
insert(0, x);
}else if(op == "R"){
cin >> x;
insert(l[1], x);
}else if(op == "D"){
cin >> k;
del(k + 1);
}else if(op == "IL"){
cin >> k >> x;
insert(l[k + 1], x);
}else{
cin >> k >> x;
insert(k + 1, x);
}
}

for(int i = r[0]; i != 1; i = r[i]){
cout << e[i] << " ";
}

return 0;

}



mx
3个月前
#include <iostream>

using namespace std;
typedef unsigned long long ULL;
const int N = 100010, P = 131;

int n, m;
int h[N], p[N];
char str[N];

ULL get(int x, int y){
return h[y] - h[x - 1] * p[y - x + 1];
}

int main(){
cin >> n >> m;
scanf("%s", str + 1);

p[0] = 1;
for(int i = 1; i <= n; i++){
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}

while(m --){
int l1, r1, l2, r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
if(get(l1, r1) == get(l2, r2)) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}



mx
3个月前

### 拉链法

#include <iostream>
#include <cstring>

using namespace std;
const int N = 100003;//大于10的5次方的第一个质数，在hash中模上质数产生哈希冲突的概率小
int n;
int h[N], e[N], ne[N], idx;

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

bool find(int x){
int k = (x % N + N) % N;
for(int i = h[k]; i != -1; i = ne[i]){
if(e[i] == x)
return true;
}
return false;
}

int main(){
cin >> n;
char op[10];
int x;
memset(h, -1, sizeof h);
while(n--){
scanf("%s%d", op, &x);
if(*op == 'I'){
insert(x);
}else{
if(find(x)) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}


···

# include [HTML_REMOVED]

using namespace std;
const int N = 200003/开放寻址法数组大小通常要开到数据范围的2倍/, null = 0x3f3f3f3f;
int h[N];
int find(int x){
int k = (x % N + N) % N;

while(h[k] != null && h[k] != x){
k++;
if(k == N) k = 0;
}

return k;


}

int main(){
int n;
cin >> n;
memset(h, 0x3f, sizeof h);
while(n –){
char op[2];
int x;
scanf(“%s%d”, op, &x);
int k = find(x);
if(*op == ‘I’){
h[k] = x;
}else{
if(h[k] != null) cout << “Yes” << endl;
else cout << “No” << endl;
}
}
return 0;
}
···

mx
3个月前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;
int n, hh = 0, tt = -1;
int q[N];

void push(int x){
q[++ tt] = x;
}

void pop(){
hh++;
}

bool empty(){
return hh > tt;
}

int query(){
return q[hh];
}

int main(){
cin >> n;
char op[10];
int x;
while(n --){
cin >> op;
if(!strcmp(op, "push")){
cin >> x;
push(x);
}else if(!strcmp(op, "pop")){
pop();
}else if(!strcmp(op, "empty")){
cout << (empty() ? "YES" : "NO") << endl;
}else {
cout << query() << endl;
}
}
return 0;
}


mx
3个月前
#include <iostream>
#include <cstring>

using namespace std;
const int N = 100010;
int s[N];
int n, tt = -1;

void push(int x){
s[++ tt] = x;
}

void pop(){
tt--;
}

bool empty(){
return tt == -1;
}

int query(){
return s[tt];
}

int main(){
cin >> n;
char op[10];

int x;
while(n --){
cin >> op;
if(!strcmp(op, "push")){
cin >> x;
push(x);
}else if(!strcmp(op, "pop")){
pop();
}else if(!strcmp(op, "empty")){
cout << (empty() ? "YES" : "NO") << endl;
}else{
cout << query() << endl;
}
}

return 0;
}



mx
3个月前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;
int h[N], ph[N], hp[N], cnt;

void heap_swap(int x, int y){
swap(ph[hp[x]], ph[hp[y]]);
swap(hp[x], hp[y]);
swap(h[x], h[y]);
}

void down(int u){
int t = u;
if(u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
if(u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if(u != t){
heap_swap(u, t);
down(t);
}
}

void up(int u){
while(u / 2 && h[u / 2] > h[u]){
heap_swap(u / 2, u);
u /= 2;
}
}

int main(){
int n, m = 0;
cin >> n;
while(n--){
char op[5];
cin >> op;
int k, x;
if(!strcmp(op, "I")){
cin >> x;
cnt++;
m++;
ph[m] = cnt, hp[cnt] = m;
h[cnt] = x;
up(cnt);
}else if(!strcmp(op, "PM")){
cout << h[1] << endl;
}else if(!strcmp(op, "DM")){
heap_swap(1, cnt);
cnt--;
down(1);
}else if(!strcmp(op, "D")){
cin >> k;
k = ph[k];
heap_swap(k, cnt);
cnt --;
down(k), up(k);
}else{
cin >> k >> x;
k = ph[k];
h[k] = x;
down(k), up(k);
}
}
return 0;
}



mx
3个月前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
int n, m;
int h[N], cnt;

void down(int u){
int t = u;
if(u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
if(u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if(t != u){
swap(h[t], h[u]);
down(t);
}

}

int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> h[i];
cnt = n;
for(int i = n / 2; i; i--) down(i);
while(m --){
cout << h[1] << " ";
h[1] = h[cnt --];
down(1);
}

return 0;
}


mx
4个月前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> s[i];
for(int j = 0; j < s[i]; j++){
cin >> v[i][j] >> w[i][j];
}
}

//枚举数量
for(int i = 1; i <= n; i++){
//枚举体积
for(int j = m; j >= 0; j--){
//枚举物品数
for(int k = 0; k < s[i]; k++){
if(v[i][k] <= j){
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
}
}
}
}

cout << f[m] << endl;
return 0;

}