2015ACM浙江省省赛部分题解

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 A_i 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 A_i (1 <= A_i <= 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

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<iomanip>
#include<list>
#include<deque>
#include<map>
#include <stdio.h>
#include <queue>
#include <stack>
#define maxn 10000+5
#define ull unsigned long long
#define ll long long
#define reP(i,n) for(i=1;i<=n;i++)
#define rep(i,n) for(i=0;i<n;i++)
#define cle(a) memset(a,0,sizeof(a))
#define mod 90001
#define PI 3.141592657
#define INF 1<<30
const ull inf = 1LL << 61;
const double eps=1e-5;

using namespace std;
struct node{
	int id;
	int cnt;
}a[1010];
bool cmp(node a,node b)
{
    return a.cnt>b.cnt;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    //freopen("out.txt","w",stdout);
    int t,n,b;
    cin>>t;
    while(t--){
		cin>>n;
		cle(a);
		for(int i=0;i<n;i++){
			cin>>b;
			a[b].id=b;
			a[b].cnt++;
		}
		sort(a,a+1001,cmp);
		if(a[0].cnt==a[1].cnt)
			cout<<"Nobody"<<endl;
		else cout<<a[0].id<<endl;
    }
    return 0;
}

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 i^thinteger denotes the skill level of i^th student. Every integer will not exceed 10⁹.

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

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<iomanip>
#include<list>
#include<deque>
#include<map>
#include <stdio.h>
#include <queue>
#include <stack>
#define maxn 100000+5
#define ull unsigned long long
#define ll long long
#define reP(i,n) for(i=1;i<=n;i++)
#define rep(i,n) for(i=0;i<n;i++)
#define cle(a) memset(a,0,sizeof(a))
#define mod 90001
#define PI 3.141592657
#define INF 1<<30
const ull inf = 1LL << 61;
const double eps=1e-5;

using namespace std;

bool cmp(int a,int b)
{
    return a>b;
}
int t,n;
int ans;
int a[maxn],b[33];//b数组存放第i位为最高位且为1数 的个数
void hibit(int x){
	int l=31;
	while(l>=0){
		if(x&(1<<l)){
			b[l]++;
			return ;
		}
		l--;
	}
	return ;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    //freopen("out.txt","w",stdout);
    cin>>t;
    while(t--){
		cin>>n;
		cle(b);
		for(int i=0;i<n;i++)
		{
			cin>>a[i];
			hibit(a[i]);
		}
		ans=0;
		for(int i=0;i<n;i++){
			int l=31;
			while(l>=0){
				if(a[i]&(1<<l))break;//去掉a[i]的最高位
				l--;
			}
			while(l>=0){
				if(!(a[i]&(1<<l)))ans+=b[l];
				l--;
			}
		}
		printf("%d\n",ans);
    }
    return 0;
}

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

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<iomanip>
#include<list>
#include<deque>
#include<map>
#include <stdio.h>
#include <queue>
#include <stack>
#define maxn 100000+5
#define ull unsigned long long
#define ll long long
#define reP(i,n) for(i=1;i<=n;i++)
#define rep(i,n) for(i=0;i<n;i++)
#define cle(a) memset(a,0,sizeof(a))
#define mod 90001
#define PI 3.141592657
#define INF 1<<30
const ull inf = 1LL << 61;
const double eps=1e-5;

using namespace std;

bool cmp(int a,int b)
{
    return a>b;
}
int t;

ll dp[maxn];
int vis[maxn*10];
ll sum;
int n,a;
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    //freopen("out.txt","w",stdout);
    cin>>t;
    while(t--){
		cin>>n;
		cle(vis);
		cle(dp);
		sum=0;
		for(int i=1;i<=n;i++){
			cin>>a;
			if(!vis[a]){
				dp[i]=dp[i-1]+a*i;
			}
			else{
				//cout<<dp[i-1]<<endl;
				dp[i]=dp[i-1]+a*i-a*vis[a];
			}
			vis[a]=i;
			sum+=dp[i];
		}
		printf("%lld\n",sum);
    }
    return 0;
}

The 999th Zhejiang Provincial Collegiate Programming Contest will be held in Marjar University. The canteen of Marjar University is making preparations for this grand competition. The canteen provides a lunch set of three types: appetizer, main course and dessert. Each type has several dishes with different prices for choosing.

Edward is the headmaster of Marjar University. One day, to inspect the quality of dishes, he go to the canteen and decides to choose a median set for his lunch. That means he must choose one dish from each of appetizers, main courses and desserts. Each chosen dish should at the median price among all dishes of the same type.

For example, if there are five dessert dishes selling at the price of 2, 3, 5, 10, 30, Edward should choose the dish with price 5 as his dessert since its price is located at the median place of the dessert type. If the number of dishes of a type is even, Edward will choose the dish which is more expensive among the two medians.

You are given the list of all dishes, please write a program to help Edward decide which dishes he should choose.

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 three integers S, M and D (1 <= S, M, D <= 100), which means that there are S dishes of appetizer, M dishes of main course and D dishes of dessert.

