noip模拟测试20

T1：周（week）

　　爆搜，完了……

 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=50;
12 ll n,ans,a[MAXN],b[MAXN],c[MAXN],d[MAXN],sum[MAXN][2];
13 void dfs(int p) {
14     if(p==n+1) {
15         ans=max(ans,sum[n][0]*sum[n][1]);
16         return;
17     }
18     sum[p][0]=sum[p-1][0]+a[p];
19     sum[p][1]=max(sum[p-1][1]-b[p],0LL);
20     dfs(p+1);
21     sum[p][0]=max(sum[p-1][0]-d[p],0LL);
22     sum[p][1]=sum[p-1][1]+c[p];
23     dfs(p+1);
24 }
25 int main() {
26     scanf("%lld",&n);
27     for(int i=1;i<=n;i++)
28         scanf("%lld%lld%lld%lld",&a[i],&b[i],&c[i],&d[i]);
29     sum[0][0]=sum[0][1]=0LL;
30     dfs(1);
31     printf("%lld
",ans);
32     return 0;
33 }

t1 Code

T2：任（duty）

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

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

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

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

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

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

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

 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
",ansp-anse);
41     }
42     return 0;
43 }

t2 Code

T3：飞（fly）

　　毒瘤题，卡空间……

　　简单分析一下，发现两条线段相交当且仅当$y_a>y_b && x_a<x_b$

　　y还是连续的正整数

　　？？？

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

　　不不不！空间开不下！！

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

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

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

 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
",ans);
33     return 0;
34 }

t3 Code