Codeforces Beta Round #77 (Div. 2 Only)

2023-08-19 23:37:52

Codeforces Beta Round #77 (Div. 2 Only)

A

 #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))

 #define pb push_back

 #define eb emplace_back

 #define maxn 13000005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<char,int> pci;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=1e9+;

 /*#ifndef ONLINE_JUDGE

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

 #endif */

 int main(){

     #ifndef ONLINE_JUDGE

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

     #endif

     std::ios::sync_with_stdio(false);

     string str;

     cin>>str;

     int co=;

     vector<int>ve;

     for(int i=;i<str.length();i++){

         if(str[i]!=str[i-]){

             ve.pb(co);

             co=;

         }

         else{

             co++;

         }

     }

     ve.pb(co);

     for(int i=;i<ve.size();i++){

         if(ve[i]>=) {cout<<"YES"<<endl;return ;}

     }

     cout<<"NO"<<endl;

 }

B

dfs+二分

 #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))

 #define pb push_back

 #define eb emplace_back

 #define maxn 13000005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<char,int> pci;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=1e9+;

 /*#ifndef ONLINE_JUDGE

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

 #endif */

 ll n;

 set<ll>se;

 map<ll,int>mp;

 void Check(ll num){

     ll tmp=num;

     int qi=,si=;

     while(num){

         if(num%==){

             si++;

         }

         else if(num%==){

             qi++;

         }

         num/=;

     }

     if(si==qi&&si>){

         se.insert(tmp);

     }

 }

 void dfs(ll num){

     if(num>n*||mp[num]) return;

     mp[num]=;

     Check(num);

     dfs(num*+);

     dfs(num*+);

 }

 int main(){

     #ifndef ONLINE_JUDGE

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

     #endif

     std::ios::sync_with_stdio(false);

     cin>>n;

     dfs();

     set<ll>::iterator it;

     it=lower_bound(se.begin(),se.end(),n);

     cout<<*it<<endl;

 }

C

模拟

 #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))

 #define pb push_back

 #define eb emplace_back

 #define maxn 13000005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<char,int> pci;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=1e9+;

 /*#ifndef ONLINE_JUDGE

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

 #endif */

 const int N = ;

 string s[N], ss[N], w, ww;

 bool vis[N];

 char str;

 string change(string x) {

     for(int i = ; i < x.length(); i ++) {

         if(x[i] >= 'A' && x[i] <= 'Z') x[i] += ;

     }

     return x;

 }

 int main(){

     #ifndef ONLINE_JUDGE

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

     #endif

     std::ios::sync_with_stdio(false);

     int n;

     cin >> n;

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

         cin >> s[i];

         ss[i] = change(s[i]);

     }

     cin >> w >> str;

     ww = change(w);

     if(str >= 'A' && str <= 'Z') str += ;

     int l = ww.length();

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

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

             if(l-s[k].length() +  >= i && ww.substr(i, ss[k].length()) == ss[k]) {

                 for(int j = i; j < i + ss[k].length(); j ++) vis[j] = ;

             }

         }

     }

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

         if(vis[i]) {

             if(ww[i] == str) {

                 char tmp = 'a';

                 if(ww[i] == 'a') tmp = 'b';

                 if(w[i] >= 'A' && w[i] <= 'Z') w[i] = tmp - ;

                 else w[i] = tmp;

             } else {

                 if(w[i] >= 'A' && w[i] <= 'Z') w[i] = str - ;

                 else w[i] = str;

             }

         }

     }

     cout << w << endl;

 }

D

