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

2017.10.2解题报告

作者头像
attack
发布2018-04-12 10:31:36
6700
发布2018-04-12 10:31:36
举报

预计分数:60+0+30=90 实际分数:60+0+0=60

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

想了五分钟,发现只会30分的做法。

后来根据暴力程序,退出了60分的容斥做法。

100分的数据范围比60分多5个0.。。。。

果断放弃。。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 const int MAXN=1001;
 7 inline void read(int &n)
 8 {
 9     char c=getchar();n=0;bool flag=0;
10     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
11     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
12 }
13 int ans[MAXN];
14 int main()
15 {
16     //freopen("a.in","r",stdin);
17     //freopen("a.out","w",stdout);
18     long long int  n,tot=0;
19     cin>>n;
20     if(n<=1000)
21     {
22         tot=0;
23         memset(ans,0,sizeof(ans));
24         for(int i=1;i<=n;i++)
25         {
26             for(int j=1;j<=i;j++)
27             {
28                 if((i%(i/j))==0&&i%j==0)    
29                 {
30                     ans[i]++;
31                     for(int k=(j*(i/j))*2;k<=n;k+=(j*(i/j)))
32                         ans[k]++;
33                 }
34             }
35         }    
36         for(int i=1;i<=n;i++)    
37             tot+=ans[i];
38         printf("%d\n",tot);    
39     }
40     else
41     {
42         cout<<(4*n+1);
43     }
44     return 0;
45 }

正解: 这道题目的实际意思是

a*b*c<=n的个数。

那么我们可以枚举a和b,统计个数,

注意 枚举的上下界

最后再减去相同的情况

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 
 5 using namespace std;
 6 
 7 long long n;
 8 
 9 #ifdef unix
10 #define LL "%lld"
11 #else
12 #define LL "%I64d"
13 #endif
14 
15 int main()
16 {
17 //    freopen("a.in","r",stdin);
18 //    freopen("a.out","w",stdout);
19 
20     scanf(LL,&n);
21     long long ans=0,tmp=0;
22     for (long long a=1,v;a*a<=(v=n/a);a++,ans++)
23         for (long long b=a+1;b*b<=v;b++)
24             tmp+=n/(a*b)-b;
25     ans+=tmp*6;
26     tmp=0;
27     for (long long a=1,v;(v=a*a)<=n;a++)
28     {
29         tmp+=n/v;
30         if (a*a<=n/a) tmp--;
31     }
32     ans+=tmp*3;
33     printf(LL "\n",ans);
34 
35     return 0;
36 }

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

一道博弈论的题,,,

还是在树上,,,,,

果断放弃,。。。。。

正解:

有一个很显然的结论:

两人都会先向公共祖先移动,

