Codeforces Round #312 (Div. 2) A B C D E
8890 ワード
A Lala Land and Apple Trees
シミュレーション.
B Amr and The Large Array
尺取り法
C Amr and Chemistry
n個の数で、毎回1個の数に対して操作します.2を乗算し、2を除去する2つの操作があります.少なくとも何回操作すれば、すべてのn個の数を等しくすることができますか.
暴力.ある数については,操作により100000以内の数が得られ,最大log^2(100000)である.到達可能なすべての数に必要な最小ステップを二重サイクルで計算することができます.それからすべての数が達成できる数を考察して、最小の答えを探します.
D Guess Your Way Out! II
高さhの満二叉木.ノードは上から下へ左から右に番号を付け、ルートから葉まで経路に沿って下ります.q個の問合せがあり,各問合せで得られた情報はi層目に区間[l,r]が通っているか否かである.質問の答えが矛盾しているかどうか、および質問が唯一の結果を十分に得ているかどうかを判断する.
YesとNoの2つの質問を分けてlrダブルキーワードを昇順に並べ替えます.イエスと答えた質問を先に処理し、ユニークでない区間を得たら矛盾する.そしてNoと答えた質問を処理し,その区間を縮小し,区間を1に縮小すれば一意解があり,そうでなければ質問が不十分である.最後に、Yesの答えが満たされているかどうかを判断する矛盾も判断しなければならない.コードを参照してください.
E A Simple Task
小文字を含む文字列で、q回の操作があり、操作ごとに昇順または降順に1つの区間をソートします.操作した後の列を求めます.
26文字に対してそれぞれ線分の木を建てて、区間を維持してどれだけのこの文字があります.メンテナンス方法は、昇順ソート、クエリー区間の「a」の数など、カウントソートのような方法を使用して、一番前に置いてbcdをクエリーします.
シミュレーション.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
pair<int,int> a[110];
int main(){
int n;
cin>>n;
a[0]=make_pair(0,0);
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
a[i]=make_pair(x,y);
}
sort(a,a+n+1);
int k;
for(k=0;k<=n;k++){
if(a[k].first==0)break;
}
int p=0;
int ans=0;
while(1){
p++;
if(k+p>n)break;
if(k-p<0)break;
ans+=a[k+p].second;
ans+=a[k-p].second;
}
if(k+p<=n)ans+=a[k+p].second;
if(k-p>=0)ans+=a[k-p].second;
cout<<ans<<endl;
return 0;
}B Amr and The Large Array
尺取り法
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int cnt[1000010];
int a[100010];
int main(){
int n;
cin>>n;
int MAX=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
cnt[a[i]]++;
MAX=max(MAX,cnt[a[i]]);
}
int l=0,r=0;
int cur=0;
memset(cnt,0,sizeof(cnt));
int ans=1e9;
int ansl,ansr;
while(1){
if(cur<MAX){
r++;
if(r>n)break;
cnt[a[r]]++;
cur=max(cur,cnt[a[r]]);
}else{
if(r-l<ans){
ans=r-l;
ansr=r; ansl=l;
}
l++;
cnt[a[l]]--;
if(cnt[a[l]]==MAX-1){
cur--;
}
}
}
cout<<ansl+1<<" "<<ansr<<endl;
return 0;
}C Amr and Chemistry
n個の数で、毎回1個の数に対して操作します.2を乗算し、2を除去する2つの操作があります.少なくとも何回操作すれば、すべてのn個の数を等しくすることができますか.
暴力.ある数については,操作により100000以内の数が得られ,最大log^2(100000)である.到達可能なすべての数に必要な最小ステップを二重サイクルで計算することができます.それからすべての数が達成できる数を考察して、最小の答えを探します.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
using namespace std;
int a[100010];
int cnt[100010]; // n i
int ans[100010];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
int rightcarry=0; // ，
while(1){
int tmp=a[i];
tmp>>=rightcarry;
if(tmp==0)break;
cnt[tmp]++;
ans[tmp]+=rightcarry;
if(rightcarry){
if( (a[i]>>(rightcarry-1)) == (tmp<<1) ){
rightcarry++;
continue;
}
}
int c=0;
while(1){
c++;
tmp<<=1;
if(tmp>100000)break;
cnt[tmp]++;
ans[tmp]+=(rightcarry+c);
}
rightcarry++;
}
}
int re=1e9;
for(int i=1;i<=100000;i++){
if(cnt[i]==n){ // i
if(ans[i]<re)re=ans[i];
}
}
cout<<re<<endl;
return 0;
}D Guess Your Way Out! II
高さhの満二叉木.ノードは上から下へ左から右に番号を付け、ルートから葉まで経路に沿って下ります.q個の問合せがあり,各問合せで得られた情報はi層目に区間[l,r]が通っているか否かである.質問の答えが矛盾しているかどうか、および質問が唯一の結果を十分に得ているかどうかを判断する.
YesとNoの2つの質問を分けてlrダブルキーワードを昇順に並べ替えます.イエスと答えた質問を先に処理し、ユニークでない区間を得たら矛盾する.そしてNoと答えた質問を処理し,その区間を縮小し,区間を1に縮小すれば一意解があり,そうでなければ質問が不十分である.最後に、Yesの答えが満たされているかどうかを判断する矛盾も判断しなければならない.コードを参照してください.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
ll l,r;;
node(){}
node(ll l,ll r):l(l),r(r){}
bool operator<(const node& other)const{
if(l==other.l)return r<other.r;
return l<other.l;
}
};
node Yes[100010];
node No[100010];
int main(){
int h,q;
cin>>h>>q;
int pYes=0;
int pNo=0;
for(int i=1;i<=q;i++){
int x,ans;
ll l,r;
scanf("%d%I64d%I64d%d",&x,&l,&r,&ans);
//
for(int hh=x;hh<h;hh++){
l<<=1;
r<<=1;
r|=1;
}
if(ans){
pYes++;
Yes[pYes].l=l;
Yes[pYes].r=r;
}else{
pNo++;
No[pNo].l=l;
No[pNo].r=r;
}
}
sort(Yes+1,Yes+pYes+1);
sort(No+1,No+pNo+1);
bool cheated=0;
bool mulsol=0;
set<node> ans; // ,
// Yes
ll l=Yes[1].l,r=Yes[1].r;
for(int i=2;i<=pYes;i++){
if(Yes[i].l>r){
cheated=1;
}else{
l=Yes[i].l;
r=min(r,Yes[i].r);
}
}
if(pYes==0){ // Yes ,
l=1LL<<(h-1);
r=(1LL<<(h))-1;
}
// No
for(int i=1;i<=pNo;i++){
if(i<pNo&&No[i].r>=No[i+1].l){
No[i+1].l=No[i].l;
No[i+1].r=max(No[i].r,No[i+1].r);
continue;
}
if(No[i].r<l){
continue;
}else{
if(No[i].l>l){
// , r
ans.insert(node(l,min(r,No[i].l-1) ));
}
l=No[i].r+1;
if(l>r)break;
}
}
//
if(l<=r)ans.insert(node(l,r));
for(int i=1;i<=pYes;i++){
set<node>::iterator it=ans.lower_bound(Yes[i]);
bool ok=0;
if(it!=ans.end()&&it->l<=Yes[i].r){
ok=1;
}
if(it!=ans.begin()){
it--;
if(it->r>=Yes[i].l)ok=1;
}
if(!ok){
cheated=1;break;
}
}
ll re;
if(ans.size()==1&&ans.begin()->l==ans.begin()->r){
re=ans.begin()->l;
}else{
mulsol=1;
}
if(ans.size()==0)cheated=1;
if(cheated){
cout<<"Game cheated!"<<endl;
}else if(mulsol){
cout<<"Data not sufficient!"<<endl;
}else{
cout<<re<<endl;
}
return 0;
}
E A Simple Task
小文字を含む文字列で、q回の操作があり、操作ごとに昇順または降順に1つの区間をソートします.操作した後の列を求めます.
26文字に対してそれぞれ線分の木を建てて、区間を維持してどれだけのこの文字があります.メンテナンス方法は、昇順ソート、クエリー区間の「a」の数など、カウントソートのような方法を使用して、一番前に置いてbcdをクエリーします.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
int l,r;
int val;
int lazy; //
}tree[26][400010];
char str[100010];
void push_up(int which,int n){
tree[which][n].val = tree[which][n<<1].val+tree[which][(n<<1)|1].val;
}
void push_down(int which,int n){
int val=tree[which][n].val;
if(tree[which][n].l==tree[which][n].r)return;
if(tree[which][n].lazy==-1){
int llen=tree[which][n<<1].r-tree[which][n<<1].l+1;
if(val>llen){
tree[which][n<<1].val=llen;
tree[which][(n<<1)|1].val=val-llen;
}else{
tree[which][n<<1].val=val;
tree[which][(n<<1)|1].val=0;
}
}
if(tree[which][n].lazy==1){
int rlen=tree[which][(n<<1)|1].r-tree[which][(n<<1)|1].l+1;
if(val>rlen){
tree[which][(n<<1)|1].val=rlen;
tree[which][n<<1].val=val-rlen;
}else{
tree[which][(n<<1)|1].val=val;
tree[which][n<<1].val=0;
}
}
tree[which][n<<1].lazy=tree[which][n].lazy;
tree[which][(n<<1)|1].lazy=tree[which][n].lazy;
tree[which][n].lazy=0;
}
void build_tree(int which,int n,int l,int r){
tree[which][n].l=l; tree[which][n].r=r;
if(l==r){
if(str[l]==which+'a'){
tree[which][n].val=1;
}
return;
}
int mid=(l+r)>>1;
build_tree(which,n<<1,l,mid);
build_tree(which,(n<<1)|1,mid+1,r);
push_up(which,n);
}
int query(int which,int n,int l,int r){
if(tree[which][n].l==l&&tree[which][n].r==r){
return tree[which][n].val;
}
int mid=(tree[which][n].l+tree[which][n].r)>>1;
if(tree[which][n].lazy){
push_down(which,n);
}
if(r<=mid){
return query(which,n<<1,l,r);
}else{
if(l>mid){
return query(which,(n<<1)|1,l,r);
}else{
return query(which,n<<1,l,mid)+
query(which,(n<<1)|1,mid+1,r);
}
}
}
void update(int which,int n,int l,int r,int val,int lr){
if(l>r)return;
if(tree[which][n].l==l&&tree[which][n].r==r){
tree[which][n].lazy=lr;
tree[which][n].val=val;
return;
}
int mid=(tree[which][n].l+tree[which][n].r)>>1;
if(tree[which][n].lazy){
push_down(which,n);
}
if(r<=mid){
update(which,n<<1,l,r,val,lr);
}else{
if(l>mid){
update(which,(n<<1)|1,l,r,val,lr);
}else{
if(lr==-1){ //
int lval=min(val,tree[which][n<<1].r-l+1);
int rval=val-lval;
update(which,n<<1,l,mid,lval,lr);
update(which,(n<<1)|1,mid+1,r,rval,lr);
}else{ //
int rval=min(val,r-tree[which][(n<<1)|1].l+1);
int lval=val-rval;
update(which,(n<<1)|1,mid+1,r,rval,lr);
update(which,n<<1,l,mid,lval,lr);
}
}
}
push_up(which,n);
}
int main(){
int n,q;
cin>>n>>q;
scanf("%s",str+1);
for(int i=0;i<26;i++){
build_tree(i,1,1,n);
}
for(int i=1;i<=q;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
int cnt[26];
for(int ch=0;ch<26;ch++){
cnt[ch]=query(ch,1,x,y);
}
int l=x,r=y;
if(z==0){ //
for(int ch=0;ch<26;ch++){
if(cnt[ch]==0)continue;
update(ch,1,r-cnt[ch]+1,r,cnt[ch],1);
update(ch,1,r+1,y,0,1);
r-=cnt[ch];
update(ch,1,x,r,0,1);
}
}else{ //
for(int ch=0;ch<26;ch++){
if(cnt[ch]==0)continue;
update(ch,1,l,l+cnt[ch]-1,cnt[ch],-1);
update(ch,1,x,l-1,0,-1);
l+=cnt[ch];
update(ch,1,l,y,0,-1);
}
}
}
for(int i=1;i<=n;i++){
for(int ch=0;ch<26;ch++){
if(query(ch,1,i,i)){
str[i]=ch+'a';
break;
}
}
}
printf("%s
",str+1);
return 0;
}