题目地址(补题)
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 ++ ;
}
}
}
break ;
}
}
}
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背包 ；
欢迎交流!
