Codeforces Beta Round #65 (Div. 2)

Codeforces Beta Round #65 (Div. 2)

http://codeforces.com/contest/71

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 1000006
 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 unsigned long long ull;
14 
15 int main(){
16     #ifndef ONLINE_JUDGE
17      //   freopen("input.txt","r",stdin);
18     #endif
19     std::ios::sync_with_stdio(false);
20     int n;
21     string str;
22     cin>>n;
23     rep(i,0,n){
24         cin>>str;
25         if(str.length()<=10){
26             cout<<str<<endl;
27         }
28         else{
29             cout<<str[0];
30             cout<<str.length()-2;
31             cout<<str[str.length()-1]<<endl;
32         }
33     }
34 }
View Code

B

 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 1000006
 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 unsigned long long ull;
14 
15 int main(){
16     #ifndef ONLINE_JUDGE
17      //   freopen("input.txt","r",stdin);
18     #endif
19     std::ios::sync_with_stdio(false);
20     int n,k,t;
21     cin>>n>>k>>t;
22     int sum=t*n*k/100;
23     int tmp=sum/k;
24     for(int i=0;i<tmp;i++) cout<<k<<" ";
25     if(tmp<n){
26        int p=sum-tmp*k;
27        cout<<p;
28        for(int i=0;i<n-tmp-1;i++) cout<<" "<<0;
29    }
30 }
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 1000006
 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 unsigned long long ull;
14 
15 int a[100005];
16 int n;
17 
18 int main(){
19     #ifndef ONLINE_JUDGE
20      //   freopen("input.txt","r",stdin);
21     #endif
22     std::ios::sync_with_stdio(false);
23     cin>>n;
24     for(int i=0;i<n;i++)cin>>a[i];
25     int flag=0;
26     for(int i=1;i<=n/3;i++)
27         if(n%i==0)
28         {
29             for(int j=0;j<i;j++)
30             {
31                 flag=1;
32                 for(int k=j;k<n;k+=i)
33                     flag&=a[k];
34                 if(flag)
35                 {
36                     cout<<"YES"<<endl;
37                     return 0;
38                 }
39             }
40         }
41     cout<<"NO"<<endl;
42 }
View Code

D

大模拟

  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 1000006
  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 unsigned long long ull;
 14 
 15 string A[25][25];
 16 
 17 bool check1(int r, int c) {
 18     set <char> S;
 19 
 20     int cnt = 0;
 21 
 22     for (int i = r; i <= r+2; i++)
 23         for (int j = c; j <= c+2; j++)
 24             if (A[i][j] == "J1" ||
 25                 A[i][j] == "J2") {
 26 
 27                     cnt++;
 28             }
 29             else
 30                 S.insert(A[i][j][0]);
 31 
 32     return ( (S.size() + cnt) == 9 );
 33 }
 34 
 35 bool check2(int r1, int c1, int r2, int c2) {
 36     for (int i = r1; i <= r1+2; i++)
 37         for (int j = c1; j <= c1+2; j++)
 38             if (r2 <= i && i <= r2+2 &&
 39                 c2 <= j && j <= c2+2) {
 40 
 41                     return false;
 42             }
 43 
 44     return true;
 45 }
 46 
 47 bool check3(int r, int c) {
 48     set <char> S;
 49 
 50     for (int i = r; i <= r+2; i++)
 51         for (int j = c; j <= c+2; j++)
 52             S.insert(A[i][j][0]);
 53 
 54     return ( S.size() == 9 );
 55 }
 56 
 57 
 58 int main(){
 59     #ifndef ONLINE_JUDGE
 60      //   freopen("input.txt","r",stdin);
 61     #endif
 62     std::ios::sync_with_stdio(false);
 63     int n, m;
 64     cin >> n >> m;
 65 
 66     string tmpRank[13] = {"2", "3", "4", "5", "6", "7", "8", "9", "T", "J", "Q", "K", "A"};
 67     string tmpSuit[4]  = {"C", "D", "H", "S"};
 68     set <string> Pack;
 69     for (int i = 0; i < 13; i++)
 70         for (int j = 0; j < 4; j++)
 71             Pack.insert(tmpRank[i] + tmpSuit[j]);
 72     bool isThereJ1 = false;
 73     int J1r;
 74     int J1c;
 75     bool isThereJ2 = false;
 76     int J2r;
 77     int J2c;
 78     for (int i = 1; i <= n; i++)
 79         for (int j = 1; j <= m; j++) {
 80             cin >> A[i][j];
 81             if (A[i][j] == "J1") {
 82                 isThereJ1  = true;
 83                        J1r = i;
 84                        J1c = j;
 85 
 86                 continue;
 87             }
 88             if (A[i][j] == "J2") {
 89                 isThereJ2  = true;
 90                        J2r = i;
 91                        J2c = j;
 92 
 93                 continue;
 94             }
 95             Pack.erase(Pack.find(A[i][j]));
 96         }
 97 
 98     vector <pair <int, int>> V;
 99 
100     for (int r = 1; r <= n-2; r++)
101         for (int c = 1; c <= m-2; c++)
102             if (check1(r, c))
103                 V.push_back(make_pair(r, c));
104 
105     for (int i = 0; i < V.size(); i++)
106         for (int j = 0; j < V.size(); j++) {
107             if (i == j)
108                 continue;
109             int r1 = V[i].first;
110             int c1 = V[i].second;
111             int r2 = V[j].first;
112             int c2 = V[j].second;
113             if (check2(r1, c1, r2, c2)) {
114                 if (isThereJ1 && isThereJ2) {
115                     for (set <string>::iterator it1 = Pack.begin(); it1 != Pack.end(); it1++)
116                         for (set <string>::iterator it2 = Pack.begin(); it2 != Pack.end(); it2++) {
117                             if (it1 == it2)
118                                 continue;
119                             A[J1r][J1c] = *it1;
120                             A[J2r][J2c] = *it2;
121                             if (check3(r1, c1) &&
122                                 check3(r2, c2)) {
123                                     cout << "Solution exists." << endl;
124                                     cout << "Replace J1 with " << (*it1) << " and J2 with " << (*it2) << "." << endl;
125                                     cout << "Put the first square to (" << r1 << ", " << c1 << ")." << endl;
126                                     cout << "Put the second square to (" << r2 << ", " << c2 << ").";
127                                     return 0;
128                             }
129                             A[J1r][J1c] = "J1";
130                             A[J2r][J2c] = "J2";
131                         }
132 
133                     continue;
134                 }
135 
136                 if (isThereJ1) {
137                     for (set <string>::iterator it = Pack.begin(); it != Pack.end(); it++) {
138                         A[J1r][J1c] = *it;
139                         if (check3(r1, c1) &&
140                             check3(r2, c2)) {
141                                 cout << "Solution exists." << endl;
142                                 cout << "Replace J1 with " << (*it) << "." << endl;
143                                 cout << "Put the first square to (" << r1 << ", " << c1 << ")." << endl;
144                                 cout << "Put the second square to (" << r2 << ", " << c2 << ").";
145                                 return 0;
146                         }
147                         A[J1r][J1c] = "J1";
148                     }
149                     continue;
150                 }
151                 if (isThereJ2) {
152                     for (set <string>::iterator it = Pack.begin(); it != Pack.end(); it++) {
153                         A[J2r][J2c] = *it;
154                         if (check3(r1, c1) &&
155                             check3(r2, c2)) {
156                                 cout << "Solution exists." << endl;
157                                 cout << "Replace J2 with " << (*it) << "." << endl;
158                                 cout << "Put the first square to (" << r1 << ", " << c1 << ")." << endl;
159                                 cout << "Put the second square to (" << r2 << ", " << c2 << ").";
160                                 return 0;
161                         }
162                         A[J2r][J2c] = "J2";
163                     }
164                     continue;
165                 }
166                 cout << "Solution exists." << endl;
167                 cout << "There are no jokers." << endl;
168                 cout << "Put the first square to (" << r1 << ", " << c1 << ")." << endl;
169                 cout << "Put the second square to (" << r2 << ", " << c2 << ").";
170                 return 0;
171             }
172         }
173     cout << "No solution.";
174 }
View Code

