【清北学堂周末刷题班】 Day3
50分 A 30分 B20分
A
【问题描述】
你是能看到第一题的friends呢。
——hja
众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。
给定一个只包含乘号、加号和数字的表达式，你需要替换其中一个位置的符号将表达式变为另一个表达式（可以替换为同样的字符，但前导零是不允许的），求所有合法情况得出的表达式的值的和。
【输入格式】
一行一个字符串代表表达式。
【输出格式】
一行一个整数代表答案。
【样例输入】
233
【样例输出】
9633
【样例解释】
不合法的串仅包括033,∗33,23∗,23+,+33
【数据规模与约定】
对于40%的数据，字符串长度不超过3。
对于80%的数据，字符串长度不超过10。
对于100%的数据，字符串长度不超过100。
思路
我考试的时候大概是想的是枚举，但是枚举数据量比较大，而且代码不太好实现，比较浪费时间，所以我只写了一个40%的规模，不超过3的字符串，但是只考虑了字符数量等于三的情况，白给了10分，剩下的我还没有听回放，先鸽一下
代码
30分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
char a,b,c;
long long ans;
int main()
{
cin>>a>>b>>c;
for(int i=1;i<=9;i++)
ans+=i*100+(b-'0')*10+(c-'0');
for(int i=0;i<=9;i++)
ans+=(a-'0')*100+i*10+(c-'0');
for(int i=0;i<=9;i++)
ans+=(a-'0')*100+(b-'0')*10+i;
ans+=(a-'0')+(c-'0');
ans+=(a-'0')*(c-'0');
cout<<ans<<endl;
return 0;
}
|
100分（等待填坑）
B
【问题描述】
你是能看到第二题的friends呢。
——aoao
众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。
现在有N个任务，完成第i个任务需要ti的时间。你只有一台机器，一台机器只能完成一个任务，完成了之后就会报废；但是你有小魔仙啦啦棒，你可以使用M的时间将一台机器变为两台机器，不同机器可以同时做任务，但一个任务只能由一台机器来做，问完成所有任务所需要的最少时间？注意小魔仙啦啦棒有无数根，即如果你有多台机器，你可以同时对这多台机器使用魔法。不能对正在工作的机器使用魔法，也不能让正在施法的机器进行工作。如果一台机器已经报废，也可以对其使用魔法，但会得到一台报废的机器和一台没报废的机器。在一些机器工作的时候你可以对其他没有工作的机器使用魔法。
【输入格式】
第一行两个整数N,M。
第二行N个整数代表ti。
【输出格式】
一行一个整数代表答案。
【样例输入】
2 2
1 2
【样例输出】
4
【数据规模与约定】
对于30%的数据，N≤10
对于60%的数据，N≤20
对于另外20%的数据，所有ti相同。
对于100%的数据，1≤N≤200,1≤M,ti≤1000
思路
最开始读完题目，仔细一想，发现了题目是这样的：有N个任务，1个机器，可以对所有机器复制，复制机会无限，并且每次复制耗时为M，并且使用完的机器会报废掉。我就想到了：对于N个任务，要复制到使机器的**数量2x≥N,求一个最小的x，**然后复制时间为M∗x,接着一起执行任务，总的任务的执行时间为M∗x+max(ti)这是他的最终答案，但是这个贪心真的有问题，真的有问题，因为在复制的时候有一些情况会多出一些机器，而复制的那些时间明显同时可以执行任务，所以这样贪心一定是错误的，目标得分20分。
然后今天下午，听老师讲了，有两种思路，第一种思路为动态规划，另一种思路类似于合并果子进行贪心
动态规划
通过分析，这个实际上是棵二叉树，然后一通分析猛如虎，老师讲完，我还在原地杵，然而我并没有看懂，所以我只记住（不确定）了一个类状态转移方程
f[l][r]=maxl≤k≤r(f[l][k]+f[k+1][r]+M)
贪心
类似于合并果子，用priority_queue 优先队列，我有时间实现一下下
代码
20分垃圾代码
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
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
long long n,m;
long long t[205];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>t[i];
long long x=0;
for(int i=1;;i++)
{
if((1<<i)>=n)
{
x=i;
break;
}
}
long long maxn=-999;
for(int i=1;i<=n;i++)
maxn=max(t[i],maxn);
cout<<(long long)(x*m+maxn)<<endl;
return 0;
}
|
100分（std）再过个5，6天自己写一下
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
|
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=210;
int n,m,z[maxn],f[maxn][maxn];
int main()
{
freopen("in","r",stdin);
freopen("out","w",stdout);
scanf("%d%d",&n,&m);
for (int a=1;a<=n;a++)
scanf("%d",&z[a]);
sort(z+1,z+n+1);
memset(f,0x3f,sizeof(f));
for (int a=1;a<=n;a++)
f[a][a]=z[a];
for (int len=2;len<=n;len++)
for (int l=1,r=len;r<=n;l++,r++)
for (int k=l;k<r;k++)
f[l][r] = min(f[l][r], max(f[l][k],f[k+1][r])+m);
printf("%d\n",f[1][n]);
return 0;
}
|
C
【问题描述】
你是能看到第三题的friends呢。
——laekov
众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。
现在你有一个大小为M的数据单元，一开始M个位置上面的数都为0。现在你会不断得到一个新的数，设这个数为v，那么我们有p的概率保留这个数，如果保留这个数，则其会等概率替换掉M个位置中的任意一个；如果选择不保留这个数，则会直接扔掉这个数。现在给你N个数，问如果我们从第p1个数访问到p2这个过程结束后，我们最后得到的数据单元里面的数的和的期望是多少。
【输入格式】
第一行三个整数N,M,K代表数的个数、数据单元大小和操作次数。
接下来NN行每行三个数v,a,b，分别代表数的值和其被保留的概率为ba。
接下来K行，每行第一个整数opt代表操作类型。如果opt=1代表一组询问操作，接下来会给出p1,p2；如果opt=2，代表一组修改操作，接下来给定p,v,a,b，代表第p个位置需要被修改为值为v，概率为ba。如果opt=3代表另一种修改操作，接下来给定l,r,v，代表将第l个数到第r个数的值全部增加v，概率不变。
【输出格式】
对于每次询问操作，输出一行一个整数代表答案对109+7取模之后的结果。
【样例输入】
5 2 5
1 1 2
2 2 3
3 3 4
4 4 5
5 5 6
1 1 5
1 5 1
2 3 3 3 5
1 1 5
1 5 1
【样例输出】
735416679
656250009
751666679
515000008
【数据规模与约定】
对于20%的数据，N,K≤1000
对于另外20%的数据，M=1
对于另外20%的数据，opt=1。
对于另外20%的数据，opt=3。
对于100%的数据，1≤M≤N,K≤105,0≤a≤b≤109,1≤v≤109
思路
然而并没有听懂（到时候再回放一下）
代码
100分 （std）
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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
| #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
using namespace std;
const int BUF_SIZE = 30;
char buf[BUF_SIZE], *buf_s = buf, *buf_t = buf + 1;
#define PTR_NEXT() \
{ \
buf_s ++; \
if (buf_s == buf_t) \
{ \
buf_s = buf; \
buf_t = buf + fread(buf, 1, BUF_SIZE, stdin); \
} \
}
#define readint(_n_) \
{ \
while (*buf_s != '-' && !isdigit(*buf_s)) \
PTR_NEXT(); \
bool register _nega_ = false; \
if (*buf_s == '-') \
{ \
_nega_ = true; \
PTR_NEXT(); \
} \
int register _x_ = 0; \
while (isdigit(*buf_s)) \
{ \
_x_ = _x_ * 10 + *buf_s - '0'; \
PTR_NEXT(); \
} \
if (_nega_) \
_x_ = -_x_; \
(_n_) = (_x_); \
}
#define wmt 1,n,1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=100010;
const int mo=1000000007;
int n,m,k,invm;
int mul(int a,int b)
{
int ans=1;
while (b)
{
if (b&1) ans=1ll*ans*a%mo;
a=1ll*a*a%mo;
b>>=1;
}
return ans;
}
struct node
{
int l_to_r,r_to_l;
int prob_decay;
int col;
int lr_prob,rl_prob;
void init(int v,int a,int b)
{
int p = 1ll*a*mul(b,mo-2)%mo;
l_to_r = r_to_l = 1ll*v*p%mo;
prob_decay = (1-1ll*p*invm%mo+mo)%mo;
col = 0;
lr_prob = rl_prob = p;
}
}z[maxn<<2];
node operator+(const node &l,const node &r)
{
node p;
p.l_to_r = ( 1ll * l.l_to_r * r.prob_decay + r.l_to_r) % mo;
p.r_to_l = ( 1ll * r.r_to_l * l.prob_decay + l.r_to_l) % mo;
p.prob_decay = 1ll*l.prob_decay*r.prob_decay % mo;
p.col = 0;
p.lr_prob = (1ll * l.lr_prob * r.prob_decay + r.lr_prob)%mo;
p.rl_prob = (1ll * r.rl_prob * l.prob_decay + l.rl_prob)%mo;
return p;
}
node color(node p,int v)
{
p.col = (p.col + v)%mo;
p.l_to_r = (p.l_to_r + 1ll * p.lr_prob * v)%mo;
p.r_to_l = (p.r_to_l + 1ll * p.rl_prob * v)%mo;
return p;
}
void update(int rt)
{
z[rt] = z[rt<<1] + z[rt<<1|1];
}
void push_col(int rt)
{
z[rt<<1] = color(z[rt<<1],z[rt].col);
z[rt<<1|1] = color(z[rt<<1|1],z[rt].col);
z[rt].col=0;
}
void build(int l,int r,int rt)
{
if (l==r)
{
int v,a,b;
readint(v);
readint(a);
readint(b);
z[rt].init(v,a,b);
return;
}
int m=(l+r)>>1;
build(lson);
build(rson);
update(rt);
}
void modify(int l,int r,int rt,int p)
{
if (l==r)
{
int a,b,v;
readint(v);
readint(a);
readint(b);
z[rt].init(v,a,b);
return;
}
push_col(rt);
int m=(l+r)>>1;
if (p<=m) modify(lson,p);
else modify(rson,p);
update(rt);
}
void modify(int l,int r,int rt,int nowl,int nowr,int v)
{
if (nowl<=l && r<=nowr)
{
z[rt] = color(z[rt],v);
return;
}
push_col(rt);
int m=(l+r)>>1;
if (nowl<=m) modify(lson,nowl,nowr,v);
if (m<nowr) modify(rson,nowl,nowr,v);
update(rt);
}
node query(int l,int r,int rt,int nowl,int nowr)
{
if (nowl<=l && r<=nowr) return z[rt];
int m=(l+r)>>1;
push_col(rt);
if (nowl<=m)
{
if (m<nowr) return query(lson,nowl,nowr)+query(rson,nowl,nowr);
else return query(lson,nowl,nowr);
}
else return query(rson,nowl,nowr);
}
int main()
{
readint(n);
readint(m);
readint(k);
invm = mul(m,mo-2);
build(wmt);
for (int a=1;a<=k;a++)
{
int opt;
readint(opt);
if (opt==1)
{
int p1,p2;
readint(p1);
readint(p2);
if (p1<=p2) printf("%d\n",query(wmt,p1,p2).l_to_r);
else printf("%d\n",query(wmt,p2,p1).r_to_l);
}
else if (opt==2)
{
int p;
readint(p);
modify(wmt,p);
}
else
{
int l,r,v;
readint(l);
readint(r);
readint(v);
modify(wmt,l,r,v);
}
}
return 0;
}
|
D
【问题描述】
你是能看到第四题的friends呢。
——laekov
众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。
你需要从(0,0)出发走到(x,y)，你只能走到整点，并且你每次移动距离的平方不能超过d，问你最少需要走多少步走到(x,y)。
【输入格式】
若干行，每行三个整数x,y,d
【输出格式】
对于每组数据，输出一行代表答案。
【样例输入】
233 233 1
-1 3 9
【样例输出】
466
2
【数据范围与规定】
对于30%的数据，∣x∣,∣y∣≤100
对于60%的数据, ∣x∣,∣y∣≤1000
对于100%的数据，∣x∣,∣y∣≤109,1≤d≤109测试数据不超过100组。
思路
这道题我看到之后是想了一下算曼哈顿距离，但是很快发现不对，然后想了一下算一个欧几里得距离，然后看是否能到整点，但是由于时间问题，也没有写出来，通过老师的讲解，应该是平面凸包问题（实际上也可以不用平面凸包来做），然后再一个就是如果多画画图的话还是可以做出来的，所以以后做的时候，一定要拿笔，一定要拿笔！！！，em具体思路我还是没有太理解，看看回放吧。
代码
100分(std)
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
| #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
const int maxn=100010;
struct point
{
long long x,y;
point(){}
point(long long a,long long b){x=a;y=b;}
}p[maxn];
point operator+(const point &p1,const point &p2)
{
return point(p1.x+p2.x,p1.y+p2.y);
}
point operator-(const point &p1,const point &p2)
{
return point(p1.x-p2.x,p1.y-p2.y);
}
long long operator*(const point &p1,const point &p2)
{
return p1.x*p2.y-p1.y*p2.x;
}
int sgn(long long a)
{
if (a==0) return 0;
if (a>0) return 1;
return -1;
}
class worker {
public:
vector <int> work(vector <int> x, vector <int> y, vector <int> d) {
vector <int> res;
for (int t=0;t<x.size();t++)
{
point q=point(abs(x[t]),abs(y[t]));
int td=d[t];
if (q.x==0 && q.y==0)
{
res.push_back(0);
continue;
}
if (q.x==0 || q.y==0)
{
res.push_back((q.x+q.y-1)/(int(sqrt(td)))+1);
continue;
}
int n=0;
for (int a=0;a*a<=td;a++)
{
int b=sqrt(td-a*a);
if (a>b) break;
p[++n] = point(a,b);
while (n>2 && (p[n]-p[n-2])*(p[n-1]-p[n-2]) < 0)
{
n--;
p[n]=p[n+1];
}
}
for (int a=n+1;a<=n+n;a++)
p[a] = point(p[n+n+1-a].y,p[n+n+1-a].x);
n<<=1;
int x;
for (int a=1;a<n;a++)
if (sgn(q*p[a])*sgn(q*p[a+1])<=0)
{
x=a;
break;
}
long long l=0;
long long r=2;
if (p[x].y) r+=q.y/p[x].y;
if (p[x+1].x) r+=q.x/p[x+1].x;
while (l+1!=r)
{
long long m=(l+r)>>1;
point p1=p[x];
point p2=p[x+1];
p1.x*=m;p1.y*=m;
p2.x*=m;p2.y*=m;
if ((q-p1)*(p2-p1) >=0) r=m;
else l=m;
}
res.push_back(int(r));
}
return res;
}
};
int main()
{
worker obj;
vector<int> x;
vector<int> y;
vector<int> d;
int a,b,c;
while (~scanf("%d%d%d",&a,&b,&c))
{
x.push_back(a);
y.push_back(b);
d.push_back(c);
}
vector<int> res=obj.work(x,y,d);
for (int a=0;a<res.size();a++)
printf("%d\n",res[a]);
return 0;
}
|
总结
还好的是这一次没有爆零，毕竟我经常爆零，希望以后少爆零甚至不爆零，而且只是写暴力还是可以拿到很多的分数的，因此遇到困难的时候千万不要放弃，而且要对于比较长的题目分析一下样例之类的，在纸上多画画，多写一写，这样就能做对题目了，下一次奥利给！
