锐客网

  1. 首页 > it技术 > >

Codeforces Round #262 (Div. 2)解题报告

【Codeforces Round #262 (Div. 2)解题报告】
详见：http://robotcator.logdown.com/posts/221514-codeforces-round-262-div-2
1：A. Vasya and Sockshttp://codeforces.com/contest/460/problem/A
有n双袜子，每天穿一双然后扔掉，每隔m天买一双新袜子，问最多少天后没有袜子穿。。
简单思维题：以前不注重这方面的训练，结果做了比较久，这种题自己边模拟边想。不过要多考虑trick
```c++
int main(){
int n, m;
long long ans = 0;
scanf("%d%d", &n, &m);
ans = n/m*m;
int tmp = n/m;
int left = tmp + n%m;
while(true){
ans += left/m*m;
tmp = left/m;
left = tmp+left%m;
if(left < m) break;
}
ans += left;
printf("%I64d\n", ans);
return 0;
}
```
2：B. Little Dima and Equationhttp://codeforces.com/contest/460/problem/B
题意：
```mathjax
求满足方程x = b*S(x)^{a}+c方程解 \\
0 \lt x \lt 10^{9},\ \1 \le a \le 5 ,\ \ 1 \le b \le 10000 ,\ \ -10000 \le c \le 10000\\
s(x) 为x每位数的和
```
题解：如果简单枚举x肯定超时，但是我们可以换个角度，枚举S(x)。这样就简单多了。因为根据右边就可以算出x..
```c++

int get_sum(long long x){
int ans = 0;
while(x){
ans += x%10;
x /= 10;
}
return ans;
}
int main(){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
long long ans[maxn];
int num = 0;
for(int i = 1; i <= 81; i ++){
long long tmp = 1;
for(int j = 1; j <= a; j ++) tmp *= i;
long long temp = b*tmp + c;
if(temp > 1e9) continue;
if(get_sum(temp) == i) {
ans[num++] = temp;
}
}
printf("%d\n", num);
if(num > 0) {
for(int i = 0; i < num; i ++)
printf("%I64d ", ans[i]);
printf("\n");
}
return 0;
}
```
3: C. Presenthttp://codeforces.com/contest/460/problem/C
题意：有n朵花，给出初始高度，然后可以浇m次水，每次浇水可以浇连续的w朵，每次浇水后花都会长高1个单位。问最后最矮的那朵花最大值为多少。
题解：刚开始想，首先要贪心选出最矮的花和其相邻的花浇水。然后是a_(i) 到a_(i+w-1)加一个单位。当时没想到什么好的办法，于是我就想用线段树维护区间最小值，每次找出最小值的下界。然后往右w多花都浇水。刚开始在求下界时想了好久，不过联系一维情况还是写出来了。
```c++
long long a[maxn];
long long mm[4*maxn];
int setv[4*maxn];

void build(int root, int l, int r){
int lc = 2*root, rc = 2*root+1;
if(l < r){
int mid = (l+r)/2;
build(2*root, l, mid);
build(2*root+1, mid+1, r);
mm[root] = min(mm[lc], mm[rc]);
}else{
mm[root] = a[l];
}
}

void pushdown(int root, int l, int r){
int lc = 2*root, rc = 2*root+1;
if(setv[root] > 0){
setv[lc] += setv[root];
setv[rc] += setv[root];
mm[lc] += setv[root];
mm[rc] += setv[root];
setv[root] = 0;
}
}

void pushup(int root, int l, int r){
int lc = 2*root, rc = 2*root+1;
mm[root] = min(mm[lc], mm[rc]);
}

void modify(int root, int l, int r, int x, int y, int s){
if(x <= l && r <= y){
mm[root] += s;
setv[root] += s;
}else{
pushdown(root, l, r);
int mid = (l+r)/2;
if(x <= mid) modify(2*root, l, mid, x, y, s);
if(y > mid) modify(2*root+1, mid+1, r, x, y, s);
pushup(root, l, r);
}
}

int minn;
void query(int root, int l, int r, int z){
int lc = 2*root, rc = 2*root+1 , mid = (l+r)/2;
if(l == r){
if(l < minn) minn = l;
}else{
pushdown(root, l, r);
if(mm[lc] <= z) query(lc, l, mid, z);
else query(rc, mid+1, r, z);
pushup(root, l, r);
}
}

void print(int root, int l, int r){
printf("%d %d\n", root, mm[root]);
if(l < r){
int mid = (l+r)/2;
print(2*root, l, mid);
print(2*root+1, mid+1, r);
}
}

int main(){
int w, n, m;
scanf("%d%d%d", &n, &m, &w);
for(int i = 1; i <= n; i ++)
scanf("%d", &a[i]);
memset(setv, 0, sizeof(setv));
build(1, 1, n);
//print(1, 1, n);
for(int i = 1; i <= m; i ++){
minn = inf;
query(1, 1, n, mm[1]);
//cout << minn << endl;
if(n-minn+1 < w) modify(1, 1, n, n-w+1, n, 1);
else modify(1, 1, n, minn, minn+w-1, 1);
}
printf("%I64d\n", mm[1]);
return 0;
}
```
昨晚上面两题时间还有15分钟左右，后两题没想出什么好办法。下次再补上。

    推荐阅读


    上一篇：华为OJ——字符串匹配

    下一篇：yum: Nothing to do