hdu6307 Turn Off The Light 2018 Multi-University Training Contest 1 J
4477 ワード
Turn Off The Light
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Problem Description
There are n lights aligned in a row. These lights are numbered 1 to n from left to right. Initially some of the lights are turned on. Chiaki would like to turn off all the lights. Chiaki starts from the p-th light. Each time she can go left or right (i.e. if Chiaki is at x, then she can go to x−1 or x+1) and then press the switch of the light in that position (i.e. if the light is turned on before, it will be turned off and vise versa). For each p=1,2,…,n, Chiaki would like to know the minimum steps needed to turn off all the lights.
Input
There are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case: The first line contains an integer n (2≤n≤106) -- the number of lights. The second line contains a binary string s where si=1 means the i-th light is turned on and si=0 means i-th light is turned off. It is guaranteed that the sum of all n does not exceed 107.
Output
For each test cases, output (∑i=1|s|i×zi)mod(109+7), where zi is the number of step needed when Chikai starts at the i-th light.
Sample Input
3
3
000
3
111
8
01010101
Sample Output
0
26
432
Source
2018 Multi-University Training Contest 1
△補題を始めたばかりの頃、試合の時の考えに沿って書いたが、やはり間違っていた..最後にdlsの講義とコードを参考にして、やっとやっとこの問題を理解した.
最初の位置pを教えて、左か右に一歩(1からnの範囲で移動)移動して、移動した後にスイッチを押さなければなりません(現在開いているランプを消して、現在開いていないランプをつけます)、すべてのランプをオフにする最小移動ステップ数z[p]を求め、pが1-nのときのすべての答えを求め、sum{z[i]*i}%(1 e 9+7)(1<=i<=n)を出力する
まず、起点が一番左の点を見て、私たちは貪欲に右へ行くことができます.つまり、現在の位置が1であれば、右へ一歩歩いてから左へ一歩歩いて元の位置に着くと、この時の位置の上で1は0になります.後の位置の値は逆になり、後に行けば、後の位置は自分の前の値になります.現在の位置が0の場合は、そのまま右に進みます.右側に1がなくなるまで.
例えば111 '1'11 ->1'0'1->'0'01->0'1'1->01'0'->0'0'0 単一引用符は現在位置を表すが,111,p=1の場合,z[p]=5であることが分かる.
もし私たちの初期位置pが真ん中であれば、まず左に一番左の点まで歩いて、それから上の方法でもう一度やって、あるいは一番右の点まで先に行って、上の方法を繰り返して歩いて、この2つの方法の最適値を取るのがz[p]の値です.
では、O(n^2)の作り方を簡単に知ることができます.(上記の歩き方をシミュレートしています)
O(n)をどのように最適化するかというと、クレイジーな接頭辞となります.
まず、pが一番左の点であると仮定し、最後に現れた1の位置をlastとすると、統計が必要なのは(last-p)+2*(その点に着いたとき1の点の数)であり、pからlastまで歩いた図の中でどれだけの点が1になったかを統計することに重点を置く.では、すべてのs[i]^1以降に接頭辞異和を計算します(この点まで行くにはこの点を変更しなければならないので、私たちは直接異和または1以降の接頭辞異和を計算します).これが統計的な値です.最後にp-1点の接頭辞異を判断すると、私たちが累積する答えがどの部分なのかを知ることができます.
pが中間の点である場合、s[i]の接頭辞異或を計算し、先に端に着いたとき、歩いた部分を異或にし、それから変わらない部分とつなぎ合わせて、前と同じ方法で計算すればいい.
具体的な実装の詳細はコードにあります.(最後に感謝dls)
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Problem Description
There are n lights aligned in a row. These lights are numbered 1 to n from left to right. Initially some of the lights are turned on. Chiaki would like to turn off all the lights. Chiaki starts from the p-th light. Each time she can go left or right (i.e. if Chiaki is at x, then she can go to x−1 or x+1) and then press the switch of the light in that position (i.e. if the light is turned on before, it will be turned off and vise versa). For each p=1,2,…,n, Chiaki would like to know the minimum steps needed to turn off all the lights.
Input
There are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case: The first line contains an integer n (2≤n≤106) -- the number of lights. The second line contains a binary string s where si=1 means the i-th light is turned on and si=0 means i-th light is turned off. It is guaranteed that the sum of all n does not exceed 107.
Output
For each test cases, output (∑i=1|s|i×zi)mod(109+7), where zi is the number of step needed when Chikai starts at the i-th light.
Sample Input
3
3
000
3
111
8
01010101
Sample Output
0
26
432
Source
2018 Multi-University Training Contest 1
△補題を始めたばかりの頃、試合の時の考えに沿って書いたが、やはり間違っていた..最後にdlsの講義とコードを参考にして、やっとやっとこの問題を理解した.
最初の位置pを教えて、左か右に一歩(1からnの範囲で移動)移動して、移動した後にスイッチを押さなければなりません(現在開いているランプを消して、現在開いていないランプをつけます)、すべてのランプをオフにする最小移動ステップ数z[p]を求め、pが1-nのときのすべての答えを求め、sum{z[i]*i}%(1 e 9+7)(1<=i<=n)を出力する
まず、起点が一番左の点を見て、私たちは貪欲に右へ行くことができます.つまり、現在の位置が1であれば、右へ一歩歩いてから左へ一歩歩いて元の位置に着くと、この時の位置の上で1は0になります.後の位置の値は逆になり、後に行けば、後の位置は自分の前の値になります.現在の位置が0の場合は、そのまま右に進みます.右側に1がなくなるまで.
例えば111 '1'11 ->1'0'1->'0'01->0'1'1->01'0'->0'0'0 単一引用符は現在位置を表すが,111,p=1の場合,z[p]=5であることが分かる.
もし私たちの初期位置pが真ん中であれば、まず左に一番左の点まで歩いて、それから上の方法でもう一度やって、あるいは一番右の点まで先に行って、上の方法を繰り返して歩いて、この2つの方法の最適値を取るのがz[p]の値です.
では、O(n^2)の作り方を簡単に知ることができます.(上記の歩き方をシミュレートしています)
O(n)をどのように最適化するかというと、クレイジーな接頭辞となります.
まず、pが一番左の点であると仮定し、最後に現れた1の位置をlastとすると、統計が必要なのは(last-p)+2*(その点に着いたとき1の点の数)であり、pからlastまで歩いた図の中でどれだけの点が1になったかを統計することに重点を置く.では、すべてのs[i]^1以降に接頭辞異和を計算します(この点まで行くにはこの点を変更しなければならないので、私たちは直接異和または1以降の接頭辞異和を計算します).これが統計的な値です.最後にp-1点の接頭辞異を判断すると、私たちが累積する答えがどの部分なのかを知ることができます.
pが中間の点である場合、s[i]の接頭辞異或を計算し、先に端に着いたとき、歩いた部分を異或にし、それから変わらない部分とつなぎ合わせて、前と同じ方法で計算すればいい.
具体的な実装の詳細はコードにあります.(最後に感謝dls)
#include
#include
#include
#include
#define ll long long
#define N 105
#define INF 1e9
#define MOD 1000000007
using namespace std;
int z1[N],z2[N],n,sum[N],sum1[N],num[N],num1[N],T;
char s[N],g[N];
void work(char *s,int *z){
for(int i=1;i<=n;i++) z[i]=INF;
int lst=-1,fir=n+1;
for(int i=1;i<=n;i++)
if(s[i]==1){
lst=i;if(fir==n+1) fir=i;
}
if(lst==-1) {
for(int i=1;i<=n;i++) z[i]=0;
return ;
}
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]^s[i]^1;
sum1[i]=sum1[i-1]^s[i];
num[i]=num[i-1]+sum[i];
num1[i]=num1[i-1]+sum1[i];
}
for(int i=1;i<=lst;i++){
int now=i,ans=0,now1;
if(i<=fir){
if(i==lst) {z[i]=3;continue;}
ans=lst-now;
if(sum[now-1]) ans+=2*(num[lst-1]-num[now-1]);
else ans+=2*(lst-now-num[lst-1]+num[now-1]);
if(sum[lst-1]^sum[now-1]^1) ans--;
z[i]=ans;
}else{
ans=lst-fir+now-fir;
now1=now;now=fir;
if(sum1[now-1])ans+=2*(num1[now1-1]-num1[now-1]);
else ans+=2*(now1-now-(num1[now1-1]-num1[now-1]));
if(sum1[now-1]^sum1[now1-1]^sum[now1-1]) ans+=2*(num[lst-1]-num[now1-1]);
else ans+=2*(lst-now1-(num[lst-1]-num[now1-1]));
if(sum[lst-1]^sum[now1-1]^sum1[now1-1]^sum1[fir-1]^1)ans--;
z[i]=ans;
}
}
}
int main(){
freopen("1.in","r",stdin);
scanf("%d",&T);
while(T--){
scanf("%d",&n);
scanf("%s",s+1);
for(int i=1;i<=n;i++) s[i]-='0';
for(int i=1;i<=n;i++) g[i]=s[n-i+1];
work(g,z2);
work(s,z1);
ll ans=0;
for(int i=1;i<=n;i++){
int x=min(z1[i],z2[n-i+1]);
ans=(ans+(ll)x*i%MOD)%MOD;
}
printf("%lld
",ans);
}
}