首页 > 其他分享 >Atcoder ABC 277 A - E

Atcoder ABC 277 A - E

时间:2022-11-22 11:48:22浏览次数:66  
标签:Atcoder ABC int LL ans vis 277 push dis

**A ^{-1} **

题意:给定一个序列,和一个指定值,输出这个值在序列中的位置(序列的下标从1开始)

思路:签到题

时间复杂度:O(n)

代码:

#include <bits/stdc++.h>
using namespace std;



int main() {
	int n, k;
	cin >> n >> k;
	
	int x, ans;
	for (int i = 1; i <= n; i ++ ) {
		cin >> x;
		
		if(x == k) ans = i;
	}
	
	cout << ans << endl;
	
	
	return 0;
}

B - Playing Cards Validation

题意:给定一些长度为2的字符串,判断字符串是否符合规定

思路:签到题

时间复杂度:O(1)

代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 1000;
int vis[N];
int n;
map<string, bool> mp;

int main() {
	cin >> n;
	
	string s;
	bool flag = false;
	
	vis['H' - '0'] = 1;
	vis['D' - '0'] = 1;
	vis['C' - '0'] = 1;
	vis['S' - '0'] = 1;
	
	vis['A' - '0'] = 2;
	vis['2' - '0'] = 2;
	vis['3' - '0'] = 2;
	vis['4' - '0'] = 2;
	vis['5' - '0'] = 2;
	vis['6' - '0'] = 2;
	vis['7' - '0'] = 2;
	vis['8' - '0'] = 2;
	vis['9' - '0'] = 2;
	vis['T' - '0'] = 2;
	vis['J' - '0'] = 2;
	vis['Q' - '0'] = 2;
	vis['K' - '0'] = 2;


	for (int i = 1; i <= n; i ++ ) {
		cin >> s;
		if(vis[s[0] - '0'] != 1 || vis[s[1] - '0'] != 2) {
			flag = true;
		}
		if(mp[s]) flag = true;
		mp[s] = true;
 	}
	
	if(flag) cout << "No" << endl;
	else cout << "Yes" << endl;
	
	
	
	return 0;
}

C - Ladder Takahashi

题意:给你n个梯子,并且每个梯子都有其自己所相连的楼层,你现在在1楼,问:你最高可以到几楼(通过梯子可以从高到低,也可以从低到高)

思路:通过存图的方法存下梯子的信息,通过dfs知道你所能到的最大楼层

时间复杂度:O(2 * n)

代码:

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 2e5 + 5;

map<LL, vector<LL> > mp;
LL ans = 1;
map<LL, bool> mp1;
LL maxx = 1;

void dfs(LL x) {
	for (auto i : mp[x]) {
		if(mp1[i]) continue;
		
		mp1[i] = true;
		ans = max(ans, i);
		
		if(ans == maxx) return ;	
	
		dfs(i);
	}
}

int main() {
	int n;
	cin >> n;
	
	LL u, v;
	for (int i = 1; i <= n; i ++ ) {
		scanf("%lld%lld", &u, &v);
		
		mp[u].push_back(v);
		mp[v].push_back(u);
		
		maxx = max(maxx, v);
		maxx = max(maxx, u);
	}
	
	dfs(1);
	
	cout << ans << endl;
	
	
	
	return 0;
}

D - Takahashi's Solitaire

题意:给定一个长度为n的序列和一个整数k,首先你可以选择一个卡片放在桌子上(卡牌上的数值是x),之后你可以

选择你手中的x或者(x + 1)% k 的卡片放在桌子上,问:你手中最少剩余卡片的总值是多少

思路:题目的意思就是让我们找出序列中非严格连续递增的子序列的总和最大是多少,首先对序列进行排序去重,之

后寻找,这里需要特判一下首尾相连的情况,

时间复杂度:O(nlogn + n)//排序去重是O(nlogn + n)

代码:

#include <bits/stdc++.h>
using namespace std; 

typedef long long LL;

const int N = 2e6 + 5;

int a[N];
int n, m;
int ans[N];

map<int, int> mp;
map<int, bool> mp1; 

struct node{
	int l, r; 
}s[N];

int main() {
	cin >> n >> m;
	
	LL ans = 0;
	
	vector<int> v;
	for (int i = 1; i <= n; i ++ ) {
		cin >> a[i];
		
		mp[a[i]] ++ ;
		ans += a[i];
		
		v.push_back(a[i]); 
	}
	
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	
	int l = 0, r = 0;
	int res = 0;

	v.push_back(-1);	
	
	for (int i = 1; i < v.size(); i ++ ) {
		if(v[i] == v[i - 1] + 1) {
			r = i;
		}
		else {
			s[ ++ res] = {l, r};
			l = i;
			r = i;
		}
	}
	
	LL sum = 0;
 	if(v[s[1].l] == 0 && v[s[res].r] == m - 1) {		
		for (int i = s[res].l; i <= s[res].r; i ++ ) {
			sum += (LL)mp[v[i]] * v[i];
		}
		for (int i = s[1].l; i <= s[1].r; i ++ ) {
			sum += (LL)mp[v[i]] * v[i];
		}
	}
	

	for (int i = 1; i <= res; i ++ ) {
		LL temp = 0;
		
		for (int j = s[i].l; j <= s[i].r; j ++ ) {
			temp += (LL)mp[v[j]] * v[j];
		}
		
		sum = max(sum, temp);
	}
	
//	cout << (LL)ans - sum << endl;
	
	if(ans < sum) cout << 0 << endl;
	else cout << (LL)ans - sum << endl;

	
	return 0;
}

