AtCoder Beginner Contest 274

A - Batting Average

题目描述：

输出 ba\frac{b}{a}ab​,保留3位小数

#include 
using namespace std;#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair  pii;#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];void work(){double a, b;cin >> a >> b;printf("%.3f\n",b/a);
}int main(){io;work();return 0;
}

B - Line Sensor

题目描述：

输入一个n*m的字符串矩型，输出每一列的#的数量

#include 
using namespace std;#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair  pii;#define MAX 300000 + 50
int n, m, k, x;
char p;
int num[MAX];void work(){cin >> n >> m;for(int i = 1; i <= n; ++i){for(int j = 1; j <= m; ++j){cin >> p;num[j] += (p == '#');}}for(int i = 1; i <= m; ++i)cout << num[i] << ' ';}int main(){io;work();return 0;
}

C - Ameba

题目描述：

给定一个长度为n的序列，现在有一个空树，只有一个根结点1，a[i]表示在第i秒产生两个最新的子节点，编号取未出现的最新的俩，输出1-2*n-1的每个点到根节点的距离

思路：

建好图以后dfs一次就行

#include 
using namespace std;#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair  pii;#define MAX 500000 + 50
int n, m, k, x;
char p;
int num[MAX];
vectorG[MAX];void dfs(int u, int fa){num[u] = num[fa] + 1;for(auto v : G[u]){if(v == fa)continue;dfs(v, u);}
}void work(){cin >> n;int tot = 1;for(int i = 1; i <= n; ++i){cin >> x;++tot;G[x].push_back(tot);G[tot].push_back(x);++tot;G[x].push_back(tot);G[tot].push_back(x);}dfs(1, 0);for(int i = 1; i <= tot; ++i)cout << num[i] - 1<< endl;
}int main(){io;work();return 0;
}

D - Robot Arms 2

题目描述：

在一个二维平面，起点是(0,0)，给你n个数字，表示每次移动的距离，且第一次必须是往右移动，将所有相邻的点连起来，要保证相邻的线之间的夹角是90度，问是否存在一条路径能到达(x,y)

思路：

由于要保证相邻的线之间的夹角是90度，也就说明了i是奇数的时候只能左右走，i是偶数的时候只能上下走，我们就可以分开考虑

现在就可以把题目转换成：

在一个数轴上，你最开始位于ar[1]的位置，可以进行m次移动,每次移动只能往左或者往右移动，问能不能到达x

数据范围不大，我们开一个map暴力更新就行

#include 
using namespace std;#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair  pii;#define MAX 300000 + 50
int n, m, k, x, y;
int tr[MAX];void work(){cin >> n >> x >> y;for(int i = 1; i <= n; ++i){cin >> tr[i];}vectorar, br;for(int i = 2; i <= n; i += 2)ar.push_back(tr[i]);for(int i = 3; i <= n; i += 2)br.push_back(tr[i]);mapmp1;mp1[0] = 1;for(auto x : ar){mapmp;for(int j = -10000; j <= 10000; ++j){if(mp1.count(j)){mp[j-x] = 1;mp[j+x] = 1;}}mp1 = mp;for(auto [x,y] : mp)mp1[x] = 1;}mapmp2;mp2[tr[1]] = 1;for(auto x : br){mapmp;for(int j = -10000; j <= 10000; ++j){if(mp2.count(j)){mp[j-x] = 1;mp[j+x] = 1;}}mp2 = mp;}if(mp1[y] && mp2[x])cout << "Yes\n";else cout << "No\n";
}int main(){io;work();return 0;
}

E - Booster

题目描述：

二维平面，给出n个城镇的坐标，和m个宝箱的坐标，每拿到一个宝箱，就会使得自己的移动速度翻倍，你从(0,0)，必须要经过n个城镇，宝箱不做要求，问回到(0,0)的最短时间是多少，初始速度是1

思路：

壮压dp

dp[i][j]表示状态为i，且当前在j的最短时间,

i是长度为n+m的二进制数，每个是1的位置的点表示已经去过了，前m个是包箱，后n个是城镇

然后就是简单的转移

