10.7NOIP模拟赛

周 (week)
【题目描述】
退役之后,liu_runda总会想起学OI的时候自己怎样被郭神虐爆…
liu_runda学文化课的时候想要学OI,学OI的时候想要学文化课.为了解决矛盾,他决定以周为单位安排文化课和OI的学习.例如:学1周文化课,学1周OI,学1周文化课,学2周OI,学2周文化课…
距离他退役还有N周.他想合理安排这N周的学习内容使得自己的知识水平在N周之后尽量高. 一个人的OI水平LevelOI和文化课水平LevelWHK的乘积等于知识水平LevelZS.具体来说,LevelOI和LevelWHK都是一个整数,而LevelZS=LevelOI*LevelWHK.
在这N周之前,liu_runda太颓了,故一开始他的OI水平为0,文化课水平为0.在第i周,如果他学习文化课,他的文化课水平提高ai,OI水平降低bi;如果他学习OI,他的OI水平提高ci,文化课水平降低di.OI水平和文化课水平的最大值没有限制,但最低不会小于0.即,如果OI水平/文化课水平不足x的时候减少了x,那么将变为0而不是一个负数.
liu_runda现在实在是太咸鱼了,求不出他能够达到的最高知识水平,于是造了个题出到联考里,要选手求出他能够达到的最高的知识水平LevelZS
【输入格式】
第一行一个整数N
接下来N行每行4个空格隔开的整数ai,bi,ci,di.
【输出格式】
一行一个整数表示答案.
【样例输入】
2
666 233 666 233
666 233 666 233
【样例输出】
288378
【数据范围】
前4个测试点满足:对于第i个测试点,N=i
第5个测试点满足:所有bi=0,所有di=0,所有ai=1,所有ci=1
第6个测试点满足:所有bi=1,所有di=1,所有ai=1,所有ci=1
全部数据,1<=N<=15,0<=ai,bi,ci,di<=1000000

