Codeforces Round #262 (ディビジョン 2)問題解決レポート_html/css_WEB-ITnose

詳細については、以下を参照してください: http://robotcator.logdown.com/posts/221514-codeforces-round-262-div-2

1: A. Vasya と Socks http://codeforces.com/contest/ 460/問題/A

靴下は n 足あります。毎日 1 足履いてから、m 日ごとに新しい靴下を購入します。靴下を履かないのに最長何日かかりますか。 。
単純な思考の質問: 以前はこの分野のトレーニングに注意を払っていませんでしたが、結局この種の質問をシミュレーションして自分で考えました。ただし、トリックについてはもっと考える必要があります
```c++
int main(){
int n, m;
scanf("%d%d", &n, &m); = n/m *m;
int left = tmp + n%m;
ans += left/m*m; = tmp+left %m;
if(left < m) ブレーク;
ans += left;
return 0;
2: B. Little Dima と方程式 http://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 は右辺に基づいて計算できるからです。 /= 10;
}
戻り値
}
int a, b, c;
long long ans[ maxn];
int num = 0;
for(int i = 1; i long long tmp = 1;
for(int j = 1; j long long temp = b*tmp + c;
if(temp > 1e9) {
ans[num++] = temp; }
}
printf("%dn", num);
if(num > 0) {
for(int i = 0; i printf("%I64d ", ans[ i]);
printf("n");
}
return 0;
`` 3: C. 現在 http://codeforces.com/contest/460/problem/C
質問: n があります花、最初の高さが与えられ、その後、水やりごとに w 連続した花に水を注ぐことができ、花の高さは 1 単位成長します。最後にある最も短い花の最大値がいくらであるかを尋ねます。
解決策: 最初にそれを考えるときは、まず最も背の低い花とその隣接する花を貪欲に選択して水やりをする必要があります。次に、a_(i) から a_(i+w-1) に 1 単位を加えます。当時は良い方法が思いつかなかったので、線分ツリーを使って間隔の最小値を維持し、毎回最小値の下限を求める方法を考えました。それから右側の花すべてに水をあげますw。最初に下限を見つけたときは長い間考えましたが、それでも一次元の状況と関連付けて書き出しました。
```c++
long long a[maxn];
int setv[4*maxn];
int lc = 2*root, rc = 2*root+1;
if(l < r){
int Mid = (l+r)/2;
build(2*root, l, mid); *root+1,mid+1,r);
mm[root] = min(mm[lc], mm[rc]);
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[rc] += setv[root]; }
}

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

voidmodify(int root, int l, int r, int x, int y, int s){
if(x mm[root] += s;
setv[ルート] += s;
プッシュダウン(ルート, l, r);
if(x if(y>mid)modify(2*root+1,mid+1,r,x,y,s); 、r);
}
}

int ミン;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 }else{
Pushdown(root, l, r);
if(mm[lc] 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 scanf("%d", &a[i]);
memset(setv, 0, sizeof(setv));
build(1, 1, n);
// print(1, 1, n);
for(int i = 1; i minn = inf;
query(1, 1, n, mm[1]);
//cout <<分 <<終わり;
if(n-minn+1 elsemodify(1, 1, n, minn, minn+w-1, 1);
}
printf("%I64dn", mm[1]);
0 を返します。 次はまた上です。