20170913NOIP模拟赛(数学联赛ヾ(◍°∇°◍)ノ゙)

摘要:
为了描述整条鱼,接下来的n行,每行有一个长度为m的01字符串,0表示白色,1表示红色。3301110001144这个问题采用子任务系统。小I有两个操作:1xy:询问[x,y]区间中房间种子值的乘积的模块,直到1000000007;2lr:将[l,r]间隔中所有房间的种子值更改为φ第二行包含n个正整数,表示每个房间的种子值。接下来的m行,每行代表一个小的I操作。561248911222421311512323532424对于20%的数据,n,m˂=1000;对于40%的数据,n,m˂=50000;另外20%的数据,种子˂=100000。对于100%数据,1˂=n,m˂=20000,1˂=种子˂=10^7。

【题目描述】

小D有一块被分为n*m个格子的矩形鱼片。为了装饰鱼片,小D决定给每个格子上色。由于小D很喜欢红白,所以小D给每个格子涂上了红色或白色,第i行第j列的格子颜色记为c[i,j]。涂完之后,小D想评估这块鱼片的“XY值”。我们定义一个有序无重复三元格子组{(x1,y1),(x2,y2),(x3,y3)}为“XY组”当且仅当:

|(x1-x2)*(y1-y2)|+|(x3-x2)*(y3-y2)|=0

  (c[x1,y1]-c[x2,y2])*(c[x3,y3]-c[x2,y2])≠0

一块鱼片的“XY值”为该块鱼片里“XY组”的数量。

【输入数据】

第一行两个正整数n,m。

为描述整块鱼片,接下来n行,每行一个长度为m的01串,0表示白色,1表示红色。

【输出数据】

输出一行,一个整数表示这块鱼片的“XY值”。

【样例输入】

3 3

011

100

011

【样例输出】

    44

【数据范围】

本题采用子任务制。

Subtask 1(20pts):1<=n,m<=100;

Subtask 2(10pts):n=1;

Subtask 3(20pts):n=3;

Subtask 4~5(各25pts) 没有数据范围限制;

对于100%的数据,1<=n*m<=4*10^6,0<=c[i][j]<=1。

【样例解释】

    由于本题比较特殊,所以没有样例解释。

solution:20170913NOIP模拟赛(数学联赛ヾ(◍°∇°◍)ノ゙)第1张

20170913NOIP模拟赛(数学联赛ヾ(◍°∇°◍)ノ゙)第2张

这题暴力10分还是挺容易的。。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define FILE "decorate"
#define MN 4000005
#define MOD 1000000000
#define ll long long
using namespace std;
struct lnb
{
    int x1,x2,x3;
    friend lnb operator+(const lnb& a,const lnb& b)
    {
        lnb c;
        c.x1=a.x1+b.x1;
        c.x2=a.x2+b.x2;
        c.x3=a.x3+b.x3;
        if (c.x1>=MOD) ++c.x2,c.x1-=MOD;
        if (c.x2>=MOD) ++c.x3,c.x2-=MOD;
        return c;
    }
    friend lnb operator*(const lnb& a,const lnb& b)
    {
        ll x1,x2,x3;
        x1=1LL*a.x1*b.x1;
        x2=1LL*a.x1*b.x2+1LL*a.x2*b.x1;
        x3=1LL*a.x1*b.x3+1LL*a.x2*b.x2+1LL*a.x3*b.x1;
        x2+=x1/MOD; x1%=MOD;
        x3+=x2/MOD; x2%=MOD;
        return (lnb){x1,x2,x3};
    }
}a[MN][2],b[MN][2],ans;
char **c;
int n,m;

lnb mak(int x) {return (lnb){x,0,0};}
inline int read()
{
    int n=0,f=1; char c=getchar();
    while (c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}
    while (c>='0' && c<='9') {n=n*10+c-'0'; c=getchar();}
    return n*f;
}