然后再占领权值大的子树

 公共祖先需要用倍增或者tarjan求

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<algorithm>
  5 
  6 using namespace std;
  7 
  8 const int maxn=100010;
  9 
 10 int n,m,en,z[maxn*3],f[maxn][20],q[maxn],depth[maxn],sum[maxn*3][2],fd[maxn],start[maxn],end[maxn],value[maxn];
 11 
 12 struct edge
 13 {
 14     int e,d;
 15     edge *next;
 16 }*v[maxn],ed[maxn<<1];
 17 
 18 void add_edge(int s,int e,int d)
 19 {
 20     en++;
 21     ed[en].next=v[s];v[s]=ed+en;v[s]->e=e;v[s]->d=d;
 22 }
 23 
 24 int get(int p,int d)
 25 {
 26     if (d==-1) return p;
 27     int x=0;
 28     while (d)
 29     {
 30         if (d&1) p=f[p][x];
 31         d>>=1;
 32         x++;
 33     }
 34     return p;
 35 }
 36 
 37 int get_lca(int p1,int p2)
 38 {
 39     if (depth[p1]<depth[p2]) swap(p1,p2);
 40     p1=get(p1,depth[p1]-depth[p2]);
 41     int x=0;
 42     while (p1!=p2)
 43     {
 44         if (!x || f[p1][x]!=f[p2][x])
 45         {
 46             p1=f[p1][x];
 47             p2=f[p2][x];
 48             x++;
 49         }
 50         else x--;
 51     }
 52     return p1;
 53 }
 54 
 55 int calc(int p1,int p2)
 56 {
 57     if (p1==f[p2][0]) return value[1]-value[p2];
 58     else return value[p1]+fd[p1];
 59 }
 60 
 61 int calcp(int p,int v)
 62 {
 63     int l=start[p]-1,r=end[p];
 64     while (l+1!=r)
 65     {
 66         int m=(l+r)>>1;
 67         if (v>z[m]) l=m;
 68         else r=m;
 69     }
 70     return r;
 71 }
 72 
 73 int main()
 74 {
 75     freopen("b.in","r",stdin);
 76     freopen("b.out","w",stdout);
 77 
 78     scanf("%d%d",&n,&m);
 79     int tot=0;
 80     for (int a=1;a<n;a++)
 81     {
 82         int s,e,d;
 83         scanf("%d%d%d",&s,&e,&d);
 84         tot+=d;
 85         add_edge(s,e,d);
 86         add_edge(e,s,d);
 87     }
 88     depth[1]=1;
 89     int front=1,tail=1;
 90     q[1]=1;
 91     for (;front<=tail;)
 92     {
 93         int now=q[front++];
 94         for (edge *e=v[now];e;e=e->next)
 95             if (!depth[e->e])
 96             {
 97                 depth[e->e]=depth[now]+1;
 98                 fd[e->e]=e->d;
 99                 f[e->e][0]=now;
100                 int p=now,x=0;
101                 while (f[p][x])
102                 {
103                     f[e->e][x+1]=f[p][x];
104                     p=f[p][x];
105                     x++;
106                 }
107                 q[++tail]=e->e;
108             }
109     }
110     int cnt=0;
111     for (int a=n;a>=1;a--)
112     {
113         int now=q[a];
114         start[now]=cnt+1;
115         for (edge *e=v[now];e;e=e->next)
116             if (depth[e->e]==depth[now]+1)
117             {
118                 z[++cnt]=value[e->e]+e->d;
119                 value[now]+=value[e->e]+e->d;
120             }
121         z[++cnt]=tot-value[now];
122         end[now]=cnt;
123         sort(z+start[now],z+end[now]+1);
124         sum[end[now]][0]=z[end[now]];
125         sum[end[now]][1]=0;
126         for (int a=end[now]-1;a>=start[now];a--)
127         {
128             sum[a][0]=sum[a+1][0];
129             sum[a][1]=sum[a+1][1];
130             if ((a&1)==(end[now]&1)) sum[a][0]+=z[a];
131             else sum[a][1]+=z[a];
132         }
133         cnt++;
134     }
135     for (int a=1;a<=m;a++)
136     {
137         int p1,p2;
138         scanf("%d%d",&p1,&p2);
139         int lca=get_lca(p1,p2);
140         int dist=depth[p1]+depth[p2]-2*depth[lca];
141         int delta=dist/2+(dist&1);
142         int px,px1,px2;
143         if (depth[p1]-depth[lca]<delta) px=get(p2,dist-delta);
144         else px=get(p1,delta);
145         if (depth[p1]-depth[lca]<delta-1) px1=get(p2,dist-delta+1);
146         else px1=get(p1,delta-1);
147         if (depth[p2]-depth[lca]<dist-delta-1) px2=get(p1,delta+1);
148         else px2=get(p2,dist-delta-1);
149         int ans=0;
150         if (p1==px)
151         {
152             if (p2==px) ans=sum[start[px]][0];
153             else
154             {
155                 int v2=calc(px2,px);
156                 int p=calcp(px,v2);
157                 ans=sum[p+1][0]+sum[start[px]][1]-sum[p][1];
158             }
159         }
160         else
161         {
162             if (p2==px)
163             {
164                 int v1=calc(px1,px);
165                 int p=calcp(px,v1);
166                 ans=v1+sum[p+1][1]+sum[start[px]][0]-sum[p][0];
167             }
168             else
169             {
170                 int v1=calc(px1,px);
171                 int pp1=calcp(px,v1);
172                 int v2=calc(px2,px);
173                 int pp2=calcp(px,v2);
174                 if (pp2==pp1) pp2++;
175                 if (pp1>pp2) swap(pp1,pp2);
176                 ans=v1+sum[pp2+1][dist&1]+sum[pp1+1][1-(dist&1)]-sum[pp2][1-(dist&1)]+sum[start[px]][dist&1]-sum[pp1][dist&1];
177             }
178         }
179         printf("%d\n",ans);
180     }
181 
182     return 0;
183 }

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

一眼看出是DP

那就好办了。

立马爆搜233333

本来以为能得30分的,结果一分没有,主要是样例给的是极限情况,这道题又没有小数据。。

