上海市青少年算法2022年5月月赛（丙组）

T1. 三数排序
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定三个整数 a,b,c，请将它们以从小到大的顺序排序后输出。
输入格式
单独一行：三个整数表示 a,b,c。
输出格式
单独一行：表示按升序排列后的三个数。
数据范围
−1000≤a,b,c≤1000。
样例数据
输入:
6 4 2
输出:
2 4 6
输入:
1 1 1
输出:
1 1 1

#include 
#include 
#include 
using namespace std;
int main()
{
	int a[3];
	for(int i=0;i<3;i++) cin>>a[i];
	sort(a,a+3);
	for(int i=0;i<3;i++) cout<

T2. 珠玑妙算（一）
内存限制: 256 Mb时间限制: 1000 ms
题目描述
珠玑妙算（Mastermind）是一种猜谜游戏。
在游戏开始前，系统会生成一个十进制的四位整数（每一位数字都不相同）作为谜底。玩家需要提供一个十进制的四位整数（每一位数字也都不相同）作为解答。
对于给定的解答，请统计谜底中有多少既被猜中了数字也被猜中了位置（称这种情况为完全猜中），有多少只猜中了数字但没猜中位置（称这种情况为部分猜中）。
输入格式
第一行：一个四位整数 a 表示谜底。
第二行：一个四位整数 b 表示解答。
输出格式
第一行：单个整数，表示完全猜中的数量；
第二行：单个整数，表示部分猜中的数量。
样例数据
输入:
5678
8671
输出:
2
1
说明:
6与7为完全猜中，8为部分猜中

#include 
#include 
#include 
using namespace std;
int main()
{
	string a,b;
	cin>>a>>b;
	int ans=0;
	for(int i=0;i<4;i++){
		if(a[i]==b[i]){
			ans++;
			a[i]=b[i]='x';
		}
	}
	cout<

T3. 打印金字塔
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定一个整数 n，请打印一个具有 n 层结构的三角形金字塔，例如当 n=3 时，打印如下图形：
     / 
    /__
   /  /
  /__/__
 /  /  /
/__/__/__
输入格式
单个整数：表示 n。
输出格式
根据题意输出层次为 n 的三角形金字塔。
数据范围
1≤n≤30。
样例数据
输入:
3
输出:
     /  
    /__
   /  / 
  /__/__
 /  /  /
/__/__/__
输入:
8
输出:
               /
              /__
             /  /
            /__/__
           /  /  /
          /__/__/__
         /  /  /  /
        /__/__/__/__
       /  /  /  /  /
      /__/__/__/__/__
     /  /  /  /  /  /
    /__/__/__/__/__/__
   /  /  /  /  /  /  /
  /__/__/__/__/__/__/__
 /  /  /  /  /  /  /  /
/__/__/__/__/__/__/__/__
 

#include 
#include 
#include 
using namespace std;
int t[2][4]={{0,1,2,0},{1,3,3,2}};
int a[121][121];
void my_cpy(int x,int y){
	for(int i=1;i>=0;i--){
		for(int j=0;j<=3;j++)
			a[x][y+j]=t[i][j];
		x--;
	}			
}
int main()
{
	int n;
	cin>>n;
	int x=120,y=1;
	for(int i=0;i 
T4. 最远城市距离
 内存限制: 256 Mb时间限制: 1000 ms
 题目描述
 大城市的道路是相互平行或垂直的，如果在城市的道路上行走，不能用点与点之间的直线距离计算长度，而是应该定义两个点（设坐标分别为 (x,y) 与 (x',y')的城市距离为
 |x-x'|+|y-y'|
 给定 n 个点的坐标，请从中寻找两个点，使得它们的城市距离达到最大，并输出这个最大值。
 输入格式
 第一行：单个整数 n。
 第二行到第 n+1 行：每行有两个整数 xi和 yi ，表示一个点的坐标。
 输出格式
 单个整数：表示最大的城市距离。
 数据范围
 对于 30% 的数据，2≤n≤5,000；
 对于 60% 的数据，2≤n≤50,000；
 对于 100% 的数据，2≤n≤500,000。
 −500,000,000≤xi ,yi≤500,000,000；
 样例数据
 输入:
 4
 0 0
 0 1
 1 3
 3 2
 输出:
 5
 说明:
 (0,0)与(3,2)的城市距离是最大的
 
#include 
#include 
using namespace std;
int n,x,y,addmax,addmin=2e9,submax,submin=2e9;
int main() {
    cin >> n;
    for (int i=1;i<=n;i++) {
        cin >> x >> y;
        addmax=max(addmax,x+y);
        addmin=min(addmin,x+y);
        submax=max(submax,x-y);
        submin=min(submin,x-y);
    }
    cout << max(addmax-addmin,submax-submin);
}
 
T5. 最大割
 内存限制: 256 Mb时间限制: 1000 ms
 题目描述
 给定一张有 nn 个点、mm 条边的无向图，如果有一种划分，能将图上的所有点不重复不遗漏地分割成两个部分（记为 S 与S'，且这两部分都不是空集，则称 (S,S') 是图的一个割（Cut）。
 对于一个割来说 (S,S') ，图上有多少边跨越这个割，这个割的大小就是多少。所谓跨越，就是指某条边的一端在 S，另一端在S'。
 对于给定的图，请找到一个最大的割，并输出这个割的大小。
 输入格式
 第一行：两个整数表示 n 与 m；
 第二行到第 m+1 行：每行两个整数 u 与 v 表示一条边的两个端点，保证 u !=v，注意同一对点之间可能有多条边，这些边应被看做是不同的边。
 输出格式
 单个整数：表示最大割的大小。
 数据范围
 对于 50% 的数据，2≤n≤16；
 对于 100% 的数据，2≤n≤24；
 1≤m≤10000。
 样例数据
 输入:
 3 5
 1 2
 2 3
 3 1
 1 3
 2 3
 输出:
 4
 说明:
 将图割成{1,2}与{3}，1与3之间有两条边，2与3之间也有两条边。
 输入:
 4 2
 1 2
 3 4
 输出:
 2
 说明:
 将图割成{1,3}与{2,4}时割最大。注意与最小割的区别，这个例子中的最小割为0（因为{1,2}与{3,4}不连通）
  
 
//部分超时
#include 
#include 
using namespace std;
const int N=30;
int a[N];//a[i]等于1或0代表 是否选取i点在集合1中(剩余的在集合2中)
int g[N][N];//邻接表
int ans=0;
void dfs(int k,int n){//枚举集合1的所有组合
	if(k>n){
		int cut=0;
		for(int i=1;i<=n;i++)
			if(a[i]==1){//该点在集合1中
				for(int j=1;j<=n;j++)//枚举所有在集合2中的点统计割
					if(a[j]==0) cut+=g[i][j];
			}
		ans=max(ans,cut);//更新最大割
		return;
	}
	a[k]=1;
	dfs(k+1,n);
	a[k]=0;
	dfs(k+1,n);
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){//完成邻接矩阵
		int u,v;cin>>u>>v;
		g[u][v]++;g[v][u]++;
	}
	dfs(1,n);
	cout<
 
//优化AC代码
#include 
#include 
using namespace std;
const int N=30;
int a[N];//a[i]等于1或0代表 是否选取i点在集合1中(剩余的在集合2中)
int g[N][N];//邻接表
int ans=0;
void dfs(int cut,int k,int n){//枚举集合1的所有组合
	if(k>n){
		ans=max(ans,cut);//更新最大割
		return;
	}
	
	int add=0;
	a[k]=1;//k点在集合1中
	for(int i=1;i>n>>m;
	for(int i=1;i<=m;i++){//完成邻接矩阵
		int u,v;cin>>u>>v;
		g[u][v]++;g[v][u]++;
	}
	dfs(0,1,n);
	cout<