RC-u1 早鸟价
代码
#include "bits/stdc++.h" using namespace std; int main(){ int n; cin>>n; int m, d, q; while(n--){ cin>>m>>d>>q; if(m > 7 || m == 7 && d > 11) { cout<<"Too late!"; } else if(m < 6 || m == 6 && d <= 20) { if(q < 1800) cout<<"Need more!"; else if(q == 1800) cout<<"Ok!" ; else cout<<"^_^"; } else { if(q < 2000) cout<<"Need more!"; else if(q == 2000) cout<<"Ok!" ; else cout<<"^_^"; } cout<<endl; } return 0; }
RC-u2 谁进线下了?III
代码:
#include "bits/stdc++.h" using namespace std; int main(){ int T; cin>>T; int n, s; int cnt = 0; int p, f; int summ = 0; while(T--){ cin>>n>>s; int m = n; cnt = 0; summ = 0; while(m--){ cin>>p>>f; if(p == 1) cnt ++; summ += f; } if(cnt >= n* 1.0 / 2) cout<<"1"; else cout<<"0"; cout<<" "; if(summ - s >= 50) cout<<"1"; else cout<<"0"; cout<<endl; } return 0; }
RC-u3 点格棋
思路:这题是个模拟,要注意的是判断条件,一是边界,二是下棋人的顺序,三是是否是相邻的格子,然后是连过的不能连,要注意的时候有可能一次连线拿两分,还有就是map如果结构体当键,无论是否里面的数据一样的,都会算成不同的键
代码:#include "bits/stdc++.h" using namespace std; int n, m, s; int mp[102][102][102][102] = {0}; int check(int x1, int y1, int x2, int y2){ int score = 0; if(x1 == x2){ if(x1 - 1 >= 1){ if(mp[x1 - 1][y1][x1][y1] && mp[x1 - 1][y2][x1][y2] && mp[x1 - 1][y1][x1 - 1][y2]) score++; } if(x1 + 1 <= n ){ if(mp[x1 + 1][y1][x1][y1] && mp[x1 + 1][y2][x1][y2] && mp[x1 + 1][y1][x1 + 1][y2] ) score++; } } else if(y1 == y2){ if(y1 - 1 >= 1){ if(mp[x1][y1- 1][x1][y1] && mp[x1 ][y1 - 1][x2][y2- 1] && mp[x2][y2 - 1][x2][y2] ) score++; } if(y1 + 1 <= m ){ if(mp[x1][y1 + 1][x1][y1] && mp[x1 ][y1 + 1][x2][y2+ 1] && mp[x2][y2 + 1][x2][y2]) score++; } } return score; } int main(){ cin>>n>>m>>s; int a, x1, y1, x2, y2; vector<int> v; int cnt = 0; int A = 0, B = 0; int next = 0; for(int i = 1; i <= s; i ++){ cin>>a>>x1>>y1>>x2>>y2; if(a == next && x1 >= 1 && y1 >= 1 && x2 >= 1 && y2 >= 1 && x1 <= n && x2 <= n && y1 <= m && y2 <= m&&(abs(x1 - x2 )+abs(y1 - y2) == 1)&&!mp[x1][y1][x2][y2] && (x1 == x2 || y1 == y2)){ mp[x1][y1][x2][y2] = 1; mp[x2][y2][x1][y1] = 1; int f = check(x1, y1, x2, y2); if(f == 0) next = 1 - next; if(a == 0) A += f; else B += f; } else v.push_back(i),cnt ++; } if(cnt == 0) cout<<-1; else for(int i = 0; i < v.size();i ++){ cout<<v[i]; if(i != v.size() - 1) cout<<" "; } cout<<endl; if(A > B) cout<<0<<" "<<A; else cout<<1<<" "<<B; return 0; }
RC-u4 Tree Tree 的
思路:很明显是找环,一个最大的,一个次大的,但是注意他这个图不一定是连通的,也就是说你从一个点开始dfs可能遍历不到所有的点。我这里用了一个dfs来进行判断,也就是一个dfs找一个连通图中所有的环。
代码:#include "bits/stdc++.h" using namespace std; vector<int> g[15]; int ans1 = 1, ans2 = 0; int pre[60], vis[20], vis1[20]; void dfs(int x, int p){ vis[x] = 1; vis1[x] = 1; for(int i = 0; i < g[x].size(); i ++){ int t = g[x][i]; vis1[t] = 1; if(vis[t]) { int cnt = 1; int xx = x; while( xx != t){ xx = pre[xx]; cnt ++; } if(cnt > ans1){ ans2 = ans1; ans1 = cnt; } if(cnt < ans1 && cnt > ans2){ ans2 = cnt; } } else if(t == p) continue; else if(!vis[t]){ pre[t] = x; dfs(t, x); } } vis[x] = 0; } int main(){ int T; cin>>T; while(T--){ int n, m, x, y; cin>>n>>m; memset(vis, 0, sizeof(vis)); memset(vis1, 0, sizeof(vis1)); memset(pre, 0, sizeof(pre)); for(int i = 0; i < 11; i ++) g[i].clear(); while(m--){ cin>>x>>y; g[x].push_back(y); g[y].push_back(x); } ans1 = 1; ans2 = 0; for(int i = 1; i <= n; i ++) if(!vis1[i]) dfs(i, -1); cout<<ans1<<" "<<ans2<<endl; } return 0; }
RC-u5 游戏设计师
思路:这题大模拟,耐心做一下就好了,细节比较多,然后的话他这个你注意是1是实心格子,2是易碎格子,直接模拟的话能拿22分,后面两个超时,这时候会想到(我看大家好像都想到了哈哈,本来以为是剪枝但是感觉没有什么好剪得)直接从终点开始遍历就能打表所有的可能了,再多询问也是O(1), 遍历的话直接bfs就可以了,这里注意可能一开始就在终点,这是第1个测试点一分。
代码:
#include "bits/stdc++.h" using namespace std; const int N = 1e3 + 10; int n, m; int g[N][N]; int vis[4][1001][1001]; int ex = -1, ey = -1; struct node{ int op; int x, y; int dis; node(int a, int b, int c, int e){ op = a, x = b, y = c, dis = e; } }; queue<node> q; void bfs(int op, int x, int y){ int x1, y1, x2, y2; if(op == 0) q.push(node(0, x, y, 0)); else if(op == 1){ q.push(node(1, x, y, 0)); } else { q.push(node(2, x, y, 0)); } int opp = -1; while(q.size()){ node t = q.front(); q.pop(); int op1 = t.op; if(op1 == 0){ x1 = t.x - 1, x2 = t.x - 2, y1 = t.y, y2 = t.y, opp = 2; if(x1 >= 0 && x1 < n && x2 >= 0 && x2 < n && y1 >= 0 && y1 < m && y2 >= 0 && y2 < m && !vis[opp][x2][y1] && (g[x1][y1] == 1 || g[x1][y1] == 2)&& (g[x2][y2] == 1 || g[x2][y2] == 2)){ q.push(node(2, x2, y1, t.dis + 1)); vis[opp][x2][y1] = t.dis + 1; } x1 = t.x + 1, x2 = t.x + 2, y1 = t.y, y2 = t.y, opp = 2; if(x1 >= 0 && x1 < n && x2 >= 0 && x2 < n && y1 >= 0 && y1 < m && y2 >= 0 && y2 < m && !vis[opp][x1][y1]&& (g[x1][y1] == 1 || g[x1][y1] == 2)&& (g[x2][y2] == 1 || g[x2][y2] == 2)){ q.push(node(2, x1, y1, t.dis + 1)); vis[opp][x1][y1] = t.dis + 1; } x1 = t.x, x2 = t.x, y1 = t.y + 1, y2 = t.y + 2, opp = 1; if(x1 >= 0 && x1 < n && x2 >= 0 && x2 < n && y1 >= 0 && y1 < m && y2 >= 0 && y2 < m && !vis[opp][x1][y1] && (g[x1][y1] == 1 || g[x1][y1] == 2)&& (g[x2][y2] == 1 || g[x2][y2] == 2)){ q.push(node(1, x1, y1, t.dis + 1)); vis[opp][x1][y1] = t.dis + 1; } x1 = t.x, x2 = t.x, y1 = t.y - 1, y2 = t.y - 2, opp = 1; if(x1 >= 0 && x1 < n && x2 >= 0 && x2 < n && y1 >= 0 && y1 < m && y2 >= 0 && y2 < m && !vis[opp][x2][y2] && (g[x1][y1] == 1 || g[x1][y1] == 2)&& (g[x2][y2] == 1 || g[x2][y2] == 2)){ q.push(node(1, x2, y2, t.dis + 1)); vis[opp][x2][y2] = t.dis + 1; } } else if(op1 == 1){ x1 = t.x - 1, x2 = t.x - 1, y1 = t.y, y2 = t.y + 1, opp = 1; if(x1 >= 0 && x1 < n && x2 >= 0 && x2 < n && y1 >= 0 && y1 < m && y2 >= 0 && y2 < m && !vis[opp][x1][y1] && (g[x1][y1] == 1 || g[x1][y1] == 2)&& (g[x2][y2] == 1 || g[x2][y2] == 2)){ q.push(node(1, x1, y1, t.dis + 1)); vis[opp][x1][y1] = t.dis + 1; } x1 = t.x + 1, x2 = t.x + 1, y1 = t.y, y2 = t.y + 1, opp = 1; if(x1 >= 0 && x1 < n && x2 >= 0 && x2 < n && y1 >= 0 && y1 < m && y2 >= 0 && y2 < m && !vis[opp][x1][y1] && (g[x1][y1] == 1 || g[x1][y1] == 2)&& (g[x2][y2] == 1 || g[x2][y2] == 2)){ q.push(node(1, x1, y1, t.dis + 1)); vis[opp][x1][y1] = t.dis + 1; } x1 = t.x, x2 = 0, y1 = t.y - 1, y2 = 0, opp = 0; if(x1 >= 0 && x1 < n && x2 >= 0 && x2 < n && y1 >= 0 && y1 < m && y2 >= 0 && y2 < m && !vis[opp][x1][y1] && (g[x1][y1] == 1 || g[x1][y1] == 3)){ q.push(node(0, x1, y1, t.dis + 1)); vis[opp][x1][y1] = t.dis + 1; } x1 = t.x, x2 = 0, y1 = t.y + 2, y2 = 0, opp = 0; if(x1 >= 0 && x1 < n && x2 >= 0 && x2 < n && y1 >= 0 && y1 < m && y2 >= 0 && y2 < m && !vis[opp][x1][y1] && (g[x1][y1] == 1|| g[x1][y1] == 3)){ q.push(node(0, x1, y1, t.dis + 1)); vis[opp][x1][y1] = t.dis + 1; } } else if(op1 == 2){ x1 = t.x , x2 = t.x + 1, y1 = t.y - 1, y2 = t.y - 1, opp = 2; if(x1 >= 0 && x1 < n && x2 >= 0 && x2 < n && y1 >= 0 && y1 < m && y2 >= 0 && y2 < m && !vis[opp][x1][y1] && (g[x1][y1] == 1 || g[x1][y1] == 2)&& (g[x2][y2] == 1 || g[x2][y2] == 2)){ q.push(node(2, x1, y1, t.dis + 1)); vis[opp][x1][y1] = t.dis + 1; } x1 = t.x, x2 = t.x + 1, y1 = t.y + 1, y2 = t.y + 1, opp = 2; if(x1 >= 0 && x1 < n && x2 >= 0 && x2 < n && y1 >= 0 && y1 < m && y2 >= 0 && y2 < m && !vis[opp][x1][y1] && (g[x1][y1] == 1 || g[x1][y1] == 2)&& (g[x2][y2] == 1 || g[x2][y2] == 2)){ q.push(node(2, x1, y1, t.dis + 1)); vis[opp][x1][y1] = t.dis + 1; } x1 = t.x - 1, x2 = 0, y1 = t.y, y2 = 0, opp = 0; if(x1 >= 0 && x1 < n && x2 >= 0 && x2 < n && y1 >= 0 && y1 < m && y2 >= 0 && y2 < m && !vis[opp][x1][y1] && (g[x1][y1] == 1|| g[x1][y1] == 3)){ q.push(node(0, x1, y1, t.dis + 1)); vis[opp][x1][y1] = t.dis + 1; } x1 = t.x + 2, x2 = 0, y1 = t.y, y2 = 0, opp = 0; if(x1 >= 0 && x1 < n && x2 >= 0 && x2 < n && y1 >= 0 && y1 < m && y2 >= 0 && y2 < m && !vis[opp][x1][y1] && (g[x1][y1] == 1|| g[x1][y1] == 3)){ q.push(node(0, x1, y1, t.dis + 1)); vis[opp][x1][y1] = t.dis + 1; } } } } int main(){ cin>>n>>m; int q; for(int i = 0; i < n; i ++){ for(int j = 0; j < m; j ++){ scanf("%1d", &g[i][j]); if(g[i][j] == 3){ ex = i, ey = j; } } } cin>>q; int x, y, op; bfs(0, ex, ey); while(q--){ cin>>x>>y>>op; if(vis[op][x - 1][y - 1] || (op == 0 && x - 1 == ex && y - 1 == ey)) cout<<vis[op][x - 1][y - 1]<<endl; else cout<<-1<<endl; } return 0; }