codeforces-1140 (div2)

2024-03-18 19:38:16

 

A.维护一个前缀最大值，不断跳即可

codeforces-1140 (div2)
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x);  
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double eps = 1e-9;
const int maxn = 1e4 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,K;
int a[maxn];
int Max[maxn];
int main(){
    Sca(N);
    for(int i = 1; i <= N ; i ++){
        Sca(a[i]);
        a[i] = max(a[i],a[i - 1]);
    }
    int cnt = 0;
    int now = 0;
    while(now < N){
        cnt++;
        now++;
        while(now != a[now]) now = a[now];
    }
    Pri(cnt);
    return 0;
}
A

 

B.从左边开始删除一直删到>或者从右边开始删除一直删到<，两种方案取最小值。

codeforces-1140 (div2)
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x);  
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double eps = 1e-9;
const int maxn = 110;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,K;
char str[maxn];
int main(){
    int T = read();
    while(T--){
        Sca(N);
        scanf("%s",str + 1);
        int ans = N - 1;
        for(int i = 1; i <= N ; i ++){
            if(str[i] == '>'){
                ans = min(ans,i - 1);
                break;
            }
        }
        for(int i = N ; i >= 1; i --){
            if(str[i] == '<'){
                ans = min(ans,N - i);
                break;
            }
        }
        Pri(ans);
    }
    return 0;
}
B

 

C.按照beauty值从大到小排序，维护一个前缀和（最多K个length）,小根堆维护一下每次要踢出哪个最小lenght的弟弟

codeforces-1140 (div2)
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x);  
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double eps = 1e-9;
const int maxn = 3e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,K;
PLL P[maxn];
bool cmp(PLL a,PLL b){
    return a.se > b.se;
}
int main(){
    Sca2(N,K);
    for(int i = 1; i <= N; i ++){
        scanf("%lld%lld",&P[i].fi,&P[i].se);
    }
    sort(P + 1,P + 1 + N,cmp);
    priority_queue<LL,vector<LL>,greater<LL>>Q;
    LL sum = 0;
    LL ans = 0;
    for(int i = 1; i <= N ; i ++){
        ans = max(ans,(sum + P[i].fi) * P[i].se);
        Q.push(P[i].fi); sum += P[i].fi;
        if(Q.size() >= K){
            sum -= Q.top();
            Q.pop();
        } 
    }
    Prl(ans);
    return 0;
}
C

 

D.发现1,2,3| 1,3,4| 1,4,5 .. |1,n - 1,n为最优解。

codeforces-1140 (div2)
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x);  
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double eps = 1e-9;
const int maxn = 3e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,K;

int main(){
    Sca(N);
    LL sum = 0;
    for(int i = 2; i < N ; i ++){
        sum += i * (i + 1);
    }
    Prl(sum);
    return 0;
}
D

 

E*

1.发现不存在奇长度的回文串只需要满足不存在长度3的回文串即可，长度为5的回文串包含了长度3的回文串。

2.也就是说，要满足所有的str[x] != str[x + 2],发现奇偶位置上的数字其实互不干扰，那可以把序列分成两个序列来做。

3.得到dp方程,dp[i][j]表示到了i这个位置，且这个位置上的数字为j的时候，满足条件序列的总数，状态转移方程为dp[i][j] = ∑dp[i - 1][p] (1 <= p <= K && p != j)

4.当然这个时间复杂度和空间复杂度双双nk的算法是行不通的，我们发现对于i相同的dp[i][j],只会有两种不同的值，并且是其中k - 1个值相同以及另一个值鹤立鸡群的情况（当然也有可能都是鸡完全相同）

5.考虑标注特殊的点位置和特殊的点值以及k - 1个其他的点值，即可压缩复杂度为O(n)

codeforces-1140 (div2)
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x);  
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double eps = 1e-9;
const int maxn = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 998244353; 
int N,M,K;
LL a[maxn],b[maxn];
LL solve(LL *x,int n){
    LL big,small,pos;
    if(x[1] == -1){
        big = 1; small = 1; pos = 1;
    }else{
        big = 0; small = 1; pos = x[1];
    } 
    for(int i = 2; i <= n ; i ++){
        if(x[i] == -1){
            LL s = big * (K - 1),b = big * (K - 2)  + small;
            small = s % mod; big = b % mod;
        }else{
            if(pos == x[i]){
                small = big * (K - 1) % mod;
                big = 0;
            }else{
                small = big * (K - 2) + small; small %= mod;
                pos = x[i];
                big = 0;
            }
        }
    }
    return (small + big * (K - 1)) % mod;
}
int main(){
    Sca2(N,K);
    int cnt1 = 0,cnt2 = 0;
    for(int i = 1; i <= N ; i ++){
        if(i & 1) a[++cnt1] = read();
        else b[++cnt2] = read();
    }
    Prl(solve(a,cnt1) * solve(b,cnt2) % mod);
    return 0;
}
E

 

