Day2下午解题报告
预计分数：100+100+30=230
实际分数：100+100+30=230 人品爆发&&智商爆发&&手感爆发
T3数据好水，，要是把数组开大一点的话还能多得10分，，，
T1洗澡
原题，不多说了。。
当时在北京花了接近一个小时才A..
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 using namespace std;
6 const int MAXN=1e6;
7 const int INF=0x7ffff;
8 inline int read()
9 {
10 char c=getchar();int flag=1,x=0;
11 while(c<'0'||c>'9') {if(c=='-') flag=-1;c=getchar();}
12 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*flag;
13 }
14 char a[MAXN];
15 int main()
16 {
17 //freopen("shower.in","r",stdin);
18 //freopen("shower.out","w",stdout);
19 scanf("%s",a+1);
20 int l=strlen(a+1);
21 int now=0,ans=0;
22 for(int i=1;i<=l;i++)
23 {
24 if(a[i]=='(')
25 {
26 if(now==l/2) ans++,now--;//修改
27 else now++;
28 }
29 else
30 {
31 if(now==0) ans++,now++;
32 else if(now<=l/2) now--;
33 }
34 }
35 printf("%d",ans+now/2);
36 return 0;
37 }T2日记
一开始想到了70分的做法，写着写着就会100分的做法了。。
先打个素数表，
对于每次询问的n
upperbound一个值，再在k-这个值之间二分，
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+10;
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 T;
17 LL vis[MAXN];
18 LL prime[MAXN];
19 LL sprime[MAXN];
20 LL tot=0;
21 LL check(LL mid,LL n,LL k)
22 {
23 if(sprime[mid]-sprime[mid-k]<=n) return 1;
24 else return 0;
25 }
26 int main()
27 {
28 // freopen("diary.in","r",stdin);
29 // freopen("diary.out","w",stdout);
30 for(LL i=2;i<=sqrt(1e6);i++)
31 {
32 if(vis[i]==0)
33 for(LL j=i*i;j<=1e6;j+=i)
34 vis[j]=1;
35 }
36 for(LL i=2;i<=1e6;i++) if(vis[i]==0)
37 prime[++tot]=i;
38 //for(LL i=1;i<=tot;i++)
39 // printf("%d\n",prime[i]);
40 T=read();
41 for(LL i=1;i<=tot;i++)
42 sprime[i]=sprime[i-1]+prime[i];
43 while(T--)
44 {
45 LL n=read(),k=read();
46 LL pos=upper_bound(prime+1,prime+tot+1,n)-prime;pos--;
47 LL ans=0;
48 bool flag=0;
49 LL l=k,r=pos;
50 while(l<=r)
51 {
52 LL mid=l+r>>1;
53 if(check(mid,n,k)) flag=1,ans=mid,l=mid+1;
54 else r=mid-1;
55 }
56 LL out=sprime[ans]-sprime[ans-k];
57 if(flag==1) printf("%lld\n",out);
58 else printf("-1\n");
59 }
60 return 0;
61 }T3洗衣
直觉告诉我，这题一定非常难，，
因为我连暴力都不会打，
想了几分钟，感觉30分可以做，就是比较奇葩，，，需要存2^m棵树，
代码很恶心，，不过还好没敲炸
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<queue>
6
7 using namespace std;
8 const int MAXN=1001;
9 const int INF=0x7ffff;
10 const int mod=1e9+7;
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 struct TREE
18 {
19 struct node
20 {
21 int u,v,w,nxt;
22 }edge[MAXN];
23 int head[MAXN];
24 int num;
25 int siz;//树的大小
26 int bg;//第一个节点的编号
27 TREE()
28 {
29 memset(head,-1,sizeof(head));
30 num=1;siz=1;bg=1;
31 }
32 void add_edge(int x,int y,int z)
33 {
34 edge[num].u=x;
35 edge[num].v=y;
36 edge[num].w=z;
37 edge[num].nxt=head[x];
38 head[x]=num++;
39 }
40 }tree[MAXN];
41 int treenum=0;
42 inline void merge(int t1,int n1,int t2,int n2,int val)
43 {
44 treenum++;
45 for(int i=1;i<=tree[t1].num-1;i++)
46 tree[treenum].add_edge(tree[t1].edge[i].u,tree[t1].edge[i].v,tree[t1].edge[i].w);
47 for(int i=1;i<=tree[t2].num-1;i++)
48 tree[treenum].add_edge(tree[t2].edge[i].u+tree[t1].siz,tree[t2].edge[i].v+tree[t1].siz,tree[t2].edge[i].w);
49 tree[treenum].add_edge(n1,n2+tree[t1].siz,val);
50 tree[treenum].add_edge(n2+tree[t1].siz,n1,val);
51 tree[treenum].siz=tree[t1].siz+tree[t2].siz;
52 }
53 int dis[MAXN];
54 int vis[MAXN];
55 int ans=0;
56 inline void BFS()
57 {
58 for(int k=0;k<=tree[treenum].siz-1;k++)
59 {
60 memset(dis,0,sizeof(dis));
61 memset(vis,0,sizeof(vis));
62 dis[k]=0;
63 queue<int>q;
64 q.push(k);
65 while(q.size()!=0)
66 {
67 int p=q.front();
68 q.pop();
69 for(int i=tree[treenum].head[p];i!=-1;i=tree[treenum].edge[i].nxt)
70 if(vis[tree[treenum].edge[i].v]==0)
71 vis[tree[treenum].edge[i].v]=1,
72 dis[tree[treenum].edge[i].v]=(dis[p]+tree[treenum].edge[i].w)%mod,
73 q.push(tree[treenum].edge[i].v);
74 }
75 for(int i=k+1;i<=tree[treenum].siz-1;i++)
76 ans=(ans+dis[i])%mod;
77 }
78 }
79 int main()
80 {
81 // freopen("cloth.in","r",stdin);
82 // freopen("cloth.out","w",stdout);
83 int n=read();
84 for(int i=1;i<=n;i++)
85 {
86 int a=read(),b=read(),c=read(),d=read(),e=read();
87 merge(a,c,b,d,e);
88 ans=0;
89 BFS();
90 printf("%d\n",ans);
91 }
92 return 0;
93 }100分
考虑每一棵树的组成
一棵树的答案一定包含了左边的树的答案
f[i]=f[j]+f[k]+dis[new]
考虑如何计算dis[new]
dis[i]=原来的j+新加的(左边树的大小*右边树的大小)+原来的k
原来的j=siz[j]*所有点到p1点的距离
k=siz[k]+g[k][p2]//g在第k棵树中所有点到达p的距离
考虑如何求g
dp
设i是由j,k合并而来
g[i][p]=g[j][p]+L+dis[j][p][p1]*siz[k]+g[k][p2]
——》会T会boom——》开map做记忆化搜索
dis[j][p][p3]+l+dis[k][p2][p4]记忆化搜索
总结：
这次考的好是有诸多方面的原因的。。
T1原题，T2不难，T3正解非常难，暴力需要较强的代码能力
这一套题貌似就是为我量身定做的啊233333
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-10-29 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录