同步发布于 Another Blog

「启」

实在是不想接着补前几天的 NOIP 冲刺了（尤其是遇到 Day11 D 这种毒瘤题），于是就上洛谷随便做点题。

发现今天的日推是 CF1602A，于是乆决定把这场比赛的 A,B,C 都做了，然后发现 F 也挺水的，就一起水掉了（

「Div2.A」Two Subsequences

「Div2.A」题目简述

给出一个字符串 \(S\)，要求找到一个字典序最小的非空字串，然后输出这个字串和原字符串删掉这个字串后形成的串。

「Div2.A」思路简述

还是一如既往的手速题（

因为是找出一个字典序最小的非空字串，所以找到一个字典序最小的字母即可。

「Code」

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cstring>

#define Heriko return
#define Deltana 0
#define Romanno 1
#define S signed
#define LL long long
#define R register
#define I inline
#define CI const int
#define mst(a, b) memset(a, b, sizeof(a))
#define ON std::ios::sync_with_stdio(false);cin.tie(0)
#define Files() freopen("RNMTQ.in","r",stdin);freopen("RNMTQ.out","w",stdout)

using namespace std;

template<typename J>
I void fr(J &x)
{
    short f(1);x=0;char c=getchar();

    while(c<'0' or c>'9')
    {
        if(c=='-') f=-1;
        
        c=getchar();
    }

    while (c>='0' and c<='9') 
    {
        x=(x<<3)+(x<<1)+(c^=48);
        c=getchar();
    }
   
    x*=f;
}

template<typename J>
I void fw(J x,bool k)
{
    if(x<0) x=-x,putchar('-');

    static short stak[35];short top(0);

    do
    {
        stak[top++]=x%10;
        x/=10;
    }
    while(x);

    while(top) putchar(stak[--top]+'0');

    k?puts(""):putchar(' ');
}

CI MXX(1005);

char s[MXX];

S main()
{
    Files();

    int T;fr(T);

    while(T--)
    {
        scanf("%s",s+1);
        int a(1),n(strlen(s+1));

        for(int i(2);i<=n;++i)
            if(s[i]<s[a])
                a=i;

        putchar(s[a]);putchar(' ');

        for(int i(1);i<=n;++i)
            if(i!=a)
                putchar(s[i]);

        puts("");
    }

    Heriko Deltana;
}

「Div2.B」Divine Array

「Div2.B」题目简述

给出一个长度为 \(n\) 的序列，求问在经过第 \(k\) 次变换之后序列中的第 \(x\) 个数。

第 \(i\) 次变换为：对于所有的 \(1 \le j \le n\)，将 \(a_j\) 变为 \(a_j\) 在第 \(i-1\) 次修改后出现的次数。

「Div2.B」思路简述

时空限制还是挺宽的，而且我们可以简单的手玩一下发现一个序列进行最多 \(n\) 操作之后就不会发生变化了，所以我们预处理出每次操作后的序列即可。

「Div2.B」Code

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cstring>

#define Heriko return
#define Deltana 0
#define Romanno 1
#define S signed
#define LL long long
#define R register
#define I inline
#define CI const int
#define mst(a, b) memset(a, b, sizeof(a))
#define ON std::ios::sync_with_stdio(false);cin.tie(0)
#define Files() freopen("RNMTQ.in","r",stdin);freopen("RNMTQ.out","w",stdout)

using namespace std;

template<typename J>
I void fr(J &x)
{
    short f(1);x=0;char c=getchar();

    while(c<'0' or c>'9')
    {
        if(c=='-') f=-1;
        
        c=getchar();
    }

    while (c>='0' and c<='9') 
    {
        x=(x<<3)+(x<<1)+(c^=48);
        c=getchar();
    }
   
    x*=f;
}

template<typename J>
I void fw(J x,bool k)
{
    if(x<0) x=-x,putchar('-');

    static short stak[35];short top(0);

    do
    {
        stak[top++]=x%10;
        x/=10;
    }
    while(x);

    while(top) putchar(stak[--top]+'0');

    k?puts(""):putchar(' ');
}

CI MXX(2001);

int a[MXX][MXX],co[MXX];

S main()
{
    Files();

    int T;fr(T);

    while(T--)
    {
        int n,q;fr(n);

        for(int i(1);i<=n;++i) fr(a[i][0]),co[i]=0;

        fr(q);

        for(int i(1);i<=n;++i) ++co[a[i][0]];

        for(int i(1);i<=n;++i)
        {
            for(int j(1);j<=n;++j) a[j][i]=co[a[j][i-1]];

            for(int j(1);j<=n;++j) co[j]=0;

            for(int j(1);j<=n;++j) ++co[a[j][i]];
        }

        while(q--)
        {
            int x,k;fr(x),fr(k);

            if(k>n) fw(a[x][n],1);
            else fw(a[x][k],1);
        }
    }

    Heriko Deltana;
}

「Div2 C/Div1 A」Array Elimination

「Div2 C/Div1 A」题目简述

给出一个长度为 \(n\) 的序列，定义操作 elimination(k) 为：从序列中选取 \(k\) 个数，设 \(x=a_{i_1} \operatorname{and} a_{i_2} \cdots \operatorname{and} a_{i_k}\)，然后让这 \(k\) 个数都减去 \(x\)，直到所有的 \(a_i\) 都变为 \(0.\)

