2017.11.2 NOIP模拟赛

题解 套题

目录

• 2017.11.2 NOIP模拟赛
  • 周
    • 思路
    • 代码
  • 任
    • 思路
    • 代码
  • 飞
    • 思路
    • 代码

周

思路

• 暴搜题，只要注意开long long不溢出就好了。

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
#include <algorithm>
using std::max;
const int MAXN=17;
int n;
long long ans;
int a[MAXN],b[MAXN],c[MAXN],d[MAXN];
void DFS(int cur,int oi,int whk){
    if(cur==n+1){
        ans=max(ans,(long long)oi*whk);
        return;
    }
    DFS(cur+1,max(0,oi-b[cur]),whk+a[cur]);
    DFS(cur+1,oi+c[cur],max(0,whk-d[cur]));
}
int main(){
#ifdef DEBUG
    setIO("a");
#endif
    read(n);
    for(int i=1;i<=n;++i)
        read(a[i]),read(b[i]),read(c[i]),read(d[i]);
    DFS(1,0,0);
    write(ans);
    return 0;
}

任

思路

• 比较巧妙的二维前缀和的题；
• 首先黑点组成了一个森林，那么我们只要用某个矩形区域内的点数减去边数就是其连通块的个数；
• 那么使用二维前缀和优化就行了；
• 边数稍微有些麻烦，要算出向左和上的边，向上的边，向左的边这三个前缀和；
• 之后按向左和上的边求出矩形范围内的边后，要补上多减的向上和向左的边就行了。

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
const int MAXN=2005;
int n,m,x1,y1,x2,y2;
int blk[MAXN][MAXN],all[MAXN][MAXN],le[MAXN][MAXN],up[MAXN][MAXN];
char G[MAXN][MAXN];
inline void prepare(){
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j)
            blk[i][j]=blk[i-1][j]+blk[i][j-1]-blk[i-1][j-1]+(G[i][j]^'0');
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(G[i][j]=='1' && G[i][j-1]=='1')
                ++all[i][j],++le[i][j];
            if(G[i][j]=='1' && G[i-1][j]=='1')
                ++all[i][j],++up[i][j];
            le[i][j]+=le[i-1][j];
            all[i][j]=all[i-1][j]+all[i][j-1]-all[i-1][j-1]+all[i][j];
        }
    }
    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j)
            up[j][i]+=up[j][i-1];
    }
}
inline int solve(){
    int ret=blk[x2][y2]-blk[x1-1][y2]-blk[x2][y1-1]+blk[x1-1][y1-1];
    ret-=all[x2][y2]-all[x1-1][y2]-all[x2][y1-1]+all[x1-1][y1-1];
    ret+=le[x2][y1]-le[x1-1][y1];
    ret+=up[x1][y2]-up[x1][y1-1];
    return ret;
}
int main(){
#ifdef DEBUG
    setIO("b");
#endif
    int q;
    read(n),read(m),read(q);
    for(int i=1;i<=n;++i)
        scanf("%s",G[i]+1);
    prepare();
    for(int i=1;i<=q;++i){
        read(x1),read(y1),read(x2),read(y2);
        write(solve(),'\n');
    }
    return 0;
}

飞

思路

• 这个题难点在于空间；
• 观察发现那个式子就是在这个点相交的边的对数，那么答案就是有多少对相交的线段；
• 由于纵截距是递增的，那么只有横截距比之前小才会相交；
• 那么就是求一下横截距里的逆序对；
• 但是这样空间不允许；
• 观察发现，横截距是一堆等差数列，就是$x_1,x_1+a,x_1+2a,\cdots$之后有一个$x_1+ka \geq mod$模了后变小了，之后继续这个过程；
• 那么，有一个性质，就是如果之前有$i$段等差数列，当前的数与之前有$j$个逆序对，下一个数会只形成$j-i$个，这个自己试一下就明白了；
• 于是我们只需知道每个等差数列开始的数的逆序对就可以了，也就是不存在$x'+a=x$的$x$，范围只有$a$的大小，只把这个用树状数组维护就能不爆空间了；
• 注意最开始那一段要跳过，因为前面没有贡献。

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
const int MAXA=1e5+5;
int n,x1,a,mod;
class BIT{
    private:
        int c[MAXA];
        int lowbit(int x){return x&-x;}
    public:
        void add(int l,int x){
            for(;l<=a;l+=lowbit(l))
                c[l]+=x;
        }
        int qry(int r){
            int ret=0;
            for(;r;r-=lowbit(r))
                ret+=c[r];
            return ret;
        }
}ta;
inline long long solve(){
    int i=1,x=x1;
    while(x<mod) ++i,x+=a;
    long long ret=0;
    for(int tot=1,cnt=0,sum,tmp;i<=n;++i){
        if(x>=mod){
            x-=mod;
            tot=1;
            sum=ta.qry(x+1);
            ta.add(x+1,1);
            ++cnt;
        }
        if(x>x1) tmp=(x-x1)/a+1;
        else tmp=0;
        tmp+=sum+(tot-1)*cnt;
        ret+=i-tmp-1;
        ++tot,x+=a;
    }
    return ret;
}
int main(){
#ifdef DEBUG
    setIO("c");
#endif
    read(n),read(x1),read(a),read(mod);
    write(solve());
    return 0;
}