Codeforces Round #262 (Div. 2)Problem Solution Report_html/css_WEB-ITnose

For details, see: http://robotcator.logdown.com/posts/221514-codeforces-round-262-div-2

1: A. Vasya and Socks http: //codeforces.com/contest/460/problem/A

There are n pairs of socks. Wear one pair every day and then throw it away. Buy a new pair of socks every m days. How many days can you go without wearing socks? .
Simple thinking questions: I didn’t pay much attention to training in this area before, but I ended up doing it for a long time. I simulated this kind of questions and thought about it myself. But think more about the 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("%I64dn", ans);
return 0;
}
```
2: B. Little Dima and Equation http://codeforces.com/contest/460/problem /B
Meaning of the question:
```mathjax
Find the solution to the equation 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) is the sum of each digit of x
```
Solution: If x is simply enumerated, it must Timeout, but we can change the angle and enumerate S(x). This is much simpler. Because x can be calculated based on the right hand side..
```c

int get_sum(long long x){
int ans = 0;
while(x){
ans = x;
x /= 10;
}
return ans; %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("%dn", num);
if(num > 0) {
for(int i = 0; i < num; i )
printf("%I64d ", ans[i]);
printf("n");
}
return 0;
}
```
3: C. Present http://codeforces.com/contest/460/problem/C
Question meaning: There are n flowers, given the initial height, and then water can be poured m times. Each watering can be watered with w consecutive flowers. After each watering, the flower will grow 1 unit in height. Ask what the maximum value of the shortest flower at the end is.
Solution: When you first think about it, you must first greedily select the shortest flower and water its adjacent flowers. Then a_(i) to a_(i w-1) plus one unit. I didn't think of any good way at the time, so I wanted to use a line segment tree to maintain the minimum value of the interval and find the lower bound of the minimum value every time. Then water all the flowers on the right w. I thought about it for a long time when I first found the lower bound, but I still wrote it out in conjunction with the one-dimensional situation.
```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 %dn", 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("%I64dn", mm[1]);
  return 0;
}
```
昨晚上面两题时间还有15分钟左右，后两题没想出什么好办法。下次再补上。