Day5下午解题报告1
预计分数：100+60+30=190
实际分数：100+60+30=190
终于有一道无脑T1了哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈
T1
https://www.luogu.org/problem/show?pid=T15744
无脑暴力，直接模拟就能水过
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<queue>
6 #include<algorithm>
7 #define Ll long long
8 using namespace std;
9 const int MAXN=1011;
10 const int INF=0x7fffff;
11 inline int read()
12 {
13 char c=getchar();int flag=1,x=0;
14 while(c<'0'||c>'9') {if(c=='-') flag=-1;c=getchar();}
15 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*flag;
16 }
17 int n,p,k;
18 struct node
19 {
20 int l;
21 int change[MAXN];
22 }lun[MAXN];
23 int now[MAXN];//每一个位置的值
24 int pos[MAXN];//每一个值的位置
25 int main()
26 {
27 //freopen("rotate.in","r",stdin);
28 // freopen("rotate.out","w",stdout);
29 n=read();p=read();k=read();
30 for(int i=1;i<=n;i++) now[i]=i,pos[i]=i;//每一个数现在是什么
31 for(int i=1;i<=p;i++)
32 {
33 lun[i].l=read();
34 for(int j=1;j<=lun[i].l;j++) lun[i].change[j]=read();
35 lun[i].l++;lun[i].change[lun[i].l]=lun[i].change[1];
36 }
37 for(int i=p;i>=1;i--)
38 {
39 for(int j=1;j<=lun[i].l-1;j++)
40 now[ pos[ lun[i].change[j] ] ]= lun[i].change[j+1];
41 for(int j=1;j<=n;j++) pos[now[j]]=j;
42 }
43 for(int i=1;i<=n;i++)
44 printf("%d ",now[i]);
45
46 return 0;
47 }
48 /*
49 (4,1)*(3,1)*(2,1)的话1变成2然后一直是2
50 2变成1然后变成3
51 3变成1然后变成4
52 4变成1
53
54 4 3 2
55 2 4 1
56 2 3 1
57 2 2 1
58 // 2 3 4 1
59
60 4 3 3
61 2 4 2
62 3 1 2 3
63 2 1 4
64 // 2 3 1 4
65
66 5 2 4
67 3 1 2 5
68 4 3 4 1 2
69 //5 3 4 2 1
70 */T2
不会，根据&和|的性质骗了60分
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<queue>
6 #include<algorithm>
7 #define Ll long long
8 using namespace std;
9 const int MAXN=1e6+10;
10 const int INF=0x7fffff;
11 const int mod=1e9+7;
12 inline int read()
13 {
14 char c=getchar();int flag=1,x=0;
15 while(c<'0'||c>'9') {if(c=='-') flag=-1;c=getchar();}
16 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*flag;
17 }
18 int n,a,b,c,d;
19 int sz[MAXN];
20 int ans=0;
21 int main()
22 {
23 // freopen("range.in","r",stdin);
24 // freopen("range.out","w",stdout);
25 n=read();a=read();b=read();c=read();d=read();
26 for(int i=1;i<=n;i++) sz[i]=read();
27 for(int i=1;i<=n;i++)
28 {
29 int yu=sz[i],huo=sz[i];
30 for(int j=i;j<=n;j++)
31 {
32 yu=yu&sz[j];
33 huo=huo|sz[j];
34 if(yu>=a&&yu<=b&&huo>=c&&huo<=d)
35 ans=(ans+1)%mod;
36 if(yu<a||huo>d) break;
37 }
38 }
39 printf("%d",ans%mod);
40 return 0;
41 }正解：
尝试固定左端点，观察右端点有什么性质
可以看出 and运算的值是递减的，or运算的值是递增的
用st表维护and和or的值||线段树||直接找结果
1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4 #include <cmath>
5 #include <algorithm>
6 #include <cassert>
7
8 using namespace std;
9 typedef long long LL;
10 LL mod = 1e9+7;
11 LL cnt;
12 int s[100005],n,a,b,c,d;
13 int sta[100005][20],sto[100005][20];
14 int aska(int l,int r){
15 int L=r-l+1;
16 int t = log2(L);
17 return sta[l][t] & sta[r-(1<<t)+1][t];
18 }
19 int asko(int l,int r){
20 int L=r-l+1;
21 int t = log2(L);
22 return sto[l][t] | sto[r-(1<<t)+1][t];
23 }
24 int main(){
25 freopen("range.in","r",stdin);
26 freopen("range.out","w",stdout);
27 scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
28 for(int i=1;i<=n;i++) scanf("%d",&s[i]),sta[i][0]=sto[i][0]=s[i];
29 // puts("aaa");
30 for(int j=1;j<20;j++)
31 for(int i=1;i<=n;i++){
32 if(i+(1<<j) -1 <=n){
33 sta[i][j] = sta[i][j-1] & sta[i+(1<<(j-1))][j-1];
34 sto[i][j] = sto[i][j-1] | sto[i+(1<<(j-1))][j-1];
35 }
36 }
37 for(int i=1;i<=n;i++){
38 int andsum = s[i], orsum = s[i];
39
40
41 for(int j=i;j<=n;j++){
42 int L=j,R=n+1;
43 andsum = aska(i,j);
44 orsum = asko(i,j);
45 while(R-L>1){
46 int mid = (L+R)/2;
47 if(aska(i,mid) == andsum && asko(i,mid) == orsum){
48 L=mid;
49 }else R=mid;
50 }
51 if(a <= andsum && andsum <= b && c <= orsum && orsum <= d){
52 cnt += L-j+1;
53 }
54 j=L;
55 }
56
57 }
58 cout<<cnt%mod<<endl;
59
60
61 return 0;
62 }T3
不会，打30分暴力走人
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<queue>
6 #include<algorithm>
7 #define Ll long long
8 using namespace std;
9 const int MAXN=1e6+10;
10 const int INF=0x7fffff;
11 const int mod=1e9+7;
12 inline int read()
13 {
14 char c=getchar();int flag=1,x=0;
15 while(c<'0'||c>'9') {if(c=='-') flag=-1;c=getchar();}
16 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*flag;
17 }
18 int n,k;
19 int a[MAXN];
20 struct node
21 {
22 int u,v,w,f,nxt;
23 }edge[MAXN];
24 int head[MAXN];
25 int num=1;
26 inline void add_edge(int x,int y)
27 {
28 edge[num].u=x;
29 edge[num].v=y;
30 edge[num].nxt=head[x];
31 head[x]=num++;
32 }
33 int ans=0;
34 int deep[MAXN];
35 void pd()
36 {
37 queue<int>q;q.push(1);
38 int now=a[1];
39 while(q.size()!=0)
40 {
41 int p=q.front();q.pop();
42 for(int i=head[p];i!=-1;i=edge[i].nxt)
43 {
44 if(edge[i].f==0&&deep[edge[i].v]>deep[edge[i].u])
45 {
46 now+=a[edge[i].v];
47 q.push(edge[i].v);
48 }
49 }
50 }
51 if(now==k) ans=(ans+1)%mod;
52 }
53 void dfs(int now)
54 {
55 if(now==num)
56 {
57 pd();
58 return ;
59 }
60 edge[now].f=1;
61 edge[now+1].f=1;
62 dfs(now+2);
63 edge[now].f=0;
64 edge[now+1].f=0;
65 dfs(now+2);
66 }
67 void make_deep(int now)
68 {
69 for(int i=head[now];i!=-1;i=edge[i].nxt)
70 if(deep[edge[i].v]==0)
71 deep[edge[i].v]=deep[now]+1,make_deep(edge[i].v);
72 }
73 int main()
74 {
75 //freopen("fruit.in","r",stdin);
76 // freopen("fruit.out","w",stdout);
77 memset(head,-1,sizeof(head));
78 n=read();k=read();
79 for(int i=1;i<=n;i++) a[i]=read();
80 for(int i=1;i<=n-1;i++)
81 {
82 int x=read(),y=read();
83 add_edge(x,y);
84 add_edge(y,x);
85 }
86 deep[1]=1;
87 make_deep(1);
88 edge[1].f=1;//断
89 edge[2].f=1;
90 dfs(3);
91 edge[1].f=0;
92 edge[2].f=0;
93 dfs(3);//没断
94 printf("%d",ans%mod);
95 return 0;
96 }
97
98 /*
99 5 3
100 2 1 0 1 1
101 1 2
102 1 3
103 3 4
104 3 5
105 //7
106
107 3 1
108 1 1 1
109 1 2
110 2 3
111 //2
112 */f[i][j] 表示i 号节点在子树中拿j 个果子的方案数
DFS 时可以直接把父节点状态传下去，减少一维合并复杂度
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<queue>
6 #include<algorithm>
7 #define Ll long long
8 using namespace std;
9 const int MAXN=1e6+10;
10 const int INF=0x7fffff;
11 const int mod=1e9+7;
12 inline int read()
13 {
14 char c=getchar();int flag=1,x=0;
15 while(c<'0'||c>'9') {if(c=='-') flag=-1;c=getchar();}
16 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*flag;
17 }
18 int n,k;
19 int a[MAXN];
20 struct node
21 {
22 int u,v,w,f,nxt;
23 }edge[MAXN];
24 int head[MAXN];
25 int num=1;
26 inline void add_edge(int x,int y)
27 {
28 edge[num].u=x;
29 edge[num].v=y;
30 edge[num].nxt=head[x];
31 head[x]=num++;
32 }
33 int ans=0;
34 int deep[MAXN];
35 void pd()
36 {
37 queue<int>q;q.push(1);
38 int now=a[1];
39 while(q.size()!=0)
40 {
41 int p=q.front();q.pop();
42 for(int i=head[p];i!=-1;i=edge[i].nxt)
43 {
44 if(edge[i].f==0&&deep[edge[i].v]>deep[edge[i].u])
45 {
46 now+=a[edge[i].v];
47 q.push(edge[i].v);
48 }
49 }
50 }
51 if(now==k) ans=(ans+1)%mod;
52 }
53 void dfs(int now)
54 {
55 if(now==num)
56 {
57 pd();
58 return ;
59 }
60 edge[now].f=1;
61 edge[now+1].f=1;
62 dfs(now+2);
63 edge[now].f=0;
64 edge[now+1].f=0;
65 dfs(now+2);
66 }
67 void make_deep(int now)
68 {
69 for(int i=head[now];i!=-1;i=edge[i].nxt)
70 if(deep[edge[i].v]==0)
71 deep[edge[i].v]=deep[now]+1,make_deep(edge[i].v);
72 }
73 int main()
74 {
75 //freopen("fruit.in","r",stdin);
76 // freopen("fruit.out","w",stdout);
77 memset(head,-1,sizeof(head));
78 n=read();k=read();
79 for(int i=1;i<=n;i++) a[i]=read();
80 for(int i=1;i<=n-1;i++)
81 {
82 int x=read(),y=read();
83 add_edge(x,y);
84 add_edge(y,x);
85 }
86 deep[1]=1;
87 make_deep(1);
88 edge[1].f=1;//断
89 edge[2].f=1;
90 dfs(3);
91 edge[1].f=0;
92 edge[2].f=0;
93 dfs(3);//没断
94 printf("%d",ans%mod);
95 return 0;
96 }
97
98 /*
99 5 3
100 2 1 0 1 1
101 1 2
102 1 3
103 3 4
104 3 5
105 //7
106
107 3 1
108 1 1 1
109 1 2
110 2 3
111 //2
112 */总结
就喜欢这种题目区分度大的考试。
拿满暴力分就有一个不错的名次23333
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017-11-01 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