最短路两次Dijstra 第一次构建以花费为权值的图，第二次跑最短路

 #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))

 #define pb push_back

 #define eb emplace_back

 #define maxn 13000005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<long long,int>pli;

 typedef pair<char,int> pci;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=1e9+;

 /*#ifndef ONLINE_JUDGE

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

 #endif */

  int n,m,s,t;

  vector<pli>G[],ve[];

  vector<pli>a;

  long long dis[],vis[];

  void dijstra1(int x){

     for(int i=;i<=n;i++) dis[i]=0x3f3f3f3f3f3f3f3f,vis[i]=;

     dis[x]=;

     priority_queue<pli,vector<pli>,greater<pli>>Q;

     Q.push({,x});

     while(!Q.empty()){

         pli p=Q.top();

         Q.pop();

         int v=p.second;

         if(!vis[v]){

             vis[v]=;

             for(int i=;i<G[v].size();i++){

                 int vv=G[v][i].second;

                 long long dist=G[v][i].first+dis[v];

                 if(!vis[vv]&&dist<dis[vv]){

                     dis[vv]=dist;

                     Q.push({dis[vv],vv});

                 }

             }

         }

     }

     for(int i=;i<a.size();i++){

         if(i!=x&&a[x].second>=dis[i]){

             ve[x].pb({a[x].first,i});

         }

     }

  }

  void dijstra2(int x,int t){

     for(int i=;i<=n;i++) dis[i]=0x3f3f3f3f3f3f3f3f,vis[i]=;

     dis[x]=;

     priority_queue<pli,vector<pli>,greater<pli>>Q;

     Q.push({,x});

     while(!Q.empty()){

         pli p=Q.top();

         Q.pop();

         int v=p.second;

         if(!vis[v]){

             vis[v]=;

             for(int i=;i<ve[v].size();i++){

                 int vv=ve[v][i].second;

                 long long dist=ve[v][i].first+dis[v];

                 if(!vis[vv]&&dist<dis[vv]){

                     dis[vv]=dist;

                     Q.push({dis[vv],vv});

                 }

             }

         }

     }

     if(dis[t]==0x3f3f3f3f3f3f3f3f) cout<<-<<endl;

     else cout<<dis[t]<<endl;

  }

 int main(){

     #ifndef ONLINE_JUDGE

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

     #endif

     std::ios::sync_with_stdio(false);

     cin>>n>>m>>s>>t;

     int u,v;

     long long c;

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

         cin>>u>>v>>c;

         G[u].pb({c,v});

         G[v].pb({c,u});

     }

     a.pb({,});

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

         cin>>u>>c;

         a.pb({c,u});

     }

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

         dijstra1(i);

     }

     dijstra2(s,t);

 }

E

大数+数位DP

 #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))

 #define pb push_back

 #define eb emplace_back

 #define maxn 13000005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<long long,int>pli;

 typedef pair<char,int> pci;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long mod=1e9+;

 /*#ifndef ONLINE_JUDGE

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

 #endif */

 const int N=;

 int digit[N];

 ll dp[N][N][];

 char l[N], r[N];

 int k;

 int dfs(int len, int p, bool flag, bool limit) {

     if (len == ) return flag;

     if (limit ==  && dp[len][p][flag] != -) return dp[len][p][flag];

     int up = limit ? digit[len] : ;

     int res = ;

     rep(i, , up + ) {

         if (i !=  && i != )

             res = (res + dfs(len - , max(, p - ), flag, limit && i == up)) % mod;

         else res = (res + dfs(len - ,  * k, flag || p, limit && i == up)) % mod;

     }

     if (!limit) dp[len][p][flag] = res;

     return res;

 }

 void solve() {

     int t;

     memset(dp, -, sizeof dp);

     scanf("%d%d", &t, &k);

     while (t--) {

         scanf("%s%s", l, r);

         int len = strlen(r);

         for(int i=len;i>=;i--) digit[i] = r[len - i] - '';

         int ans = dfs(len, , , );

         len = strlen(l);

         for(int i=len;i>=;i--) digit[i] = l[len - i] - '';

         digit[]--;

         for (int i = ; digit[i] < ; i++) {

             digit[i] += ;

             digit[i + ]--;

         }

         if (digit[len] == ) len--;

         ans = (ans - dfs(len, , , ) + mod) % mod;

         printf("%d\n", ans);

     }

 }

 int main(){

     #ifndef ONLINE_JUDGE

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

     #endif

     std::ios::sync_with_stdio(false);

     solve();

 }

码农公寓

Codeforces Beta Round #77 (Div. 2 Only)

A

B

C

D

E

相关文章