头像

Kylin




离线:4天前


活动打卡代码 AcWing 143. 最大异或对

Kylin
10天前
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn = 1e5+10;
int son[31*maxn][2], a[maxn];
int idx = 0, n, res = -1, p;

void insert(int x)
{
    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)
{
    p = 0;
    int res = 0;
    for(int i = 30; i >= 0; i --)
    {
        int u = x >> i & 1;
        if(son[p][!u])
        {
            p = son[p][!u];
            res = res*2 + !u;
        } 
        else {
          p = son[p][u];
          res = res*2 + u;
        }
    }
    return res;

}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
        scanf("%d", a+i);
    for(int i = 0; i < n; i ++)
    {
        insert(a[i]);
        int t = query(a[i]);
        res = max(res, a[i] ^ t);
    }
    printf("%d", res);

    return 0;
}


活动打卡代码 AcWing 835. Trie字符串统计

Kylin
12天前
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int maxn = 1e5+10;
int idx = 0, n;
int a[maxn][26], cnt[maxn];
char x;
char s[maxn];

void insert(char s[])
{
    int p = 0;
    int len = strlen(s);
    for(int i = 0; i < len; i ++)
    {
        int c = s[i] - 'a';
        if(!a[p][c]) a[p][c] = ++idx;
        p = a[p][c];
    }
    cnt[p] ++;
}

int query(char s[])
{
    int p = 0;
    int len = strlen(s);
    for(int i = 0; i < len; i ++)
    {
        int c = s[i] - 'a';
        if(!a[p][c]) return 0;
        p = a[p][c];
    }
    return cnt[p];
}

int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        string x;
        cin >> x;
        if(x == "I")
        {
            scanf("%s", s);
            insert(s);
        }
        else {
            scanf("%s", s);
            printf("%d\n", query(s));
        }
    }
    system("pause");
    return 0;
}


活动打卡代码 AcWing 827. 双链表

Kylin
27天前
#include<iostream>
using namespace std;
const int maxn = 1e5+10;
int e[maxn], l[maxn], r[maxn];
int idx;

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

void ladd(int x)
{
    e[idx] = x;
    r[idx] = r[0];
    l[idx] = 0;
    l[r[idx]] = idx;
    r[0] = idx;
    idx++;
}

void radd(int x)
{
    e[idx] = x;
    r[idx] = 1;
    l[idx] = l[1];
    r[l[idx]] = idx;
    l[1] = idx;
    idx++;
}

void rmv(int k)
{
    k++;
    r[l[k]] = r[k];
    l[r[k]] = l[k];

}

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

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

int main()
{
    int t;
    cin >> t;
    init();
    while(t--)
    {
        int k, x;
        string c;
        cin >> c;
        if(c == "L")
        {
            cin >> x;
            ladd(x);
        }
        if(c == "R")
        {
            cin >> x;
            radd(x);
        }
        if(c == "D")
        {
            cin >> k;
            rmv(k);
        }
        if(c == "IL")
        {
            cin >> k >> x;
            kladd(k, x);
        }
        if(c == "IR")
        {
            cin >> k >> x;
            kradd(k, x);
        }
    }
    for(int i = r[0]; i != 1; i = r[i])
        cout << e[i] << " ";
    system("pause");
    return 0;

}


活动打卡代码 AcWing 803. 区间合并

Kylin
1个月前
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn = 1e5+10;
struct node{
    int f, e;
}a[maxn];
int endd, cnt = 1, n, ans = 1;

int cmp(node x, node y)
{
    return x.f < y.f;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
        scanf("%d%d", &a[i].f, &a[i].e);
    sort(a+1, a+n+1, cmp);
    endd = a[1].e;
    for(int i = 2; i <= n; i ++)
    {
        if(endd < a[i].f)
        {
            endd = a[i].e;
            ans ++;
        }
        else {
            if(endd < a[i].e) endd = a[i].e;
        }
    }
    printf("%d", ans);
  //  system("pause");
    return 0;
}


活动打卡代码 AcWing 802. 区间和

Kylin
2个月前

