Ace of Aces
Time Limit: 2 Seconds Memory Limit: 65536 KB
There is a mysterious organization called Time-Space Administrative Bureau (TSAB) in the deep universe that we humans have not discovered yet. This year, the TSAB decided to elect an outstanding member from its elite troops. The elected guy will be honored with the title of "Ace of Aces".
After voting, the TSAB received N valid tickets. On each ticket, there is a number Ai denoting the ID of a candidate. The candidate with the most tickets nominated will be elected as the "Ace of Aces". If there are two or more candidates have the same number of nominations, no one will win.
Please write program to help TSAB determine who will be the "Ace of Aces".
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first line contains an integer N (1 <= N <= 1000). The next line contains N integers Ai (1 <= Ai <= 1000).
Output
For each test case, output the ID of the candidate who will be honored with "Ace of Aces". If no one win the election, output "Nobody" (without quotes) instead.
Sample Input
3
5
2 2 2 1 1
5
1 1 2 2 3
1
998
Sample Output
2
Nobody
998
题意：求出现次数最多的那个数，如果有多个（最多次数相等的）就输出Nobody
转载请注明出处：寻找&星空の孩子
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
#define ls 2*i
#define rs 2*i+1
#define up(i,x,y) for(i=x;i<=y;i++)
#define down(i,x,y) for(i=x;i>=y;i--)
#define mem(a,x) memset(a,x,sizeof(a))
#define w(a) while(a)
#define LL long long
const double pi = acos(-1.0);
#define Len 20005
#define mod 19999997
const int INF = 0x3f3f3f3f; int t,n,a,maxn,flag; struct node
{
int cnt,id;
}hsh[]; int cmp(node a,node b)
{
return a.cnt<b.cnt;
}; int main()
{
int i;
scanf("%d",&t);
w(t--)
{
scanf("%d",&n);
mem(hsh,);
up(i,,n-)
{
scanf("%d",&a);
hsh[a].id = a;
hsh[a].cnt++;
}
sort(hsh,hsh+,cmp);
if(hsh[].cnt==hsh[].cnt)
printf("Nobody\n");
else
printf("%d\n",hsh[].id);
} return ;
}
Team Formation
Time Limit: 3 Seconds Memory Limit: 131072 KB
For an upcoming programming contest, Edward, the headmaster of Marjar University, is forming a two-man team from N students of his university.
Edward knows the skill level of each student. He has found that if two students with skill level A and B form a team, the skill level of the team will be A ⊕ B, where ⊕ means bitwise exclusive or. A team will play well if and only if the skill level of the team is greater than the skill level of each team member (i.e. A ⊕ B > max{A, B}).
Edward wants to form a team that will play well in the contest. Please tell him the possible number of such teams. Two teams are considered different if there is at least one different team member.
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first line contains an integer N (2 <= N <= 100000), which indicates the number of student. The next line contains N positive integers separated by spaces. The ith integer denotes the skill level of ith student. Every integer will not exceed 109.
Output
For each case, print the answer in one line.
Sample Input
2
3
1 2 3
5
1 2 3 4 5
Sample Output
1
6
题意：选数组里的两个数，要求A与B异或得C，C>max(A，B)；
思路：利用二进制，把每个数分解成二进制，循环对每个数的各个位取&，在高位相等的情况下，低位有为0的情况就说明可以加上，然后加上对应是数量。
转载请注明出处：寻找&星空の孩子
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
#define ls 2*i
#define rs 2*i+1
#define up(i,x,y) for(i=x;i<=y;i++)
#define down(i,x,y) for(i=x;i>=y;i--)
#define mem(a,x) memset(a,x,sizeof(a))
#define w(a) while(a)
#define LL long long
const double pi = acos(-1.0);
#define Len 20005
#define mod 19999997
const int INF = 0x3f3f3f3f; int t,n,a[],bit[]; int main()
{
int i,j,k;
scanf("%d",&t);
w(t--)
{
mem(bit,);
scanf("%d",&n);
up(i,,n-)
{
scanf("%d",&a[i]);
for(j = ;j>=;j--)
{
if(a[i]&(<<j))
{
bit[j]++;
break;
}
}
}
LL ans = ;
up(i,,n-)
{
if(a[i])
{
int l = ;
w()
{
if(a[i]&(<<l)) break;
l--;
}
w(l>=)
{
if(!(a[i]&(<<l))) ans+=bit[l];
l--;
}
}
}
printf("%lld\n",ans);
} return ;
}
Convex Hull
Time Limit: 3 Seconds Memory Limit: 65536 KB
Edward has n points on the plane. He picks a subset of points (at least three points), and defines the beauty of the subset as twice the area of corresponding convex hull. Edward wants to know summation of the beauty of all possible subsets of points (at least three points).
No two points coincide and no three points are on the same line.
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first line contains an integer n (3 ≤ n ≤ 1000). Each of following n lines contains 2 integers xi, yi which denotes a point (xi, yi) (0 ≤ |xi|, |yi| ≤ 109).
The sum of values n for all the test cases does not exceed 5000.
Output
For each case, if the answer is S, output a single integer denotes S modulo 998244353.
Sample Input
1
3
0 0
0 1
1 0
Sample Output
1
题意：求凸边型面积的2倍，问你取大于等于3个点的两倍面积的和；
思路：求每个三个点组成的三角形面积的2倍，然后多边形面积可以由三角形面积的加起来；（三角形每个有2^(n-3)个）
（超时了。。。还在改，有没有更好的思路）
Beauty of Array
Time Limit: 2 Seconds Memory Limit: 65536 KB
Edward has an array A with N integers. He defines the beauty of an array as the summation of all distinct integers in the array. Now Edward wants to know the summation of the beauty of all contiguous subarray of the array A.
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first line contains an integer N (1 <= N <= 100000), which indicates the size of the array. The next line contains N positive integers separated by spaces. Every integer is no larger than 1000000.
Output
For each case, print the answer in one line.
Sample Input
3
5
1 2 3 4 5
3
2 3 3
4
2 3 3 2
Sample Output
105
21
38
转载请注明出处：寻找&星空の孩子
题意：算连续集合里不同数的和，然后所有集合的总和；
思路：dp，每次新加的数,先dp[i-1]+a[i]，总是要减去最近的相同的数的个数；
eg： 2 3 4 3 2 3 .....(括号内的数，表示集合由多少个数)
2(1) 3(1) 4(1) 3(1) 2(1) 3(1)
2+3(2) 3+4(2) 4+3(2) 3+2(2) 2+3(2)
2+3+4(3) 3+4(3) 4+3+2(3) 3+2(3)
2+3+4(4) 3+4+2(4) 4+3+2(4)
2+3+4(5) 3+4+2(5)
2+3+4(5)
#include<stdio.h>
#include<string.h>
#define LL long long
const int N = ;
LL dp[N];
int hsh[N]; int main()
{
int t,n,a;
scanf("%d",&t);
while(t--)
{
memset(hsh,,sizeof(hsh));
scanf("%d",&n);
dp[]=;
for(int i=;i<=n;i++)
{
scanf("%d",&a);
dp[i]=dp[i-]+a+(i--hsh[a])*a;
hsh[a]=i;
}
LL ans=;
for(int i=;i<=n;i++)
ans+=dp[i];
printf("%lld\n",ans);
}
}