所以就比较尴尬了,,,,

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cmath>
  4 #include<algorithm>
  5 #include<ctime>
  6 using namespace std;
  7 inline void read(int &n)
  8 {
  9     char c=getchar();n=0;bool flag=0;
 10     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
 11     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
 12 }
 13 int A,B,C,D,E;
 14 struct node
 15 {
 16     int num;
 17     int val[6];
 18     int happen[35];
 19 }a[7][7];
 20 //int xx1[10]={0,-1,+1,0,0,-1,+1,-1,+1};
 21 //int yy1[10]={0,0,0,-1,+1,-1,-1,+1,+1};//8
 22 //int xx2[25]={0,-2,-2,-2,-2,-2,-1,0,+1,+2,+2,+2,+2,+2,+1,0,-1};
 23 //int yy2[25]={0,-2,-1,0,+1,+2,+2,+2,+2,+2,+1,0,-1,-2,-2,-2,-2};//16
 24 int xx1[10]={0,-1,+1,0,0};
 25 int yy1[10]={0,0,0,-1,+1,};//8
 26 int xx2[25]={0,-2,+2,0,0};
 27 int yy2[25]={0,0,0,-2,+2};//16
 28 bool pd_dis(int x,int y)
 29 {
 30     if(x>=1&&x<=6&&y>=1&&y<=6)    return true;
 31     else return false;
 32 }
 33 int calc_tot_ouqi(int x,int y)
 34 {
 35     int oq=0;
 36     for(int i=2;i<=a[x][y].num;i++)    
 37         if(a[x][y].num-a[x][y].num==1)oq+=A;
 38     for(int i=1;i<=4;i++)
 39     {
 40         int wx=x+xx1[i],wy=y+yy1[i];
 41         if(pd_dis(wx,wy)==1)
 42             for(int j=1;j<=a[x][y].num;j++)
 43                 for(int k=1;k<=a[wx][wy].num;k++)
 44                 {
 45                     if(a[x][y].val[j]==a[wx][wy].val[k])    oq+=B;
 46                     if(fabs( a[x][y].val[j]-a[wx][wy].val[k] ) == 1)    oq+=C;
 47                 }
 48                     
 49     }
 50     for(int i=1;i<=4;i++)
 51     {
 52         int wx=x+xx2[i],wy=y+yy2[i];
 53         if(pd_dis(wx,wy)==1)
 54             for(int j=1;j<=a[x][y].num;j++)
 55                 for(int k=1;k<=a[wx][wy].num;k++)
 56                 {
 57                     if(a[x][y].val[j]==a[wx][wy].val[k])    oq+=D;
 58                     if(fabs( a[x][y].val[j]-a[wx][wy].val[k] ) == 1)    oq+=E;
 59                 }
 60     }
 61     return oq;
 62 }
 63 int bgoq=0;
 64 int ans=0x7fffff;
 65 int t=clock();
 66 int pd()
 67 {    
 68     bgoq=0;
 69     for(int i=1;i<=6;i++)
 70         for(int j=1;j<=6;j++)
 71             bgoq=bgoq+calc_tot_ouqi(i,j);
 72     ans=min(ans,bgoq);
 73 }
 74 void dfs(int x,int y,int havenum)
 75 {
 76     if(x==4&&y==4&&havenum==a[x][y].num+1)    
 77     {
 78         pd();    
 79         return ;
 80     }
 81     for(int i=30;i>=26;i--)
 82     {
 83         if(a[x][y].happen[i]==0)
 84         {
 85             a[x][y].happen[i]=1;
 86             a[x][y].val[havenum]=i;
 87             if(x==3&&y==3&&havenum==a[x][y].num)    dfs(3,4,1);
 88             else if(x==3&&y==4&&havenum==a[x][y].num)    dfs(4,3,1);
 89             else if(x==4&&y==3&&havenum==a[x][y].num)    dfs(4,4,1);
 90             else dfs(x,y,havenum+1);
 91             a[x][y].happen[i]=0;
 92         }
 93     }
 94 }
 95 void dfs2(int x,int y,int havenum)
 96 {
 97     if( clock()-t >=850)
 98     {
 99         printf("%d",ans/2);
100         exit(0);
101     }
102     if(x==4&&y==4&&havenum==a[x][y].num+1)    
103     {
104         pd();    
105         return ;
106     }
107     for(int i=30;i>=1;i=i-2)
108     {
109         if(a[x][y].happen[i]==0)
110         {
111             a[x][y].happen[i]=1;
112             a[x][y].val[havenum]=i;
113             if(x==3&&y==3&&havenum==a[x][y].num)    dfs2(3,4,1);
114             else if(x==3&&y==4&&havenum==a[x][y].num)    dfs2(4,3,1);
115             else if(x==4&&y==3&&havenum==a[x][y].num)    dfs2(4,4,1);
116             else dfs2(x,y,havenum+1);
117             a[x][y].happen[i]=0;
118         }
119     }
120 }
121 int main()
122 {
123     //freopen("c.in","r",stdin);
124     //freopen("c.out","w",stdout);
125     read(A);read(B);read(C);read(D);read(E);
126     for(int i=1;i<=6;i++)
127     {
128         for(int j=1;j<=6;j++)
129         {
130             int xuannum=0;
131             read(xuannum);
132             a[i][j].num=xuannum;
133             for(int k=1;k<=xuannum;k++)
134                 read(a[i][j].val[k]);
135             sort(a[i][j].val+1,a[i][j].val+xuannum+1);
136         }
137     }
138     if(a[3][3].num+a[4][3].num+a[4][4].num+a[3][4].num<=30)
139     {
140         dfs(3,3,1);
141         printf("%d",ans/2);    
142     }
143     return 0;
144 }