E

dfs+剪枝

剪完由超时变成了31ms....

 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 1000006
 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 unsigned long long ull;
14 
15 int a[100005];
16 int n,k;
17 map<string,int>mp;
18 string str;
19 int s1[25],s2[25];
20 int flag;
21 int book[25];
22 vector<int>ans[25];
23 
24 void dfs(int l,int r,int sum){
25     if(r==k){
26         flag=1;
27         return;
28     }
29     if(s2[r]==sum){
30         dfs(0,r+1,0);
31         return;
32     }
33     int pre=-1;
34     for(int i=0;i<n&&!flag&&s1[i]+sum<=s2[r];i++){
35         if(book[i]==-1&&s1[i]!=pre){///剪枝
36             pre=s1[i];
37             book[i]=r;
38             dfs(l+1,r,s1[i]+sum);
39             if(!flag){
40                 book[i]=-1;
41             }
42         }
43     }
44 }
45 
46 int main(){
47     #ifndef ONLINE_JUDGE
48      //   freopen("input.txt","r",stdin);
49     #endif
50     std::ios::sync_with_stdio(false);
51     string element[] = {
52         "kong","H","He","Li","Be","B","C","N","O","F","Ne","Na","Mg","Al","Si","P","S","Cl","Ar",
53         "K","Ca","Sc","Ti","V","Cr","Mn","Fe","Co","Ni","Cu","Zn","Ga","Ge","As","Se","Br",
54         "Kr","Rb","Sr","Y","Zr","Nb","Mo","Tc","Ru","Rh","Pd","Ag","Cd","In","Sn","Sb","Te",
55         "I","Xe","Cs","Ba","La","Ce","Pr","Nd","Pm","Sm","Eu","Gd","Tb","Dy","Ho","Er","Tm",
56         "Yb","Lu","Hf","Ta","W","Re","Os","Ir","Pt","Au","Hg","Tl","Pb","Bi","Po","At","Rn",
57         "Fr","Ra","Ac","Th","Pa","U","Np","Pu","Am","Cm","Bk","Cf","Es","Fm"
58     };
59     for(int i=0;i<sizeof(element)/sizeof(element[0]);i++){
60         mp[element[i]]=i;
61     }
62     cin>>n>>k;
63     for(int i=0;i<n;i++){
64         cin>>str;
65         s1[i]=mp[str];
66     }
67     for(int i=0;i<k;i++){
68         cin>>str;
69         s2[i]=mp[str];
70     }
71     sort(s1,s1+n);
72     sort(s2,s2+k);
73     memset(book,-1,sizeof(book));
74     dfs(0,0,0);
75     if(flag){
76         cout<<"YES"<<endl;
77         for(int i=0;i<n;i++){
78             ans[book[i]].pb(s1[i]);
79         }
80         for(int i=0;i<k;i++){
81             cout<<element[ans[i][0]];
82             for(int j=1;j<ans[i].size();j++){
83                 cout<<"+"<<element[ans[i][j]];
84             }
85             cout<<"->"<<element[s2[i]]<<endl;
86         }
87     }
88     else {
89         cout<<"NO"<<endl;
90     }
91 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Fighting-sh/p/10464047.html