AtCoder Beginner Contest 308

A：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<string>
 6 #include<vector>
 7 #include<stack>
 8 #include<bitset>
 9 #include<cstdlib>
10 #include<cmath>
11 #include<set>
12 #include<list>
13 #include<deque>
14 #include<map>
15 #include<queue>
16 #include <iomanip>
17 #include<ctime>
18 using namespace std;
19 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
20 #define TLE (double)clock()/CLOCKS_PER_SEC<=0.95
21 #define int long long 
22 #define double long double
23 #define endl '\n'
24 #define inf LLONG_MAX
25 #define iinf INT_MAX
26 typedef pair<int,int> PII;
27 const double PI = acos(-1.0);
28 const double eps = 1e-6;
29 const int INF = 0x3f3f3f3f;
30 const int N = 20;
31 int a[N];
32 signed main()
33 {
34     IOS;
35     for(int i=1;i<=8;i++)
36     {
37         cin>>a[i];
38     }
39     bool flag=true;
40     for(int i=1;i<8;i++)
41     {
42         if(a[i]>a[i+1])
43         {
44             cout<<"No"<<endl;
45             return 0;
46         }
47     }
48     for(int i=1;i<=8;i++)
49     {
50         if(a[i]>=100&&a[i]<=675&&a[i]%25==0)
51         {
52             flag=true;
53         }
54         else
55         {
56             flag=false;
57             break;
58         }
59     }
60     if(flag)    cout<<"Yes"<<endl;
61     else cout<<"No"<<endl;
62     return 0;
63 }

B：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<string>
 6 #include<vector>
 7 #include<stack>
 8 #include<bitset>
 9 #include<cstdlib>
10 #include<cmath>
11 #include<set>
12 #include<list>
13 #include<deque>
14 #include<map>
15 #include<queue>
16 #include <iomanip>
17 #include<ctime>
18 using namespace std;
19 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
20 #define TLE (double)clock()/CLOCKS_PER_SEC<=0.95
21 #define int long long 
22 #define double long double
23 #define endl '\n'
24 #define inf LLONG_MAX
25 #define iinf INT_MAX
26 typedef pair<int,int> PII;
27 const double PI = acos(-1.0);
28 const double eps = 1e-6;
29 const int INF = 0x3f3f3f3f;
30 const int N = 1e2+10;
31 string s[N];
32 int n,m;
33 string d[N];
34 map<string,int>mp;
35 bool is_find(string tmp)
36 {
37     for(int i=1;i<=m;i++)
38     {
39         if(d[i]==tmp)
40         return true;
41     }
42     return false;
43 }
44 signed main()
45 {
46     IOS;
47     cin>>n>>m;
48     int p0;
49     for(int i=1;i<=n;i++)
50     {
51         cin>>s[i];
52     }
53     for(int i=1;i<=m;i++)
54     {
55         cin>>d[i];
56     }
57     cin>>p0;
58     int t;
59     for(int i=1;i<=m;i++)
60     {
61         cin>>t;
62         mp[d[i]]=t;
63     }
64     int sum=0;
65     for(int i=1;i<=n;i++)
66     {
67         if(is_find(s[i]))
68         {
69             sum+=mp[s[i]];
70         }
71         else
72         {
73             sum+=p0;
74         }
75     }
76     cout<<sum<<endl;
77     return 0;
78 }

C:浮点数存储然后排个序

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<string>
 6 #include<vector>
 7 #include<stack>
 8 #include<bitset>
 9 #include<cstdlib>
