2019-11-27 18:20 已编辑闽南师范大学 C++

关注

2019 The Preliminary Contest for ICPC China Nanchang National Invitational（A 、H 、I 、K 、M）

A. PERFECT NUMBER PROBLEM

题目链接：https://nanti.jisuanke.com/t/38220

题意：

输出前五个完美数

分析：

签到。直接百度完美数输出即可

#include<bits/stdc++.h>
#define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0)
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define ll long long
#define numm ch - 48
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define pi 3.14159265358979323
#define debug(x) cout << #x << ": " << x << endl
#define debug2(x, y)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define debug3(x, y, z)       cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define debug4(a, b, c, d)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
using namespace std;
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm);flag&&(res=-res);}
template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;}
ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;}

const int N = 2e5 + 10;

int main()
{ 
    printf("6\n28\n496\n8128\n33550336\n");
    return 0;
}

View Code

H. Coloring Game

题目链接：https://nanti.jisuanke.com/t/38227

题意：

给你个 2 * N 的网格 , 你有up(↑), down(↓), left(←), right(→), left up(↖), left down(↙), right up(↗), right down (↘) 八个路径走到下一个网格

网格原来是全白色的 , 你每经过一个网格它就会变黑色（白变黑 , 黑变黑）. 要求你从左上角走到右下角 , 问能有多少种不同的配色方案（只要有一处网格颜色不同即为不同方案）

分析：

由于起点和终点固定 , 所以对于第一列和最后一列网格不同配色方案为 2 * 2 = 4 ; 而对于起点与终点之间的网格每一列都只有三种状态（黑白、白黑、黑黑）,所以答案为 4 * 3 ^ (n - 2) % MOD;

快速幂跑一遍。。。

#include<bits/stdc++.h>
#define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0)
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define ll long long
#define numm ch - 48
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define pi 3.14159265358979323
#define debug(x) cout << #x << ": " << x << endl
#define debug2(x, y)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define debug3(x, y, z)       cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define debug4(a, b, c, d)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
using namespace std;
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm);flag&&(res=-res);}
template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;}
ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;}

const int N = 2e5 + 10;

int main()
{
    ll n;
    cin >> n;
    if(n == 1){
        cout << 1 << endl;
        return 0;
    }
    cout << 4 * pow_mod(3 , n - 2 , MOD) % MOD << endl;
    return 0;
}

View Code

I. Max answer

题目链接：https://nanti.jisuanke.com/t/38228

题意：

给一个长为n(n <= 500000)的数组a, 对每个区间，求区间和乘区间最小值的最大值 $(- 1e$

分析：

这道题乍一看像是单调栈的模板题 , 但很可惜的是 ai 的取值可以为负数 , 所以对于以 ai 为最小值的区间 , 若 ai 为负数 , 要找到最小区间和 , 若为 ai 为正数 , 要找到最大区间和

对于正数ai，利用单调栈寻找以ai为最小值的区间，利用前缀和数组求区间和再*ai 即结果（ai 为正数 , ai为区间最小值）

先用单调栈求出以a[i]为最小值能够延伸的左端点L[i]和右端点R[i] , 然后对于每个正数，我们用该数乘以这个区间和。区间和用前缀和来求，对于每个数所能影响的最大区间我们已经求出来了。对于负数来说，我们需要求在它右区间的最小前缀和减去左区间的最大前缀和 , 因为只有它的区间和最小对应的这个区间的value值才最大，又由区间和=sum[j]-sum[i]可知，sum[j]最小，sum[i]最大时才能时这个区间和最小，所以问题的关键转化为寻找最小的sum[j]和最大的sum[i]

对于右区间的最小前缀和，以及左区间的最大前缀和我们用线段树来求

#include<bits/stdc++.h>
#define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0)
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define ll long long
#define numm ch - 48
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define pi 3.14159265358979323
#define debug(x) cout << #x << ": " << x << endl
#define debug2(x, y)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define debug3(x, y, z)       cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define debug4(a, b, c, d)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
using namespace std;
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm);flag&&(res=-res);}
template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;}
ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;}

