Codeforces Beta Round #74 (Div. 2 Only)

2023-08-19 23:38:04

Codeforces Beta Round #74 (Div. 2 Only)

A

 #include<iostream>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define sqr(x) ((x)*(x))

 #define maxn 100005

 typedef long long ll;

 typedef unsigned long long ull;

 const ull MOD=;

 /*#ifndef ONLINE_JUDGE

         freopen("1.txt","r",stdin);

 #endif */

 int num1(int n){return (n/)+(n%);}

 int main(){

     #ifndef ONLINE_JUDGE

      //   freopen("1.txt","r",stdin);

     #endif

     std::ios::sync_with_stdio(false);

     int r,g,b;

     cin>>r>>g>>b;

     int ans=max(num1(r)*-+,max(num1(g)*-+,num1(b)*-+));

     cout<<ans<<endl;

 }

B

 #include<iostream>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define sqr(x) ((x)*(x))

 #define maxn 100005

 typedef long long ll;

 typedef unsigned long long ull;

 const ull MOD=;

 /*#ifndef ONLINE_JUDGE

         freopen("1.txt","r",stdin);

 #endif */

 int n,m;

 string s[];

 int book[][];

 int main(){

     #ifndef ONLINE_JUDGE

      //   freopen("1.txt","r",stdin);

     #endif

     std::ios::sync_with_stdio(false);

     cin>>n>>m;

     for(int i=;i<n;i++) cin>>s[i];

     for(int i=;i<n;i++){

         for(int j=;j<m;j++){

             for(int k=i+;k<n;k++){

                 if(s[i][j]==s[k][j]) book[k][j]=,book[i][j]=;

             }

             for(int k=j+;k<m;k++){

                 if(s[i][j]==s[i][k]) book[i][k]=,book[i][j]=;

             }

         }

     }

     for(int i=;i<n;i++){

         for(int j=;j<m;j++){

             if(book[i][j]==) cout<<s[i][j];

         }

     }

 }

C

 #include<iostream>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define sqr(x) ((x)*(x))

 #define maxn 100005

 typedef long long ll;

 typedef unsigned long long ull;

 const ull MOD=;

 /*#ifndef ONLINE_JUDGE

         freopen("1.txt","r",stdin);

 #endif */

 int n,m,k;

 long long a;

 int main(){

     #ifndef ONLINE_JUDGE

      //   freopen("1.txt","r",stdin);

     #endif

     std::ios::sync_with_stdio(false);

     cin>>n>>m>>k;

     ll tmp=;

     for(int i=;i<=n;i++){

         cin>>a;

         if(tmp>a&&((i%)==)){

             tmp=a;

         }

     }

     ll ans=,x=n/+;

     if((n%)&&(x<=m)){

         ans=m/x*k;

         ans=min(ans,tmp);

     }

     cout<<ans<<endl;

 }

D

