头像

Liyb




离线:1小时前


最近来访(40)
用户头像
77777777777
用户头像
陌丨落
用户头像
Hangya
用户头像
心は行きたくない
用户头像
抒怀
用户头像
s.y.
用户头像
NULL_
用户头像
用户头像
JcWing
用户头像
incra
用户头像
做题必ac
用户头像
清风不是峰
用户头像
雨中辰龙
用户头像
ljlhandsome
用户头像
................
用户头像
V1
用户头像
lsz_
用户头像
WangJY
用户头像
狂气电波
用户头像
凌乱之风

活动打卡代码 AcWing 734. 能量石

Liyb
14小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 10010;
int f[N];
int n,m;

struct Node
{
    int s,e,l;
    bool operator<(const Node &W)const 
    {
        return W.l * s < W.s * l;
    }
}q[N];

int main()
{
    int t;cin >> t;
    for(int k = 1; k <= t; k ++)
    {
        cin >> n;m = 0;
        for(int i = 1; i <= n; i ++)
        {
            cin >> q[i].s >> q[i].e >> q[i].l;
            m += q[i].s;
        }

        sort(q + 1, q + n + 1);
        //体积恰好为j
        memset(f, -0x3f, sizeof f);
        f[0] = 0;

        for(int i = 1; i <= n; i ++)a
        {
            for(int j = m; j >= q[i].s; j --)
            {
                int s = q[i].s,e = q[i].e,l = q[i].l;
                f[j] = max(f[j], f[j - s] + e - (j - s) * l);
            }
        }

        int res = 0;
        for(int i = 0; i <= m; i ++)
            res = max(res, f[i]);
        printf("Case #%d: %d\n", k,res);
    }
    return 0;
}


活动打卡代码 AcWing 4582. Yih的线段树

Liyb
18小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

bool check(int x)
{
    x --;
    if(x & 1)return false;

    bool meet_one = false;
    while(x)
    {
        if(x & 1)meet_one = true;
        else if(meet_one)return false;
        x >>= 1;
    }

    return true;
}

int main()
{
    int q;cin >> q;
    while(q --)
    {
        int x;cin >> x;
        if(check(x))cout << "Y" << endl;
        else cout << "N" << endl;
    }

    return 0;
}



Liyb
23小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 1010,mod = 1e9 + 7;
int g[N],f[N];