const int N = 5e5 + 10;
ll sum[N],a[N];
ll maxn[N << 2],minn[N << 2];
void build(int l,int r,int root)
{
    if(l==r)
    {
        maxn[root]=minn[root]=sum[l];
        return ;
    }
    int mid=l+r>>1;
    build(l,mid,root<<1);
    build(mid+1,r,root<<1|1);
    maxn[root]=max(maxn[root<<1],maxn[root<<1|1]);
    minn[root]=min(minn[root<<1],minn[root<<1|1]);
}
ll qmax(int l,int r,int root,int ql,int qr)
{
    if(l>=ql&&r<=qr)
        return maxn[root];
    int mid=l+r>>1;
    ll ans=-INF;
    if(mid>=ql)
        ans=qmax(l,mid,root<<1,ql,qr);
    if(mid<qr)
        ans=max(ans,qmax(mid+1,r,root<<1|1,ql,qr));
    return ans;
}
ll qmin(int l,int r,int root,int ql,int qr)
{
    if(l>=ql&&r<=qr)
        return minn[root];
    int mid=l+r>>1;
    ll ans=INF;
    if(mid>=ql)
        ans=qmin(l,mid,root<<1,ql,qr);
    if(mid<qr)
        ans=min(ans,qmin(mid+1,r,root<<1|1,ql,qr));
    return ans;
}
int LL[N],RR[N],st[N];
int main()
{
    ios;
    int n;
    cin >> n;
    rep(i ,1 ,n)
    cin >> a[i],sum[i] = sum[i-1]+a[i];
    build(1,n,1);
    int top=0;
    rep(i ,1 ,n)
    {
        while(top&&a[st[top]]>a[i])
            RR[st[top--]]=i-1;
        st[++top]=i;
    }
    while(top)
        RR[st[top--]]=n;
    for(int i=n;i>=1;i--)
    {
        while(top&&a[st[top]]>a[i])
            LL[st[top--]]=i+1;
        st[++top]=i;
    }
    while(top)
        LL[st[top--]]=1;
    ll ans = -INF;
    rep(i ,1 ,n)
    {
        if(a[i]>0)
            ans=max(ans,a[i]*(sum[RR[i]]-sum[LL[i]-1]));
        else
            ans=max( ans,a[i]*( qmin(1,n,1,i,RR[i])-qmax(1,n,1,LL[i],i)) );
    }
       cout << ans << endl;
    return 0;
}

View Code

K. MORE XOR

题目链接：https://nanti.jisuanke.com/t/38230

题意：

分析：

对于 L - R 内的每一个数 ai 只有当 ai 出现次数为奇数时才会对结果做出贡献 , 所以我们可以先暴力打表找找规律

打表函数：

void f(int l,int r)
{
    for(int i=l; i<=r; i++)
        cnt[i]++;
}
void g(int l,int r)
{
    for(int x=l; x<=r; x++)
        for(int y=x; y<=r; y++)
            f(x,y); 
}
void w(int l,int r)
{
    for(int x=l; x<=r; x++)
        for(int y=x; y<=r; y++)
            g(x,y);
}

打表

记录每个数字出现的次数，奇数次说明这个数存在于答案中，偶数次相当于对答案没有贡献。打表找规律发现跟4的倍数有关，所以我们预处理以4为分组的异或和，然后O(1)输出结果就可以了。

#include<bits/stdc++.h>
#define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0)
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define ll long long
#define numm ch - 48
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define pi 3.14159265358979323
#define debug(x) cout << #x << ": " << x << endl
#define debug2(x, y)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define debug3(x, y, z)       cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define debug4(a, b, c, d)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
using namespace std;
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm);flag&&(res=-res);}
template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;}
ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;}

const int N = 1e5 + 10;

