然后昨天打了多校,因为太菜,没办法,然后罚时爆炸。。。一想到明天要写xy题,好慌。。。

T1:Ascending Rating

题意:

给你一个数组生成公式:ai =(p*ai−1+q*i+r)mod MOD;

然后给你数列长度n,m(之后有用),和k(题目给出了a数组的前k项)。。。然后给了你p,q,r,MOD用于生成数列。。。然后题目定义了两个输出,一个是长度为m的连续数列最大值乘上其开头序列位置i的和。。。另一个是长度为m的连续数列包括ai的上升序列长度乘上i。。。

火狐截图_2018-07-31T11-25-07.916Z

就在这个样子。。。然后数据范围:火狐截图_2018-07-31T11-26-21.807Z

太长自己看。。。

分析:

一看这个范围,就知道要么O(n),要么O(log(n))。。。然后我们考虑算法。。。如果我们从前往后算,那么发现B处理不出来。。。怎么办,聪明的大佬们想到了从后往前维护一个单调队列,然后B就是队列长度,A就是队列开头元素。。。

代码:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e7+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f;
namespace FastIO
{
    template inline void read(tp &x)
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template inline void write(tp x)
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template inline void writeln(tp x)
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
LL T,n,m,k,p,q,r,Mod;
LL A,B;
struct Node{LL val,name;}a[N];
deque de;
main()
{
    read(T);
    while(T--)
    {
        A=0,B=0;de.clear();
        read(n),read(m),read(k),read(p),read(q),read(r),read(Mod);
        for(int i=1;i<=k;i++)
            read(a[i].val),a[i].name=i;
        for(int i=k+1;i=1;i--)
        {
            while(!de.empty()&&de.back().vali+m-1)
                de.pop_front();
            if(i<=n-m+1)
            {
                A+=de.front().val^i;
                B+=de.size()^i;
            }
        }
        printf("%lld %lld\n",A,B);
    }
    return 0;
}

T3:Dynamic Graph Matching

题意:

给你一棵定点不超过10个的树,刚开始没有边,给出m个加边或者删边操作,问你每次操作以后树上的匹配数。。。匹配定义为一个边的集合中任意两个元素没有重复的点,所以匹配的边数最多只有n/2个。。。

分析:

我们思考我们加边或者删边只对一些状态有影响,我们枚举终止状态,然后对它进行+-操作就好了。。。详细见代码。。。

代码:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e7+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
namespace FastIO
{
    template inline void read(tp &x)
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template inline void write(tp x)
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template inline void writeln(tp x)
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
int T,n,m,cnt;
vector xx[6];
int ret[6],x[1024];
int dp[1024],zz,change;
main()
{
    // cout<<(15&5)<<endl;
    read(T);
    while(T--)
    {
        read(n),read(m);
        cnt=n/2;dp[0]=1;
        for(int i=1;i<=cnt;i++)
            ret[i]=0,xx[i].clear();
        for(int i=1;i<(1<>1].push_back(i);
        }
        for(int cas=1,x,y;cas<=m;cas++)
        {
            char s[100];
            scanf("%s",s);read(x),read(y);
            if(x==y)continue;
            change=(1<<--x)|(1<<--y);zz=s[0]=='+'?1:-1;
            for(int i=1;i<=cnt;i++)
            {
                int size=xx[i].size();
                for(int j=0;j<size;j++)
                    if((xx[i][j]&change)==change)
                    {
                        dp[xx[i][j]]+=dp[xx[i][j]^change]*zz;
                        ret[i]+=dp[xx[i][j]^change]*zz;
                        dp[xx[i][j]]=(dp[xx[i][j]]%mod+mod)%mod;
                        ret[i]=(ret[i]%mod+mod)%mod;
                    }
            }printf("%d",ret[1]);
            for(int i=2;i<=cnt;i++)
                printf(" %d",ret[i]);
            puts("");
        }
    }
    return 0;
}

T4:Euler Function

题意:

给出多组询问,然后问你第k个欧拉函数值是合数的数。。。

分析:

找规律就好了。。。

代码:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e7+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
namespace FastIO
{
    template inline void read(tp &x)
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template inline void write(tp x)
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template inline void writeln(tp x)
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
int T,n;
main()
{
    read(T);
    while(T--)
    {
        read(n);
        if(n==1)puts("5");
        else if(n==2)puts("7");
        else writeln(n+5);
    }
    return 0;
}

T6:Grab The Tree

题意:

两个人轮流取一颗树上数字,取出数字的集合内不可以有边相连。。。问谁赢。。。

分析:

直接Xor整棵树,如果答案是0,那么平局,否则先手赢。。。因为如果Xor的值大于1,那么先手总有办法掌握先机。。。拿到比后手大。。。

代码:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e7+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
namespace FastIO
{
    template inline void read(tp &x)
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template inline void write(tp x)
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template inline void writeln(tp x)
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
int T,n,flag;
main()
{
    read(T);
    while(T--)
    {
        flag=0,read(n);
        for(int i=1,zz;i<=n;i++)
            read(zz),flag^=zz;
        for(int i=1,u,v;i<n;i++)
            read(u),read(v);
        if(!flag)puts("D");
        else puts("Q");
    }
    return 0;
}

T12:Visual Cube

题意:

打出一个长宽高给定的立体图形。。。

分析:

直接打。。

代码:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e7+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
namespace FastIO
{
    template inline void read(tp &x)
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template inline void write(tp x)
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template inline void writeln(tp x)
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
int T, a, b, c, n, m;
char s[250][250];
signed main()
{
    scanf("%d", &T);
    for(int _ = 1; _ <= T; _++)
    {
        scanf("%d%d%d", &a, &b, &c);
        n = ((c + b) << 1) + 1;
        m = ((a + b) << 1) + 1;
        for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) s[i][j] = '!';
        for(int i = 1 + 2 * b; i <= n ; i ++)
        {
            int flag = 1;
            for(int j = 1; j = n - 2 * b + 1; pp--)
        {
            int up = pp;
            int row = n - pp + 1, col = m - (n - pp);
            for(int i = 1; i <= empty; i++) s[row][i] = '.';
            for(int i = 1; i <= empty; i++) s[n - i + 1][col] = '.';
            
            if(! (empty & 1))
            {
                int flag = 1;
                for(int i = empty + 1; i <= col; i++)
                {
                    if(flag) s[row][i] = '+', flag ^= 1;
                    else s[row][i] = '-', flag ^= 1;
                }
                flag = 1;
                for(int i = row + 1; i <= n && s[i][col] == '!'; i ++)
                {
                    if(flag) s[i][col] = '|', flag ^= 1;
                    else s[i][col] = '+', flag ^= 1;
                }
            }
            else
            {
                int flag = 1;
                for(int i = empty + 1; i <= col; i++)
                {
                    if(flag) s[row][i] = '/', flag ^= 1;
                    else s[row][i] = '.', flag ^= 1;
                }
                flag = 1;
                for(int i = row + 1; i <= n && s[i][col] == '!'; i ++)
                {
                    if(flag) s[i][col] = '.', flag ^= 1;
                    else s[i][col] = '/', flag ^= 1;
                }
            }
            empty --;
        }
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
                cout <<s[i][j];
            puts("");
        }
    }
    return 0;
}

 

 

 

Leave A Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注