• 暑假算法训练day1

    目录

    B. Diameter of Graph

    题目大意：
    给出 n ( 1 ≤ n ≤ 1 0 9 ) n(1\leq n \leq 10^9) n(1≤n≤109) 个点， m ( 0 ≤ m ≤ 1 0 9 ) m(0\leq m \leq 10^9) m(0≤m≤109))条边，一个整数 k ( 0 ≤ k ≤ 1 0 9 ) k(0\leq k\leq 10^9) k(0≤k≤109)。
    定义图的直径是任意两点的最短路径中最长的路径。
    判断能否构成一个无向连通图，满足图的直径严格小于 k − 1 k - 1 k−1， 并且不能连自环，重边。
    思路：让所有的点尽量构成“菊花图”，这样图的直径将尽可能地小，
    菊花图时，图的直径为2
    在这里插入图片描述
    首先先判断给定的n和m能否构成一个符合题意图

    if(m<n-1 || m>n*(n-1)/2) puts("No");

    • 1

    如果 k − 2 < 0 k-2<0 k−2<0 无解
    如果 k − 2 = 0 k-2=0 k−2=0,当 n = 1 n=1 n=1的时候符合，其余不符合。
    如果 k − 2 = = 1 k-2==1 k−2==1那么一定是一个完全图。 m = ( n − 1 ) ∗ n m=(n-1) *n m=(n−1)∗n。
    如果 k − 2 > 1 k-2>1 k−2>1 一定有解。

    #include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