题解：暴搜，枚举所有状态更新答案。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int n,a[17],b[17],c[17],d[17];
ll ans=0,X=0,Y=0;
void dfs(int pos) {
    if (pos>n) {
        ans=max(ans,X*Y);
        return ;
    }
    ll t1=X,t2=Y;
    X+=a[pos],Y=max(0ll,Y-b[pos]);
    dfs(pos+1);
    X=t1,Y=t2;
    Y+=c[pos],X=max(0ll,X-d[pos]);
    dfs(pos+1);
    X=t1,Y=t2;
}
int main() {
    freopen("week.in","r",stdin);
    freopen("week.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;++i) scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
    dfs(1);
    cout<<ans<<endl;
    return 0;
}

任(duty)
【题目描述】
在画板上有一片黑白相间的矩形区域满足这样的性质:如果认为相同颜色的方块可以在上下左右四个方向连通,那么任意两个黑色方块要么不连通,要么连通但之间只有一条简单路径(不重复经过同一个格子的路径).
这个矩形区域有N行M列,从上到下依次为第1,2,3…N-1,N行,从左到右依次为第1,2,3…M-1,M列.
每次郭神会询问这片矩形区域内的一个子矩形.在只考虑这个子矩形内的像素时(即从子矩形内部不能和子矩形之外的像素相连通),问这个子矩形内的黑色方块组成了多少连通块.
如果不能完成这个任务,liu_runda就会被郭神批判一番…
【输入格式】
第一行三个整数N,M,Q,表示矩形区域有N行M列,有Q组询问.
接下来N行,每行一个长为M的01字符串.0表示白色,1表示黑色.第i行第j个字符表示第i行j列的颜色,
接下来Q行,每行4个整数x1,y1,x2,y2,(x1<=x2,y1<=y2)表示选出的矩形区域的两个对角.即选出一个左上角为第x1行第y1列,右下角为第x2行第y2列,包含x2-x1+1行,y2-y1+1列的区域.
【输出格式】
Q行,第i行一个整数ans表示第i组询问的答案.
【样例输入1】
3 4 4
1101
0110
1101
1 1 3 4
1 1 3 1
2 2 3 4
1 2 2 4
【样例输出1】
3
2
2
2
【样例输入2】
5 5 6
11010
01110
10101
11101
01010
1 1 5 5
1 2 4 5
2 3 3 4
3 3 3 3
3 1 3 5
1 1 3 4
【样例输出2】
3
2
1
1
3
2
【数据范围】
对于第1,2个测试点,Q=1
对于第3,4个测试点,N=1
对于第5,6,7个测试点,N=2
对于第8个测试点,N,M<=1000
对于第9个测试点,N,M<=1500
对于全部测试点,1<=N,M<=2000,1<=Q<=200000,1<=x1<=x2<=N,1<=y1<=y2<=M,保证任意两个黑色像素之间最多只有一条简单路径.

题解：连通块数就是点数-边数，然后前缀和乱搞一下即可。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=2005;
char s[MAXN][MAXN];
int n,m,q,a[MAXN][MAXN];
int e[MAXN][MAXN],d[MAXN][MAXN];
int r[MAXN][MAXN],c[MAXN][MAXN];
inline int read() {
    int x=0;char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x;
}
/*void print(int s[MAXN][MAXN]) {
    for (int i=1;i<=n;++i) {
        for (int j=1;j<=m;++j)
            printf("%-3d ",s[i][j]);
        puts("");
    }
    puts("");
}*/
int main() {
    freopen("duty.in","r",stdin);
    freopen("duty.out","w",stdout);
//  freopen("map.txt","w",stdout);
//  printf("memory==%d\n",sizeof(a)*10);
    memset(r,0,sizeof(r));
    memset(c,0,sizeof(c));
    memset(a,0,sizeof(a));
    n=read(),m=read(),q=read();
    for (int i=1;i<=n;++i) {
        scanf("%s",s[i]+1);
        for (int j=1;j<=m;++j) {
            a[i][j]=s[i][j]-'0';
            r[i][j]=(a[i][j]+a[i][j-1]==2);
            c[i][j]=(a[i][j]+a[i-1][j]==2);
            d[i][j]=a[i][j];
            e[i][j]=r[i][j]+c[i][j];
            e[i][j]+=e[i-1][j]+e[i][j-1]-e[i-1][j-1];
            d[i][j]+=d[i-1][j]+d[i][j-1]-d[i-1][j-1];
        }
    }
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j)
            r[i][j]+=r[i][j-1];
    for (int j=1;j<=m;++j)
        for (int i=1;i<=n;++i)
            c[i][j]+=c[i-1][j];
/*  print(a);
    print(d);
    print(e);
    print(r);
    print(c);*/
    for (register int t=0;t<q;++t) {
        int x1=read(),y1=read(),x2=read(),y2=read();
        int node=d[x2][y2]-d[x2][y1-1]-d[x1-1][y2]+d[x1-1][y1-1];
        int edge=e[x2][y2]-e[x2][y1]-e[x1][y2]+e[x1][y1];
        int add=r[x1][y2]-r[x1][y1]+c[x2][y1]-c[x1][y1];
        printf("%d\n",node-edge-add);
    }
    return 0;
}

