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 <iostream>
#include <cmath>
#include <algorithm>
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<<a[i]<<" ";
return 0;
}T2. 珠玑妙算（一）
内存限制: 256 Mb时间限制: 1000 ms
题目描述
珠玑妙算（Mastermind）是一种猜谜游戏。
在游戏开始前，系统会生成一个十进制的四位整数（每一位数字都不相同）作为谜底。玩家需要提供一个十进制的四位整数（每一位数字也都不相同）作为解答。
对于给定的解答，请统计谜底中有多少既被猜中了数字也被猜中了位置（称这种情况为完全猜中），有多少只猜中了数字但没猜中位置（称这种情况为部分猜中）。
输入格式
第一行：一个四位整数 a 表示谜底。
第二行：一个四位整数 b 表示解答。
输出格式
第一行：单个整数，表示完全猜中的数量；
第二行：单个整数，表示部分猜中的数量。
样例数据
输入:
5678
8671
输出:
2
1
说明:
6与7为完全猜中，8为部分猜中
#include <iostream>
#include <cstring>
#include <algorithm>
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<<ans<<endl;
ans=0;
for(int i=0;i<4;i++){
if (b[i]!='x'){
for(int j=0;j<4;j++)
if(i!=j&&b[i]==a[j]){
ans++;
break;
}
}
}
cout<<ans;
return 0;
}T3. 打印金字塔
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定一个整数 n，请打印一个具有 n 层结构的三角形金字塔，例如当 n=3 时，打印如下图形：
? ? ?/\?
? ? /__\
? ?/\ ?/\
? /__\/__\
?/\ ?/\ ?/\
/__\/__\/__\
输入格式
单个整数：表示 n。
输出格式
根据题意输出层次为 n 的三角形金字塔。
数据范围
1≤n≤30。
样例数据
输入:
3
输出:
? ? ?/\ ?
? ? /__\
? ?/\ ?/\?
? /__\/__\
?/\ ?/\ ?/\
/__\/__\/__\
输入:
8
输出:
? ? ? ? ? ? ? ?/\
? ? ? ? ? ? ? /__\
? ? ? ? ? ? ?/\ ?/\
? ? ? ? ? ? /__\/__\
? ? ? ? ? ?/\ ?/\ ?/\
? ? ? ? ? /__\/__\/__\
? ? ? ? ?/\ ?/\ ?/\ ?/\
? ? ? ? /__\/__\/__\/__\
? ? ? ?/\ ?/\ ?/\ ?/\ ?/\
? ? ? /__\/__\/__\/__\/__\
? ? ?/\ ?/\ ?/\ ?/\ ?/\ ?/\
? ? /__\/__\/__\/__\/__\/__\
? ?/\ ?/\ ?/\ ?/\ ?/\ ?/\ ?/\
? /__\/__\/__\/__\/__\/__\/__\
?/\ ?/\ ?/\ ?/\ ?/\ ?/\ ?/\ ?/\
/__\/__\/__\/__\/__\/__\/__\/__\
?
#include <iostream>
#include <string>
#include <algorithm>
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<n;i++){
y+=i*2;
for(int j=1;j<=n-i;j++){
my_cpy(x,y);
y+=4;
}
x-=2;
y=1;
}
for(int i=120-2*n+1;i<=120;i++){
for(int j=1;j<=4*n+1;j++)
switch(a[i][j]){
case 0:cout<<" ";break;
case 1:cout<<"/";break;
case 2:cout<<"\\";break;
case 3:cout<<"_";break;
}
cout<<endl;
}
return 0;
}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 <iostream>
#include <algorithm>
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);
}
/*
任意两点的曼哈顿距离公式：
｜ x-x' ｜ + ｜ y-y' ｜
绝对值里面的值可正可负。接下来分类讨论。
在下面的式子中，(x,y)为平面上一点，(x',y')为平面上另一点。我们可以对原式变形：
1.两个绝对值内都是正数：(x-x')+(y-y')=(x+y)-(x'+y')
2.两个绝对值内都是负数：(-x+x')+(-y+y')=(x'+y')-(x+y)
3.两个绝对值为一正一负：(x-x')+(-y+y')=(x-y)-(x'-y')
4.两个绝对值为一负一正：(-x+x')+(y-y')=(x'-y')-(x-y)
我们把式子这样变形，是为了让减号前的值最大，减号后的值最小。
这样我们就只要取一个最大值，一个最小值就可以得出最远距离。而
且，每一个点是相互独立的，我们要保证减号两边的运算都只和一个点相关。
可以发现，一式和二式等价，三式和四式等价（互为相反数），
所以我们只要在每组等价的式子中取正值，再对它们取最大值即可。
而取最大值最小值的工作，只需要边输入边做。
经过观察，我们只需要在输入时取x+y的最大最小值和x-y的最大最小值，
因为(x,y)和(x',y')在这里是等价的。
*/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 <iostream>
#include <cstdio>
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<<ans<<endl;
return 0;
}//优化AC代码
#include <iostream>
#include <cstdio>
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<k;i++) //统计k点于已分配集合2中的点形成的割
if(a[i]==0) add+=g[k][i];
dfs(cut+add,k+1,n);
if(k==1) return;//优化算法 只求元素1在集合1中的方法 减少半数计算
add=0;
a[k]=0;//k点在集合2中
for(int i=1;i<k;i++) //统计k点于已分配集合1中的点形成的割
if(a[i]==1) add+=g[k][i];
dfs(cut+add,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(0,1,n);
cout<<ans<<endl;
return 0;
}
