头像

Froggy

$Current$ $Online$ $User$




在线 


最近来访(187)
用户头像
归伤中
用户头像
wbs411
用户头像
周树人之怒
用户头像
IEE_
用户头像
周星星
用户头像
Alan_Zhao
用户头像
Irana
用户头像
Lwejor
用户头像
Bluegleam
用户头像
A-SOUL_Diana
用户头像
染指流年_1
用户头像
zhaojunhan2010
用户头像
济南屁王
用户头像
ymh
用户头像
华悦泽
用户头像
周赛二题必超时
用户头像
song666
用户头像
Nan97
用户头像
灵茶山艾府
用户头像
小青蛙

活动打卡代码 AcWing 795. 前缀和

Froggy
1小时前
#include <iostream>
#include <cstring>
#include <algorithm>

#pragma GCC optimize (2)

using namespace std;

const int N = 1e5 + 10;

int n, m, x, s[N];

int main()
{
    scanf ("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf ("%d", &x), s[i] = s[i - 1] + x;
    while (m--)
    {
        int l, r;
        scanf ("%d %d", &l, &r);
        printf ("%d\n",s[r] - s[l - 1]);
    }
    return 0;
}



Froggy
2小时前
#include <stdio.h>

#define lowbit(n) n & n - 1

using namespace std;

int n, x;

int main()
{
    scanf ("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf ("%d", &x);
        int ans = 0;
        while (x) x = lowbit (x), ++ans;
        printf ("%d ", ans);
    }
    return 0;
}


活动打卡代码 AcWing 826. 单链表

Froggy
2小时前
#include <iostream>
#include <cstring>
#include <algorithm>

#pragma GCC optimize (2, 3)

using namespace std;

const int N = 1e5 + 10;

int head, e[N], ne[N], idx;

inline void init ()
{
    head = -1, idx = 0;
}

inline void add_to_head (int x)
{
    e[idx] = x, ne[idx] = head, head = idx++;
}

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

inline void remove (int k)
{
    ne[k] = ne[ne[k]];
}

int main()
{
    int n;
    scanf ("%d", &n);

    init();

    while (n--)
    {
        int k, x;
        char opt;
        cin >> opt;

        if (opt == 'I')
        {
            scanf ("%d %d", &k, &x);
            add (k - 1, x);
        }
        if (opt == 'H')
        {
            scanf ("%d", &x);
            add_to_head (x);
        }
        if (opt == 'D')
        {
            scanf ("%d", &k);
            if (!k) head = ne[head];
            else remove (k - 1);
        }
    }

    for (int i = head; i != -1; i = ne[i]) printf ("%d ", e[i]);
    return 0;
}


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

Froggy
2小时前
#include <iostream>
#include <cstring>
#include <algorithm>

#pragma GCC optimize (2, 3)

using namespace std;

const int N = 2e4 + 10;

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

inline 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];
}

inline 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];
}

int main()
{
    int n;
    scanf ("%d", &n);

    while (n--)
    {
        char opt[2], str[N];
        scanf ("%s%s", opt, str);

        if (*opt == 'I') insert (str);
        else printf ("%d\n", query (str));
    }
    return 0;
}


活动打卡代码 AcWing 787. 归并排序

Froggy
2小时前
#include <iostream>
#include <cstring>
#include <algorithm>

#pragma GCC optimize (2, 3)

using namespace std;

const int N = 1e5 + 10;

int n, a[N], b[N];