大模拟

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define sqr(x) ((x)*(x))

 typedef long long ll;

 typedef unsigned long long ull;

 const ull MOD=;

 /*#ifndef ONLINE_JUDGE

         freopen("1.txt","r",stdin);

 #endif */

 const int maxn = ;

 const int max_len = ;

 struct widget;

 struct Box{

     string name;

     long long x, y;

     vector<Box * > box_inside;

     vector<widget *> widget_inside;

     long long border, space;

     // type = true if Box = HBox

     bool type;

     vector<Box *> parent;

     void init(const string s, const bool t){

         //printf("init box name = %s type = %d\n", s.c_str(), t);

         //fflush(stdout);

         name = s;

         x = y = ;

         border = space = ;

         type = t;

     }

     void update();

     void pack(Box * new_parent){

         parent.push_back(new_parent);

         new_parent->box_inside.push_back(this);

         (*new_parent).update();

     }

     void set_space(const int new_space){

         space = new_space;

         update();

     }

     void set_border(const int new_border){

         border = new_border;

         update();

     }

 };

 struct widget{

     string name;

     long long x, y;

     void pack(Box * new_parent){

         new_parent->widget_inside.push_back(this);

         (*new_parent).update();

     }

     void init(const string s, const int x1, const int y1){

         name = s;

         x = x1;

         y = y1;

     }

 };

 void Box::update(){

     //printf("trying to update %s type = %d\n", name.c_str(), type);

     //fflush(stdout);

     if (type){

         x = ;

         y = ;

         for(size_t i = ; i < box_inside.size(); ++i){

             x += box_inside[i]->x;

             y = max(y, box_inside[i]->y);

         }

         for(size_t i = ; i < widget_inside.size(); ++i){

             x += widget_inside[i]->x;

             y = max(y, widget_inside[i]->y);

         }

         if (widget_inside.size() + box_inside.size() != ){

             x +=  * border + (box_inside.size() + widget_inside.size() - ) * space;

             y +=  * border;

         }

     }

     else{

         x = ;

         y = ;

         for(size_t i = ; i < box_inside.size(); ++i){

             y += box_inside[i]->y;

             x = max(x, box_inside[i]->x);

         }

         for(size_t i = ; i < widget_inside.size(); ++i){

             y += widget_inside[i]->y;

             x = max(x, widget_inside[i]->x);

         }

         if (widget_inside.size() + box_inside.size() != ){

             y +=  * border + (box_inside.size() + widget_inside.size() - ) * space;

             x +=  * border;

         }

     }

     for(size_t i = ; i < parent.size(); ++i)

         (*parent[i]).update();

 }

 struct res{

     string name;

     long long x, y;

 };

 bool comp(const res a, const res b){

     if (a.name < b.name)

         return ;

     else

         return ;

 }

 Box ar_of_box[maxn];

 widget ar_of_widget[maxn];

 int n, last_b, last_w;

 char buf[max_len];

 string s;

 res res_ar[maxn];

 int main(){

     #ifndef ONLINE_JUDGE

        // freopen("1.txt","r",stdin);

     #endif

     last_b = last_w = ;

     scanf("%d\n", &n);

     for(int i = ; i < n; ++i){

         cin.getline(buf,);

         s = buf;

         if (s.substr(, ) == "VBox")

             ar_of_box[last_b++].init(s.substr(, s.size() - ), false);

         if (s.substr(, ) == "HBox")

             ar_of_box[last_b++].init(s.substr(, s.size() - ), true);

         if (s.substr(, ) == "Widget"){

             int x, y;

             x = y = ;

             s.erase(, );

             string name = "";

             int k = ;

             while (s[k] != '('){

                 name += s[k];

                 ++k;

             }

             ++k;

             while (s[k] >= '' && s[k] <= ''){

                 x = x *  + s[k] - '';

                 ++k;

             }

             ++k;

             while (s[k] >= '' && s[k] <= ''){

                 y = y *  + s[k] - '';

                 ++k;

             }

             ar_of_widget[last_w++].init(name, x, y);

         }

         if (s.find(".pack") != s.npos){

             string name1, name2;

             name1 = name2 = "";

             int k = ;

             while (s[k] != '.'){

                 name1 += s[k];

                 ++k;

             }

             while (s[k] != '(')

                 ++k;

             ++k;

             while (s[k] != ')'){

                 name2 += s[k];

                 ++k;

             }

             Box * parent = NULL;

             for(int j = ; j < last_b; ++j)

                 if (name1 == ar_of_box[j].name)

                     parent = &ar_of_box[j];

             for(int j = ; j < last_b; ++j)

                 if (name2 == ar_of_box[j].name)

                     ar_of_box[j].pack(parent);

             for(int j = ; j < last_w; ++j)

                 if (name2 == ar_of_widget[j].name)

                     ar_of_widget[j].pack(parent);

         }

         if (s.find(".set_border") != s.npos){

             string name = "";

             int k = ;

             int border = ;

             while (s[k] != '.'){

                 name += s[k];

                 ++k;

             }

             while (s[k] != '(')

                 ++k;

             ++k;

             while (s[k] >= '' && s[k] <= ''){

                 border = border *  + s[k] - '';

                 ++k;

             }

             for(int j = ; j < last_b; ++j)

                 if (name == ar_of_box[j].name)

                     ar_of_box[j].set_border(border);

         }

         if (s.find(".set_spacing") != s.npos){

             string name = "";

             int k = ;

             int space = ;

             while (s[k] != '.'){

                 name += s[k];

                 ++k;

             }

             while (s[k] != '(')

                 ++k;

             ++k;

             while (s[k] >= '' && s[k] <= ''){

                 space = space *  + s[k] - '';

                 ++k;

             }

             for(int j = ; j < last_b; ++j)

                 if (name == ar_of_box[j].name)

                     ar_of_box[j].set_space(space);

         }

     }

     for(int i = ; i < last_b; ++i){

         res_ar[i].name = ar_of_box[i].name;

         res_ar[i].x = ar_of_box[i].x;

         res_ar[i].y = ar_of_box[i].y;

     }

     for(int i = ; i < last_w; ++i){

         res_ar[i + last_b].name = ar_of_widget[i].name;

         res_ar[i + last_b].x = ar_of_widget[i].x;

         res_ar[i + last_b].y = ar_of_widget[i].y;

     }

     sort(&res_ar[], &res_ar[last_b + last_w], comp);

     for(int i = ; i < last_b + last_w; ++i)

         printf("%s %I64d %I64d\n", res_ar[i].name.c_str(), res_ar[i].x, res_ar[i].y);

 }

