Educational Codeforces Round 80 (Rated for Div. 2)

\[Educational\ Codeforces\ Round\ 80\ (Rated\ for\ Div.\ 2)\]

A.Deadline

打勾函数找最小值,在\(\sqrt{d}\)邻域里找\(x\)最小化\(x+\lceil\frac{d}{x+1}\rceil\)即可

//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include
using namespace std;
function ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
int T,n,d;
typedef long long int LL;
int main(){
    ____();
    cin >> T;
    while(T--){
        cin >> n >> d;
        LL dd = sqrt(d);
        bool ok = false;
        for(LL x = max(0ll,dd-2); x <= dd+2; x++) if(x+d/(x+1)+(d%(x+1)!=0)<=n) ok = true;
        cout << (ok?"YES":"NO") << endl;
    }
    return 0;
}

B.Yet Another Meme Problem

\(1\le a \le A, 1\le b \le B\),问区间内满足\(a·b+a+b=a·10^{dig(b)}+b\),其中\(dig(b)\)为b的位数
化简之后得到\(b-1=10^{dig(b)}\),也就是形如9、99、999……之类的数,找到这样的数的个数,乘上\(A\)即可

//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include
using namespace std;
function ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
using LL = int_fast64_t;
int t;
LL a,b;
int main(){
    ____();
    cin >> t;
    while(t--){
        cin >> a >> b;
        LL cnt = 0,cur = 10;
        while(cur-1<=b){
            cnt++;
            cur*=10;
        }
        cout << cnt*a << endl;
    }
    return 0;
}

C.Two Arrays

有两个序列\(a\)\(b\),问能够造出多少对满足\(a\)不减,\(b\)不增,且\(a[i]\le n,b[i]\le n,a[i]\le b[i]\ for\ all\ i\ from\ 1\ to\ m\)的序列
考虑\(dp[k][i][j]\)表示当前处理到第\(k\)位,\(a\)序列当前为\(i\),\(b\)序列当前为\(j\)的情况有多少种
状态转移方程:\(dp[k][i][j] = \sum_{a=1}^{i} \sum_{b=j}^{n}dp[k-1][a][b]\)
用二维前缀和维护一下即可

//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include
using namespace std;
function ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
typedef int_fast64_t LL;
const LL MOD = 1e9+7;
const int MAXN = 1111;
int n,m;
LL f[11][MAXN][MAXN],sum[MAXN][MAXN];
int main(){
    ____();
    cin >> n >> m;
    for(int i = 1; i <= n; i++) for(int j = i; j <= n; j++) f[1][i][j] = 1;
    for(int k = 2; k <= m; k++){
        for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++)
            sum[i][j] = (sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+f[k-1][i][j])%MOD;
        for(int i = 1; i <= n; i++) for(int j = i; j <= n; j++)
            f[k][i][j] = (sum[i][n]-sum[i][j-1]+MOD)%MOD;
    }
    LL res = 0;
    for(int i = 1; i <= n; i++) for(int j = i; j <= n; j++) res = (res+f[m][i][j])%MOD;
    cout << res << endl;
    return 0;
}

D. Minimax Problem

