这场数学题似乎比较多,数据结构是模板题,dp题感觉挺难的。

  • 数学,gcd
  • 树链刨分,线段树
  • dp
  • 数学,几何

Ticket

 

完全水题,分类讨论即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
using namespace std;
#define ll long long
int n;
double sum, ans;
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
double a;
cin >> a;
double b;
if (sum < 100) {
sum += a;
}
else if (sum >= 100 && sum < 150) {
sum += a*0.8;
}
else if (sum >= 150 && sum < 400) {
sum += a*0.5;
}
else {
sum += a;
}
}
printf("%.2f\n", sum);
return 0;
}

 

Gcd

 

题意可转化为a+b=sum,求gcd(a,b)。

设gcd(a,b)=p;可证p为sum的最大因数。

证:

gcd(a,b)=gcd(a,a+b)=gcd(a,sum),所以只要a=p,p为最大因数,gcd(a,sum)一定最大。

而因为a,b无限制,所以a一定是可以等于p的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
ll n;
int main() {
cin >> n;
ll sum = (1 + n)*n / 2;
for (ll i = 2; i <= sqrt(sum); i++) {
if (sum%i == 0) {
cout << sum / i << endl;
return 0;
}
}
return 0;
}

 

Tree

 

树链刨分+线段树

当线段树到叶节点时更新节点,当区间和为1时不再更新这个区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+10;
struct edge{
int next,to;
}e[maxn*2];
struct node{
int l,r,ls,rs,sum,lazy;
int flag;
}a[maxn*2];
int n,m,r,rt,v[maxn],head[maxn],cnt,f[maxn],d[maxn],son[maxn],size[maxn],top[maxn],id[maxn],rk[maxn];
void add(int x,int y)
{
e[++cnt].next=head[x];
e[cnt].to=y;
head[x]=cnt;
}
void dfs1(int x)
{

size[x]=1,d[x]=d[f[x]]+1;
for(int v,i=head[x];i;i=e[i].next)
if((v=e[i].to)!=f[x])
{
f[v]=x,dfs1(v),size[x]+=size[v];
if(size[son[x]]<size[v])
son[x]=v;
}
}
void dfs2(int x,int tp)
{

top[x]=tp,id[x]=++cnt,rk[cnt]=x;
if(son[x])
dfs2(son[x],tp);
for(int v,i=head[x];i;i=e[i].next)
if((v=e[i].to)!=f[x]&&v!=son[x])
dfs2(v,v);
}
inline void pushup(int x)
{
a[x].sum=(a[a[x].ls].sum+a[a[x].rs].sum);
a[x].flag=(a[a[x].ls].flag&a[a[x].rs].flag);
}
void build(int l,int r,int x)
{

//cout<<l<<" "<<r<<endl;
a[x].flag=0;
if(l==r)
{

a[x].sum=v[rk[l]],a[x].l=a[x].r=l;
if(a[x].sum==1) a[x].flag=1;
return;
}
int mid=l+r>>1;
a[x].ls=cnt++,a[x].rs=cnt++;
build(l,mid,a[x].ls),build(mid+1,r,a[x].rs);
a[x].l=a[a[x].ls].l,a[x].r=a[a[x].rs].r;
pushup(x);
}
inline int len(int x)
{
return a[x].r-a[x].l+1;
}
inline void pushdown(int x)
{
if(a[x].lazy)
{
int ls=a[x].ls,rs=a[x].rs,lz=a[x].lazy;
(a[ls].lazy+=lz),(a[rs].lazy+=lz);
(a[ls].sum+=lz*len(ls)),(a[rs].sum+=lz*len(rs));
a[x].lazy=0;
}
}
void update(int l,int r,int x)
{
if(a[x].l>=l&&a[x].r<=r)
{
if(a[x].flag==1)
return;
}
if(a[x].l==a[x].r)
{
a[x].sum=sqrt(a[x].sum);
if(a[x].sum==1) a[x].flag=1;
return ;
}
int mid=a[x].l+a[x].r>>1;
if(mid>=l)
update(l,r,a[x].ls);
if(mid<r)
update(l,r,a[x].rs);
pushup(x);
}
int query(int l,int r,int x)
{
if(a[x].l>=l&&a[x].r<=r)
return a[x].sum;
pushdown(x);
int mid=a[x].l+a[x].r>>1,tot=0;
if(mid>=l)
tot+=query(l,r,a[x].ls);
if(mid<r)
tot+=query(l,r,a[x].rs);
return tot;
}
inline int sum(int x,int y)
{
int ret=0;
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]])
swap(x,y);
(ret+=query(id[top[x]],id[x],rt));
x=f[top[x]];
}
if(id[x]>id[y])
swap(x,y);
return (ret+query(id[x],id[y],rt));
}
inline void updates(int x,int y)
{
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]])
swap(x,y);
update(id[top[x]],id[x],rt);
x=f[top[x]];
}
if(id[x]>id[y])
swap(x,y);
update(id[x],id[y],rt);
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld",&v[i]);
for(int x,y,i=1;i<n;i++)
{
scanf("%lld%lld",&x,&y);
add(x,y),add(y,x);
}
r=1;
cnt=0,dfs1(r),dfs2(r,r);
cnt=0,build(1,n,rt=cnt++);
// cout<<111<<endl;
for(int op,x,y,k,i=1;i<=m;i++)
{
scanf("%lld",&op);
if(op==0)
{
k=0;
scanf("%lld%lld",&x,&y);
updates(x,y);
}
else if(op==1)
{
scanf("%lld%lld",&x,&y);
printf("%lld\n",sum(x,y));
}
/*for(int z=1;z<=n;z++)
cout<<sum(z,z)<<"# "; */
}
return 0;
}

 