#include 
using namespace std;#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair  pii;#define MAX 300000 + 50
int a, b;
int n;
pii tr[100];
double dp[MAX][20];double cal(int i, int j){return sqrt((tr[i].first - tr[j].first)*(tr[i].first - tr[j].first)+(tr[i].second - tr[j].second)*(tr[i].second - tr[j].second));
}bool judge(int p){if((p & ((1<cin >> a >> b;n = a + b;tr[0] = m_p(0, 0);for(int i = 1; i <= n; ++i){cin >> tr[i].first >> tr[i].second;}for(int i = 0; i < (1<dp[1<<(i-1)][i] = cal(0, i);}for(int i = 0; i < (1<bitset<10>b(i>>a);double v = pow(2, b.count());for(int j = 1; j <= n; ++j){if(!(1 & (i>>(j-1))))continue;for(int k = 1; k <= n; ++k){if(1 & (i>>(k-1)))continue;double p = cal(j, k) / v;dp[i|(1<<(k-1))][k] = min(dp[i|(1<<(k-1))][k], dp[i][j] + p);}}}double ans = 1e14;for(int i = 0; i < (1<if(!judge(i))continue;bitset<10>b(i>>a);double v = pow(2, b.count());for(int j = 1; j <= n; ++j){if(!(i & ((1<io;work();return 0;
}

F - Fishing

题目描述：

一维直线上有n条鱼，每条鱼的重量是ai，初始位置是xi，速度是vi

你有一个长度为k的鱼网，你可以在任意时间下网一次，问最多能抓到的鱼的重量是多大

思路：

我们枚举每条鱼作为鱼网起点，其他每条鱼最多进一次鱼网，出一次鱼网，我们计算进鱼网的时间t，记录下来，计算出鱼网的时候t，也记录下来，开一个pair的vector，把进网的时间和重量放进去，把出网的时间和负的重量放进去，然后排个序，求最大区间子段和，显然不会存在某些鱼没进网但是出网的情况，所以求的过程不会出现负数的情况，所以求最大子段和的时候不用判断和为负数的时候重制为0，还有就是用pair的时候排序第二维要插相反数，计算的时候也是计算负权值，防止由于排序引起在同一时刻有鱼进有鱼出，直接pair排序会在时间相同的情况下把负权值的鱼放前面，导致答案错误

#include 
using namespace std;#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair  pii;#define MAX 300000 + 50
int n;
ll k;struct ran{int w;double x, v;
}tr[MAX];
vectorv;
void fuck(int i, int j){if(tr[i].x > tr[j].x){if(tr[i].v >= tr[j].v)return;v.push_back(m_p((tr[i].x - tr[j].x) / (tr[j].v - tr[i].v), -tr[j].w));v.push_back(m_p((tr[i].x + k - tr[j].x) / (tr[j].v - tr[i].v), tr[j].w));}else if(tr[j].x >= tr[i].x && tr[j].x <= tr[i].x + k){v.push_back(m_p(0, -tr[j].w));if(tr[j].v > tr[i].v)v.push_back(m_p((tr[i].x + k - tr[j].x) / (tr[j].v - tr[i].v), tr[j].w));else if(tr[j].v < tr[i].v)v.push_back(m_p((tr[j].x - tr[i].x) / (tr[i].v - tr[j].v), tr[j].w));}else{if(tr[i].v > tr[j].v){v.push_back(m_p((tr[j].x-tr[i].x-k)/(tr[i].v-tr[j].v), -tr[j].w));v.push_back(m_p((tr[j].x-tr[i].x)/(tr[i].v-tr[j].v), +tr[j].w));}}
}void work(){cin >> n >> k;for(int i = 1; i <= n; ++i){cin >> tr[i].w >> tr[i].x >> tr[i].v;}int ans = 0;for(int i = 1; i <= n; ++i){v.clear();int sum = 0;for(int j = 1; j <= n; ++j){fuck(i, j);}sort(v.begin(), v.end());for(auto [x, y] : v){sum -= y;ans = max(ans, sum);}}cout << ans << endl;
}int main(){io;work();return 0;
}