Day3下午解题报告
预计分数：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 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