String

 

dp

找了很久的题解,但发现都有些问题,虽然能AC,但是有错。

所以选择一个好理解的版本改了一下。

d[i] [j] [c]表示处理完第i个字符,已经有k段,且第i个字符为c+‘a’,总共用的最小操作数。

初始状态:

  • d[0] [1] [s[0]-‘a’]=0,因为第0个字符已经在那,不需要操作,此时就是1段。
  • d[0] [1] [c]=1,其中c!=s[0]-‘a’,表示修改第0个字符,使其变为c,需操作1次。

状态转移:

  • 不修改,新增操作数0

    • 枚举第i-1位的结尾字符c,若枚举的字符与原串第i个字符相同,段数不变,d[i] [j] [s[i]-‘a’]=min(d[i] [j] [s[i]-‘a’],d[i-1] [j] [s[i]-‘a’])
    • 不同,第i-1的段数应该为第i的段数-1,d[i] [j] [s[i]-‘a’]=min(d[i] [j] [s[i]-‘a’],d[i-1] [j-1] [c])
  • 修改,新增操作数1

    因为能改长度len,则只要在该范围内,改的长度越长,肯定是稳赚不亏的,所以我们每次都改长度len。主要注意段数的改变。

    • 枚举第i位字符c,内层再一个循环枚举第i-len位字符p,若c==p,则段数相同,d[i] [j] [c]=min(d[i] [j] [c],d[i-len] [j] [p]+1)
    • 反之第i位段数=第i-len位段数+1,d[i] [j] [c]=min(d[i] [j] [c],d[i-len] [j-1] [p]+1)。这里注意不能暴力枚举,否则会T。应该先预处理出第i-len位字符为0到25的操作数最小值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 1e5 + 5;
#define ll long long
const int INF = 0x3f3f3f3f;
int n, l, k;
string s;
int d[maxn][15][30];
int main() {
cin >> n >> l >> k;
cin >> s;
memset(d, 0x3f, sizeof(d));
for (int i = 0; i < 26; i++) {
d[0][1][i] = 1;
}
d[0][1][s[0] - 'a'] = 0;
for (int i = 1; i < n; i++) {
for (int j = 1; j <= k; j++) {
d[i][j][s[i] - 'a'] = min(d[i][j][s[i] - 'a'], d[i - 1][j][s[i] - 'a']);
for (int c = 0; c < 26; c++) {
if (c != s[i] - 'a') {
d[i][j][s[i] - 'a'] = min(d[i][j][s[i] - 'a'], d[i - 1][j - 1][c]);
}
}
int bef = max(0, i - l);
int mn = d[bef][j - 1][0];
for (int i = 1; i < 26; i++) {
mn = min(d[bef][j - 1][i], mn);
}
for (int c = 0; c < 26; c++) {
d[i][j][c] = min(d[i][j][c], d[bef][j][c] + 1);
d[i][j][c] = min(d[i][j][c], mn + 1);
}
}
}
int ans = INF;
for (int i = 1; i <= k; i++) {
for (int j = 0; j < 26; j++) {
ans = min(ans, d[n - 1][i][j]);
}
}
cout << ans << endl;
return 0;
}

 

