2017年浙江工业大学大学生程序设计迎新赛预赛

A 栗酱的异或和

题意： 栗酱特别喜欢玩石子游戏，就是两个人玩，有n堆石子，每堆有a_i个，每次一个人可以轮流选择任意一堆，取走任意多的石子（但不能不取），谁先不能取谁输。
每组数据第一行一个n，k表示一共有n堆石子，接下来你试图从第k堆开始取，从第二行开始，每隔一个空格一个第i堆石子的数量ai。输出Yes和No表示从第k堆开始取是否可以获胜
题解： 将除了第k堆以外堆的石子数异或和，如果最后结果sum<a[k] 那么先手可以将取走a[k] 中的石子使得石子数等于sum这样就达到一个平衡局面，而面对平衡局面的人必输。有关平衡局面可以参考这篇博文—>取石子（平衡问题）

#include <cstdio>
const int N = 1e5 + 5 ;
int a[N] ;
int main(){
    int t ; scanf ("%d",&t) ;
    while(t --){
        int n,k ; scanf("%d%d",&n,&k) ;
        int sum = 0 ;
        for (int i = 1 ; i <= n ; ++ i){
            scanf ("%d",&a[i]) ;
            if (i != k)    sum ^= a[i] ;
        }
        if (sum >= a[k])    printf ("No\n") ;
        else    printf ("Yes\n") ;
    }
    return 0 ;
}

D 简单的数据结构

题意：一开始该容器为空，有以下七种操作。
1 从前面插入元素a
2 从前面删除一个元素
3 从后面插入一个元素
4 从后面删除一个元素
5 将整个容器头尾翻转
6 输出个数和所有元素
7 对所有元素进行从小到大排序
题解：其实就是用双头队列deque来模拟实现，但是因为我并不知道有这样一个容器，emmmmm所以记录一下—>deque常用方法

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std ;
deque<int> q ;
int main(){
    int n , m ; scanf ("%d%d",&n,&m) ;
    while(m -- ){
        int x ; scanf ("%d",&x);
        if (x == 1){
            int a ; scanf ("%d",&a) ;
            q.push_front(a) ;
        }
        else if (x == 2)    q.pop_front() ;
        else if (x == 3){
            int a ; scanf ("%d",&a) ;
            q.push_back(a) ;
        }
        else if (x == 4)    q.pop_back() ;
        else if (x == 5)    reverse(q.begin(),q.end()) ;
        else if (x == 6){
            printf ("%d\n",q.size()) ;
            for (int i = 0 ; i < q.size() ; ++ i)
                printf ("%d ",q[i]) ;
            printf ("\n") ;
        }
        else if (x == 7)    sort(q.begin(),q.end()) ;
    }
    return 0;
}

E-小咪买东西

题意：给出n个物品的价值v_i和花费c_i，要求选择k个物品使得${\sum }_{i=1}^n$V_i / ${\sum }_{i=1}^n$C_i 最大。
题解：这是一个最大平均值问题。本来用贪心去做，以所有的物品的单位价值去排序然后来选择，但是这样是错的因为它求的是总的价值比总的花费最大。
正确做法：
设答案为ans即${\sum }_{i=1}^n$V_i / ${\sum }_{i=1}^n$C_i =ans，将公式变形就是${\sum }_{i=1}^n$V_i - ans*${\sum }_{i=1}^n$C_i = 0 ,可以二分答案ans只要${\sum }_{i=1}^n$V_i - ans*${\sum }_{i=1}^n$C_i >= 0即可，然后二分找出最大的ans 。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std ;
const int N = 1e4 + 5 ;
typedef long long ll ; 
struct node{
	int v , c ; 
}a[N] ;
ll b[N] ; 
int n , k ; 
bool cmp(int x,int y){
	return x > y ; 
}
bool check(int mid){
	for (int i=0 ; i<n ; ++i)
		b[i] = a[i].v-a[i].c*mid ; 
	sort(b,b+n,cmp) ;
	ll sum = 0 ;//sum 和b数组要用long long否则会超内存
	for (int i=0;i<k;++i)	sum += b[i] ;
	return sum>=0 ; 
}
int main(){
	int t ; cin >> t ; 
	while(t--){
		scanf ("%d%d",&n,&k) ;
		for (int i=0 ; i<n ; ++i)
			scanf("%d%d",&a[i].c,&a[i].v) ;
		int l = 0 , r = 10000 , ans = 0 ; 
		while(l <= r){
			int mid = (l+r)/2 ; 
			if (check(mid))	
				ans = max(ans,mid) , l=mid+1 ; 
			else	r = mid-1 ; 
		}
		printf ("%d\n",ans) ;
	}
	return 0;
} 

J-裁缝大师

题意：给出圆心坐标x,y还有圆的半径r，以及正多边形的边数n，问以圆心x轴正方向为第一个顶点，顺时针输出每个顶点的坐标。
题解：先假设圆心在原点算出每个顶点的x，y然后加上圆心坐标，通过圆心角的cos值算出x还有圆心角的sin值算出y值。这道题最后输出要保留两位小数所以有可能输出的时候输出-0.00的情况（因为本身是-0.0000001后面被舍去但是负号仍保留所以要加上0.00000001要避免这种情况）

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std ;
int main(){
    int t ; cin >> t ;
    while(t--){
        int x , y , r , n ;
        scanf ("%d%d%d%d",&x,&y,&r,&n) ;
        double pi = 4*atan(1.0) ;
        for (int i = 0;i < n; ++ i){
            printf ("%.2lf %.2lf\n",
                    r*cos(2.0*pi-2.0*pi/n*i)+x+0.00000001,
                    r*sin(2.0*pi-2.0*pi/n*i)+y+0.00000001) ;
        }
    }
    return 0;
}