noip模拟测试20

我会带着你远行 2023-08-17 15:43 117阅读 0赞

--------------------

**T1：周（week）**

爆搜，完了……

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

t1 Code

--------------------

**T2：任（duty）**

因为保证任意两个黑色像素之间最多只有一条简单路径，所以黑色点组成的应该是森林

一个子矩形实际上就是割出一些树的一部分，同样也是森林

我们的问题就转化为求一个森林中有几棵树

可以用总点数减总边数得到

所以我们只需要用子矩阵中的点数减去边数就行了

那点数和边数该怎么快速求出呢？

把边分为横纵两种，二维前缀和就完了……

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<algorithm>
     3 #include<cstring>
     4 #include<cmath>
     5 #include<iostream>
     6 #include<queue>
     7 #include<vector>
     8 #include<cstdlib>
     9 #define ll long long
    10 using namespace std;
    11 const int MAXN=2100;
    12 int n,m,anse,ansp,q,er[MAXN][MAXN],ec[MAXN][MAXN],p[MAXN][MAXN];
    13 char s[MAXN][MAXN];
    14 int main() {
    15     scanf("%d%d%d",&n,&m,&q);
    16     for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
    17     for(int i=1;i<=n;i++)
    18         for(int j=1;j<=m;j++)
    19             if(s[i][j]=='1') p[i][j]=1;
    20     for(int i=1;i<=n;i++)
    21         for(int j=1;j<=m;j++)
    22             p[i][j]=p[i][j]+p[i-1][j]+p[i][j-1]-p[i-1][j-1];
    23     for(int i=1;i<=n;i++)
    24         for(int j=1;j<m;j++)
    25             if(s[i][j]=='1'&&s[i][j+1]=='1') er[i][j]=1;
    26     for(int i=1;i<=n;i++)
    27         for(int j=1;j<m;j++)
    28             er[i][j]=er[i][j]+er[i-1][j]+er[i][j-1]-er[i-1][j-1];
    29     for(int i=1;i<n;i++)
    30         for(int j=1;j<=m;j++)
    31             if(s[i][j]=='1'&&s[i+1][j]=='1') ec[i][j]=1;
    32     for(int i=1;i<n;i++)
    33         for(int j=1;j<=m;j++)
    34             ec[i][j]=ec[i][j]+ec[i-1][j]+ec[i][j-1]-ec[i-1][j-1];
    35     for(int i=1,aa,bb,cc,dd;i<=q;i++) {
    36         scanf("%d%d%d%d",&aa,&bb,&cc,&dd);
    37         ansp=p[cc][dd]-p[aa-1][dd]-p[cc][bb-1]+p[aa-1][bb-1];
    38         anse=(er[cc][dd-1]-er[aa-1][dd-1]-er[cc][bb-1]+er[aa-1][bb-1])
    39             +(ec[cc-1][dd]-ec[aa-1][dd]-ec[cc-1][bb-1]+ec[aa-1][bb-1]);
    40         printf("%d\n",ansp-anse);
    41     }
    42     return 0;
    43 }

t2 Code

--------------------

**T3：飞（fly）**

毒瘤题，卡空间……

简单分析一下，发现两条线段相交当且仅当$y\_a>y\_b  \\&\\&  x\_a<x\_b$

y还是连续的正整数

？？？

这不就是简单的逆序对吗？

不不不！空间开不下！！

发现a很小，再看数据的生成方式是一个模意义下的等差数列

于是可以在a上开树状数组，对于长度为a每段的数的分布应该是一样的，就可以算了

（注意第一段等差数列比较特殊，需要特判）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<iostream>
     3 #include<algorithm>
     4 #include<cmath>
     5 #include<cstring>
     6 #include<cstdlib>
     7 #define ll long long
     8 using namespace std;
     9 const int MAXA=1e5+233;
    10 ll n,xx,a,D,now,cnt,d,ans,tr[MAXA];
    11 void add(int x) {
    12     for(++x;x<=a+1;x+=x&-x) ++tr[x];
    13 }
    14 ll ask(int x) {
    15     ll ret=0;
    16     for(++x;x;x-=x&-x) ret+=tr[x];
    17     return ret;
    18 }
    19 int main() {
    20     scanf("%lld%lld%lld%lld",&n,&xx,&a,&D);
    21     now=xx;
    22     for(int i=1;i<=n;i++) {
    23         if(now<a) add(now),d=i-ask(now),ans+=d;
    24         else {
    25             d-=cnt;
    26             if(now<xx) ++d;
    27             ans+=d;
    28         }
    29         now+=a;
    30         if(now>=D) now-=D,++cnt;
    31     }
    32     printf("%lld\n",ans);
    33     return 0;
    34 }

t3 Code

--------------------

转载于:https://www.cnblogs.com/Gkeng/p/11354497.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230810/f068687ce77d4bff8729de7ceb6ae407.png