’[//]: # (打卡模板,上面预览按钮可以展示预览效果 ^^)

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
const int maxn = 300010;
int a[maxn], s[maxn];
int n, m;
vector<int> alls;
typedef pair<int, int> pi;
vector<pi> add, que; 

int find(int x)
{
    int l = 0, r = alls.size()-1;
    while(l < r)
    {
        int mid = l+r >> 1;
        if(alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r+1;
}


int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++)
    {
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});
        alls.push_back(x);
    }
    for(int i = 0; i < m; i ++)
    {
        int l, r;
        cin >> l >> r;
        que.push_back({l, r});
        alls.push_back(l);
        alls.push_back(r);
    }
    // 去重 
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    // 加数 
    for(auto item : add)
    {
        int x = find(item.first);
        a[x] += item.second;
    }
    //前缀和处理
    s[0] = 0;
    for(int i = 1; i <= alls.size(); i ++)
        s[i] = s[i-1] + a[i];
    //查询
    for(auto item : que)
    {
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l-1] << endl;
    } 
    return 0;
}



活动打卡代码 AcWing 2816. 判断子序列

Kylin
3个月前
#include<iostream>
using namespace std;
const int maxn = 1e5 + 10;
int n, m, num = 0;
int a[maxn], b[maxn];
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i ++)
        scanf("%d", &a[i]);
    for(int i = 0; i < m; i ++)
        scanf("%d", &b[i]);
    int i, j;
    i = j = 0;
    while(i < n && j < m)
    {
        if(a[i] == b[j])
        {
            i++, j++;
            num++; 
        }
        else j++;
    }
    if(num == n) printf("Yes");
    else printf("No");
    return 0;
}



Kylin
3个月前
#include<iostream>
using namespace std;
const int maxn = 1e5 + 10; 
int a[maxn], b[maxn];
int n, m, x;
int main()
{
    cin >> n >> m >> x;
    for(int i = 0; i < n; i ++) 
        cin >> a[i];
    for(int i = 0; i < m; i ++)
        cin >> b[i];
    for(int l = 0, r = m-1; l < n; l ++)
    {
        while(r >= 0 && a[l] + b[r] > x) r--;
        if(a[l] + b[r] == x) {
            cout << l << " " << r; break;
        }
    }
    return 0;

} 



Kylin
3个月前

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
const int maxn = 1e5+10;
int n, ans;
int b[maxn], a[maxn];
int main()
{
cin >> n;
for(int i = 0; i < n; i )
cin >> a[i];
int i = 0, j = 1;
b[a[i]] = 1;
while(j < n)
{
while(!b[a[j]]) b[a[j
]] = 1;
ans = max(ans, j-i);
while(b[a[j]])
{
if(a[i] == a[j])
{
b[a[j]] = 0;
i;
}
else b[a[i
]] = 0;
}
}
cout << ans;
return 0;
}




Kylin
4个月前

include[HTML_REMOVED]

using namespace std;
const int maxn = 1e5+10;
int a[maxn], n, ans;
int main()
{
cin >> n;
for(int i = 1; i <= n; i )
cin >> a[i];
for(int i = 1; i <= n; i
)
{
ans = 0;
while(a[i] != 0)
{
if(a[i] & 1) ans++;
a[i] >>= 1;
}
cout << ans << ” “;

}
return 0;

}



活动打卡代码 AcWing 798. 差分矩阵

Kylin
4个月前

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
const int maxn = 1e3 + 10;
int q, n, m, x1, x2, y1, y2, c;
int a[maxn][maxn], b[maxn][maxn];

void insert(int x1, int y1, int x2, int y2, int c)
{
b[x1][y1] += c;
b[x1][y2+1] -= c;
b[x2+1][y1] -= c;
b[x2+1][y2+1] += c;
}

int main()
{
scanf(“%d%d%d”, &n, &m, &q);
for(int i = 1; i <= n; i )
for(int j = 1; j <= m; j
)
scanf(“%d”, &a[i][j]);
for(int i = 1; i <= n; i )
for(int j = 1; j <= m; j
)
insert(i, j, i, j, a[i][j]);
while(q–)
{
scanf(“%d%d%d%d%d”, &x1, &y1, &x2, &y2, &c);
insert(x1, y1, x2, y2, c);
}
for(int i = 1; i <= n; i )
for(int j = 1; j <= m; j
)
a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + b[i][j];
for(int i = 1; i <= n; i )
{
for(int j = 1; j <= m; j
)
printf(“%d “, a[i][j]);
printf(“\n”);
}
return 0;

}