int main()
{
//    freopen(FILE".in","r",stdin);
//    freopen(FILE".out","w",stdout);
    register int i,j;
    n=read(); m=read();
    c=new char*[n];
    for (i=0;i<n;++i)
        c[i]=new char[m+1],scanf("%s",c[i]);
    for (i=0;i<n;++i)
        for (j=0;j<m;++j)
            ++a[i][c[i][j]-'0'].x1,++b[j][c[i][j]-'0'].x1;
    for (i=0;i<n;++i)
        for (j=0;j<m;++j)
            ans=ans+a[i][(c[i][j]-'0')^1]*b[j][(c[i][j]-'0')^1]*mak(2);
    for (i=0;i<n;++i)
        ans=ans+a[i][0]*a[i][1]*(a[i][1]+mak(-1)),
        ans=ans+a[i][1]*a[i][0]*(a[i][0]+mak(-1));
    for (i=0;i<m;++i)
        ans=ans+b[i][0]*b[i][1]*(b[i][1]+mak(-1)),
        ans=ans+b[i][1]*b[i][0]*(b[i][0]+mak(-1));
    if (ans.x3) printf("%d%09d%09d",ans.x3,ans.x2,ans.x1);
    else if (ans.x2) printf("%d%09d",ans.x2,ans.x1);
    else if (ans.x1) printf("%d",ans.x1);
}

T2:洞悉(insight)

【题目描述】

在走出了第6扇门后,小I终于可以使用他之前获得的水晶球了。当他透过水晶球看向前方,发现门的后面,是一扇又一扇无尽的门。n个房间排在一起,笔直地延伸向远方。为了让自己接下来的体验不算太差,小I想知道这n个房间中其中一些房间的信息,并进行一些修改。每个房间都有一个seed值。而小I有两种操作:

1 x y:询问[x,y]区间的房间的seed值的乘积对1000000007的模;

2 l r:将[l,r]区间里所有房间的seed值改为φ(seed)

其中,φ(x)为欧拉函数,即小等于x的与x互质的数的个数

【输入数据】

第一行两个正整数n,m。

第二行n个正整数,表示每个房间的seed值。

接下来m行,每行表示一个小I的操作。

【输出数据】

对于每个操作1,输出一行询问的答案。

【样例输入】

5 6

1 2 4 8 9

1 1 2

2 2 4

2 1 3

1 1 5

1 2 3

2 3 5

【样例输出】

32

4

24

【数据范围】

对于20%的数据,n,m<=1000;

对于40%的数据,n,m<=50000;

另外20%的数据,seed<=100000。

对于100%的数据,1<=n,m<=200000,1<=seed<=10^7。

【样例解释】

下面给出每次操作得到的结果:

①序列变为1 1 4 8 9

    ②1*4*8=32

    ③1*1*4=4

    ④序列变为1 1 2 4 6

    ⑤序列变为1 1 1 4 6

    ⑥1*4*6=24

solution:20170913NOIP模拟赛(数学联赛ヾ(◍°∇°◍)ノ゙)第3张

20170913NOIP模拟赛(数学联赛ヾ(◍°∇°◍)ノ゙)第4张

#include <cstdio>
#include <cstring>
#include <algorithm>
#define l(a) (a<<1)
#define r(a) (a<<1|1)
#define FILE "insight"
#define mod 1000000007
#define MS 10000005
#define MM 800005
#define MN 200005
using namespace std;
struct node{int pr,mx;}t[MM];
int phi[MS],pri[MS],a[MN];
int n,m,rin;

inline int read()
{
    int n=0,f=1; char c=getchar();
    while (c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}
    while (c>='0' && c<='9') {n=n*10+c-'0'; c=getchar();}
    return n*f;
}

inline void update(int x)
{
    t[x].mx=max(t[l(x)].mx,t[r(x)].mx);
    t[x].pr=1LL*t[l(x)].pr*t[r(x)].pr%mod;
}

void getdown(int x,int L,int R)
{
    if (t[x].mx==1) return;
    if (L==R) {t[x].mx=t[x].pr=phi[t[x].mx]; return;}
    int mid=L+R>>1;
    getdown(l(x),L,mid); getdown(r(x),mid+1,R);
    update(x);
}
int getpro(int x,int L,int R,int ql,int qr)
{
    if (ql==L&&qr==R) return t[x].pr;
    int mid=L+R>>1;
    if (qr<=mid) return getpro(l(x),L,mid,ql,qr);
    else if (ql>mid) return getpro(r(x),mid+1,R,ql,qr);
    else return 1LL*getpro(l(x),L,mid,ql,mid)*getpro(r(x),mid+1,R,mid+1,qr)%mod;
}
void getphi(int x,int L,int R,int ql,int qr)
{
    if (ql==L&&qr==R) {getdown(x,L,R); return;}
    int mid=L+R>>1;
    if (qr<=mid) getphi(l(x),L,mid,ql,qr);
    else if (ql>mid) getphi(r(x),mid+1,R,ql,qr);
    else getphi(l(x),L,mid,ql,mid),getphi(r(x),mid+1,R,mid+1,qr);
    update(x);
}

