首页 > 其他分享 >abc302 题解

abc302 题解

时间：2023-05-21 10:11:23浏览次数：44  
标签：const int 题解 LL cin long abc302 adj

打的还行，加的分不多。

A

直接除完上取整即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	LL a, b;
	cin >> a >> b;
	cout << a / b + (a % b == 0 ? 0 : 1) << '\n';
    return 0;
}

看了看jls的

	cout << (a + b - 1) / b << '\n';

妙蛙。

B

建议看jls的，我写的太复杂了。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e2 + 5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n, m;
string s[N];
string temp = "snuke";
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
	{
		cin >> s[i]; 
		s[i] = ' ' + s[i];	
	}
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m - 4; j++)
		{
			string str = s[i].substr(j, 5);
			if(str == temp)
			{
				cout << i << ' ' << j << '\n';
				cout << i << ' ' << j + 1 << '\n';
				cout << i << ' ' << j + 2 << '\n';
				cout << i << ' ' << j + 3 << '\n';
				cout << i << ' ' << j + 4 << '\n';
				return 0;
			}
			reverse(str.begin(), str.end());
			if(str == temp)
			{
				cout << i << ' ' << j + 4 << '\n';
				cout << i << ' ' << j + 3 << '\n';
				cout << i << ' ' << j + 2 << '\n';
				cout << i << ' ' << j + 1 << '\n';
				cout << i << ' ' << j << '\n';
				return 0;
			}
		}
	for(int i = 1; i <= m; i++)
		for(int j = 1; j <= n - 4; j++)
		{
			string st = "";
			for(int k = j; k <= j + 4; k++) st += s[k][i];
			if(st == temp)
			{
				cout << j << ' ' << i << '\n';
				cout << j + 1 << ' ' << i << '\n';
				cout << j + 2 << ' ' << i << '\n';
				cout << j + 3 << ' ' << i << '\n';
				cout << j + 4 << ' ' << i << '\n';
				return 0;
			}
			reverse(st.begin(), st.end());
			if(st == temp)
			{
				cout << j + 4 << ' ' << i << '\n';
				cout << j + 3 << ' ' << i << '\n';
				cout << j + 2 << ' ' << i << '\n';
				cout << j + 1 << ' ' << i << '\n';
				cout << j << ' ' << i << '\n';
				return 0;
			}
		}
	for(int i = 1; i <= n - 4; i++)
		for(int j = 1; j <= m - 4; j++)
		{
			string st = "";
			for(int k = 0; k <= 4; k++) st += s[i+k][j+k];
			if(st == temp){
				cout << i << ' ' << j << '\n';
				cout << i + 1 << ' ' << j + 1 << '\n';
				cout << i + 2 << ' ' << j + 2 << '\n';
				cout << i + 3 << ' ' << j + 3 << '\n';
				cout << i + 4 << ' ' << j + 4 << '\n';
				return 0;
			}
			reverse(st.begin(), st.end());
			if(st == temp){
				cout << i + 4 << ' ' << j + 4 << '\n';
				cout << i + 3 << ' ' << j + 3 << '\n';
				cout << i + 2 << ' ' << j + 2 << '\n';
				cout << i + 1 << ' ' << j + 1 << '\n';
				cout << i << ' ' << j << '\n';
				return 0;
			}
		}
	for(int i = 1; i <= n; i++)
		for(int j = 5; j <= m; j++)
		{
			string st = "";
			for(int k = 0; k <= 4; k++) st += s[i+k][j-k];
			if(st == temp){
				cout << i << ' ' << j << '\n';
				cout << i + 1 << ' ' << j - 1 << '\n';
				cout << i + 2 << ' ' << j - 2 << '\n';
				cout << i + 3 << ' ' << j - 3 << '\n';
				cout << i + 4 << ' ' << j - 4 << '\n';
				return 0;
			}
			reverse(st.begin(), st.end());
			if(st == temp)
			{
				cout << i + 4 << ' ' << j - 4 << '\n';
				cout << i + 3 << ' ' << j - 3 << '\n';
				cout << i + 2 << ' ' << j - 2 << '\n';
				cout << i + 1 << ' ' << j - 1 << '\n';
				cout << i << ' ' << j << '\n';
				return 0;
			}
		}
	return 0;
}

