AtCoder Beginner Contest 274「A」「B」「C dfs」「D 暴力dp？」「E 旅行商状压dp」「F 排序」
admin
|
|
240
|
Atcoder

1217 字
|
20 分钟

AtCoder Beginner Contest 274

A – Batting Average

题目描述：

输出 ,保留3位小数

#include <bits/stdc++.h>
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 <int,int> 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 <bits/stdc++.h>
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 <int,int> 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 <bits/stdc++.h>
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 <int,int> pii;

#define MAX 500000 + 50
int n, m, k, x;
char p;
int num[MAX];
vector<int>G[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 <bits/stdc++.h>
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 <int,int> 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];
    }
    vector<int>ar, 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]);
    map<int, bool>mp1;
    mp1[0] = 1;
    for(auto x : ar){
        map<int, bool>mp;
        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;
    }
    
    map<int, bool>mp2;
    mp2[tr[1]] = 1;
    for(auto x : br){
        map<int, bool>mp;
        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 <bits/stdc++.h>
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 <double,double> 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<<a)-1)) != ((1<<a)-1))return false;
    return true;
}

void work(){
    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<<n); ++i)for(int j = 0; j <= n; ++j)dp[i][j] = 1e14;
    for(int i = 1; i <= n; ++i){
        dp[1<<(i-1)][i] = cal(0, i);
    }
    for(int i = 0; i < (1<<n); ++i){
        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<<n); ++i){
        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<<j)-1)))continue;
            double p = cal(j, 0) / v;
            ans = min(ans, dp[i][j] + p);
        }
    }
    printf("%6f\n", ans);
}


int main(){
    io;
    work();
    return 0;
}

F – Fishing

题目描述：

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

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

思路：

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

#include <bits/stdc++.h>
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 <double,int> pii;

#define MAX 300000 + 50
int n;
ll k;

struct ran{
    int w;
    double x, v;
}tr[MAX];
vector<pii>v;
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;
}

 

博客内容均系原创，未经允许严禁转载！
Atcoder
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																					

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
AtCoder Beginner Contest 257

							
							

							
AtCoder Beginner Contest 226「E」

							
							

							
AtCoder Beginner Contest 236 F – Spices「贪心 + 位运算」

							
							

							
AtCoder Beginner Contest 266 「A」「B 取模」「C 凸多边形」「D 状态机dp」「E 概率dp」「F 思维+dfs」

							
							

							
ARC 138 B – 01 Generation