10 #include<cmath>
11 #include<set>
12 #include<list>
13 #include<deque>
14 #include<map>
15 #include<queue>
16 #include <iomanip>
17 #include<ctime>
18 using namespace std;
19 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
20 #define TLE (double)clock()/CLOCKS_PER_SEC<=0.95
21 #define int long long 
22 #define double long double
23 #define endl '\n'
24 #define inf LLONG_MAX
25 #define iinf INT_MAX
26 typedef pair<double,int> PII;
27 const double PI = acos(-1.0);
28 const double eps = 1e-6;
29 const int INF = 0x3f3f3f3f;
30 const int N = 2e5+10;
31 int n;
32 struct node
33 {
34     double f;
35     int id;
36 }a[N];
37 bool cmp(node b,node c)
38 {
39     if(b.f!=c.f)
40     {
41         return b.f>c.f;
42     }
43     else
44     {
45         return b.id<c.id;
46     }
47 }
48 signed main()
49 {
50     IOS;
51     double h,t;
52     cin>>n;
53     for(int i=1;i<=n;i++)
54     {
55         a[i].id=i;
56         cin>>h>>t;
57         a[i].f=h/(h+t);
58     }
59     sort(a+1,a+1+n,cmp);
60     for(int i=1;i<=n;i++)
61     {
62         cout<<a[i].id<<" ";
63     }
64     return 0;
65 }

D：从（1，1）走到（n,m)，保证此条路径上的字符串序列为

且行走的轨迹只能移动到相邻的格子

走的时候利用前驱后继思想就能解决这个问题，根本用不到一点回溯，最后检查一下最后一个格子被访问了没有即可

  1 //中心思想就是根据当前找前驱，不需要回溯
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<iostream>
  6 #include<string>
  7 #include<vector>
  8 #include<stack>
  9 #include<bitset>
 10 #include<cstdlib>
 11 #include<cmath>
 12 #include<set>
 13 #include<list>
 14 #include<deque>
 15 #include<map>
 16 #include<queue>
 17 #include <iomanip>
 18 #include<ctime>
 19 using namespace std;
 20 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 21 #define TLE (double)clock()/CLOCKS_PER_SEC<=0.95
 22 #define int long long 
 23 #define double long double
 24 #define endl '\n'
 25 #define inf LLONG_MAX
 26 #define iinf INT_MAX
 27 typedef pair<int,int> PII;
 28 const double PI = acos(-1.0);
 29 const double eps = 1e-6;
 30 const int INF = 0x3f3f3f3f;
 31 const int N = 5e2+10;
 32 char ch[N][N];
 33 int n,m;
 34 int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
 35 bool flag;
 36 string s="snuke";
 37 bool vis[N][N];
 38 // bool check(int x,int y,int k)
 39 // {
 40     // if(ch[x][y]==s[(k-1)%5+1])    return true;
 41     // else    return false;
 42 // }
 43 vector<char>nxt(N);
 44 void init()
 45 {
 46     nxt['s'] = 'n';
 47     nxt['n'] = 'u';
 48     nxt['u'] = 'k';
 49     nxt['k'] = 'e';
 50     nxt['e'] = 's';
 51 }
 52 // void dfs(int x,int y)//dfs版本
 53 // {
 54     // vis[x][y]=true;
 55     // for(int i=0;i<4;i++)
 56     // {
 57         // int nx=x+dx[i];
 58         // int ny=y+dy[i];
 59         // if(nx<0||nx>=n||ny<0||ny>=m)    continue;
 60         // if(ch[nx][ny]!=nxt[ch[x][y]])    continue;
 61         // if(vis[nx][ny])    continue;
 62         // dfs(nx,ny);
 63     // }
 64 // }
 65 void bfs(int x,int y)//bfs版本
 66 {
 67     queue<PII>q;
 68     vis[x][y]=true;
 69     q.push({x,y});
 70     while(!q.empty())
 71     {
 72         int tx=q.front().first;
 73         int ty=q.front().second;
 74         q.pop();
 75         // if(tx==n-1&&ty==m-1)
 76         // {
 77             // flag=true;
 78             // return ;
 79         // }
 80         for(int i=0;i<4;i++)
 81         {
 82             int nx=tx+dx[i];
 83             int ny=ty+dy[i];
 84             if(nx<0||nx>=n||ny<0||ny>=m)    continue;
 85             if(ch[nx][ny]!=nxt[ch[tx][ty]])    continue;
 86             if(vis[nx][ny])    continue;
 87             vis[nx][ny]=true;
 88             q.push({nx,ny});
 89         }
 90     }
 91 }
 92 signed main()
 93 {
 94     IOS;
 95     cin>>n>>m;
 96     for(int i=0;i<n;i++)
 97     {
 98         for(int j=0;j<m;j++)
 99         {
100             cin>>ch[i][j];
101         }
102     }
103     if(ch[0][0]!='s')
104     {
105         cout<<"No"<<endl;
106         return 0;
107     }
108     init();
109     //dfs(0,0);
110     bfs(0,0);
111     if(vis[n-1][m-1])    cout<<"Yes"<<endl;
112     else    cout<<"No"<<endl;
113 }

 E:给定一个字符串序列由"MEX"序列构成，给定数字序列a[i]（由0，1，2数组构成），让寻找满足(a[i],a[j],a[k])i<=j<=k且s[i]s[j]s[k]="MEX",求所有满足条件的mex(a[i],a[j],a[k])的和