void build(int x,int L,int R)
{
    if (L==R) {t[x].mx=t[x].pr=a[L]; return;}
    int mid=L+R>>1;
    build(l(x),L,mid); build(r(x),mid+1,R);
    update(x);
}

int main()
{
    freopen(FILE".in","r",stdin);
    freopen(FILE".out","w",stdout);
    register int i,j,g,x,y;
    for (phi[1]=1,i=2;i<MS;++i)
    {
        if (!phi[i]) pri[++rin]=i,phi[i]=i-1;
        for (j=1;i*pri[j]<MS;++j)
            if (i%pri[j]) phi[i*pri[j]]=phi[i]*phi[pri[j]];
            else {phi[i*pri[j]]=phi[i]*pri[j]; break;}
    }
    n=read(); m=read();
    for (i=1;i<=n;++i) a[i]=read();
    build(1,1,n);
    while (m--)
    {
        g=read(); x=read(); y=read();
        if (g==1) getphi(1,1,n,x,y);
        else if (g==2) printf("%d
",getpro(1,1,n,x,y));
    }
}

T3:命令(order)

【题目描述】

小O开了许多年飞机,现在她准备更换自己的炮台。于是就有很多炮台来应聘。为了选拔最优秀的炮台,小O给炮台们下了一条指令,要求他们在n个数中,选出若干个数,使得它们两两之间的和不为质数,最后使得这些数的乘积尽可能大。作为一名优秀的炮台,为了使自己处于尴尬的境地,你需要又快又好地解决这个问题。

【输入数据】

第一行一个正整数n。

第二行n个正整数a1~an,表示小O给出的数字。

【输出数据】

输出一行表示最大乘积,答案对10^9+7取模。

【样例输入】

6

3 2 2 3 4 4

【样例输出】

    64

【数据范围】

本题采用子任务制。

Subtask 1(10pts):n<=13;

Subtask 2(12pts):n<=23;

Subtask 3(13pts):ai<=20;

Subtask 4(15pts):ai<=2000;

Subtask 5~6(各25pts):没有数据范围限制;

对于100%的数据,1<=n<=1000,1<=ai<=5*10^5。

【样例解释】

选取2、2、4、4四个数,2*2*4*4=64。

solution:

20170913NOIP模拟赛(数学联赛ヾ(◍°∇°◍)ノ゙)第5张

#include <cstdio>
#include <cstring>
#include <algorithm>
#define l(a) (a<<1)
#define r(a) (a<<1|1)
#define FILE "insight"
#define mod 1000000007
#define MS 10000005
#define MM 800005
#define MN 200005
using namespace std;
struct node{int pr,mx;}t[MM];
int phi[MS],pri[MS],a[MN];
int n,m,rin;

inline int read()
{
    int n=0,f=1; char c=getchar();
    while (c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}
    while (c>='0' && c<='9') {n=n*10+c-'0'; c=getchar();}
    return n*f;
}

inline void update(int x)
{
    t[x].mx=max(t[l(x)].mx,t[r(x)].mx);
    t[x].pr=1LL*t[l(x)].pr*t[r(x)].pr%mod;
}

void getdown(int x,int L,int R)
{
    if (t[x].mx==1) return;
    if (L==R) {t[x].mx=t[x].pr=phi[t[x].mx]; return;}
    int mid=L+R>>1;
    getdown(l(x),L,mid); getdown(r(x),mid+1,R);
    update(x);
}
int getpro(int x,int L,int R,int ql,int qr)
{
    if (ql==L&&qr==R) return t[x].pr;
    int mid=L+R>>1;
    if (qr<=mid) return getpro(l(x),L,mid,ql,qr);
    else if (ql>mid) return getpro(r(x),mid+1,R,ql,qr);
    else return 1LL*getpro(l(x),L,mid,ql,mid)*getpro(r(x),mid+1,R,mid+1,qr)%mod;
}
void getphi(int x,int L,int R,int ql,int qr)
{
    if (ql==L&&qr==R) {getdown(x,L,R); return;}
    int mid=L+R>>1;
    if (qr<=mid) getphi(l(x),L,mid,ql,qr);
    else if (ql>mid) getphi(r(x),mid+1,R,ql,qr);
    else getphi(l(x),L,mid,ql,mid),getphi(r(x),mid+1,R,mid+1,qr);
    update(x);
}

void build(int x,int L,int R)
{
    if (L==R) {t[x].mx=t[x].pr=a[L]; return;}
    int mid=L+R>>1;
    build(l(x),L,mid); build(r(x),mid+1,R);
    update(x);
}

int main()
{
    freopen(FILE".in","r",stdin);
    freopen(FILE".out","w",stdout);
    register int i,j,g,x,y;
    for (phi[1]=1,i=2;i<MS;++i)
    {
        if (!phi[i]) pri[++rin]=i,phi[i]=i-1;
        for (j=1;i*pri[j]<MS;++j)
            if (i%pri[j]) phi[i*pri[j]]=phi[i]*phi[pri[j]];
            else {phi[i*pri[j]]=phi[i]*pri[j]; break;}
    }
    n=read(); m=read();
    for (i=1;i<=n;++i) a[i]=read();
    build(1,1,n);
    while (m--)
    {
        g=read(); x=read(); y=read();
        if (g==1) getphi(1,1,n,x,y);
        else if (g==2) printf("%d
",getpro(1,1,n,x,y));
    }
}

(10分深搜还是可做的 (〃´皿`)q)

总结:学好数理化,走遍天下都不怕。

免责声明:文章转载自《20170913NOIP模拟赛(数学联赛ヾ(◍°∇°◍)ノ゙)》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇20170915NOIP练习赛(滑稽)20170906ditoly的信心大赛(╥╯^╰╥)下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

武汉大学2020年数学分析考研试题参考解答

251119武汉大学2020年数学分析考研试题参考解答 1、 若 , 计算 . 跟锦数学跟锦考研小锦教学微信公众号有参考解答哦欢迎关注 2、 设 , 求 的全微分和二阶偏导数. 跟锦数学跟锦考研小锦教学微信公众号有参考解答哦欢迎关注 3、 计算不定积分 . 跟锦数学跟锦考研小锦教学微信公众号有参考解答哦欢迎关注 4、 计算...

Typora使用说明(记录总结)

Typora是一款超简洁的markdown编辑器,具有如下特点: 完全免费,目前已支持中文 跨平台,支持windows,mac,linux 支持数学公式输入,图片插入 极其简洁,无多余功能 界面所见即所得 目录 区域元素 YAML FONT Matters 菜单 段落 标题 引注 序列 可选序列 代码块 数学块 表格 脚注 水平线 特征元素...

数学趣题——猴子吃桃问题

an / 2 – 1 = an+1 1: #include <stdio.h> 2: 3: int main() 4: { 5: int sum = 1, i; 6: for (i = 9; i >= 1; i--) 7: { 8: sum = (sum + 1) * 2; 9: } 1...

数学建模----线性规划

我理解的线性规划就是在给定的一些线性方程可以列出的约束条件下求解目标函数的极值。 它在matlab中的标准型为:[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS) ,fval为返回的目标函数的值 默认求最小值,求最大值的话,把c换成-c就好了(最大值取个﹣就是最小值了)...

BZOJ 4459: [Jsoi2013]丢番图 数学推导

之前绝对做过几乎一模一样的题,现在做竟然忘了. code: #include <bits/stdc++.h> #define ll long long #define setIO(s) freopen(s".in","r",stdin) using namespace std; ll n,ans=1; int main...

【NOI2012】骑行川藏

获得成就:第一次在信竞做神仙数学题 先放个前言,$OI$ 出大型数学题还是比较麻烦的,因为主要是考你数学推导 / 手算式子,你算出来之后把公式套个板子,就得到结论——$OI$ 的大型数学题的代码都是板子…… 然后再放一些前置物理知识——功的计算公式:$E(W)=F imes s$($s$ 表示路程)。 首先,我们得知道题目隐含条件,就是人速不能小于等于风速...