飞(fly)
【题目描述】
liu_runda决定提高一下知识水平,于是他去请教郭神.郭神随手就给了liu_runda一道神题,liu_runda并不会做,于是把这个题扔到联考里给高二的做.
郭神有n条位于第一象限内的线段,给出每条线段与x轴和y轴交点的坐标,显然这样就可以唯一确定每一条线段.
n条线段和y轴交点的纵坐标分别为1,2,3,4…n.我们记和y轴交点纵坐标为i的线段和x轴交点的横坐标为x[i]+1,x[i]按这样的方式生成:
x[1]由输入给出.
x[i]=(x[i-1]+a) % mod,2<=i<=n.
即:如果x[3]=4,则与y轴交点纵坐标为3的抛物线,和x轴交点的横坐标为4+1=5.
我们保证给出的n,x[1],a,mod使得所有的x[i]互不相同.
对于第一象限内的所有点(点的横纵坐标可以是任意实数),如果一个点被x条线段经过,它的鬼畜值就是x*(x-1)/2.
求第一象限内的所有点的鬼畜值之和.
【输入格式】
一行4个整数n,x[1],a,mod
【输出格式】
1行一个整数表示鬼畜值之和.
【样例输入1】(即sample1.in)
5 2 4 7
【样例输出1】(即sample1.ans)
5
【数据范围】
第1,2个测试点,n<=100.
第3,4个测试点,n<=10^5.
第5,6个测试点的数据,a<=10.
第7,8个测试点,x[1]=a.
第9,10个测试点,无特殊限制.
对于全部数据,1<=n<=1e7,1<=a<=1e5,1<=mod<=1e8,a,mod互质,n < mod,给出的n,x[1],a,mod使得所有的x[i]互不相同.
请选手注意,1e7个int类型的变量将占用大约40mb的内存,导致内存超限,本题得0分.
题
解：
考虑线段相交的性质.显然有这样的结论:0 < a < b,0 < c < d,那么在(0,a),(c,0)之间连线段,在(0,b),(d,0)之间连线段,这样的两条线段在第一象限一定没有交点.
答案就是x[1],x[2]…x[n]这个序列的逆序对个数.

考虑树状数组算法,我们需要求出第i个元素和前面i-1个元素形成的逆序对个数.
整个序列由若干段等差数列组成(不超过a段)（题目描述有“x[i]互不相同”）.而第i个元素前面的i-1个元素也可以分成不超过a段等差数列.在每段等差数列内大于第i个元素的元素个数可以O(1)求出,因此O(a)的时间内即可求出第i个元素和前面i-1个元素组成的逆序对数.时间复杂度O(na).
可以得到a<=10时的20分.结合算法3可以得到60分.

x[1]=a的数据告诉我们,x[i]=i*a%mod
假设x[i]=x[i-1]+a(也就是x[i-1]+a < mod),且x[i-1]和前面所有数字形成了m个逆序对,同时,除去x[i-1]和x[i]所在的等差数列,x[i]前面的所有数字可以分成k段等差序列,那么x[i]将和前面所有数字组成m-k个逆序对.
原因在于:每段等差序列中必然有一个数字和x[i-1]能组成逆序对,但不能和x[i]组成逆序对.那么每段等差数列的贡献都会减1.
因此我们可以O(1)从x[i-1]的贡献得到x[i]的贡献.
如果x[i] < a,不存在对应的x[i-1],我们需要直接计算它的贡献.前面有i-1个数字,我们数出有多少个数字不产生贡献(即小于x[i]的数字个数),即可求出有多少个数字形成了逆序对.用树状数组维护小于a的所有数值,可以在O(loga)的时间内完成一次这样的计算.小于a的数字至多有a个,所以这一部分的时间复杂度为O(aloga),空间复杂度为O(a)
总的时间复杂度为O(aloga+n)
可以得到x[1]=a的20分.

现在x[1]!=a,我们只需针对最开始的一段不完整等差数列加一些特判就可以通过本题.

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e5+4;
int n,a,x1,MOD,c[MAXN];
ll ans=0;
int query(int x) {
    int ret=0;
    ++x;
    for (;x;x-=x&(-x)) ret+=c[x];
    return ret;
}
int add(int x) {
    ++x;
    for (;x<MAXN;x+=x&(-x)) ++c[x];
}

int main() {
    freopen("fly.in","r",stdin);
    freopen("fly.out","w",stdout);
    memset(c,0,sizeof(c));
    scanf("%d%d%d%d",&n,&x1,&a,&MOD);
    int seq(0),cur=x1,rev(0);
    for (register int i=1;i<=n;++i) {
        if (cur>=a) {//>a也行？理论上else是<
            rev-=seq;
            if (x1>cur) ++rev;//第一项所在等差序列不完整，多出的k个顺序对中多算了一对
            ans+=rev;
        }
        else rev=i-1-query(cur),ans+=rev,add(cur);
        cur+=a;
        if (cur>=MOD) cur-=MOD,++seq;
    }
    cout<<ans<<endl;
    return 0;
}