求问能选出多少个 \(k\)，输出它们。

「Div2 C/Div1 A」思路简述

考虑到要让数变为全 \(0\)，于是我们选的数 and 起来必须要让每个数每一位上的 \(1\) 都被消除，所以选定的 \(k\) 必然是所有位上的 \(1\) 出现次数的公因数。

总体的时间复杂度为 \(O(Tn\log^2n+n\sqrt{n}).\)

「Div2 C/Div1 A」Code

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cstring>

#define Heriko return
#define Deltana 0
#define Romanno 1
#define S signed
#define LL long long
#define R register
#define I inline
#define CI const int
#define mst(a, b) memset(a, b, sizeof(a))
#define ON std::ios::sync_with_stdio(false);cin.tie(0)
#define Files() freopen("RNMTQ.in","r",stdin);freopen("RNMTQ.out","w",stdout)

using namespace std;

template<typename J>
I void fr(J &x)
{
    short f(1);x=0;char c=getchar();

    while(c<'0' or c>'9')
    {
        if(c=='-') f=-1;
        
        c=getchar();
    }

    while (c>='0' and c<='9') 
    {
        x=(x<<3)+(x<<1)+(c^=48);
        c=getchar();
    }
   
    x*=f;
}

template<typename J>
I void fw(J x,bool k)
{
    if(x<0) x=-x,putchar('-');

    static short stak[35];short top(0);

    do
    {
        stak[top++]=x%10;
        x/=10;
    }
    while(x);

    while(top) putchar(stak[--top]+'0');

    k?puts(""):putchar(' ');
}

CI MXX(2e5+1);

int GCD(int x,int y) {Heriko !y?x:GCD(y,x%y);}

int a[MXX],n,co[31],ans[MXX],cnt;

S main()
{
    Files();

    int T;fr(T);

    while(T--)
    {
        fr(n);mst(co,0);cnt=0;

        for(int i(1);i<=n;++i) fr(a[i]);

        for(int i(1);i<=n;++i)
            for(int j(0);j<=30;++j)
                co[j]+=((a[i]>>j)&1);

        int g(0);

        for(int i(0);i<=30;++i) g=GCD(g,co[i]);

        if(!g)
        {
            for(int i(1);i<=n;++i) fw(i,0);

            puts("");

            continue;
        }

        for(int i(1);i*i<=g;++i)
            if(!(g%i))
            {
                ans[++cnt]=i;

                if(i*i!=g) ans[++cnt]=(g/i);
            }
        
        sort(ans+1,ans+1+cnt);


        for(int i(1);i<=cnt;++i) fw(ans[i],0);

        puts("");
    }

    Heriko Deltana;
}

「Div1.D/Div2.F」Difficult Mountain

「Div1.D/Div2.F」题面简述

有 \(n\) 个人去爬难度为 \(d\) 的山，每个人都有 \(a,s\) 两个值。

\(s\) 表示当且仅当一个人的 \(s\) 大于 \(d\) 的时候它才能登山，后者则表示这个人登山之后这所山的权值会被修改为 \(\max(d,s).\)

「Div1.D/Div2.F」思路简述

显然是要贪心的去解，手玩分讨发现，当最值相等时我们让 \(s\) 小的先爬不会使答案变劣，所以我们直接进行一边排序即可。

「Div1.D/Div2.F」Code

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cstring>

#define Heriko return
#define Deltana 0
#define Romanno 1
#define S signed
#define LL long long
#define R register
#define I inline
#define CI const int
#define mst(a, b) memset(a, b, sizeof(a))
#define ON std::ios::sync_with_stdio(false);cin.tie(0)
#define Files() freopen("RNMTQ.in","r",stdin);freopen("RNMTQ.out","w",stdout)

using namespace std;

template<typename J>
I void fr(J &x)
{
    short f(1);x=0;char c=getchar();

    while(c<'0' or c>'9')
    {
        if(c=='-') f=-1;
        
        c=getchar();
    }

    while (c>='0' and c<='9') 
    {
        x=(x<<3)+(x<<1)+(c^=48);
        c=getchar();
    }
   
    x*=f;
}

template<typename J>
I void fw(J x,bool k)
{
    if(x<0) x=-x,putchar('-');

    static short stak[35];short top(0);

    do
    {
        stak[top++]=x%10;
        x/=10;
    }
    while(x);

    while(top) putchar(stak[--top]+'0');

    k?puts(""):putchar(' ');
}

template<typename J>
I J Hmax(const J &x,const J &y) {Heriko x>y?x:y;}

CI MXX(500001);

struct Rubbisher
{
    int a,s;

    I bool operator < (const Rubbisher &co) const
    {
        int mx1(Hmax(a,s)),mx2(Hmax(co.a,co.s));

        if(mx1!=mx2) Heriko mx1<mx2;
        else Heriko s==co.s?a<co.a:s<co.s;
    }
}

a[MXX];

int n,d,ans;

S main()
{
    Files();

    fr(n),fr(d);

    for(int i(1);i<=n;++i) fr(a[i].s),fr(a[i].a);

    sort(a+1,a+1+n);

    for(int i(1);i<=n;++i)
        if(a[i].s>=d)
            ++ans,d=Hmax(d,a[i].a);

    fw(ans,1);

    Heriko Deltana;
}

「终」

水。