2020EC-final

时间：2022-12-16 02:00:00 500n扭距传感器

传送门

文章目录

B - Rectangle Flip 2
- 题意：
- 思路：
A - Namomo Subsequence
- 题意：
- 思路：
D - City Brain
- 题意:
- 思路:

B - Rectangle Flip 2

题意：

给你一个 $n ? m$ 下一步，矩阵 $n ? m$ 每秒钟都会消失一个格子，问矩阵中有多少个矩形。

$n,m\le 500$

思路：

先说复杂性 $n^4$ 然而，运行不满意的算法维护了每个删除点的上下界，如左右位置，如上界 $x$ 下界 $y$ ，当前点是 $(d x, d y)$ ，答案是 $y + 1) * (x - d x + 1) ，看似 n^{4} ，实际 500 m s 就跑完了。$

还有一个稳定 $n^3$ 用单调栈跑的并没有看懂代码是怎么写的，就先咕咕了。

//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
//#pragma GCC optimize(2)
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std;

//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); }
//void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); }
//void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;

const int N=510,mod=1e9+7,INF=0x3f3f3f3f;
const double eps=1e-6;

int n,m;
int D[N][N],U[N][N];
int st[N][N];

int main()
{ 
        
// ios::sync_with_stdio(false);
// cin.tie(0);

    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) { 
        
        for(int j=1;j<=m;j++){ 
        
            D[i][j]=n+1;
            U[i][j]=0;
        }
    }
    LL ans=1ll*n*(n+1)*m*(m+1)/4;
    for(int i=1;i<=n*m;i++) { 
        
        int x,y; scanf("%d%d",&x,&y);
        for(int l=y,u1=0,d1=n+1;l>=1&&!st[x][l];l--) { 
        
            u1=max(u1,U[x][l]+1);
            d1=min(d1,D[x][l]-1);
            for(int r=y,u2=u1,d2=d1;r<=m&&!st[x][r];r++) { 
        
                u2=max(u2,U[x][r]+1);
                d2=min(d2,D[x][r]-1);
                ans-=1ll*(x-u2+1)*(d2-x+1);
            }
        }
        for(int j=x;j<=n;j++) U[j][y]=max(U[j][y],x);
        for(int j=x;j>=1;j--) D[j][y]=min(D[j][y],x);
        printf("%lld\n",ans);
        st[x][y]=1;
    }


















	return 0;
}
/* */

A - Namomo Subsequence

题意：

给你一个串 $s$ ，问你有多少个长度为 $6$ 且形如 $A B C D C D$ 的子序列。

$6\le |s|\le 1e6$ ,字符集大小 $62$

思路：

考虑到字符集和长度都很长，所以考虑 $62 n$ 的算法， $62 * 62 n$ 的肯定过不去了。

直接维护肯定是不好弄的，可以发现能维护出来前两个位置就不错了，所以我们考虑将其切割，分开来看。

将其分成 $A B$ 和 $C D C D$ 两个部分来看，枚举 $C$ 的位置，那么答案就是两边的方案数乘起来。

对于 $C D C D$ ，我们比较容易维护出来，定义 $f [i] [j] [k]$ 代表类型为 $i$ 的 $C = j, D = k$ 的个数，其中 $i = 2$ 代表 $i j i j$ ， $i = 1$ 代表 $j i j$ ， $i = 0$ 代表 $i j$ ，那么转移也比较容易，直接从上一个状态切过来即可，注意每次 $f [2] [j] [k]$ 都要清零。

由于很难将左边的信息也记下来，记下来也需要 $62 * 62$ 来遍历，所以很不划算。

考虑容斥，将左边的所有方案(不包含相同字符个数相乘)直接于右边相乘，考虑这样多算了什么，显然多算了 $A = C, A = D, B = D, B = C$ 的情况，这个可以容斥来求。

复杂度 $O (62 n)$

//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
//#pragma GCC optimize(2)
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std;

//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); }
//void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); }
//void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;

const int N=1000010,mod=998244353,INF=0x3f3f3f3f;
const double eps=1e-6;

int n;
int a[N];
LL pre[N][64];
LL f[3][64][64],n2;
char s[N];

int get(char c) { 
        
    if(c>='a'&&c<='z') return c-'a'+1;
    else if(c>='A'&&c<='Z') return c-'A'+27;
    else return c-'0'+53;
}

void add(LL &x,LL y) { 
        
    x+=y; 
    if(x>=mod) x-=mod;
}

void del(LL &x,LL y) { 
        
    x-=y; 
    if(x<0) x+=mod;
}

LL qmi(LL a,LL b) { 
        
    LL ans=1;
    while(b) { 
        
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans%mod;
}

int main()
{ 
        
// ios::sync_with_stdio(false);
// cin.tie(0);

    n2=qmi(2,mod-2);
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;i++) a[i]=get(s[i]);
    for(int i=1;i<=n;i++) { 
        
        for(int j=1;j<=62;j++) { 
        
            pre[i][j]=pre[i-1][j];
        }
        pre[i][a[i]]++;
    }
    LL ans=0;
    for(int i=n;i>=1;i--) { 
        
        LL sum=0,all=i-1元器件数据手册、IC替代型号，打造电子元器件IC百科大全！

2020EC-final

文章目录

相关文章