int main()
{
    int n,m;cin >> n >> m;
    g[0] = 1;

    for(int i = 1; i <= n; i ++)
    {
        int v,w;cin >> v >> w;
        int maxv = 0;
        for(int j = m; j >= v; j --)
        {
            LL cnt = 0;
            maxv = max(f[j], f[j - v] + w);
            if(maxv == f[j])cnt += g[j];
            if(maxv == f[j - v] + w)cnt += g[j - v];
            f[j] = maxv;
            g[j] = cnt % mod;
        }
    }

    int res = 0;
    for(int i = 0; i <= m; i ++)
        if(f[i] == f[m])res += g[i];

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



Liyb
23小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 1010,mod = 1e9 + 7;
int g[N],f[N];

int main()
{
    int n,m;cin >> n >> m;
    g[0] = 1;

    for(int i = 1; i <= n; i ++)
    {
        int v,w;cin >> v >> w;
        int maxv = 0;
        for(int j = m; j >= v; j --)
        {
            LL cnt = 0;
            maxv = max(f[j], f[j - v] + w);
            if(maxv == f[j])cnt += g[j];
            if(maxv == f[j - v] + w)cnt += g[j - v];
            f[j] = maxv;
            g[j] = cnt % mod;
        }
    }

    int res = 0;
    for(int i = 0; i <= m; i ++)
        if(f[i] == f[m])res += g[i];

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


活动打卡代码 AcWing 255. 第K小数

Liyb
2天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 1e5 + 10;
int a[N];
vector<int>nums;
int n,m;

struct Node
{
    int l,r;
    int cnt;
}tr[4 * N + N * 17];

int root[N],idx;

int build(int l,int r)
{
    int p = ++ idx;//建立一个新的点
    if(l == r)return p;//走到叶节点就不用继续开点了,直接返回
    int mid = l + r >> 1;//否则继续往下走
    tr[p].l = build(l, mid),tr[p].r = build(mid + 1, r);//记录左子树和右子树的编号
    return p;//返回每一棵子树的p更新上一层
}

int find(int x)
{
    //返回x在离散化数组中的位置
    return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}

//前一个根节点是u,要插入的区间范围,要插入的位置
int insert(int p, int l, int r, int x)
{
    int q = ++ idx;//创建一个新的点
    tr[q] = tr[p];//将上一个版本复制过来
    if(l == r)//叶节点
    {
        tr[q].cnt ++;//将这个位置的数量加1
        return q;//返回当前最新的根结点的编号
    }
    int mid = l + r >> 1;
    if(x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);//递归到左儿子
    else tr[q].r = insert(tr[p].r, mid + 1, r, x);
    //当前点的cnt等于左子树的cnt加上右子树的cnt
    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
    return q;
}

int query(int q, int p, int l, int r, int k)
{
    if(l == r)return r;
    //左子树的cnt等于当前版本左子树的cnt(1,r)减去先前版本左子树的cnt(1,l-1)
    //我们先考虑左子树[l,r]这一段的cnt
    int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
    int mid = l + r >> 1;//然后在[l,r]内递归查找到某个确定的值
    if(k <= cnt) return query(tr[q].l, tr[p].l, l, mid, k);
    else return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        nums.push_back(a[i]);
    }

    //有序离散化
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());

    //第一个版本的线段树
    root[0] = build(0, nums.size() - 1);

    //记录各个版本的线段树编号
    for(int i = 1; i <= n; i ++) 
        root[i] = insert(root[i - 1], 0, nums.size() - 1, find(a[i]));//在a[i]这个位置上加1

    while(m --)
    {
        int l,r,k;cin >> l >> r >> k;
        //返回的是离散化之前的值
        cout << nums[query(root[r], root[l - 1], 0, nums.size() - 1, k)] << endl;
    }
    return 0;
}


活动打卡代码 AcWing 256. 最大异或和

Liyb
3天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 6e5 + 10,M = N * 25;
int s[N];
int tr[M][2];
int root[N],idx;
int max_id[M];//记录trie树上每一个结点能到达的最大位置
int n,m;

//i表示当前插入的是第i个数,k是第几位,p是上一个版本的根节点号,q是当前结点的根节点号
void insert(int i,int k,int p,int q)
{
    if(k < 0)//走到结尾判断给他赋一个编号
    {
        max_id[q] = i;
        return;
    }
    else
    {
        int u = s[i] >> k & 1;//取出第k位
        //如果p不空的话,将不同方向的路径复制过来
        if(p)tr[q][u ^ 1] = tr[p][u ^ 1];

        tr[q][u] = ++ idx;
        //递归到儿子结点
        insert(i, k - 1, tr[p][u], tr[q][u]);
        //当前根节点下能走到的最大编号是他的所有儿子取一个max
        max_id[q] = max(max_id[tr[q][0]],max_id[tr[q][1]]);
        //最终我们的每个结点都会存储一个对应的最大值
    }
}

int query(int l,int r,int c)
{
    int p = root[r];//查询r版本的trie树
    for(int i = 23; i >= 0; i --)
    {
        int u = c >> i & 1;
        //如果当前结点子树的存在最大编号大于等于l的直接走下去
        if(max_id[tr[p][u ^ 1]] >= l)p = tr[p][u ^ 1];
        //否则退而求其次,走另一侧
        else p = tr[p][u];
    }
    //最后我们会走到一个满足条件的最优叶节点
    return c ^ s[max_id[p]];//我们的max_id存的是结点的编号在前缀和数组中的下标
}

