Codeforces Beta Round #77 (Div. 2 Only)

A

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 13000005
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef pair<int,int> pii;
14 typedef pair<char,int> pci;
15 typedef pair<pair<int,string>,pii> ppp;
16 typedef unsigned long long ull;
17 const long long MOD=1e9+7;
18 /*#ifndef ONLINE_JUDGE
19         freopen("1.txt","r",stdin);
20 #endif */
21 
22 
23 
24 int main(){
25     #ifndef ONLINE_JUDGE
26      //   freopen("1.txt","r",stdin);
27     #endif
28     std::ios::sync_with_stdio(false);
29     string str;
30     cin>>str;
31     int co=1;
32     vector<int>ve;
33     for(int i=1;i<str.length();i++){
34         if(str[i]!=str[i-1]){
35             ve.pb(co);
36             co=1;
37         }
38         else{
39             co++;
40         }
41     }
42     ve.pb(co);
43     for(int i=0;i<ve.size();i++){
44         if(ve[i]>=7) {cout<<"YES"<<endl;return 0;}
45     }
46     cout<<"NO"<<endl;
47 }

View Code

B

dfs+二分

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 13000005
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef pair<int,int> pii;
14 typedef pair<char,int> pci;
15 typedef pair<pair<int,string>,pii> ppp;
16 typedef unsigned long long ull;
17 const long long MOD=1e9+7;
18 /*#ifndef ONLINE_JUDGE
19         freopen("1.txt","r",stdin);
20 #endif */
21 
22 ll n;
23 
24 set<ll>se;
25 map<ll,int>mp;
26 
27 void Check(ll num){
28     ll tmp=num;
29     int qi=0,si=0;
30     while(num){
31         if(num%10==4){
32             si++;
33         }
34         else if(num%10==7){
35             qi++;
36         }
37         num/=10;
38     }
39     if(si==qi&&si>0){
40         se.insert(tmp);
41     }
42 }
43 
44 void dfs(ll num){
45     if(num>n*100000||mp[num]) return;
46     mp[num]=1;
47     Check(num);
48     dfs(num*10+4);
49     dfs(num*10+7);
50 }
51 
52 
53 int main(){
54     #ifndef ONLINE_JUDGE
55      //   freopen("1.txt","r",stdin);
56     #endif
57     std::ios::sync_with_stdio(false);
58     cin>>n;
59     dfs(0);
60     set<ll>::iterator it;
61     it=lower_bound(se.begin(),se.end(),n);
62     cout<<*it<<endl;
63 }

View Code

C

模拟

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 13000005
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef pair<int,int> pii;
14 typedef pair<char,int> pci;
15 typedef pair<pair<int,string>,pii> ppp;
16 typedef unsigned long long ull;
17 const long long MOD=1e9+7;
18 /*#ifndef ONLINE_JUDGE
19         freopen("1.txt","r",stdin);
20 #endif */
21 const int N = 105;
22 string s[N], ss[N], w, ww;
23 bool vis[N];
24 char str;
25 string change(string x) {
26     for(int i = 0; i < x.length(); i ++) {
27         if(x[i] >= 'A' && x[i] <= 'Z') x[i] += 32;
28     }
29     return x;
30 }
31 
32 int main(){
33     #ifndef ONLINE_JUDGE
34      //   freopen("1.txt","r",stdin);
35     #endif
36     std::ios::sync_with_stdio(false);
37     int n;
38     cin >> n;
39     for(int i = 0; i < n; i ++) {
40         cin >> s[i];
41         ss[i] = change(s[i]);
42     }
43     cin >> w >> str;
44     ww = change(w);
45     if(str >= 'A' && str <= 'Z') str += 32;
46 
47     int l = ww.length();
48     for(int i = 0; i < l; i ++) {
49         for(int k = 0; k < n; k ++) {
50             if(l-s[k].length() + 1 >= i && ww.substr(i, ss[k].length()) == ss[k]) {
51                 for(int j = i; j < i + ss[k].length(); j ++) vis[j] = 1;
52             }
53         }
54     }
55 
56 
57     for(int i = 0; i < l; i ++) {
58         if(vis[i]) {
59             if(ww[i] == str) {
60                 char tmp = 'a';
61                 if(ww[i] == 'a') tmp = 'b';
62 
63                 if(w[i] >= 'A' && w[i] <= 'Z') w[i] = tmp - 32;
64                 else w[i] = tmp;
65             } else {
66                 if(w[i] >= 'A' && w[i] <= 'Z') w[i] = str - 32;
67                 else w[i] = str;
68             }
69         }
70     }
71     cout << w << endl;
72 }

View Code