inline void merge_sort (int m[], int l, int r)
{
    if (l >= r) return ;
    int mid = l + r >> 1;
    merge_sort (m, l, mid), merge_sort (m, mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
    {
        if (m[i] <= m[j]) b[k++] = a[i++];
        else b[k++] = a[j++];
    }
    while (i <= mid) b[k++] = a[i++];
    while (j <= r) b[k++] = a[j++];
    for (i = l, j = 0; i <= r; ++i, ++j) m[i] = b[j];
}

int main()
{
    scanf ("%d", &n);
    for (int i = 1; i <= n; ++i) scanf ("%d", &a[i]);
    merge_sort (a, 1, n);
    for (int i = 1; i <= n; ++i) printf ("%d ", a[i]);
    return 0;
}


活动打卡代码 AcWing 786. 第k个数

Froggy
2小时前
#include <iostream>
#include <cstring>
#include <algorithm>

#pragma GCC optimize (2)

using namespace std;

const int N = 1e5 + 10;

int n, k, q[N];

inline void read (int &x) { x = 0; bool f = 0; char ch = getchar(); while (ch < '0' || ch > '9') f |= ch == '-', ch = getchar(); while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar(); x = f ? ~x + 1 : x; }
inline void write (int x) { static char c[11]; unsigned p = 0; if (x < 0) putchar ('-'), x = ~x + 1; if (!x) { putchar ('0'); return ; } while (x) c[++p] = x % 10 ^ 48, x /= 10; while (p) putchar (c[p]), --p; }
template <class T, class... U> inline void read (T &x, U &...t) { read (x), read (t...); }
template <class T, class... U> inline void write (T x, U ...t) { write (x), write (t...); }

signed main()
{
    read (n, k);
    for (int i = 1; i <= n; ++i) read (q[i]);
    nth_element (q + 1, q + k, q + 1 + n);
    write (q[k]);
    return 0;
}


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

Froggy
2小时前
#include <iostream>
#include <cstring>
#include <algorithm>

#pragma GCC optimize (2)
#pragma GCC optimize (3)

using namespace std;

typedef pair <int, int> PII;

const int N = 1e5 + 10;

int n, l, r;
vector <PII> segs;

inline void merge (vector <PII> &segs)
{
    sort (segs.begin(),segs.end());

    vector <PII> res;
    int st = -1e9, ed = -1e9;

    for (auto seg : segs)
        if (ed < seg.first) 
        {
            if (st != -1e9) res.push_back ({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max (ed, seg.second);
    if (st != -N) res.push_back ({st, ed});

    segs = res;
}

int main()
{
    scanf ("%d", &n);
    while (n--)
    {
        scanf ("%d %d", &l, &r);
        segs.push_back ({l, r});
    }
    merge (segs);
    printf ("%d", segs.size());
    return 0;
}


活动打卡代码 AcWing 1884. COW

Froggy
22小时前
#include <iostream>

using namespace std;

int main()
{
    long long n, a, b, c; string str;
    cin >> n >> str;
    a = b = c = 0;
    for (auto &x : str)
    {
        if (x == 'C') ++a;
        if (x == 'O') b += a;
        if (x == 'W') c += b;
    }
    cout << c;
    return 0;
}



Froggy
8天前

纯纯的暴搜 + unordered_map
请大佬们慢慢食用

#include <cstdio>
#include <unordered_map>

#pragma GCC optimize (2)

using namespace std;

const int N = 1e2 + 10;

int n;
long long a[N], ans[N];
unordered_map <long long, int> h;

inline void read (register long long &x) { x = 0; register bool f = 0; register char ch = getchar(); while (ch < '0' || ch > '9') f |= ch == '-', ch = getchar(); while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar(); x = f ? ~x + 1 : x; }
inline void write (register long long x) { static char c[21]; register unsigned p = 0; if (x < 0) putchar ('-'), x = ~x + 1; if (!x) { putchar ('0'); return ; } while (x) c[++p] = x % 10 ^ 48, x /= 10; while (p) putchar (c[p]), --p; }
template <class T, class... U> inline void read (register T &x, register U &...t) { read (x), read (t...); }
template <class T, class... U> inline void write (register T x, register U ...t) { write (x), write (t...); }

inline void dfs (long long x, int dep)
{
    ans[++ans[0]] = x, --h[x];
    if (dep == n)
    {
        for (int i = 1; i <= n; ++i) write (ans[i]), putchar (' ');
        exit (0);
    }
    if (h[x << 1]) dfs (x << 1, dep + 1), ++h[x << 1], --ans[0];
    if (x % 3 == 0 && h[x / 3]) dfs (x / 3, dep + 1), ++h[x / 3], --ans[0];
}

int main()
{
    scanf ("%d", &n);
    for (int i = 1; i <= n; ++i) read (a[i]), ++h[a[i]];
    for (int i = 1; i <= n; ++i) ans[0] = 0, dfs (a[i], 1), ++h[a[i]];
    return 0;
}


神奇,只用了12ms




Froggy
8天前
inline void read (register int &x) { x = 0; register bool f = 0; register char ch = getchar(); while (ch < '0' || ch > '9') f |= ch == '-', ch = getchar(); while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar(); x = f ? ~x + 1 : x; }
inline void write (register int x) { static char c[11]; register unsigned p = 0; if (x < 0) putchar ('-'), x = ~x + 1; if (!x) { putchar ('0'); return ; } while (x) c[++p] = x % 10 ^ 48, x /= 10; while (p) putchar (c[p]), --p; }
template <class T, class... U> inline void read (register T &x, register U &...t) { read (x), read (t...); }
template <class T, class... U> inline void write (register T x, register U ...t) { write (x), write (t...); }