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

Day3下午解题报告

作者头像
attack
发布2018-04-11 16:08:03
7190
发布2018-04-11 16:08:03
举报

预计分数:20+40+30=90

实际分数:40+90+60=190

再次人品爆发&&手感爆发&&智商爆发

谁能告诉我为什么T1数据这么水。。

谁能告诉我为什么T2数据这么水。。

谁能告诉我为什么T3数据这么水。。

T1

https://www.luogu.org/problem/show?pid=T15476

比赛开始,果断放弃T1,。

去搞T2

最后还有40分钟的时候回来敲的T1的暴力。。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define LL int 
 7 using namespace std;
 8 const LL MAXN=1e6;
 9 const LL INF=0x7ffff;
10 const int mod=1e9+7;
11 inline LL read()
12 {
13     char c=getchar();LL 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 struct node
18 {
19     LL u,v,w,nxt;
20 }edge[MAXN];
21 LL head[MAXN];
22 LL num=1;
23 inline void add_edge(LL x,LL y)
24 {
25     edge[num].u=x;
26     edge[num].v=y;
27     num++;
28 }
29 int vis[MAXN];
30 int ans=0;
31 int n,m;
32 void dfs(int now)
33 {
34     if(now==m)
35     {
36         ans=(ans+1)%mod;
37         return ;
38     }
39     if(vis[edge[now+1].u]==0)
40     {
41         vis[edge[now+1].u]=1;
42         dfs(now+1);
43         vis[edge[now+1].u]=0;
44     }
45     if(vis[edge[now+1].v]==0)
46     {
47         vis[edge[now+1].v]=1;
48         dfs(now+1);
49         vis[edge[now+1].v]=0;
50     }
51         
52     
53 }
54 int main()
55 {
56 //    freopen("girl.in","r",stdin);
57 //    freopen("girl.out","w",stdout);
58     n=read(),m=read();
59     for(int i=1;i<=m;i++)
60     {
61         int x=read(),y=read();
62         add_edge(x,y);
63     }
64     vis[edge[1].u]=1;
65     dfs(1);
66     vis[edge[1].u]=0;
67     vis[edge[1].v]=1;
68     dfs(1);
69     printf("%d",ans);
70     return 0;
71 }
72 
73 
74 /*
75 
76 
77 5 4
78 1 2
79 3 2
80 4 5
81 4 5
82 
83 */

正解:

结论:

  • 出现大于等于两个环的时候方案数为0
  • 当时章鱼图的时候,分配方案唯一确定,方案数为2
  • 没有环的图—>树—>方案数=点数(总会有一个点没有被分配到)

并查集维护连通性

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<cctype>
  5  
  6 using namespace std;
  7 
  8 const int BUF_SIZE = 30;
  9 char buf[BUF_SIZE], *buf_s = buf, *buf_t = buf + 1;
 10   
 11 #define PTR_NEXT() \
 12     { \
 13         buf_s ++; \
 14         if (buf_s == buf_t) \
 15         { \
 16             buf_s = buf; \
 17             buf_t = buf + fread(buf, 1, BUF_SIZE, stdin); \
 18         } \
 19     }
 20    
 21 #define readint(_n_) \
 22     { \
 23         while (*buf_s != '-' && !isdigit(*buf_s)) \
 24             PTR_NEXT(); \
 25         bool register _nega_ = false; \
 26         if (*buf_s == '-') \
 27         { \
 28             _nega_ = true; \
 29             PTR_NEXT(); \
 30         } \
 31         int register _x_ = 0; \
 32         while (isdigit(*buf_s)) \
 33         { \
 34             _x_ = _x_ * 10 + *buf_s - '0'; \
 35             PTR_NEXT(); \
 36         } \
 37         if (_nega_) \
 38             _x_ = -_x_; \
 39         (_n_) = (_x_); \
 40     }
 41  
 42 const int maxn=100010;
 43 const int mo=1000000007;
 44  
 45 int n,m,en,size;
 46  
 47 bool vis[maxn],circle;
 48  
 49 struct edge
 50 {
 51     int e;
 52     edge *next;
 53 }*v[maxn],ed[maxn<<1];
 54  
 55 void add_edge(int s,int e)
 56 {
 57     en++;
 58     ed[en].next=v[s];v[s]=ed+en;v[s]->e=e;
 59 }
 60  
 61 void dfs(int now,int pre)
 62 {
 63     vis[now]=true;
 64     size++;
 65     for (edge *e=v[now];e;e=e->next)
 66         if (e->e!=pre)
 67         {
 68             if (vis[e->e]) circle=true;
 69             else dfs(e->e,now);
 70         }
 71 }
 72  
 73 int main()
 74 {
 75     freopen("girl.in","r",stdin);
 76     freopen("girl.out","w",stdout);
 77  
 78     readint(n);
 79     readint(m);
 80     for (;m--;)
 81     {
 82         int s,e;
 83         readint(s);
 84         readint(e);
 85         add_edge(s,e);
 86         add_edge(e,s);
 87     }
 88     int ans=1;
 89     for (int a=1;a<=n;a++)
 90         if (!vis[a])
 91         {
 92             circle=false;
 93             size=0;
 94             dfs(a,0);
 95             if (circle) ans=(ans<<1)%mo;
 96             else ans=(long long)ans*size%mo;
 97         }
 98     printf("%d\n",ans);
 99  
100     return 0;
101 }

T2

https://www.luogu.org/problem/show?pid=T15479

T2好水,一眼秒,,只要保证偶数位为0就好了

然后乘法原理暴力统计一下就好了。

可是超出边界的怎么处理。。。

怎么处理。。。。

50分钟过去了。。

不管了,边写边想吧。。。。

怎么处理,,,,怎么处理。。啊啊啊啊。。。。

又50分钟过去了。。

感觉自己写了一坨shit。。。。

大概长这样

谁能告诉我这份代码在干什么。。。

为什么边界这么奇怪,,

直到现在我都搞不明白这份代码是怎么过掉50分的。。。。

我自己拍的时候平均7组错一组,。。。。

玄学。。。。。

最后一个点貌似炸long long了。。。

为什么会炸long long 。。。。。

然后把所有变量都改成long long之后炸了两个点。。。。。。。。。。。。

感觉我做了假题写了假代码跑了假分数开了假longlong

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define LL long long 
 7 using namespace std;
 8 const LL MAXN=1e6;
 9 const LL INF=0x7ffff;
10 inline LL read()
11 {
12     char c=getchar();LL flag=1,x=0;
13     while(c<'0'||c>'9')    {if(c=='-')    flag=-1;c=getchar();}
14     while(c>='0'&&c<='9')     x=x*10+c-48,c=getchar();return x*flag;
15 }
16 LL fen[MAXN];
17 LL num=0;
18 LL fastpow(LL a,LL p)
19 {
20     LL base=1;
21     while(p)
22     {
23         if(p&1)    base=base*a;
24         a=a*a;
25         p>>=1;
26     }
27     return base;
28 }
29 LL ans=1;
30 LL powk[MAXN];
31 int main()
32 {
33     //freopen("endless.in","r",stdin);
34     //freopen("endless.out","w",stdout);
35     LL n=read(),k=read();
36     if(n<=10000)
37     {
38         for(LL i=0;i<=n;i++)
39         {
40             num=0;
41             LL p=i;
42             while(p)    fen[++num]=p%k,p/=k;
43             for(LL j=1;j<=num;j++)
44                 p+=fen[j]*fastpow(-k,j-1);
45             if(p==i)    
46             {
47                 //printf("%d\n",i);
48                 ans++;    
49             }
50         }
51         printf("%lld",ans-1);
52     }
53     else
54     {
55         if(n<k)    
56         {
57             printf("%lld",n+1);
58             exit(0);
59         }
60         LL p=n;
61         while(p)    fen[++num]=p%k,p/=k;
62         for(LL i=1;i<num;i++)
63             if((i-1)%2==0)    
64                 ans=ans*k;
65         if(num%2==1&&num>1)
66         ans=ans*(fen[num]+1);
67         p=1;
68         for(int i=num-1;i>=1;i--)
69         {
70             if((i%2==0&&fen[i]>0))    break;
71             if(i%2==0)    continue;
72             int cha=(k-1)-fen[i];
73             for(int j=i-1;j>=1;j--)    cha*=k;
74             p+=cha;
75         }
76         printf("%lld",ans-p+1);    
77     }
78     
79     return 0;
80 }
 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4  
 5 using namespace std;
 6 
 7 long long n,f[2][2];
 8 
 9 int k,bit[60];
10 
11 int main()
12 {
13     freopen("endless.in","r",stdin);
14     freopen("endless.out","w",stdout);
15 
16     while (~scanf("%I64d%d",&n,&k))
17     {
18         int num=0;
19         while (n)
20             bit[++num]=n%k,n/=k;
21         if (num&1) f[1][0]=bit[num],f[1][1]=1;
22         else f[1][0]=1,f[1][1]=0;
23         int now=1,last=0;
24         for (int a=num-1;a>=1;a--)
25         {
26             now^=1;last^=1;
27             if (a&1) f[now][0]=f[last][0]*k+f[last][1]*bit[a],f[now][1]=f[last][1]; 
28             else
29             {
30                 f[now][0]=f[last][0];
31                 f[now][1]=0;
32                 if (!bit[a]) f[now][1]=f[last][1];
33                 else f[now][0]+=f[last][1];
34             }
35         }
36         printf("%I64d\n",f[now][0]+f[now][1]);
37     }
38 
39     return 0;
40 }

T3 https://www.luogu.org/problemnew/show/T15479

yy了一个比暴力还暴力的解法。。

不过貌似是正解的铺垫。。

暴力维护前缀和,每次dfs

本来以为只能拿30分的,结果水到了60分233333

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 #define LL long long 
  7 using namespace std;
  8 const LL MAXN=1e6;
  9 const LL INF=0x7ffff;
 10 inline LL read()
 11 {
 12     char c=getchar();LL flag=1,x=0;
 13     while(c<'0'||c>'9')    {if(c=='-')    flag=-1;c=getchar();}
 14     while(c>='0'&&c<='9')     x=x*10+c-48,c=getchar();return x*flag;
 15 }
 16 struct node
 17 {
 18     LL u,v,w,nxt;
 19 }edge[MAXN];
 20 LL head[MAXN];
 21 LL num=1;
 22 inline void add_edge(LL x,LL y)
 23 {
 24     edge[num].u=x;
 25     edge[num].v=y;
 26     edge[num].nxt=head[x];
 27     head[x]=num++;
 28 }
 29 LL deep[MAXN];
 30 LL val[MAXN];
 31 LL a[MAXN];
 32 struct NODE
 33 {
 34     LL pos,pointval;
 35 }t[MAXN];
 36 void Make_deep(LL now)
 37 {
 38     for(LL i=head[now];i!=-1;i=edge[i].nxt)
 39     {
 40         if(deep[edge[i].v]==0)
 41             deep[edge[i].v]=deep[now]+1,
 42             val[edge[i].v]=val[now]+a[edge[i].v],
 43             t[edge[i].v].pos=edge[i].v,
 44             Make_deep(edge[i].v);
 45     }
 46 }
 47 LL comp(const NODE &a,const NODE &b)
 48 {
 49     return a.pointval>b.pointval;
 50 }
 51 void dele(LL now)
 52 {
 53     for(LL i=head[now];i!=-1;i=edge[i].nxt)
 54     {
 55         if(deep[edge[i].v]<deep[edge[i].u])
 56         {
 57             a[edge[i].v]=0,val[edge[i].v]=0,dele(edge[i].v);
 58         }
 59     }
 60 }
 61 int main()
 62 {
 63 //    freopen("tour.in","r",stdin);
 64 //    freopen("tour.out","w",stdout);
 65     LL n=read(),k=read();
 66     memset(head,-1,sizeof(head));
 67     for(LL i=1;i<=n;i++)    a[i]=read();
 68     for(LL i=1;i<=n-1;i++)
 69     {
 70         LL x=read(),y=read();
 71         add_edge(x,y);
 72         add_edge(y,x);
 73     }
 74     deep[1]=1;val[1]=a[1];t[1].pos=1;
 75     LL ans=0;
 76     while(k--)
 77     {
 78         memset(deep,0,sizeof(deep));
 79         deep[1]=1;
 80         Make_deep(1);
 81         for(LL i=1;i<=n;i++)
 82         t[i].pointval=val[t[i].pos];
 83         sort(t+1,t+n+1,comp);
 84         ans+=t[1].pointval;
 85         dele(t[1].pos);
 86         val[t[1].pos]=0;
 87         a[t[1].pos]=0;
 88     }
 89     printf("%lld",ans);
 90     return 0;
 91 }
 92 
 93 
 94 /*
 95 
 96 5 2
 97 4 3 2 1 1
 98 1 2
 99 1 5
100 2 3
101 2 4
102 //10
103 
104 
105 4 2
106 1 2 4 8
107 1 2
108 1 3
109 2 4
110 //15
111 
112 4 1
113 1 2 8 4
114 1 2
115 1 3
116 2 4
117 //9
118 */

100分:

①考虑优化,每次dfs只会影响到一条链上的权值,会影响一段连续的区间,线段树维护。

删除的时候打标机,如果曾经被删除过就不删了

②树链剖分的思想,把孩子权值最大的当做重儿子 时间复杂度:O(nlogn)

dfs序+线段树维护贪心

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<cctype>
  5 #include<algorithm>
  6  
  7 using namespace std;
  8  
  9 const int BUF_SIZE = 30;
 10 char buf[BUF_SIZE], *buf_s = buf, *buf_t = buf + 1;
 11    
 12 #define PTR_NEXT() \
 13     { \
 14         buf_s ++; \
 15         if (buf_s == buf_t) \
 16         { \
 17             buf_s = buf; \
 18             buf_t = buf + fread(buf, 1, BUF_SIZE, stdin); \
 19         } \
 20     }
 21     
 22 #define readint(_n_) \
 23     { \
 24         while (*buf_s != '-' && !isdigit(*buf_s)) \
 25             PTR_NEXT(); \
 26         bool register _nega_ = false; \
 27         if (*buf_s == '-') \
 28         { \
 29             _nega_ = true; \
 30             PTR_NEXT(); \
 31         } \
 32         int register _x_ = 0; \
 33         while (isdigit(*buf_s)) \
 34         { \
 35             _x_ = _x_ * 10 + *buf_s - '0'; \
 36             PTR_NEXT(); \
 37         } \
 38         if (_nega_) \
 39             _x_ = -_x_; \
 40         (_n_) = (_x_); \
 41     }
 42  
 43 #define wmt 1,cnt,1
 44 #define lson l,m,rt<<1
 45 #define rson m+1,r,rt<<1|1
 46  
 47 const int maxn=200010;
 48  
 49 int n,k,en,z[maxn],f[maxn],s[maxn],leaf[maxn],l[maxn],r[maxn];
 50  
 51 long long y[maxn<<2|1],col[maxn<<2|1];
 52  
 53 bool del[maxn];
 54  
 55 struct edge
 56 {
 57     int e;
 58     edge *next;
 59 }*v[maxn],*ve[maxn],ed[maxn];
 60  
 61 inline void add_edge(int s,int e)
 62 {
 63     en++;
 64     ed[en].next=v[s];v[s]=ed+en;v[s]->e=e;
 65 }
 66  
 67 #define update(rt) y[rt]=max(y[rt<<1],y[rt<<1|1]);
 68  
 69 #define push_col(rt)\
 70     if (col[rt])\
 71     {\
 72         col[rt<<1]+=col[rt];y[rt<<1]+=col[rt];\
 73         col[rt<<1|1]+=col[rt];y[rt<<1|1]+=col[rt];\
 74         col[rt]=0;\
 75     }
 76  
 77 inline void modify(int l,int r,int rt,int nowl,int nowr,int delta)
 78 {
 79     if (nowl<=l && r<=nowr)
 80     {
 81         y[rt]+=delta;
 82         col[rt]+=delta;
 83         return;
 84     }
 85     push_col(rt);
 86     int m=(l+r)>>1;
 87     if (nowl<=m) modify(lson,nowl,nowr,delta);
 88     if (m<nowr) modify(rson,nowl,nowr,delta);
 89     update(rt);
 90 }
 91  
 92 inline int query(int l,int r,int rt)
 93 {
 94     if (l==r) return l;
 95     push_col(rt);
 96     int m=(l+r)>>1;
 97     if (y[rt<<1]>y[rt<<1|1]) return query(lson);
 98     else return query(rson);
 99 }
100  
101 int main()
102 {
103     freopen("tour.in","r",stdin);
104     freopen("tour.out","w",stdout);
105 
106     readint(n);
107     readint(k);
108     for (int a=1;a<=n;a++)
109     {
110         readint(z[a]);
111     }
112     for (int a=1;a<n;a++)
113     {
114         int p1,p2;
115         readint(p1);
116         readint(p2);
117         f[p2]=p1;
118         add_edge(p1,p2);
119     }
120     int root;
121     for (int a=1;a<=n;a++)
122         if (!f[a]) root=a;
123     int size=1;
124     s[1]=root;
125     for (int a=1;a<=n;a++)
126         ve[a]=v[a];
127     memset(l,0x3f,sizeof(l));
128     int cnt=0;
129     while (size)
130     {
131         int now=s[size];
132         if (!ve[now])
133         {
134             if (!v[now]) 
135             {
136                 l[now]=r[now]=++cnt;
137                 leaf[cnt]=now;
138             }
139             l[f[now]]=min(l[f[now]],l[now]);
140             r[f[now]]=max(r[f[now]],r[now]);
141             size--;
142         }
143         else
144         {
145             size++;
146             s[size]=ve[now]->e;
147             ve[now]=ve[now]->next;
148         }
149     }
150     for (int a=1;a<=n;a++)
151         modify(wmt,l[a],r[a],z[a]);
152     k=min(k,cnt);
153     long long ans=0;
154     for (int a=1;a<=k;a++)
155     {
156         int p=query(wmt);
157         p=leaf[p];
158         while (!del[p] && p)
159         {
160             modify(wmt,l[p],r[p],-z[p]);
161             ans+=z[p];
162             del[p]=true;
163             p=f[p];
164         }
165     }
166     printf("%I64d\n",ans);
167  
168     return 0;
169 }

总结

这一场比赛可以用两个字来评价

玄学

我感觉这场比赛题目难道炸,但是有7.8个AK的。。,

我感觉我的小伙伴们都应该考的不错,但是gryz集体考炸。。

我感觉我会挂成SB,但是莫名其妙多得100分。。

玄学。。。。。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017-10-30 ,如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 预计分数:20+40+30=90
  • 实际分数:40+90+60=190
  • T1
  • T2
  • T3 https://www.luogu.org/problemnew/show/T15479
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档