首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Day5下午解题报告1

Day5下午解题报告1

作者头像
attack
发布2018-04-11 15:56:16
5290
发布2018-04-11 15:56:16
举报

预计分数: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 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 预计分数:100+60+30=190
  • 实际分数:100+60+30=190
  • 终于有一道无脑T1了哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈
    • T1
      • T2
        • T3
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档