Circle

 

数学题,几何

先把原先的正多边形面积求出来,再加上新的三角形面积S=12absincS=\frac{1}{2}ab\sin c

新加的点一定是在两个相邻点正中间的,其实由对称性也可以猜出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const double pi = acos(-1);
double n;
int main()
{
while (cin>>n)
{
double t1 = sin(2 * pi*1.0 / n);
double t2 = sin(pi*1.0 / n);
double ans = (double)(n - 1) / 2.0*t1*1.0 + t2*1.0;
printf("%.6lf\n", ans);
}
return 0;
}

 

Clock

 

先处理数据,把时分秒全变为秒,以0:00为零点,重新画图。

最后结果一秒等于6度。

共4种情况:

  • 一直顺时针转
  • 一直逆时针转
  • 先顺时针,再逆时针
  • 先逆时针,再顺时针

前两种情况容易,后面两种需要枚举。

以先逆时针为例:

枚举除初始位置外每一个点作为逆时针的终点。

结果=360°-(枚举的点-该点逆时针方向最近点)+(初始位置-枚举的点)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<bits/stdc++.h>
#define INF 0x3F3F3F3F
#define endl '\n'
#define css(n) cout<<setiosflags(ios::fixed)<<setprecision(n);
#define sd(a) scanf("%d",&a)
#define sld(a) scanf("%lld",&a)
#define m(a,b) memset(a,b,sizeof a)
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int n,m;
int t;
int tn(int x)
{
int z=x%12;
return z;
}
struct node
{
int shun;
int ni;
int a,b,c;
int num;
}dian[90000];
int tim(int h,int m,int s)
{
int zz=h*3600+m*60+s;
return zz;
}
bool comp(node a,node b)
{
return a.shun<b.shun;
}
int main()
{
sd(n);
int qx,qy,qz;
sd(qx);sd(qy);sd(qz);
qx=tn(qx);
int qi=tim(qx,qy,qz);

// cout<<"qi"<<qi<<endl;

int n1=1;
for(int i=1;i<=n;i++)
{
int a,b,c;
sd(a);sd(b);sd(c);
a=tn(a);
dian[n1].a=a;dian[n1].b=b;dian[n1].c=c;
int zz=tim(a,b,c);

// cout<<"zz"<<zz<<endl;

int kk=zz-qi;
// cout<<"kk"<<kk<<endl;

if(kk<0)
{
dian[n1].ni=abs(kk);
dian[n1].shun=43200-dian[n1].ni;
n1++;
}
else
{
if(kk>0)
{
dian[n1].shun=kk;
// cout<<"kk>0"<<endl;
dian[n1].ni=43200-dian[i].shun;
n1++;
}
if(kk==0)
{
continue;
}
}
}
sort(dian+1,dian+n1,comp);
int mi=INF;
int ss=dian[n1-1].shun;
mi=min(ss,mi);
ss=dian[1].ni;
mi=min(ss,mi);

// cout<<n1<<"---"<<endl;
/* for(int i=1;i<n1;i++)
{
cout<<dian[i].shun<<"..."<<endl;
cout<<"ni "<<dian[i].ni<<endl;
}*/



for(int i=1;i<=n1-1;i++)//顺时针最后一个点的讨论
{
int summ=0;
summ=summ+dian[i].shun;
summ=summ+dian[i].shun;
int zzz=dian[i+1].ni;
summ=summ+zzz;
mi=min(mi,summ);
}
for(int i=n1;i>=2;i--)
{
int summ=0;
summ+=dian[i].ni*2;
summ+=dian[i-1].shun;
mi=min(mi,summ);
}
double fin=(double)mi*1.0*6.00;
// cout<<"mi"<<" "<<mi<<endl;
printf("%.2lf\n",fin);
return 0;
}