预计分数:60+0+30=90 实际分数:60+0+0=60
想了五分钟,发现只会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 }
一道博弈论的题,,,
还是在树上,,,,,
果断放弃,。。。。。
正解:
有一个很显然的结论:
两人都会先向公共祖先移动,
然后再占领权值大的子树
公共祖先需要用倍增或者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 }
一眼看出是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都出问题,,,
爆搜明明是我擅长的东西,,
但是都出了问题,,
该好好反思反思