首页 > 其他分享 >Sumsets UVA - 10125

Sumsets UVA - 10125

时间:2023-04-16 16:13:35浏览次数:46  
标签:int pair UVA include Sumsets 10125

 

一个集合中需要找到 a,b,c,d ,使得 a+b+c=d

 

枚举a,b ,计算a+b,存在map里

再枚举d,c ,计算d-c 是否 存在 d-c==a+b

 

#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;
const int N=1e3+2;

//a+b==d-c
#define pii pair<int,int>
#define mk(x,y) make_pair(x,y)
int n;
 map<int,vector<pii> > mp;
 int a[N];
 
 int H(){
 	int i,j;
 	for(j=n;j>0;j--)
 	 for(i=j-1;i>0;i--){
 	 	int t=a[j]-a[i];
 	 	for(int k=0;k<mp[t].size();k++){
 	 		int xx=mp[t][k].first,yy=mp[t][k].second;
 	 		if(xx!=a[i]&&yy!=a[j]&&xx!=a[j]&&yy!=a[i])
 	 			return j;
 	 	}
 	 }
 	return -1;
 }
 void sov(){
 	int i,j;
 	for(i=1;i<=n;++i) cin>>a[i];sort(a+1,a+1+n);
 	for(i=1;i<=n;i++)
 	 for(j=i+1;j<=n;j++)
 	  mp[a[i]+a[j]].push_back(mk(a[i],a[j]));
 	
 	int t=H();
 	if(t==-1) cout<<"no solution"<<endl;
 	else  cout<<a[t]<<endl;
 }
 signed main(){
 	while(cin>>n,n){
 		mp.clear() ;
 		sov();
 	}
 }
 
 

 

标签:int,pair,UVA,include,Sumsets,10125
From: https://www.cnblogs.com/towboa/p/17323406.html

相关文章

  • UVA1382 Distant Galaxy
    给出平面上的n个点,找一个矩形,使得边界上包含的点尽可能地多。 先维护前缀和col[i][j],row[i][j],表示i行前j个的和。。枚举上下边界,右边界,考虑维护左边届 #include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;constintN=200;struct......
  • UVA1330 City Game
    利用网格图上空白的方格上建一个矩形的建筑。问地区中建筑物的最大面积  递推(dp) #include<iostream>#include<cstring>#include<sstream>usingnamespacestd;constintN=1e3+2;chara[N][N];intn,m,up[N][N],L[N][N],R[N][N];voidsolve(){ inti,j;......
  • kuangbin专题一 简单搜索 起火迷宫(UVA-11624)
    Fire!DescriptionJoeworksinamaze.Unfortunately,portionsofthemazehavecaughtonfire,andtheownerofthemazeneglectedtocreateafireescapeplan.HelpJoeescapethemaze.GivenJoe’slocationinthemazeandwhichsquaresofthemazeareo......
  • UVA1650 数字串 Number String
    对于任意一个只含数字1~n的有序数字串{a1,a2,……,an},比较数字串中所有相邻数字的大小,后者大于前者的用I表示,否则用D表示。例如,数字串{3,1,2,7,4,6,5},{2,1,3,7,4,6,5}和{3,1,2,7,5,6,4}就表示为'DIIDID'。"?"则表示两数的关系未知。例如,'?D'既有可能是ID,也有可能是‘DD’。现给出......
  • UVA 12295 Optimal Symmetric Paths 最短路求方案数
    题目:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=23587题意:给一个n*n的矩阵,每个方格中有一个数字,从左上角走到右下角,且路径必须关于副对角线对称,求使路线上数字和最小的方案数思路:既然要关于副对角线对称,那么可以把关于副对角线对称的方格的值加到一起去,这样就......
  • UVA - 699 The Falling Leaves 二叉树
    题目:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19244题意:给定一棵二叉树,把根节点标号成0,然后每往左走标号就减1,每往右走标号就加1,问相同标号的节点的值得和,按标号的大写依次输出思路:输入挺坑的,不过看了一会,可以边输入边建树,碰到其他值要接着往下递归建树,碰到-1......
  • Party at Hali-Bula UVA - 1220
     多判断一个唯一性 only[x][0/1]#include<iostream>#include<cstring>#include<vector>#include<map>#include<algorithm>usingnamespacestd;constintN=205;intf[N][2],n,K;intonly[N][3];vector<int>g[N];map&l......
  • Another Crisis UVA - 12186
      #include<iostream>#include<cstring>#include<vector>#include<algorithm>usingnamespacestd;constintN=1e5+3;intf[N],n,K;vector<int>g[N];voiddfs(intx){ intb[N],tot; tot=0; if(g[x].size()==0)......
  • UVa 10182 Bee Maja (规律&O(1)算法)
    10182-BeeMajaTimelimit:3.000seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1123Majaisabee.Shelivesinabeehivewiththousandsofotherbees.Thisbeehivecon......
  • Alibaba UVA - 1632
    在一条直线的同一个方向上有nn件珠宝,已知每件珠宝的位置,并且第ii件珠宝在Ti时刻消失,问将所有的珠宝收集起来最小耗时?搜集不耗时,移动需要耗时 类似区间dpf[i][j][2]#pragmaGCCoptimize(2)#include<iostream>usingnamespacestd;constintN=1e4+3......