C

枚举全排列判一下就行。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 10, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n, m;
int a[N];
char s[N][N];
int match(char *s1, char *s2)
{
	int cnt = 0;
	for(int i = 0; i < m; i ++) if(s1[i] != s2[i]) cnt ++;
	return cnt;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) cin >> s[i];
	for(int i = 1; i <= n; i ++) a[i] = i;
	bool f = false;
    do 
	{	
		bool ok = true;
		for(int i = 1; i < n; i ++) if(match(s[a[i]], s[a[i + 1]]) != 1) ok = false;
		if(ok)
		{
			f = true;
			break;
		} 
    } while (next_permutation(a + 1, a + 1 + n));
   	if(f) cout << "Yes\n";
   	else cout << "No\n";
    return 0;
}

D

在 \(b\) 数组中找到最后一个小于等于 \(a_i + d\) 的数，判一下差记录答案就行。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
LL a[N], b[N];
LL n, m, d;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	cin >> n >> m >> d;
	for(int i = 1; i <= n; i ++) cin >> a[i];
	for(int i = 1; i <= m; i ++) cin >> b[i];
	sort(b + 1, b + m + 1);
	LL res = -1;
	for(int i = 1; i <= n; i ++)
	{
		int tmp = upper_bound(b + 1, b + m + 1, a[i] + d) - b - 1;
		if(abs(a[i] - b[tmp]) <= d) res = max(res, a[i] + b[tmp]);
	}
	cout << res << '\n';
    return 0;
}

E

按照题意用set模拟。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5 + 5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n, q, cnt;
set<int> adj[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	cin >> n >> q;
	cnt = n;
	while(q --)
	{
		int op, u, v;
		cin >> op >> u;
		if(op == 1)
		{
			cin >> v;
			if(adj[u].size() == 0) cnt --;
			if(adj[v].size() == 0) cnt --;
			adj[u].insert(v);
			adj[v].insert(u);
		}
		else
		{
			if(adj[u].size() != 0)  cnt ++;
			for(auto t : adj[u]) 
			{
				adj[t].erase(u);
				if(adj[t].size() == 0) cnt ++;
			}
			adj[u].clear();
		}
		cout << cnt << '\n';
	}
    return 0;
}

F

集合编号像集合内的每个元素连边权为 \(1\) 的边，元素向集合编号连边权为 \(0\) 的边，跑 \(01bfs\)即可，\(dijkstra\) 也不是不行。
赛后发现边权一定是交错走的，不用跑，但是 \(01bfs\) 好像挺快？79ms，目前没发现更短的。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 5e5 + 5, M = N, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n, m;
int h[N], nxt[M << 1], to[M << 1], val[M << 1], cnt;
int dist[N];
bool st[N];
void add(int u, int v, int w)
{
	to[++ cnt] = v, val[cnt] = w, nxt[cnt] = h[u], h[u] = cnt;
}
void bfs(int s)
{
	for(int i = 1;i <= n + m;i ++) dist[i] = INF, st[i] = false;
	deque<int> q;
	q.push_back(s);
	dist[s] = 0;
	while(q.size())
	{
		int u = q.front();
		q.pop_front();
		if(st[u]) continue;
		st[u] = true;
		if(u == n + m) break;
		for(int i = h[u]; i; i = nxt[i])
		{
			int v = to[i], w = val[i];
			if(dist[u] + w < dist[v])
			{
				dist[v] = dist[u] + w;
				if(w == 1) q.push_back(v);
				else q.push_front(v);
			}
		}
	}
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	cin >> n >> m;
	for(int i = 1; i <= n; i ++)
	{
		int len;
		cin >> len;
		while(len --)
		{
			int x;
			cin >> x;
			add(i, n + x, 0);
			add(n + x, i, 1);
		}
	}
	bfs(n + 1);
	if(dist[n + m] == INF) dist[n + m] = 0;
	cout << dist[n + m] - 1 << '\n';
    return 0;
}

G

不会，后面补。

Ex

不会，后面补。

标签：const,int,题解,LL,cin,long,abc302,adj
From： https://www.cnblogs.com/Svemit/p/17418264.html