#define x first
#define y second
#define LL long long 
#define int LL
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
LL Mod(LL a,LL mod){return (a%mod+mod)%mod;}
LL lowbit(LL x){return x&-x;}//最低位1及其后面的0构成的数值
LL qmi(LL a,LL b,LL mod) {LL ans = 1; while(b){ if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; }
int _;
int n,m,k;
void solve()
{
	cin>>n>>m>>k;
	if(n-1>m||m>n*(n-1)/2)
	{
		cout<<"NO"<<endl;
		return;
	}
	if(k-2>=2)cout<<"YES"<<endl;
	else if(k-2>=1)
	{
		if(m==n*(n-1)/2)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	else if(k-2==0)
	{
		if(n==1)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	else cout<<"NO"<<endl;	
}
signed main()
{
    io;
  	cin>>_; 
 	while(_--)
    solve();
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48

    E1. Permutation Minimization by Deque

    题意
    给定一个 1 ∼ n 1 \sim n 1∼n的排列 p p p 和一个双端队列，按先后顺序将排列的第一个数字取出并插入到双端队列的队头或队尾。求插完所有数字后双端队列中字典序最小的排列。
    思路：
    当插入的数字 x 小于队头时入队头，反之入队尾即为最小字典序排列。

    #include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
#define x first
#define y second
#define LL long long 
#define int LL
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
LL Mod(LL a,LL mod){return (a%mod+mod)%mod;}
LL lowbit(LL x){return x&-x;}//最低位1及其后面的0构成的数值
LL qmi(LL a,LL b,LL mod) {LL ans = 1; while(b){ if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; }
int _;
int n;
const int N=2e5+10;
int a[N];
void solve()
{
	cin>>n;
	deque<int>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	q.push_front(a[1]);
	for(int i=2;i<=n;i++)
	{
		if(a[i]<=q.front())
			q.push_front(a[i]);
		else q.push_back(a[i]);
	}	
	while(q.size())
	{
		auto t=q.front();
		q.pop_front();
		cout<<t<<' ';
	}
	cout<<endl;
}
signed main()
{
    io;
  	cin>>_; 
 	while(_--)
    solve();
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    B. Chess Tournament

    题意：
    n 个人进行比赛，每场比赛的结果只有输，赢，平局三种情况。
    每个玩家对于比赛都有自己的期望，有以下两种类型：
    1.玩家不想输掉任何一场比赛；
    2.玩家想要赢得至少一场比赛。
    判断是否存在所有比赛的结果，使得所有玩家都满足他们的期望。 如果有多种可能的结果，输出任意一种即可。 如果没有，输出 No

    思路：
    当2 的个数为1 时，不成立。因为剩下所以的1 就不成立了
    当2的个数为2 时，不成立。
    当 2的个数大于等于3 时。成立，让2构成一个环
    让所有的1打平

    #include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
#define x first
#define y second
#define LL long long 
#define int LL
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
LL Mod(LL a,LL mod){return (a%mod+mod)%mod;}
LL lowbit(LL x){return x&-x;}//最低位1及其后面的0构成的数值
LL qmi(LL a,LL b,LL mod) {LL ans = 1; while(b){ if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; }
int _;
int n,m;
const int N=110;
char g[N][N];
void solve()
{
	cin>>n;
	string s;
	cin>>s;
	int one=0,two=0;
	for(auto x:s)if(x=='1')one++;
	else two++;
	if(two==1||two==2)
	{
		cout<<"NO"<<endl;
		return;
	}
	cout<<"YES"<<endl;
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j++)
		{
			if(i==j)g[i][j]='X';
			else if(s[i-1]=='1'||s[j-1]=='1')g[i][j]=g[j][i]='=';
			else if(s[i-1]=='2')s[i-1]='0',g[i][j]='+',g[j][i]='-';
			else if(s[j-1]=='2')s[j-1]='0',g[j][i]='+',g[i][j]='-';
			else g[i][j]=g[j][i]='=';
			
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			cout<<g[i][j];
		cout<<endl;
	}
}
signed main()
{
    io;
  	cin>>_; 
 	while(_--)
    solve();
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62

    B. Scenes From a Memory

    题目描述
    给出一个正整数 n，n 中不包含 0。求最大删去多少位使其变成一个合数或 1。数据保证一定存在答案。
    素数是指除 1​​ 和它本身外没有除数的数。合数是指一个有两个以上除数的数。1 既不是质数也不是合数。
    思路：
    删除最长的位数，那么只留一位时，只要包含1，4，6，8，9都可以保留只剩一位
    其余情况，这个数字每一位只含有2，3，5，7，会发现组成的三位及以上的数都可以只剩下两位的合数。

    #include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
#define x first
#define y second
#define LL long long 
#define int LL
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
LL Mod(LL a,LL mod){return (a%mod+mod)%mod;}
LL lowbit(LL x){return x&-x;}//最低位1及其后面的0构成的数值
LL qmi(LL a,LL b,LL mod) {LL ans = 1; while(b){ if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; }
int _;
int n;
bool cmp(int x)
{
	if(x<=1)return false;
	for(int i=2;i<=x/i;i++)
		if(x%i==0)return false;
	return true;
}
void solve()
{
	cin>>n;
	string s;
	cin>>s;
	map<int,int>mp;
	mp[1]=mp[4]=mp[6]=mp[8]=mp[9]=1;
	for(auto x:s)
		if(mp.count(x-'0'))
		{
			cout<<1<<endl;
			cout<<x<<endl;
			return;
		}
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			int sum=(s[i]-'0')*10+s[j]-'0';
			if(!cmp(sum))
			{
				cout<<2<<endl;
				cout<<sum<<endl;
				return;
			}
		}
	}
	
}
signed main()
{
    io;
  	cin>>_; 
 	while(_--)
    solve();
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63

    C. Mocha and Hiking

    题意：
    有一张有 n + 1 n+1 n+1 个点和 2 n − 1 2n-1 2n−1 条有向边的图，边有以下两种：

    对于所有 1 ≤ i < n 1 \leq i < n 1≤i<n，有 n − 1 n-1 n−1条从 ii 到 i + 1 i+1 i+1 的边
    对于所有 1 ≤ i ≤ n 1 \leq i \leq n 1≤i≤n，有 n n n 条 i i i 与 n + 1 n+1 n+1 的单向边，若 a i = 0 a_i = 0 ai​=0，为从 i i i 到 n + 1 n+1 n+1的边，反之则为从 n + 1 n+1 n+1 到 i i i 的边。
    思路：
    发现从 [ 1 , n ] [1,n] [1,n]的可以一步到位，对 a 1 和 a n a_1和a_n a1​和an​进行以下分类讨论：

    1. 如果 a n = 0 a_n=0 an​=0那么可以直接 1 − > n + 1 1->n+1 1−>n+1
    2. 如果 a n = 1 a_n=1 an​=1那么
      (1). 如果 a 1 = 1 a_1=1 a1​=1那么可以从 n + 1 − > 1 − > n n+1 ->1->n n+1−>1−>n
      (2). 如果 a 1 = 0 a_1=0 a1​=0那么从 [ n − 1 , 2 ] [n-1,2] [n−1,2]找第一个 a i = 0 a_i=0 ai​=0,如果有，那么与之相邻的 a i + 1 = 1 a_{i+1}=1 ai+1​=1那么可以 1 − > i − > n + 1 − > i + 1 − > n 1->i->n+1->i+1->n 1−>i−>n+1−>i+1−>n，否则 1 − > n + 1 − > 2 − > n 1->n+1->2->n 1−>n+1−>2−>n

    发现必定有解

    #include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
#define x first
#define y second
#define LL long long 
#define int LL
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
LL Mod(LL a,LL mod){return (a%mod+mod)%mod;}
LL lowbit(LL x){return x&-x;}//最低位1及其后面的0构成的数值
LL qmi(LL a,LL b,LL mod) {LL ans = 1; while(b){ if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; }
int _;
int n;
const int N=1e4+10;
int a[N];
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	if(a[n]==0)
	{
		for(int i=1;i<=n+1;i++)cout<<i<<' ';
		cout<<endl;
		return;
	}
	else
	{
		if(a[1]==1)
		{
			cout<<n+1<<' ';
			for(int i=1;i<=n;i++)cout<<i<<' ';
			cout<<endl;
			return;
		}
		else
		{
			int idx=0;
			for(int i=n;i>=2;i--)
				if(a[i]==0)
				{
					idx=i;
					break;
				}
			if(idx)
			{
				for(int i=1;i<=idx;i++)cout<<i<<' ';
				cout<<n+1<<' ';
				for(int i=idx+1;i<=n;i++)cout<<i<<' ';
				cout<<endl;	
			}
			else 
			{
				cout<<1<<' '<<n+1<<' ';
				for(int i=2;i<=n;i++)cout<<i<<' ';
				cout<<endl;
			}
		}
	}
}
signed main()
{
    io;
 	cin>>_; 
 	while(_--)
    solve();
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
  • 相关阅读:
    Java学习笔记5.2.2 List接口 - LinkedList类
    Hadoop总结——HDFS
    React v6（仅支持函数组件，不支持类组件）与v5版本路由使用详情和区别（详细版）
    JS中对象数组用sort按属性排序
    8.Excel vba开发-突出显示范围内的最小值
    linux驱动39：内存池
    【VIM】VIM中的保存和退出、VIM退出命令、如何退出vim编辑、VIM命令大全
    STM32F407（野火霸天虎v2）学习理解记录（持续更新）
    自古以来，代理程序都是兵家折戟之地
    【LeetCode】238. 除自身以外数组的乘积
  • 原文地址：https://blog.csdn.net/qq_52765554/article/details/125437819