Then followed by three parts. The first part contains S lines, the second and the last part contains M and D lines respectively. In each line of the three parts, there is a string and an integer indicating the name and the price of a dish. The name of dishes will only consist of non-whitespace characters with no more than 50 characters. The price of dishes are non-negative integers less than or equal to 1000. All dish names will be distinct.

Output

For each test case, output the total price of the median set, together with the names of appetizer, main course and dessert, separated by a single space.

Sample Input

2
1 3 2
Fresh_Cucumber 4
Chow_Mein 5
Rice_Served_with_Duck_Leg 12
Fried_Vermicelli 7
Steamed_Dumpling 3
Steamed_Stuffed_Bun 4
2 3 1
Stir-fried_Loofah_with_Dried_Bamboo_Shoot 33
West_Lake_Water_Shield_Soup 36
DongPo's_Braised_Pork 54
West_Lake_Fish_in_Vinegar 48
Longjing_Shrimp 188
DongPo's_Crisp 18

Sample Output

15 Fresh_Cucumber Fried_Vermicelli Steamed_Stuffed_Bun
108 West_Lake_Water_Shield_Soup DongPo's_Braised_Pork DongPo's_Crisp

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<iomanip>
#include<list>
#include<deque>
#include<map>
#include <stdio.h>
#include <queue>
#include <stack>
#define maxn 10000+5
#define ull unsigned long long
#define ll long long
#define reP(i,n) for(i=1;i<=n;i++)
#define rep(i,n) for(i=0;i<n;i++)
#define cle(a) memset(a,0,sizeof(a))
#define mod 90001
#define PI 3.141592657
#define INF 1<<30
const ull inf = 1LL << 61;
const double eps=1e-5;

using namespace std;
struct node{
	int num;
	char s[110];
}n1[110],n2[110],n3[110];
bool cmp(node a,node b)
{
    return a.num<b.num;
}
int a,b,c;
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    //freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    while(t--){
		cin>>a>>b>>c;
		for(int i=0;i<a;i++)
			cin>>n1[i].s>>n1[i].num;
		for(int i=0;i<b;i++)
			cin>>n2[i].s>>n2[i].num;
		for(int i=0;i<c;i++)
			cin>>n3[i].s>>n3[i].num;
		sort(n1,n1+a,cmp);
		sort(n2,n2+b,cmp);
		sort(n3,n3+c,cmp);
		int sum=0;
		sum=n1[a/2].num+n2[b/2].num+n3[c/2].num;
		printf("%d %s %s %s\n",sum,n1[a/2].s,n2[b/2].s,n3[c/2].s);
    }
    return 0;
}

As a university advocating self-learning and work-rest balance, Marjar University has so many days of rest, including holidays and weekends. Each weekend, which consists of Saturday and Sunday, is a rest time in the Marjar University.

The May Day, also known as International Workers' Day or International Labour Day, falls on May 1st. In Marjar University, the May Day holiday is a five-day vacation from May 1st to May 5th. Due to Saturday or Sunday may be adjacent to the May Day holiday, the continuous vacation may be as long as nine days in reality. For example, the May Day in 2015 is Friday so the continuous vacation is only 5 days (May 1st to May 5th). And the May Day in 2016 is Sunday so the continuous vacation is 6 days (April 30th to May 5th). In 2017, the May Day is Monday so the vacation is 9 days (April 29th to May 7th). How excited!

Edward, the headmaster of Marjar University, is very curious how long is the continuous vacation containing May Day in different years. Can you help him?

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, there is an integer y (1928 <= y <= 9999) in one line, indicating the year of Edward's query.

Output

For each case, print the number of days of the continuous vacation in that year.

Sample Input

3
2015
2016
2017

Output

5
6
9

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<iomanip>
#include<list>
#include<deque>
#include<map>
#include <stdio.h>
#include <queue>
#include <stack>
#define maxn 10000+5
#define ull unsigned long long
#define ll long long
#define reP(i,n) for(i=1;i<=n;i++)
#define rep(i,n) for(i=0;i<n;i++)
#define cle(a) memset(a,0,sizeof(a))
#define mod 90001
#define PI 3.141592657
#define INF 1<<30
const ull inf = 1LL << 61;
const double eps=1e-5;

using namespace std;

bool cmp(int a,int b)
{
    return a>b;
}
int n,a;
int mp[10]={6,9,6,5,5,5,5};
bool leap(int x){
	if(x%4==0&&x%100!=0)
		return true;
	if(x%400==0)
		return true;
	return false;
}
int solve(int x){
	int cnt=0;
	if(x>2015){
		for(int i=2016;i<=x;i++)
			if(leap(i))cnt++;
		int d=(x-2015+cnt)%7;
		int t=(5+d)%7;
		return mp[t];
	}
	else if(x<2015){
		for(int i=x;i<2015;i++)
			if(leap(i))cnt++;
		if(leap(x))cnt--;
		int d=(2015-x+cnt)%7;
		int t=(abs(5-d))%7;
		//cout<<t<<endl;
		return mp[t];
	}
	else if(x==2015)return 5;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    //freopen("out.txt","w",stdout);
    while(cin>>n){
		for(int i=1;i<=n;i++){
			cin>>a;
			printf("%d\n",solve(a));
		}
    }
    return 0;
}
/*
//以下是网上的题解。。
#include<stdio.h>
int a[7]= {6,9,6,5,5,5,5};
int main()
{
    int year,T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&year);
        int k=year-1928;
        int cnt=0;
        for(int i=1929; i<=year; i++)
        {
            if(i%400==0||(i%4==0&&i%100!=0)) cnt++;
        }
        printf("%d\n",a[(2+k+cnt)%7]);
    }
    return 0;
}
*/