正解:

因为我们需要考虑的只有四个格子,那么我们用

dp[i][n1][n2][n3][n4][b1][b2][b3][b4]

表示对于第i个玄学值

转移。。。

枚举所有情况。。。

然后代码就比较美观了。。。

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<algorithm>
  5 
  6 using namespace std;
  7 
  8 #define now pre[a][b][c][d][e][s1][s2][s3][s4]
  9 #define dis(a,b,c,d) (abs(a-c)+abs(b-d))
 10 
 11 const int INF=0x3f3f3f3f;
 12 
 13 int A,B,C,D,E,num[10][10],value[10][10][10],delta[10][10][40],dp[31][6][6][6][6][2][2][2][2];
 14 
 15 char s[500];
 16 
 17 bool map[6][6][6][6];
 18 
 19 int main()
 20 {
 21     freopen("c.in","r",stdin);
 22     freopen("c.out","w",stdout);
 23 
 24     scanf("%d%d%d%d%d",&A,&B,&C,&D,&E);
 25     for (int a=0;a<6;a++)
 26     {
 27         scanf("%s",s);
 28         int p=0;
 29         for (int b=0;b<6;b++)
 30         {
 31             int px=p;
 32             while (s[px]!=']')
 33                 px++;
 34             p++;
 35             num[a][b]=s[p]-'0';
 36             p++;
 37             p++;
 38             for (int c=1;c<=num[a][b];c++)
 39             {
 40                 int v=0;
 41                 while (s[p]>='0' && s[p]<='9')
 42                 {
 43                     v=v*10+s[p]-'0';
 44                     p++;
 45                 }
 46                 value[a][b][c]=v;
 47                 p++;
 48             }
 49             p=px+1;
 50         }
 51     }
 52     int base=0;
 53     for (int a=0;a<6;a++)
 54         for (int b=0;b<6;b++)
 55             if (a>=2 && a<=3 && b>=2 && b<=3) ;
 56             else
 57             {
 58                 sort(value[a][b]+1,value[a][b]+num[a][b]+1);
 59                 for (int c=2;c<=num[a][b];c++)
 60                     if (value[a][b][c]-value[a][b][c-1]==1) base+=A;
 61                 for (int c=2;c<=3;c++)
 62                     for (int d=2;d<=3;d++)
 63                     {
 64                         if (dis(a,b,c,d)==1)
 65                         {
 66                             for (int e=1;e<=num[a][b];e++)
 67                             {
 68                                 delta[c][d][value[a][b][e]]+=B;
 69                                 delta[c][d][value[a][b][e]-1]+=C;
 70                                 delta[c][d][value[a][b][e]+1]+=C;
 71                             }
 72                         }
 73                         if (dis(a,b,c,d)==2)
 74                         {
 75                             for (int e=1;e<=num[a][b];e++)
 76                             {
 77                                 delta[c][d][value[a][b][e]]+=D;
 78                                 delta[c][d][value[a][b][e]-1]+=E;
 79                                 delta[c][d][value[a][b][e]+1]+=E;
 80                             }
 81                         }
 82                     }
 83                 for (int c=0;c<6;c++)
 84                     for (int d=0;d<6;d++)
 85                         if (dis(a,b,c,d)<=2 && (c!=a || d!=b) && !map[a][b][c][d])
 86                         {
 87                             map[a][b][c][d]=map[c][d][a][b]=true;
 88                             if (c>=2 && c<=3 && d>=2 && d<=3) ;
 89                             else
 90                             {
 91                                 int dist=dis(a,b,c,d);
 92                                 for (int e=1;e<=num[a][b];e++)
 93                                     for (int f=1;f<=num[c][d];f++)
 94                                     {
 95                                         if (abs(value[a][b][e]-value[c][d][f])==0)
 96                                         {
 97                                             if (dist==1) base+=B;
 98                                             else base+=D;
 99                                         }
100                                         if (abs(value[a][b][e]-value[c][d][f])==1)
101                                         {
102                                             if (dist==1) base+=C;
103                                             else base+=E;
104                                         }
105                                     }
106                             }
107                         }
108             }
109     memset(dp,0x3f,sizeof(dp));
110     dp[0][0][0][0][0][0][0][0][0]=base;
111     for (int a=0;a<30;a++)
112         for (int b=0;b<=num[2][2];b++)
113             for (int c=0;c<=num[2][3];c++)
114                 for (int d=0;d<=num[3][2];d++)
115                     for (int e=0;e<=num[3][3];e++)
116                         for (int s1=0;s1<=1;s1++)
117                             for (int s2=0;s2<=1;s2++)
118                                 for (int s3=0;s3<=1;s3++)
119                                     for (int s4=0;s4<=1;s4++)
120                                         if (dp[a][b][c][d][e][s1][s2][s3][s4]!=INF)
121                                         {
122                                             int v=dp[a][b][c][d][e][s1][s2][s3][s4];
123                                             for (int sx1=0;sx1<=(b!=num[2][2]);sx1++)
124                                                 for (int sx2=0;sx2<=(c!=num[2][3]);sx2++)
125                                                     for (int sx3=0;sx3<=(d!=num[3][2]);sx3++)
126                                                         for (int sx4=0;sx4<=(e!=num[3][3]);sx4++)
127                                                         {
128                                                             int wmt=0;
129                                                             if (sx1) 
130                                                             {
131                                                                 wmt+=delta[2][2][a+1];
132                                                                 if (s1) wmt+=A;
133                                                                 if (s2) wmt+=C;
134                                                                 if (s3) wmt+=C;
135                                                                 if (s4) wmt+=E;
136                                                             }
137                                                             if (sx2) 
138                                                             {
139                                                                 wmt+=delta[2][3][a+1];
140                                                                 if (s1) wmt+=C;
141                                                                 if (s2) wmt+=A;
142                                                                 if (s3) wmt+=E;
143                                                                 if (s4) wmt+=C;
144                                                             }
145                                                             if (sx3) 
146                                                             {
147                                                                 wmt+=delta[3][2][a+1];
148                                                                 if (s1) wmt+=C;
149                                                                 if (s2) wmt+=E;
150                                                                 if (s3) wmt+=A;
151                                                                 if (s4) wmt+=C;
152                                                             }
153                                                             if (sx4) 
154                                                             {
155                                                                 wmt+=delta[3][3][a+1];
156                                                                 if (s1) wmt+=E;
157                                                                 if (s2) wmt+=C;
158                                                                 if (s3) wmt+=C;
159                                                                 if (s4) wmt+=A;
160                                                             }
161                                                             if (sx1 && sx2) wmt+=B;
162                                                             if (sx1 && sx3) wmt+=B;
163                                                             if (sx1 && sx4) wmt+=D;
164                                                             if (sx2 && sx3) wmt+=D;
165                                                             if (sx2 && sx4) wmt+=B;
166                                                             if (sx3 && sx4) wmt+=B;
167                                                             int &t=dp[a+1][b+sx1][c+sx2][d+sx3][e+sx4][sx1][sx2][sx3][sx4];
168                                                             if (t>v+wmt) t=v+wmt;
169                                                         }
170                                         }
171     int ans=INF;
172     for (int a=0;a<=1;a++)
173         for (int b=0;b<=1;b++)
174             for (int c=0;c<=1;c++)
175                 for (int d=0;d<=1;d++)
176                     ans=min(ans,dp[30][num[2][2]][num[2][3]][num[3][2]][num[3][3]][a][b][c][d]);
177     printf("%d\n",ans);
178 
179     return 0;
180 }

总结:

60分,大众分吧。全程50多60分的,,

T3比较遗憾,虽然不知道怎么错的。。

两天的T3都是爆搜。。。

两天的T3都出问题,,,

爆搜明明是我擅长的东西,,

但是都出了问题,,

该好好反思反思

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

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

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • T1:https://www.luogu.org/problem/show?pid=T12865
  • T2:https://www.luogu.org/problem/show?pid=T12866
  • T3:https://www.luogu.org/problem/show?pid=T12822
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档