D

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

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define lson l,mid,rt<<1
  4 #define rson mid+1,r,rt<<1|1
  5 #define sqr(x) ((x)*(x))
  6 #define pb push_back
  7 #define eb emplace_back
  8 #define maxn 13000005
  9 #define eps 1e-8
 10 #define pi acos(-1.0)
 11 #define rep(k,i,j) for(int k=i;k<j;k++)
 12 typedef long long ll;
 13 typedef pair<int,int> pii;
 14 typedef pair<long long,int>pli;
 15 typedef pair<char,int> pci;
 16 typedef pair<pair<int,string>,pii> ppp;
 17 typedef unsigned long long ull;
 18 const long long MOD=1e9+7;
 19 /*#ifndef ONLINE_JUDGE
 20         freopen("1.txt","r",stdin);
 21 #endif */
 22 
 23  int n,m,s,t;
 24 
 25  vector<pli>G[1005],ve[1005];
 26  vector<pli>a;
 27 
 28  long long dis[1005],vis[1005];
 29 
 30  void dijstra1(int x){
 31     for(int i=0;i<=n;i++) dis[i]=0x3f3f3f3f3f3f3f3f,vis[i]=0;
 32     dis[x]=0;
 33     priority_queue<pli,vector<pli>,greater<pli>>Q;
 34     Q.push({0,x});
 35     while(!Q.empty()){
 36         pli p=Q.top();
 37         Q.pop();
 38         int v=p.second;
 39         if(!vis[v]){
 40             vis[v]=1;
 41             for(int i=0;i<G[v].size();i++){
 42                 int vv=G[v][i].second;
 43                 long long dist=G[v][i].first+dis[v];
 44                 if(!vis[vv]&&dist<dis[vv]){
 45                     dis[vv]=dist;
 46                     Q.push({dis[vv],vv});
 47                 }
 48             }
 49         }
 50     }
 51     for(int i=1;i<a.size();i++){
 52         if(i!=x&&a[x].second>=dis[i]){
 53             ve[x].pb({a[x].first,i});
 54         }
 55     }
 56  }
 57 
 58  void dijstra2(int x,int t){
 59     for(int i=0;i<=n;i++) dis[i]=0x3f3f3f3f3f3f3f3f,vis[i]=0;
 60     dis[x]=0;
 61     priority_queue<pli,vector<pli>,greater<pli>>Q;
 62     Q.push({0,x});
 63     while(!Q.empty()){
 64         pli p=Q.top();
 65         Q.pop();
 66         int v=p.second;
 67         if(!vis[v]){
 68             vis[v]=1;
 69             for(int i=0;i<ve[v].size();i++){
 70                 int vv=ve[v][i].second;
 71                 long long dist=ve[v][i].first+dis[v];
 72                 if(!vis[vv]&&dist<dis[vv]){
 73                     dis[vv]=dist;
 74                     Q.push({dis[vv],vv});
 75                 }
 76             }
 77         }
 78     }
 79     if(dis[t]==0x3f3f3f3f3f3f3f3f) cout<<-1<<endl;
 80     else cout<<dis[t]<<endl;
 81  }
 82 
 83 int main(){
 84     #ifndef ONLINE_JUDGE
 85      //   freopen("1.txt","r",stdin);
 86     #endif
 87     std::ios::sync_with_stdio(false);
 88     cin>>n>>m>>s>>t;
 89     int u,v;
 90     long long c;
 91     for(int i=1;i<=m;i++){
 92         cin>>u>>v>>c;
 93         G[u].pb({c,v});
 94         G[v].pb({c,u});
 95     }
 96     a.pb({0,0});
 97     for(int i=1;i<=n;i++){
 98         cin>>u>>c;
 99         a.pb({c,u});
100     }
101     for(int i=1;i<=n;i++){
102         dijstra1(i);
103     }
104     dijstra2(s,t);
105 }

View Code

E

大数+数位DP

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 13000005
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef pair<int,int> pii;
14 typedef pair<long long,int>pli;
15 typedef pair<char,int> pci;
16 typedef pair<pair<int,string>,pii> ppp;
17 typedef unsigned long long ull;
18 const long long mod=1e9+7;
19 /*#ifndef ONLINE_JUDGE
20         freopen("1.txt","r",stdin);
21 #endif */
22 const int N=1005;
23 int digit[N];
24 ll dp[N][N][2];
25 char l[N], r[N];
26 int k;
27 int dfs(int len, int p, bool flag, bool limit) {
28     if (len == 0) return flag;
29     if (limit == 0 && dp[len][p][flag] != -1) return dp[len][p][flag];
30     int up = limit ? digit[len] : 9;
31     int res = 0;
32     rep(i, 0, up + 1) {
33         if (i != 4 && i != 7)
34             res = (res + dfs(len - 1, max(0, p - 1), flag, limit && i == up)) % mod;
35         else res = (res + dfs(len - 1, 1 * k, flag || p, limit && i == up)) % mod;
36     }
37     if (!limit) dp[len][p][flag] = res;
38     return res;
39 }
40 void solve() {
41     int t;
42     memset(dp, -1, sizeof dp);
43     scanf("%d%d", &t, &k);
44     while (t--) {
45         scanf("%s%s", l, r);
46         int len = strlen(r);
47         for(int i=len;i>=0;i--) digit[i] = r[len - i] - '0';
48         int ans = dfs(len, 0, 0, 1);
49         len = strlen(l);
50         for(int i=len;i>=0;i--) digit[i] = l[len - i] - '0';
51         digit[1]--;
52         for (int i = 1; digit[i] < 0; i++) {
53             digit[i] += 10;
54             digit[i + 1]--;
55         }
56         if (digit[len] == 0) len--;
57         ans = (ans - dfs(len, 0, 0, 1) + mod) % mod;
58         printf("%d
", ans);
59     }
60 }
61 
62 int main(){
63     #ifndef ONLINE_JUDGE
64      //   freopen("1.txt","r",stdin);
65     #endif
66     std::ios::sync_with_stdio(false);
67     solve();
68 }

View Code