首页 > 代码库 > 不知道说些什么
不知道说些什么
昨天学会了KMP,trie，AC自动机。好兴奋，又可以刷一波题啦。。
还是先把我出的题题解发一下吧，
T 1 圆排列
题目背景
第一题总是不会太难的
题目描述
小学奥数班要召开会议，但是只有一个桌子。小学生们啊，就是不愿意别人说自己矮。于是他们找到了正在上高中的你来帮助他们
有N个学生顺时针围在一圆桌上开会，他们对身高很敏感。 因此决定想使得任意相邻的两人的身高差距最大值最小。 如果答案不唯一，输出字典序最小的排列，指的是身高的排列。
输入输出格式
输入格式：
第一行：一个整数ng, 1 <= ng <= 5. 表示有ng组测试数据。
每组测试数据格式如下：
第一行: 一个整数N, 3 <= N <= 50
第二行, 有个N整数, 第i个整数表示第i个人的身高hi, 1<=hi<=1000。 按顺指针给出N个人的身高， 空格分开。
输出格式：
字典序最小的身高序列,同时满足相邻的两人的身高差距最大值最小。
n行，每行对应一组输入数据。
输入输出样例
2 5 1 3 4 5 7 4 1 2 3 4
1 3 5 7 4 1 2 4 3
个人觉得是一个很好的贪心，我做这道题的时候，一开始想到二分加贪心验证构造最小字典序。（此方法完全可行）
但是仔细想想，直接贪心求最小间隔不就可以吗。
具体思路，先将输入排序1 3 4 5 7
然后把最小的放在中间 1
第二小的往右放 1 3 想象此时l=1,r=3
然后把第三小的往左放，为什么这样优呢？因为如果往左放得到的l,r为4，3，否则为1，4，明显前者更优
然后把minn求出来之后，贪心求最小字典序即可
#include <bits/stdc++.h> using namespace std; int a[200]; int b[200]; int main() { int ng; scanf("%d",&ng); while(ng--){ int n; scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); sort(a+1,a+n+1); int l=a[1],r=a[1]; int minn=0; for(int i=2;i<=n;i++){ if(l>r)minn=max(minn,a[i]-r),r=a[i]; else minn=max(minn,a[i]-l),l=a[i]; } b[100]=a[1]; int head=100,tail=100; l=r=a[1]; for(int i=2;i<=n;i++){ if(a[i+1]-l<=minn)b[++tail]=a[i]; else b[--head]=a[i],l=a[i]; } for(int i=100;i<=tail;i++)printf("%d ",b[i]); for(int i=head;i<100;i++)printf("%d ",b[i]); if(ng!=0)printf("\n"); } return 0; }
T 2
删数
（同bzojCow Lineup
T 3
题目背景
Amphetamine挑战Alphago
但是这种事，他们不屑于干，于是就找到了大名鼎鼎的Farmer John来代替他们
题目描述
这个游戏上在一个无限大的棋盘上， 棋盘上只有一颗棋子（x,y）(0<=x)
棋盘的左下角是（0，0）
Amphetamine每次都是第一个移动棋子，然后Amphetamine与Alphago轮流移动。每一轮可以做以下三种中的一种操作：
1）将棋子从当前位置向左移动任意格；
2）将棋子从当前位置向下移动任意格；
3）将棋子从当前位置向下移动k格再向左移动k格（k为任意正整数，且要满足移动后的棋子仍然在棋盘上）
第一个不能在棋盘上移动的人比赛算输（因为棋子处在（0,0）点）。
共有T个回合（1<=T<=1,000）,每次给出一个新起始点的坐标（x,y）,确定是谁赢。
输入输出格式
输入格式：
第1行：两个用空格隔开的整数M和N；
第2行：一个整数T；
第3到第T+2行：两个用空格隔开的整数x和y.
输出格式：
第1到T行：包含“Farmer John”或者是“Bessie”，表示谁赢了这轮游戏。
输入输出样例
1 1 1
Bessie
说明
对于100% 的数据x在int范围内T<=1000
30%的数据 x,y<=1000
60%的数据 x,y<=100000
威佐夫博弈不多说
170B超短代码
#include<ios> main(){int x,y;scanf("%d");while(scanf("%d%d",&x,&y)==2){if(x>y)x^=y,y^=x,x^=y;printf(x==int(1.618033989*(y-x))?"Alphago\n":"Amphetamine\n");}}
不知道说些什么