ll a[N] , sum[N];
int n , q;
int main()
{
    int t;
    sd(t);
    while(t--)
    {
        cin >> n;
        rep(i ,1 ,n)
        sld(a[i]);
        sd(q);
        rep(i , 1 ,n)
        {
            if(i <= 4) sum[i] = a[i];
            else
                sum[i] = sum[i - 4] ^ a[i];
        }
        while(q--)
        {
            int l , r;
            sdd(l , r);
            int len = r - l + 1 ;
            ll ans ;
            if(len % 4 == 0)
                ans = 0;

            else if(len % 4 == 1)
            {
                ans = sum[r];
                if(l - 4 > 0)
                    ans ^= sum[l - 4];
            }
            
            else if(len % 4 == 2)
            {
                ans = sum[r] ^ sum[r - 1];
                if(l - 3 > 0)
                    ans ^= sum[l - 3];
                if(l - 4 > 0)
                    ans ^= sum[l - 4];
            }

            else if(len % 4 == 3)
            {
                ans = sum[r - 1];
                if(l - 3 > 0)
                    ans ^= sum[l - 3];
            }
            pld(ans);
        }
    }
    return 0;
}

View Code

M. Subsequence

题目链接：https://nanti.jisuanke.com/t/38232

题意：

给你个母串S , 在给你 N 个字符串 T , 为 T 是否为 S 的子序列

分析：

这道题时间卡得有点过分 , 我用 string 读取字符串竟然分分钟 Tle 。。。

首先我们用 nex[ i ][ j ] 表示 S 串中 i 字符之后的离它最近的 j 字符的位置 , 从后往前预处理 S串中每一个字符 i 的下一位字符 j 的位置

然后输入 T 串判断 T 串当前字符 now1和 T 串下一个字符 T[i] 在主串中的位置是否会合法（即判断nex[now1][ T[i] - 'a'] 是否会小于 len（字符串下标从0开始））

#include<bits/stdc++.h>
#define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0)
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define ll long long
#define numm ch - 48
#define INF 0x3f3f3f3f
#define pi 3.14159265358979323
#define debug(x) cout << #x << ": " << x << endl
#define debug2(x, y)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define debug3(x, y, z)       cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define debug4(a, b, c, d)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
using namespace std;
template<typename T>void read(T &res)
{
    bool flag=false;
    char ch;
    while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
    for(res=numm; isdigit(ch=getchar()); res=(res<<1)+(res<<3)+numm);
    flag&&(res=-res);
}
template<typename T>void Out(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)Out(x/10);
    putchar(x%10+'0');
}
ll gcd(ll a,ll b)
{
    return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b)
{
    return a*b/gcd(a,b);
}
ll pow_mod(ll x,ll n,ll mod)
{
    ll res=1;
    while(n)
    {
        if(n&1)res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}
ll fact_pow(ll n,ll p)
{
    ll res=0;
    while(n)
    {
        n/=p;
        res+=n;
    }
    return res;
}
const int N = 1e5 + 10;
int nex[N][30];
int now[N];
char s[N] , t[N];
void init(int &len)
{
    len = strlen(s);
    rep(i , 0 , len - 1) now[i] = len;
    for(int i = len - 1 ; i >= 0 ; i --)
    {
        for(int j = 0 ; j < 26 ;j ++)
        {
            nex[i][j] = now[j];
        }
        now[s[i] - 'a'] = i;
    }
}
int main()
{

    scanf("%s" , s);
    int len ;
    init(len);
    int n;
    read(n);
    while(n --)
    {
    scanf("%s" , t);
        int len2 = strlen(t);
        int flag = 0;
        int now1 = now[t[0] - 'a'];
        if(len < len2)
        {
            puts("NO");
            continue;
        }
        if(now1 >= len)
        {
            puts("NO");
            continue;
        }
        for(int i = 1 ; i < len2 ; i++)
        {
            now1 = nex[now1][t[i] - 'a'];
            if(now1 >= len){flag = 1 ;break;}
        }
        if(flag)    puts("NO");
        else    puts("YES");/*123*/
    }
    return 0;
}