E

dfs+十字链表

参考博客：https://blog.csdn.net/jnxxhzz/article/details/83067769

 #include<iostream>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define sqr(x) ((x)*(x))

 #define maxn 100005

 typedef long long ll;

 typedef unsigned long long ull;

 const ull MOD=;

 /*#ifndef ONLINE_JUDGE

         freopen("1.txt","r",stdin);

 #endif */

 int n,m;

 string s[];

 int L[],R[],U[],D[];

 void init(){///十字链表初始化

     int b,pos;

     for(int i=;i<n;i++){

         b=-;

         for(int j=;j<m;j++){

             if(s[i][j]!='.'){

                 pos=i*m+j;

                 L[pos]=b;

                 if(b!=-)

                     R[b]=pos;

                 b=pos;

             }

         }

         R[b]=-;

     }

     for(int i=;i<m;i++){

         b=-;

         for(int j=;j<n;j++){

             if(s[j][i]!='.'){

                 pos=j*m+i;

                 U[pos]=b;

                 if(b!=-){

                     D[b]=pos;

                 }

                 b=pos;

             }

         }

         D[b]=-;

     }

 }

 int dfs(int now){

     int x=now/m,y=now%m;

     if(L[now]!=-) R[L[now]]=R[now];

     if(R[now]!=-) L[R[now]]=L[now];

     if(U[now]!=-) D[U[now]]=D[now];

     if(D[now]!=-) U[D[now]]=U[now];

     int go;

     if(s[x][y]=='U') go=U[now];

     else if(s[x][y]=='D') go=D[now];

     else if(s[x][y]=='L') go=L[now];

     else if(s[x][y]=='R') go=R[now];

     if(go==-) return ;

     return dfs(go)+;

 }

 int main(){

     #ifndef ONLINE_JUDGE

      //   freopen("1.txt","r",stdin);

     #endif

     std::ios::sync_with_stdio(false);

     cin>>n>>m;

     for(int i=;i<n;i++){

         cin>>s[i];

     }

     int ans=,num=,tmp;

     for(int i=;i<n;i++){

         for(int j=;j<m;j++){

             if(s[i][j]!='.'){

                 init();

                 tmp=dfs(i*m+j);

                 if(tmp==ans) num++;

                 else if(tmp>ans){

                     ans=tmp;

                     num=;

                 }

             }

         }

     }

     cout<<ans<<" "<<num<<endl;

 }

码农公寓

Codeforces Beta Round #74 (Div. 2 Only)

A

B

C

D

E

相关文章