今天考试本暴力选手爱了

   

这道题真的签到题了... 暴力枚举所有情况a了

代码

#include 
     
      using namespace std;const int N = 100;int n, a[N], b[N], c[N], d[N];long long ans = 0;void deal(int sta) {        int oi = 0, whk = 0;    for(int i = 1;i <= n;i ++) {        int D = sta & (1 << (i - 1)) ? 1 : 0;        if(D) {            oi += c[i]; whk -= d[i];            if(whk < 0) whk = 0;        }        else {            oi -= b[i], whk += a[i];            if(oi < 0) oi = 0;        }    }    ans = max(ans, 1ll * oi * whk);}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]);    for(int sta = 0; sta < (1 << n); sta ++) deal(sta);    printf("%lld\n", ans);}
     

  

样例再次又臭又长

输入

3 4 4 1101 0110 1101 1 1 3 4 1 1 3 1 2 2 3 4 1 2 2 4

输出

3222

这道题因为他说了每两个黑色块块之间只有一条路径相连 也就是说每两个连通块之间也只有一条路径

换句话说没多一条边就减少一个连通块  连通块数 = 总点数 - 边数 

维护一个边点的二维前缀和即可

代码

#include 
     
      using namespace std;const int N = 2000 + 5;const int M = 2e5 + 5;int n, m, q, a[N][N], R[N][N], C[N][N], nd[N][N], edg[N][N];char s[N];void Init( ) {        scanf("%d%d%d",& n,& m,& q);    for(int i = 1;i <= n;i ++) {        scanf("%s", s + 1);        for(int j = 1;j <= m;j ++) a[i][j] = s[j] - '0';    }    for(int i = 1;i <= n;i ++)        for(int j = 1;j <= m;j ++) {            edg[i][j] = edg[i][j - 1];            nd[i][j] = nd[i][j - 1];            if(a[i][j]) nd[i][j] ++;            if(a[i][j] && a[i][j - 1]) edg[i][j] ++;            R[i][j] = edg[i][j];        }    for(int i = 2;i <= n;i ++)        for(int j = 1;j <= m;j ++) {            C[i][j] = C[i - 1][j];            if(a[i][j] && a[i - 1][j]) C[i][j] ++;        }    for(int i = 2;i <= n;i ++) {        int tmp = 0;        for(int j = 1;j <= m;j ++) {            nd[i][j] += nd[i - 1][j];            if(a[i][j] && a[i - 1][j]) tmp ++;            edg[i][j] += edg[i - 1][j] + tmp;        }    }}void Solve( ) {        for(int i = 1;i <= q;i ++) {        int l1, r1, l2, r2;        scanf("%d%d%d%d",& l1, & r1, & l2, & r2);        int nds = nd[l2][r2] - nd[l2][r1 - 1] - nd[l1 - 1][r2] + nd[l1 - 1][r1 - 1];        int edgs = edg[l2][r2] - edg[l2][r1] - edg[l1][r2] + edg[l1][r1];        edgs += C[l2][r1] - C[l1][r1] + R[l1][r2] - R[l1][r1];        printf("%d\n", nds - edgs);    }}int main( ) {        freopen("duty.in", "r", stdin);    freopen("duty.out", "w", stdout);    Init( );    Solve( );}
     

   

     

这道题首先可以发现若两条线段$a, b$有交点 那么需要满足$ax > bx,ay < by$很容易想到使用逆序对

但是多条线交于一点呢 可以发现每与一个点相交 产生的贡献即为原本经过该点的线段数量 同样转化为相交求逆序对的问题

但是这道题数据范围直接树状数组要凉 然后我们发现对于没超过$mod$范围的点他们之间的距离成等差数列 差$a$

那么可以考虑将原序列拆成大小为$a$的块 每个块内的点数都是一样的 点数为总的轮数 每越过一次$mod$记一次

从前往后做$y$递增 所以我们每次要求的是有多少个$x$比他大 每次我们查看他是第几块 递增的求出对于当前线的逆序对的数量即可

需要特判初始$x > a$的情况 因为这时候每个块内的点数不同

代码

#include 
     
      using namespace std;const int N = 1e5 + 5;int c[N], a, n, x, mod;long long ans;int lowbit(int pos) {    return pos & (-pos);}int query(int pos) {        int ans = 0;    while(pos) {        ans += c[pos];        pos -= lowbit(pos);    }    return ans;}void add(int pos) {        while(pos <= a) {        c[pos] ++;        pos += lowbit(pos);    }}int main( ) {        freopen("fly.in", "r", stdin);    freopen("fly.out", "w", stdout);    scanf("%d%d%d%d",& n,& x,& a,& mod);    long long rev = 0;    int cur = x, idc = 0;    for(int i = 1;i <= n;i ++) {        if(cur >= a) {            rev -= idc;            if(cur < x) rev ++;            ans += rev;        }        else rev = i - 1 - query(cur + 1), ans += rev, add(cur + 1);        cur += a;        if(cur >= mod) cur -= mod, idc ++;      }    printf("%lld\n", ans);}