mex表示除去a[i],a[j],a[k]中最小的非负整数

比如：

确定以字母E为中继点，寻找e的前缀字母M的数量和后缀E的数量，求最后的组合贡献总和即可

 1 //要找的位置满足字符串"MEX"的形式，根据1，3样例可知有多个组合形式的"MEX"
 2 //这就需要我们把E的位置作为中继点，找前缀"M"和后缀"E"的数量，并且统计为0，1，2的数量的情况
 3 //最后求解时，枚举M为0，1，2的三种和E为0，1，2的情况，这样一共有九种组合方式，每种组合的对结果的贡献是
 4 //cntm*cntx*mex(a[[nowm]],a[i],a[nowe])，i代表当前字母是E的情况
 5 #include<cstdio>
 6 #include<cstring>
 7 #include<algorithm>
 8 #include<iostream>
 9 #include<string>
10 #include<vector>
11 #include<stack>
12 #include<bitset>
13 #include<cstdlib>
14 #include<cmath>
15 #include<set>
16 #include<list>
17 #include<deque>
18 #include<map>
19 #include<queue>
20 #include <iomanip>
21 #include<ctime>
22 using namespace std;
23 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
24 #define TLE (double)clock()/CLOCKS_PER_SEC<=0.95
25 #define int long long 
26 #define double long double
27 #define endl '\n'
28 #define inf LLONG_MAX
29 #define iinf INT_MAX
30 typedef pair<int,int> PII;
31 const double PI = acos(-1.0);
32 const double eps = 1e-6;
33 const int INF = 0x3f3f3f3f;
34 const int N = 2e5+10;
35 int n,a[N];
36 string s;
37 int mex(int x,int y,int z)
38 {
39     for(int i=0;i<3;i++)    
40     {
41         if(x!=i&&y!=i&&z!=i)    return i;
42     }
43     return 3;
44 }
45 signed main()
46 {
47     IOS;
48     cin>>n;
49     for(int i=0;i<n;i++)    cin>>a[i];
50     cin>>s;
51     vector<vector<int>>cnt_l(n+1,vector<int>(3,0));
52     vector<vector<int>>cnt_r(n+1,vector<int>(3,0));
53     for(int i=0;i<n;i++)
54     {
55         cnt_l[i+1]=cnt_l[i];
56         if(s[i]=='M')    cnt_l[i+1][a[i]]++;
57     }
58     for(int i=n-1;i>=0;i--)
59     {
60         cnt_r[i]=cnt_r[i+1];
61         if(s[i]=='X')    cnt_r[i][a[i]]++;
62     }
63     int sum=0;
64     for(int i=0;i<n;i++)
65     {
66         if(s[i]!='E')    continue;
67         for(int j=0;j<3;j++)
68         {
69             for(int k=0;k<3;k++)
70             {
71                 sum+=cnt_l[i][j]*cnt_r[i+1][k]*mex(j,a[i],k);
72             }
73         }
74     }
75     cout<<sum<<endl;
76     return 0;
77 }