F*

1.考虑将两个集合用一个二维的表来表示，添加就是将i行j列合并，最终答案是每个联通块的行数 * 列数。

2.考虑到用并查集,size1[maxn],size2[maxn],分别表示这个集合里面行列的数量。

3.问题在于删除，并查集是不存在在线直接删除这种黑科技的，但是我们可以用离线的方式，将并查集的存在生命周期放到线段树上，然后dfs整颗线段树进行优化。

这个操作在BZOJ2049里遇到过了，当时还写了blog https://www.cnblogs.com/Hugh-Locke/p/10367480.html

结果这次还是翻皮水了（雾）

codeforces-1140 (div2)
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x);  
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double eps = 1e-9;
const int maxn = 6e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,K;
map<PII,int>P;
//并查集 
int fa[maxn];
LL size1[maxn],size2[maxn];
int dep[maxn];
void init(){
    for(int i = 0; i < maxn; i ++){
        fa[i] = i;
        if(i > 3e5) size2[i] = 1;
        else size1[i] = 1;
        dep[i] = 0;
    } 
}
//线段树
struct Edge{
    PII to;
    int next;
}edge[maxn * 20];
int tot;
void add(int& t,PII w){
    edge[tot].to = w;
    edge[tot].next = t;
    t = tot++;
}
struct Tree{
    int l,r;
    int head;
}tree[maxn << 2]; 
void Build(int t,int l,int r){
    tree[t].l = l; tree[t].r = r;
    tree[t].head = -1;
    if(l == r) return;
    int m = l + r >> 1;
    Build(t << 1,l,m); Build(t << 1 | 1,m + 1,r);
}
void add(int t,int l,int r,PII w){
    if(l <= tree[t].l && tree[t].r <= r){
        add(tree[t].head,w);
        return;
    }
    int m = tree[t].l + tree[t].r >> 1;
    if(r <= m) add(t << 1,l,r,w);
    else if(l > m) add(t << 1 | 1,l,r,w);
    else{
        add(t << 1,l,m,w); add(t << 1 | 1,m + 1,r,w);
    }
}
int Stack[maxn],top;
int find(int x){
    while(fa[x] != x) x = fa[x];
    return x;
}
LL ans; 
void rewind(int t){
    while(top > t){
         int x = Stack[--top];
         dep[fa[x]] -= dep[x] + 1;
         ans -= 1LL * size1[fa[x]] * size2[fa[x]];
         size1[fa[x]] -= size1[x];
         size2[fa[x]] -= size2[x];
         ans += 1LL * size1[fa[x]] * size2[fa[x]];
         ans += 1LL * size1[x] * size2[x];
         fa[x] = x;
    }
}
void dfs(int t){
    int now = top;
    for(int i = tree[t].head; ~i ; i = edge[i].next){
        PII t = edge[i].to;
        t.fi = find(t.fi); t.se = find(t.se);
        if(t.fi == t.se) continue;
        if(dep[t.fi] > dep[t.se]) swap(t.fi,t.se);
        Stack[top++] = t.fi;
        fa[t.fi] = t.se;
        dep[t.se] += dep[t.fi] + 1;
        ans -= 1LL * size1[t.fi] * size2[t.fi]; ans -= size1[t.se] * size2[t.se];
        size1[t.se] += size1[t.fi]; size2[t.se] += size2[t.fi];
        ans += 1LL * size1[t.se] * size2[t.se];
    }
    if(tree[t].l == tree[t].r){
        printf("%lld ",ans);
    }else{
        dfs(t << 1); 
        dfs(t << 1 | 1);
    }
    rewind(now);
}
int main(){
    Sca(N); init();
    Build(1,1,N);
    for(int i = 1; i <= N; i ++){
        PII p; p.fi = read(),p.se = read() + 3e5;
        if(P[p]){
            add(1,P[p],i - 1,p);
            P[p] = 0;
        }else P[p] = i;
    }
    for(map<PII,int>::iterator it = P.begin(); it != P.end(); it++)  if((*it).se) add(1,(*it).se,N,(*it).fi);
    dfs(1);
    return 0;
}
F

 

上一篇：Luogu 1140 相似基因


下一篇：web应用系统开发，CSS内联样式的使用