int main()
{
    cin >> n >> m;
    //前缀和初始化root[0]
    max_id[0] = -1;
    root[0] = ++ idx;
    insert(0,23,0,root[0]);

    for(int i = 1; i <= n; i ++)
    {
        int x;cin >> x;
        s[i] = s[i - 1] ^ x;
        root[i] = ++ idx;
        insert(i, 23, root[i - 1],root[i]);
    }

    while (m -- )
    {
        char op[2];
        int l,r,x;
        scanf("%s",op);
        if(*op == 'A')
        {
            cin >> x;
            n ++;
            s[n] = s[n - 1] ^ x;
            root[n] = ++ idx;
            insert(n, 23, root[n - 1], root[n]);
        }
        else 
        {
            cin >> l >> r >> x;
            cout << query(l - 1, r - 1, s[n] ^ x) << endl;
        }
    }
    return 0;
}



Liyb
3天前

盲打
签到题

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
#define int long long
const int N = 1e7 + 10,mod = 1e11 + 3;
//typedef long long LL;

#define endl "\n"
typedef pair<int,int>PII;
#define x first
#define y second

char g[5][20] = 
{
    {'q','w','e','r','t','y','u','i','o','p'},
    {'a','s','d','f','g','h','j','k','l',' '},
    {'!','z','x','c','v','b','n','m',' ',' '}
};