E - Crystal Switches

题意:

在一个有n个节点和m条边的无向图中,每一条边有一个判断值,若是为1,则证明该条边可通,是0,则证明这个

边无法使用,在图中存在k个节点存在开关,每个使用开关可以使得图中的m条边的通行情况变成相反的,现在你在1节

,问:你最快多久可以到达节点n(没有一步需要消耗1秒)

思路:

若开关按动偶数次,则先前判断值为1的可以通行,0的无法通行,若是次数时奇数次,相反,在一个点上我们可以

重复的按动开关,所以实际上所有边都可以是联通的,所以我们建图时,只需要将一条边拆成两条边即可,最后通

过djistra得到dis[n] 和 dis[n + n],并输出最小值

参考:https://www.cnblogs.com/jakon/p/16888643.html

时间复杂度:O(mlog2n)

代码:

#include <bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f

typedef long long LL;
typedef pair<int, int> PII;

const int N = 4e5 + 5;

int n, m, k;
int dis[N];
bool vis[N];
vector<PII> q[N];

int dijkstra() {
	memset(dis, 0x3f, sizeof dis);
	dis[1] = 0;
	priority_queue<PII, vector<PII>, greater<PII> > qq;
	qq.push({0, 1});

	while (qq.size()) {
		auto temp = qq.top();
		qq.pop();

		int u = temp.second;
		if(vis[u]) continue;
		vis[u] = true;

		for (auto i : q[u]) {
			int v = i.first;
			int w = i.second;

			if(dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				qq.push({dis[v], v});
			}
		} 
	}

	int ans = min(dis[n], dis[n + n]);

	return ans == inf ? -1 : ans;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);

	cin >> n >> m >> k;

	for (int i = 1; i <= m; i ++ ) {
		int x, y, a;
		cin >> x >> y >> a;
		if(a) q[x].push_back({y, 1}), q[y].push_back({x, 1});
		else q[x + n].push_back({y + n, 1}), q[y + n].push_back({x + n, 1});
	}

	for (int i = 1; i <= k; i ++ ) {
		int x;
		cin >> x;

		q[x].push_back({x + n, 0}), q[x + n].push_back({x, 0});
	}

	cout << dijkstra() << endl;




	return 0;
}

标签:Atcoder,ABC,int,LL,ans,vis,277,push,dis
From: https://www.cnblogs.com/luoyefenglin/p/16914628.html

相关文章

  • AtCoder 题解集
    虽然暂时不知道会不会从XCPC中退役,但还是想把这个题解集给维护下去。\(created\;at\;2022/6/24\;by\;Roshin\)目录AGCARCABCABC138F.Coincidence(结论,数位DP)AB......
  • AtCoder Beginner Contest 278
    Preface刚打完就来写题解,热乎的很这周CF没Div2,Atcoder的ARC和微积分考试撞了打不了所以和ztc一起打一下Div3和ABC,顺便锻炼一波解释题目的能力做到G的时候还有30min的,然......
  • ABC262F
    ABC262F*2334卡手的构造题,不是很难想,主要是细节比较多。题意给定一个排列\(p\)。你可以最多执行\(k\)次操作。删除一个数。将\(p\)中末尾的数移到开头。找出......
  • AtCoder Regular Contest 152 (A-D)
    根本不知道有ARC。然后unratedregister。然后一直在聊天,只写了A。难蚌。按照pog的说法,这场应该不看题直接写代码!!1这样才能写的飞快。摆了一上午。我好像一直在贺题,所以......
  • AtCoder Beginner Contest 278-F
    F-Shiritori题解:n最大16,所以可以状态压缩,相当于n个点的带权有向图。dp[i][j]表示当前状态为i,j结尾的情况,其中dp[i][j]=1表示First赢,0为second赢,如果一个字符串s[i],第......
  • ABC278 整合题解
    AA题,送分题。link。思路数据范围很小,其实直接模拟也是可以通过的。不过我们很容易想到\(O(n)\)的算法。对于前\(k\)个数,不输出,其他数正常输出。然后再在末尾......
  • ABC278F 题解
    前言题目传送门!或许更好的阅读体验?博弈论,状压,记忆化搜索。思路看到很小的\(n\),容易联想到状压、搜索。本题就是状压加搜索。设状态\(x\)的每一位表示:如果第\(i\)......
  • ABC278D 题解
    前言题目传送门!更好的阅读体验?难度加强版:P1253。思路很容易想到线段树。维护\(cov_i\)表示覆盖的懒标记。单点加与单点查都非常简单。全局覆盖只需要给每一层都打......
  • ABC245G题解
    似乎是经典套路?先不考虑颜色限制,那么就直接把\(l\)个关键点当作起点跑多源最短路就行了。现在考虑颜色限制,有一种暴力的想法是枚举所有颜色,只把这种颜色的点当作起点,然......
  • ABC138F
    稍微手玩一下可以发现:若\(y\ge2x\),那么\(y-x\gty\%x\)若\(y\lt2x\),那么\(y-x=y\%x\)\(y\oplusx\gey-x\)于是不难发现只有\(y\lt2x\)时才可能有贡献。即......