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 }
- Beginner AtCoder Contest 308beginner atcoder contest 308 beginner atcoder 308e mex contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334