相关文章

  • 【CF1833C】题解
    本文章同步发表于洛谷思路首先，先明确一点：同奇偶的两个数相减，等于偶数。奇偶性不同的两个数相减，等于奇数。接下来，我们要确定要都变成奇数还是偶数。偶数？如果是偶数，由于要同奇偶的两个数相减，结果才等于偶数。又因为改变后的每个数都要\(\gt0\)，所以，最小的奇数没有可以与其......
  • 【CF1833D】题解
    本文章同步发表于洛谷思路这是一道水题，但细节很多......首先，要求字典序最大，显然就想到了让最大的数字在第一位。于是就进一步得出了应该让最大数字在翻转区间的后一位，初步得出了以下思路：找到最大的数（\(n\)）所在位置\(r\)，将\(r-1\)；贪心的寻找\(r-1\)以前第一个比\(p_1\)......
  • 【题解】CF193D Two Segments
    题意给定一个\(1\simN\)的排列，在这个排列中选出两段互不重叠的区间，求使选出的元素排序后构成公差为1的等差数列的方案数。选出的两段区间中元素构成的集合相同时视为同一种方案。\(1\leN\le3\times10^5\)。传送门分析如果考虑怎么优化枚举的两个区间的话，发现不太好搞（反正......
  • jre jdk更改目录后Java无法运行问题解决方案
    问题：在将Java文件（包含jdkjre）由C盘直接剪贴到D盘后，所有Java程序无法运行，且其Java图标不再显示。解决方案：首先更改环境变量。当我们单纯地将Java文件更改位置后，我们计算机的环境变量仍未改变，依旧是当时安装Java时的配置。步骤：控制面板—>系统和安全—>系统—>高级系统设置—>环境......
  • P5179 Fraction 题解
    题目描述给你四个正整数\(a,\,b,\,c,\,d\)，求一个最简分数\(\frac{p}{q}\)满足\(\frac{a}{b}<\frac{p}{q}<\frac{c}{d}\)。若有多组解，输出\(q\)最小的一组，若仍有多组解，输出\(p\)最小的一组。前置知识：Stern-Brocot树首先引入分数逼近。这里的分数逼近是指用用一个......
  • CF1781F题解
    \(\text{link}\)。也是一道非常巧妙的\(\texttt{dp}\)。容易想到把括号变成\(\pm1\)。考虑括号序列合法等价于前缀和\(\ge0\)，我们可以想加入\(()\)或\()(\)对前缀的影响。设加入的位置的前一位前缀和为\(x\)，则加入\(()\)相当于把\(x\)替换为\([x,x+1,x]\)，加入......
  • CSP-J2021试题题解
    1.分糖果原题：https://www.luogu.com.cn/problem/P7909原代码：#include<bits/stdc++.h>#definelllonglongusingnamespacestd;lln,l,r;intmain(){ cin>>n>>l>>r; if(r%n==n-1)cout<<n-1; elseif(l%n==n-1)cout<<n-1; elseif(......
  • 问题解一
    （1）用pycharm连接mysql时，需要安装一个驱动，点击连接界面，如果TestConnection不可用，点击右边的按钮即可（2）如果要将同一网站不同链接的数据存入数据库，可考虑重写start_requestseg:forindex,hrefinenumerate(self.start_urls):ifindex==0:yieldscrapy.Request(......
  • 僵尸进程问题解决
    1何为僵尸进程僵尸进程是当子进程比父进程先结束，而父进程又没有回收子进程，释放子进程占用的资源，此时子进程将成为一个僵尸进程。如果父进程先退出，子进程被init接管，子进程退出后init会回收其占用的相关资源。在UNIX系统中，一个进程结束了，但是它的父进程没有等待（调用wait/wai......
  • 【P4331 [BalticOI 2004]】Sequence 数字序列 题解（左偏树维护动态区间中位数）
    左偏树维护动态区间中位数。传送门P4331BalticOI2004Sequence数字序列。Solution1我的思路和题解前半部分完全重合了（（如果按照单调不增去分割\(a\)序列的话，对于每一段我们能很简单地得出它的最佳答案：中位数。发现严格单调很难做，很难拿捏，考虑对\(a\)序列的每一项都进......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99