阅读量:0
题目地址(补题)
RC-u1 热҈热҈热҈
简单模拟题，没什么好说的 :
#include<bits/stdc++.h> using namespace std ; const int N = 55 ; int a[N] ; int main(){ int n , w ; cin >> n >> w ; for(int i=1;i<=n;i++) cin >> a[i] ; int t = w ; int x = 0 , y = 0 ; for(int i=1;i<=n;i++){ if(a[i]>=35){ if(t!=4) x++ ; else y++ ; } t = (t + 8) % 7 ; } cout << x << " " << y << endl ; }RC-u2 谁进线下了？
简单模拟题，没什么好说的 :
#include<bits/stdc++.h> using namespace std; #define endl '\n' int yss[21] = {0, 12, 9, 7, 5, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0}; int get(int x){ return yss[x] ; } int main(){ int n ; cin >> n ; vector<int> a(21,0) ; for(int i=1;i<=n;i++){ for(int j=1;j<=20;j++){ int p , k ; cin >> p >> k ; a[j] += k + get(p) ; } } for(int i=1;i<=20;i++){ cout << i << " " << a[i] << endl ; } return 0; }RC-u3 暖炉与水豚
简单模拟题，没什么好说的 (注意看清题目就ok):
#include<bits/stdc++.h> using namespace std ; const int N = 1010 ; int n , m ; char a[N][N] ; bool st[N][N] ; /** wm....mw .w..ww.. ..wm.wwm w.w....w .m.c.m.. w.....w. */ void f(int i , int j){ for(int x=-1;x<=1;x++){ for(int y=-1;y<=1;y++){ int xx = i+x , yy = j + y ; if(xx>=1&&xx<=n&&yy>=1&&yy<=m) { st[xx][yy] = true ; } } } } bool pd(int i , int j){ for(int x=-1;x<=1;x++){ for(int y=-1;y<=1;y++){ int xx = i+x , yy = j + y ; if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[xx][yy]=='c') { return false ; } } } return true ; } int main(){ cin >> n >> m ; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin >> a[i][j] ; if(a[i][j]=='m') f(i,j) ; } } int cnt = 0 ; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i][j]=='w' && !st[i][j]){ for(int x=-1;x<=1;x++){ for(int y=-1;y<=1;y++){ int xx = i+x , yy = j + y ; if(a[xx][yy]=='.'&&pd(xx,yy)){ cout << xx << " " << yy << '\n' ; cnt ++ ; } } } } } } if(cnt==0){ cout << "Too cold!" ; } return 0 ; }RC-u4 章鱼图的判断
1 . 先用并查集求每一个连通块的环的个数 :
ps : 对于每一对点 ， 如果祖先相同 ， 那么必定存在环，环数++ ， 不同，进行union操作
2 . 对于输出yes的答案 ， 记录环中一对相邻点 ， 用bfs求两点距离 ，则为环的大小 ；
#include<bits/stdc++.h> #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) ; using namespace std ; const int N = 1e5+10 ; #define endl '\n' vector<int> e[N] ; int n , m ; int p[N]; //存储每个点的祖宗节点 int sz[N] ;// 维护联通图中环的数量 int find(int x) {return x == p[x] ? x : p[x] = find(p[x]);} int a , b ; int d[N] ;// 存距离 // 所在连通图只有一个环的时候才满足题意 // 假设只有一个章鱼环 ， a , b为环中相邻的两个点 inline void solve(){ cin >> n >> m ; for(int i=1;i<=n;i++) e[i].clear() , p[i] = i , d[i] = 0 , sz[i] = 0 ; for(int i=1;i<=m;i++){ int u , v ; cin >> u >> v ; e[u].push_back(v) ; e[v].push_back(u) ; int fu = find(u) , fv = find(v) ; if(fu==fv) sz[fu]++ , a = u , b = v ; // 必定存在环 else p[fu]=fv ,sz[fv]+=sz[fu] ;// union两个点 } int ans = 0 ; // 求章鱼环的数量 for(int i=1;i<=n;i++) if(find(i)==i&&sz[i]==1) ans ++ ; if(ans != 1) { cout << "No" << " " << ans << endl ; return ; } // 求a->b中这个环中点的数量-->题目所求 // 章鱼子图 点数>=3 , 直接bfs来求 a->b的距离(不是直接两点两边的距离，这个用continue跳过) queue<int> q ; q.push(a) ; while(!q.empty()){ int u = q.front() ; q.pop() ; for(int v : e[u]){ if(u==a&&v==b) continue ; if(!d[v]) d[v] = d[u] + 1,q.push(v) ; } } cout << "Yes" << " " << d[b]+1 << endl ; } int main(){ IOS int _ ; cin >> _ ; while(_--) solve() ; return 0 ; }RC-u5 工作安排
先看赛时代码 :
先按截止时间排序 ，然后dp ;
dp[i][j] 代表前i个任务，截止时间为j的最大值 ;
转移方程 : dp[i][j] = max(dp[i][j],dp[i-1][k]+a[i].p) ;
#include<bits/stdc++.h> #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) ; using namespace std ; #define endl '\n' int n ; struct Node{ int t,d,p ; }; bool cmp(Node& x , Node& y){ return x.d < y.d ; } inline void solve(){ cin >> n ; int ma = 0 ; int tx = 1 ; vector<Node> a(n+1) ; for(int i=1;i<=n;i++){ int x , y , z ; cin >> x >> y >> z ; if(x>y) continue ; a[tx].t = x ; a[tx].d = y ; a[tx++].p = z ; ma = max(ma , y) ; } tx -= 1 ; // cout << tx << endl ; sort(a.begin()+1,a.begin()+1+tx,cmp) ; vector<vector<int>> dp(tx+1,vector<int>(ma+1,0)) ; for(int i=1;i<=tx;i++){ for(int j=1;j<=a[i].d;j++){ dp[i][j] = max(dp[i-1][j] , dp[i][j-1]) ; int k = j - a[i].t ; if(k>=0){ dp[i][j] = max(dp[i][j],dp[i-1][k]+a[i].p) ; } } } cout << dp[tx][ma] << endl ; } int main(){ IOS int _ ; cin >> _ ; while(_--){ solve() ; } return 0 ; }ps : 这个代码爆空间了 ， 丢了5分 ， 正解应该是一个01背包 ；
欢迎交流!