给一个的矩阵,任意取两行,对应数取\(max\),再对得到的数取\(min\),问得到的最大值可以由哪两行操作得到
最小化最大值问题,考虑二分答案,接下来变成判定可行性问题
假设当前二分值为\(x\)
由于\(m\le 8\),对于当前矩阵中的每一个数,大于等于\(x\)的为1,小于\(x\)的为0,这样每行可以用二进制来表示,现在问题转化为判断是否存在两行,使得其二进制表示取或为\((1<,用set或者map维护即可

//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include
using namespace std;
function ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 3e5+7;
int n,m,mat[MAXN][10];
bool check(int mid){
    unordered_set S;
    for(int i = 1; i <= n; i++){
        int msk = 0;
        for(int j = 1; j <= m; j++) if(mat[i][j]>=mid) msk|=(1<<(j-1));
        S.insert(msk);
        for(auto x : S) if((x|msk)==((1<> 1;
        if(check(mid)) l = mid + 1;
        else r = mid - 1;
    }
    unordered_map mp;
    for(int i = 1; i <= n; i++){
        int msk = 0;
        for(int j = 1; j <= m; j++) if(mat[i][j]>=r) msk|=(1<<(j-1));
        mp.insert(make_pair(msk,i));
        for(auto x : mp) if((x.first|msk)==((1<

E. Messenger Simulator

初始序列为\([1,2,3,...,n]\)现在有\(m\)次操作,每次操作把第\(x\)个数放到序列的最前面,问从开始到结束的过程中,每个数下标的最小值\(lmax[i]\)和最大值\(rmax[i]\)分别是多少
下标最小值:如果一个数\(i\)有被放到最前面过,那其下标最小值为\(1\),否则为\(i\)(只能被往后推)
下标最大值:分两部分来做。

  • 对于每个数\(i\),在它第一次被放到第一个位置之前,统计出现过不同的大于\(i\)的数\(dif\),更新\(rmax[i]\)\(rmax[i]+dif\)。换一个角度,每个第一次出现的\(i\),可以对\([1,i-1]\)之间的每个数贡献\(1\),也就是区间加\(1\),更新的时候需要查询单点值,用树状数组维护即可
  • 对于每个数\(i\),当它被放到第一个位置之后,统计从当前操作到下一次\(i\)被放到第一个位置之前(如果没有下一次那就是到最后一次操作),出现过多少不同的数,记为dif,更新答案\(rmax[i] = max(rmax[i],1+dif)\),dif可以用主席树查询
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include
using namespace std;
function ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 3e5+7;
int n,m,lmax[MAXN],rmax[MAXN],A[MAXN];
vector vec[MAXN];
bool vis[MAXN];
struct BinaryIndexedTree{
    int val[MAXN];
    inline int lowbit(int x){ return x & -x; }
    void update(int pos, int x){
        while(pos<=n){
            val[pos] += x;
            pos += lowbit(pos);
        }
    }
    int query(int pos){
        int res = 0;
        while(pos){
            res += val[pos];
            pos -= lowbit(pos);
        }
        return res;
    }
}BIT;
int last[MAXN];
struct PersistentSegmentTree{
    int root[MAXN],ls[MAXN<<6],rs[MAXN<<6],sz[MAXN<<6],tot;
    void update(int &now, int pre, int L, int R, int pos, int x){
        now = ++tot;
        sz[now] = sz[pre] + x;
        ls[now] = ls[pre]; rs[now] = rs[pre];
        if(L+1==R) return;
        int mid = (L+R) >> 1;
        if(pos=R) return 0;
        if(L>=pos) return sz[rt];
        int mid = (L+R) >> 1;
        return query(L,mid,ls[rt],pos) + query(mid,R,rs[rt],pos);
    }
}PST;
int main(){
    scanf("%d %d",&n,&m);
    for(int i = 1; i <= n; i++) lmax[i] = rmax[i] = i;
    for(int i = 1; i <= m; i++){
        scanf("%d",&A[i]);
        vec[A[i]].emplace_back(i);
        lmax[A[i]] = 1;
    }
    for(int i = 1; i <= m; i++){
        if(!last[A[i]]){
            PST.update(PST.root[i],PST.root[i-1],1,MAXN,i,1);
            last[A[i]] = i;    
        }
        else{
            int tmp;
            PST.update(tmp,PST.root[i-1],1,MAXN,last[A[i]],-1);
            last[A[i]] = i;
            PST.update(PST.root[i],tmp,1,MAXN,last[A[i]],1);
        }
        if(vis[A[i]]) continue;
        vis[A[i]] = true;
        rmax[A[i]]+=BIT.query(A[i]);
        BIT.update(1,1);
        BIT.update(A[i],-1);
    }
    for(int i = 1; i <= n; i++) if(!vis[i]) rmax[i] += BIT.query(i);
    for(int i = 1; i <= n; i++){
        if(vec[i].empty()) continue;
        for(int j = 0; j < (int)vec[i].size(); j++){
            int pos = vec[i][j];
            int nxtpos = pos==vec[i].back()?m+1:vec[i][j+1];
            if(pos+1==nxtpos) continue;
            rmax[i] = max(rmax[i],1+PST.query(1,MAXN,PST.root[nxtpos-1],pos+1));
        }
    }
    for(int i = 1; i <= n; i++) cout << lmax[i] << ' ' << rmax[i] << endl;
    return 0;
}

你可能感兴趣的