Edward, a poor copy typist, is a user of the Dvorak Layout. But now he has only a QWERTY Keyboard with a broken Caps Lock key, so Edward never presses the broken Caps Lock key. Luckily, all the other keys on the QWERTY keyboard work well. Every day, he has a lot of documents to type. Thus he needs a converter to translate QWERTY into Dvorak. Can you help him?

The QWERTY Layout and the Dvorak Layout are in the following:

The QWERTY Layout

The Dvorak Layout

Input

A QWERTY document Edward typed. The document has no more than 100 kibibytes. And there are no invalid characters in the document.

Output

The Dvorak document.

Sample Input

Jgw Gqm Andpw a H.soav Patsfk f;doe
Nfk Gq.d slpt a X,dokt vdtnsaohe
Kjd yspps,glu pgld; aod yso kd;kgluZ
1234567890
`~!@#$%^&*()}"']_+-=ZQqWEwe{[\|
ANIHDYf.,bt/
ABCDEFuvwxyz

Sample Output

Hi, I'm Abel, a Dvorak Layout user.
But I've only a Qwerty keyboard.
The following lines are for testing:
1234567890
`~!@#$%^&*()+_-={}[]:"'<>,.?/\|
ABCDEFuvwxyz
AXJE>Ugk,qf;

在CF上做过类似的题目。哈哈

就是打两个表，，不过要细心啊

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<iomanip>
#include<list>
#include<deque>
#include<map>
#include <stdio.h>
#include <queue>
#include <stack>
#define maxn 10000+5
#define ull unsigned long long
#define ll long long
#define reP(i,n) for(i=1;i<=n;i++)
#define rep(i,n) for(i=0;i<n;i++)
#define cle(a) memset(a,0,sizeof(a))
#define mod 90001
#define PI 3.141592657
#define INF 1<<30
const ull inf = 1LL << 61;
const double eps=1e-5;

using namespace std;

bool cmp(int a,int b)
{
    return a>b;
}
char *s={"_-+=QWERTYUIOP{}[]qweASDFGHJKL:\";'ZzXCVBNM<>?,./rtyuiopasdfghjklxcvbnm"};
char *t={"{[}]\"<>PYFGCRL?+/=',.AOEUIDHTNS_s-:;QJKXBMWVZwvzpyfgcrlaoeuidhtnqjkxbm"};
char p;
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    //freopen("out.txt","w",stdout);
    //cout<<strlen(s1)<<" "<<strlen(t)<<endl;
    map<char,char>mp;
    for(int i=0;i<strlen(s);i++)
		mp[s[i]]=t[i];
    while(~scanf("%c",&p)){//不知道为什么用gets()会re..
		if(!mp[p]){
			putchar(p);
		}
		else putchar(mp[p]);
    }
    return 0;
}

L http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3880

   Demacia of the Ancients

There is a popular multiplayer online battle arena game called Demacia of the Ancients. There are lots of professional teams playing this game. A team will be approved as Level K if there are exact K team members whose match making ranking (MMR) is strictly greater than 6000.

You are given a list of teams. Please calculate the level of each team.

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 <= 10) indicating the number of team members.

The second line contains N integers representing the MMR of each team member. All MMRs are non-negative integers less than or equal to 9999.

Output

For each test case, output the level of the given team.

Sample Input

3
5
7986 6984 6645 6200 6150
5
7401 7377 6900 6000 4300
3
800 600 200

Sample Output

5
3
0

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<iomanip>
#include<list>
#include<deque>
#include<map>
#include <stdio.h>
#include <queue>
#include <stack>
#define maxn 10000+5
#define ull unsigned long long
#define ll long long
#define reP(i,n) for(i=1;i<=n;i++)
#define rep(i,n) for(i=0;i<n;i++)
#define cle(a) memset(a,0,sizeof(a))
#define mod 90001
#define PI 3.141592657
#define INF 1<<30
const ull inf = 1LL << 61;
const double eps=1e-5;

using namespace std;

bool cmp(int a,int b)
{
    return a>b;
}
int t,n;
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    //freopen("out.txt","w",stdout);
	cin>>t;
	while(t--){
		cin>>n;
		int ans=0,a;
		for(int i=1;i<=n;i++)
		{
			cin>>a;
			if(a>6000)ans++;
		}
		cout<<ans<<endl;
	}
    return 0;
}