void solve()
{
    string s;cin >> s;
    for(int i = 0; i < s.size(); i ++)
    {
        if(s[i] >= 'A' && s[i] <= 'Z')
        {
            s[i] += 'a' - 'A';
            cout << 3 << " " << 1 << " ";
            for(int j = 0; j < 3; j ++)
                for(int k = 0; k < 10; k ++)
                    if(s[i] == g[j][k]){
                cout << j + 1 << ' ' << k + 1 << endl;
                break;
            }
        }
        else 
        {
            for(int j = 0; j < 3; j ++)
                for(int k = 0; k < 10; k ++)
                    if(s[i] == g[j][k]){
                cout << j + 1 << ' ' << k + 1 << endl;
                break;
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int t;cin >> t;
    while(t --)
    {
        solve();
    }
    //solve();
    return 0;
}

数列求和
签到题

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
#define int long long
const int N = 1e7 + 10,mod = 1e11 + 3;
//typedef long long LL;

#define endl "\n"

void solve()
{
    int n;cin >> n;
    int sum = 0;
    if(n == 1)cout << 1 << endl;
    else if(n == 2)cout << 4 << endl;
    else 
    {
        int a = 1,b = 3,c;
        for(int i = 3; i <= n; i ++)
        {
            c = (a + b) % mod;
            sum = (sum + c) % mod;
            a = b,b = c;
        }

        printf("%lld\n",(sum + 4) % mod);
    }
}

signed main()
{
    //ios::sync_with_stdio(0), cin.tie(0);
//  int t;cin >> t;
//  while(t --)
//  {
//      solve();
//  }
    solve();
    return 0;
}

魔法数

设x为一合数,那么有x=a^k * b^p * ...,约数个数为(k+1)*(p+1)*...
我们想让这几个数的乘积为5,只有让x=a^4才能成立,其中a是质数
所以我们可以处理出1到1000之内的质数,然后暴力枚举看那些在l到r内
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
#define int long long

const int N = 1001,INF = 0x3f3f3f3f;
typedef long long LL;

#define endl "\n"
typedef pair<int,int>PII;
#define x first
#define y second
int primes[N],cnt;
bool st[N];

void solve()
{
    for(int i = 2; i < N; i ++)
    {
        if(!st[i])primes[cnt ++] = i;

        for(int j = 0; i * primes[j] < N; j ++)
        {
            st[i * primes[j]] = true;
            //i是pj的倍数了就退出
            if(i % primes[j] == 0)break;
        }
    }

    int T;cin >> T;
    while(T --)
    {
        int l,r;cin >> l >> r;

        int res = 0;
        for(int i = 0; i < cnt; i ++)
        {
            int t = primes[i] * primes[i] * primes[i] * primes[i];
            if(t >= l && t <= r)res ++;
        }

        cout << res << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
//  int t;cin >> t;
//  while(t --)
//  {
//      solve();
//  }
    solve();
    return 0;
}

取石子 ,但是作弊

Nim游戏是所有的异或和为0先手必输,我们只能从第一堆中移动,所以可以枚举移到那一堆
只要得到所有的异或和为0那么就可以使得后手必胜了
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
//#define int long long

const int N = 1010,INF = 0x3f3f3f3f;
typedef long long LL;

#define endl "\n"
typedef pair<int,int>PII;
#define x first
#define y second
int a[N];

void solve()
{
    int n;cin >> n;
    int sum = 0;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        sum ^= a[i];
    }

    int t = sum;
    for(int i = 0; i < a[1]; i ++)//枚举从第一堆中移多少
    {
        for(int j = 2; j <= n ; j ++)//枚举移动到那一堆中
        {
            sum = sum ^ a[1] ^ (a[1] - i) ^ a[j] ^ (a[j] + i);
            if(sum == 0){
                cout << i << endl;
                return;
            }
            sum = t;
        }
    }

    cout << -1 << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
//  int t;cin >> t;
//  while(t --)
//  {
//      solve();
//  }
    solve();
    return 0;
}

求四边形内一点

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
//#define int long long

const int N = 1010,INF = 0x3f3f3f3f;
typedef long long LL;

#define endl "\n"
//typedef pair<int,int>PII;
//#define x first
//#define y second

void solve()
{
    int x1,y1,x2,y2;
    double k,x;
    cin >> x1 >> x2 >> y1 >> y2;
    k = (y2 - y1) * 1.0 / (x2 - x1);
    x = (x1 * y1 + x2 * y2) / (k * (x1 + x2) + y1 + y2);
    printf("%lf %lf",x,k * x);
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    //  int t;cin >> t;
    //  while(t --)
    //  {
    //      solve();
    //  }
    solve();
    return 0;
}

字符串

大胆猜测考察的应该是求字符串的循环节,kmp的经典应用,只要能除尽就说明合法
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
//#define int long long

const int N = 2e6 + 10,INF = 0x3f3f3f3f;
typedef long long LL;

#define endl "\n"
//typedef pair<int,int>PII;
//#define x first
//#define y second
char p[N];
int ne[N];
void solve()
{
    int n;cin >> n;
    cin >> p + 1;

    for(int i = 2,j = 0; i <= n; i ++)
    {
        while(j && p[i] != p[j + 1])j = ne[j];
        if(p[j + 1] == p[i])j ++;
        ne[i] = j;
    }

    int k = n - ne[n];

    if(n % k)cout << 1 << endl;
    else cout << n / k << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    //  int t;cin >> t;
    //  while(t --)
    //  {
    //      solve();
    //  }
    solve();
    return 0;
}

想要更多的0

看到数据范围我们可以想到采用二分,而且数越大越更劣,具有单调性
问题的难点是如何统计出某一段区间内0的个数,采用枚举的方式一定会超时的

参考求1到n中1的个数

我们对0进行分类讨论:
考虑对于每一位分别计算有多少数字这一位上有多少个0,令第i位上的数字是now,比第i位更高的数字组成a(上界),比第i位低的数字组成b(上界)
假设当前位位i,高位上的数可以取的值为[1,a],低位上的数可以取得的值为[0,10^i)

1.如果当前位上不是0,那么高位上可以取[1,a],低位上可以取[0,10^i),(这样低位不受高位影响了)方案数为a*10^i
2.如果当前位上是0,
(1)如果高位上的数字取[1,a),则低位数字随便取.方案数为(a-1)*10^i
(2)如果高位上的数字为a,那么低位上只能取到b.方案数为1*(b+1)

如此我们就可以用log的时间求出方案数了
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
#define int long long

const int N = 20,INF = 0x3f3f3f3f;
typedef long long LL;

#define endl "\n"
//typedef pair<int,int>PII;
//#define x first
//#define y second
int f[N];
int n,k;

int quick(int x,int i)
{
    return f[i];
}

int ask(int x)
{
    int a = x / 10,b = 0,now = x % 10,res = 1;//将0加进去
    for(int i = 0; a; i ++)//枚举每位
    {
        if(now != 0)
            res = res + a * quick(10,i);
        else res = res + (a - 1) * quick(10, i) + b + 1;
        now = a % 10;
        a /= 10;
        b = b + x % 10 * quick(10,i);
        x /= 10;
    }

    return res;
}

bool check(int x)
{
    if(ask(n) - ask(x - 1) >= k)return true;
    return false;
}

void solve()
{
    cin >> n >> k;
    f[0] = 1;
    for(int i = 1; i <= 18; i ++)
        f[i] = f[i - 1] * 10;

    if(ask(n) < k)cout << -1 << endl;
    else 
    {
        int l = 0,r = n;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(check(mid))l = mid;
            else r = mid - 1;
        }
        cout << l << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    //  int t;cin >> t;
    //  while(t --)
    //  {
    //      solve();
    //  }
    solve();
    return 0;
}

树上祖先询问

性质:a是b的祖先的充分必要条件是a点的入栈时间早于b点且a点的出栈时间晚于b点

首先必要性是显然成立的
QQ截图20220816194008.png
充分性也是显然的,祖先一定也满足入栈时间早并且出栈时间晚于b,否则他们就没有在同一分支中
则有本条性质成立

因此我们只需要求出每个点的进栈时间和出栈时间,然后在b中查找是否有满足条件的存在即可
当然我们可以写lca的板子,但是要知道一个结论:求若干个点的最近公共祖先,我们只需要取这些点中dfs序最小的和最大的
两个点求lca即可
但是本题不是求最近的,只要是祖先就行,所以我们在判断一下b的祖先是否出现在a中的最近公共祖先中

证明
留个标记

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
//typedef long long LL;
#define int long long
const int N = 1e5 + 10,INF = 0x3f3f3f3f;

//typedef pair<int,int>PII;
//#define x first
//#define y second

int h[N],e[N],ne[N],idx;
int dfn[N],lfn[N],timestamp;

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

void dfs(int u)
{
    dfn[u] = ++ timestamp;//入栈时间
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        dfs(j);
    }
    lfn[u] = ++ timestamp;//出栈时间
}

void solve()
{
    int n,q;cin >> n >> q;

    memset(h,-1,sizeof h);

    for(int i = 2; i <= n; i ++)
    {
        int x;cin >> x;
        add(x,i);
    }

    dfs(1);

    while(q --)
    {
        int l,r;cin >> l >> r;
        //cout << l << ' ' << r << endl;
        int minv = INF,maxv = 0;
        for(int i = 0; i < l; i ++)
        {
            int a;cin >> a;
            minv = min(minv, dfn[a]);
            maxv = max(maxv, lfn[a]);
        }

        bool ok = false;
        for(int i = 0; i < r; i ++)
        {
            int a;cin >> a;
            if(dfn[a] < minv && lfn[a] > maxv)
                ok = true;
            //注意这里不能提前退出,我们要读完所有的输入,否则会出现错误
        }

        if(ok)cout << "yes" << endl;
        else cout << "no" << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
//  int t;cin >> t;
//  while(t --)
//  {
//      solve();
//  }
    solve();
    return 0;
}



Liyb
4天前

A Wonderful Permutation
只需要将前k小的数放到前k位即可

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
//#define int long long

const int N = 110,M = N * N,INF = 0x3f3f3f3f;
typedef long long LL;

#define endl "\n"
typedef pair<int,int>PII;
#define x first
#define y second
int a[N];

void solve()
{
    int n,k;cin >> n >> k;
    for(int i = 1; i <= n; i ++)cin >> a[i];
    //我们只需要将前k小的数放到前k位即可
    int res = 0;
    for(int i = 1; i <= k; i ++)
        if(a[i] > k)res ++;
    cout << res << endl;

}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int t;cin >> t;
    while(t --)
    {
        solve();
    }
    //solve();
    return 0;
}

B Woeful Permutation
从大到小考虑每个数,只要两个数互质乘积一定是最大的,详见代码

  #include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;

const int N = 1e5 + 10;
typedef long long LL;
//#define int long long
#define endl "\n"
typedef pair<int,int>PII;
#define x first
#define y second
//inline int read()
//{
//  int x = 0,f = 1; char ch = getchar();
//  while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}
//  while(ch >= '0' && ch <= '9')x = (x << 3) + (x << 1) + ch - '0',ch = getchar();
//  return x * f;
//}

//互质
void solve()
{
    int n;cin >> n;
    if(n & 1)
    {
        cout << 1 << " ";
        for(int i = 2; i <= n; i ++)
            cout << (i ^ 1) << " ";
    }

    else 
    {
        for(int i = 1; i <= n; i += 2)
            cout << i + 1 << " " << i << " ";
    }
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int t;cin >> t;
    while(t --)
    {
        solve();
    }
    return 0;
}

C Sort Zero

题意:给定你一个数组,定义一种操作为将所有值为x的数变成0,问最少操作多少次后数组变成
非严格单调递增的
思路:对于一组合法的解,我们要找到最终0和非零的分界线
一个数要变成零,那么他前面的所有的数也要全部变成零才合法,考虑到有重复,所以是其最后一个位置之前的所有数
我们想想看如果只找到最长的不减后缀也是不能满足条件的,因为重复的存在,我们在将前面元素置成0的同时可能会影响到
我们的后缀,所以我们要找到每个至少出现两次且不相邻的数出现的最后位置,这种数从前到所到达的所有位置一定都得是0
这是我们最长后缀的一个限制,在此条件下枚举最长后缀得到最大操作位置即可

核心:发现不相邻的多段之间为零,最长后缀
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
//#define int long long

const int N = 1e5 + 10,INF = 0x3f3f3f3f;
typedef long long LL;

#define endl "\n"
typedef pair<int,int>PII;
#define x first
#define y second
int a[N];

void solve()
{
    int n; cin >> n;
    for(int i = 1; i <= n; i ++)cin >> a[i];

    map<int,int>mp;//用来标记这个数是否出现过
    int maxv = 0;//用来找到最远的一个至少出现两次的不相邻的数的位置
    for(int i = 1; i <= n; i ++)
    {
        if(mp[a[i]] && a[i] != a[i - 1])
        {
            maxv = max(maxv, i);
            mp[a[i]] = 1;
        }
        else mp[a[i]] = 1;
    }
    //cout << maxv << endl;

    //在限制条件下找到最长后缀
    for(int i = n; i > maxv + 1; i --)//我们最多到maxv+1的位置
        if(a[i] < a[i - 1]) {
        maxv = i - 1;
        break;
    }

    //cout << maxv << endl;
    map<int,int>m;//判重
    int res = 0;
    //将前面不合法的置成0
    for(int i = 1; i <= maxv; i ++)
    {
        if(!m[a[i]])res ++;
        m[a[i]] = 1;
    }

    cout << res << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int t;cin >> t;
    while(t --)
    {
        solve();
    }
    //solve();
    return 0;
}

D Empty Graph

题意:给定一个n个结点的无向图,定义边权为数组种l->r一段的最小值
我们要求出图的直径,为某两个点之间最短路的最大值
贪心:
两点之间如果是直接到达,一定是最近限制越小取的值越大。
两点之间的最近距离一共有两种情况:
1.直达 a[i]和a[i+1]的最小值
2.经中转点到最小值点 2*minv

我们可以用操作尽可能使得最小值最大,所以可以用k-1次操作使得最小的k-1个数变成正无穷
最后一次操作有两种选择:
(1)使第k小的数变成正无穷
(2)使得a[i]和a[i+1]比较中取到最大的那一个

将这两种操作都做一遍取一个最大值
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
const int N = 2e5 + 10,INF = 1e9;
typedef long long LL;
#define int long long
typedef pair<int,int>PII;
#define x first
#define y second
PII q[N];
int a[N],b[N];

bool cmp(PII a, PII b)
{
    return a.second < b.second;
}

void solve()
{
    int n,k;cin >> n >> k;
    for(int i = 0; i < n; i ++)cin >> a[i],q[i] = {i, a[i]};

    sort(q, q + n, cmp);

    //将前k小的数变成正无穷
    for(int i = 0; i < k - 1 ; i ++)
    {
        q[i].second = INF;
        a[q[i].first] = INF;
    }

    for(int i = 0; i < n; i ++)b[i] = a[i];//两种情况

    int t = -INF;
    a[q[k - 1].first] = INF;//将前k小的全部置成无穷的情况
    for(int i = 0; i < n - 1; i ++)
        t = max(t, min(a[i], a[i + 1]));

    int res1 = 0,res2 = 0;
    sort(a, a + n);
    res1 = min(a[0] * 2, t);//现在a数组中最小的数和t取一个最小是我们的距离
    sort(b, b + n);
    //最小数的二倍和最大的数取一个最小
    res2 = min(b[0] * 2, b[n - 1]);//剩一种操作,一定能取到最大的数

    //两种情况取一个最大就是直径
    cout << max(res1,res2) << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int t;cin >> t;
    while(t --)
    {
        solve();
    }
    return 0;
}


活动打卡代码 AcWing 4507. 子数组异或和

Liyb
5天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
#define int long long

const int N = 3e5 + 10;
int a[N],b[N];
int n;
signed main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)cin >> a[i];
    // for(int i = 1; i <= n; i ++)
    // {
    //     cin >> a[i];
    //     b[i] = b[i - 1] ^ a[i];
    // }

    // int res = 0;
    // for(int len = 2; len <= n; len += 2)
    // {
    //     for(int l = 1; l + len - 1 <= n; l ++)
    //     {
    //         int r = l + len - 1;
    //         cout << b[l - 1] << ' ' << b[r] << ' ' << endl;
    //         if(b[l - 1] == b[r])res ++;
    //     }
    // }

    // cout << res << endl;

    //考虑优化:固定一个点r,那么我们的条件就变为了查询前面有多少个数的前缀b等于b[r](哈希表维护)
    //且与r奇偶性不同,所以开两个哈希表
    unordered_map<int,int>hash[2];//0存偶数,1存奇数
    int res = 0,sum = 0;
    hash[0][sum] ++;//初始化,我们要找的是l-1,所以0也要算
    for(int r = 1; r <= n; r ++)//从前向后枚举我们的r
    {
        sum ^= a[r];
        res += hash[r & 1][sum];
        hash[r & 1][sum] ++;//合法的答案
    }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 1749. 阻挡广告牌 II

Liyb
5天前
//我们将每个牌子看成是由若干个小正方形组成的,我们将所有第一个组成的置成true
//所有第二个组成的置成false,然后找到四个最值即可得解
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 2010,B = N / 2;
bool st[N][N];
int main()
{
    int a,b,c,d;cin >> a >> b >> c >> d;
    a += B,b += B,c += B,d += B;
    for(int i = a; i < c; i ++)//枚举格子的横坐标
        for(int j = b; j < d; j ++)
            st[i][j] = true;

    cin >> a >> b >> c >> d;
    a += B,b += B,c += B,d += B;
    for(int i = a; i < c ;i ++)
        for(int j = b;j < d; j ++)
            st[i][j] = false;

    //分别维护横坐标最小值,纵坐标最小值,横坐标最大值,纵坐标最大值
    a = N,c = N,b = 0,d = 0;
    for(int i = 1; i < N; i ++)
        for(int j = 1; j < N; j ++)
            if(st[i][j])
            {
                a = min(a, i),c = min(c, j);
                b = max(b, i),d = max(d, j);
            }

    int w = max(0, b - a + 1);
    int h = max(0, d - c + 1);
    cout << w * h << endl;
    return 0;
}