Good Bye 2018！
题目链接：https://codeforces.com/contest/1091
A. New Year and the Christmas Ornament
题意：
给出三堆数量分别为y，b，r的东西，现在要你从三堆中各选一堆，满足y'+1=b'且b'+1=r' (y',r',b'分别是指从中选取的个数)。
现在问最多能拿出的个数为多少。
题解：
我是直接模拟的= =但是有更简单的方法。
让y+=2，b+=1，那么现在的最优解为min(y,b,r)*3-3。这个还是很好证明的。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,y,b,r;
int ans = ;
void Print(int x,int z,int t){
ans=max(x+z+t,ans);
}
int ok(int o,int p,int q){
return o<=y && p<=b && q<=r;
}
int main(){
cin>>y>>b>>r;
if(ok(r-,r-,r)) Print(r-,r-,r);
else if(ok(b-,b,b+)) Print(b-,b,b+);
else Print(y,y+,y+);
cout<<ans;
return ;
}
B. New Year and the Treasure Geolocation
题意：
给出两个种类的点，每个种类的点有n个，现在要求一个目的点，满足两类点中，各存在一个点，它们的横纵坐标之和等于目的点的横纵坐标。
题目保证存在这个目的点。
题解:
我想的是排序后，最小的x加上最大的x即为目的点的横坐标，对于纵坐标也同理。
因为假设x1<x2<...<xn-1<xn，现在选取的两个点是x2,xn，那么对于其它的选择，肯定有个xt与x1匹配，又因x1<x2,xt<xn，就有x1+xt<x2+xn，这时不符合题意。
还有一种更为简单的方法，直接取均值即可，因为题目保证有解，目的点的横坐标就可以为（x1+x2+...x2*n）/n。
其实两种方式的本质都是一样的。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = ;
int n;
struct node{
int x,y;
bool operator < (const node &A)const{
return A.x==x ? y<A.y : x<A.x;
}
}p1[N],p2[N];
int main(){
cin>>n;
for(int i=;i<=n;i++) scanf("%d%d",&p1[i].x,&p1[i].y);
for(int i=;i<=n;i++) scanf("%d%d",&p2[i].x,&p2[i].y);
sort(p1+,p1+n+);sort(p2+,p2+n+);
cout<<p1[].x+p2[n].x<<" "<<p1[].y+p2[n].y;
return ;
}
C. New Year and the Sphere Transmission
题意：
n个人围成一个圈，然后从1号开始丢球，丢到后面第k个人(1+k)，问最后如果球可以回到1号手中，那么接到球的人的编号总和是多少。
题解：
我们可以知道，如果k为n的因子，那么球是肯定能够回到1号手中的。如果不为因子呢？
考察等式：a*k-b*n=c，这里假定k为已知量，那么当c=gcd(k,n)时，这个方程有整数解，这时c就为k确定时可能到的人的编号。
从这里可以看出，如果k不为n的因子而如果为一些其它的值，那么结果会重复。
所以我们就找n的因子就好了，对于每一个确定的k，因为他是因子，那么跳一圈即可回到1手中，最后求个等差数列求和就行了。
代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
vector <ll> vec;
int main(){
cin>>n;
for(int i=;i*i<=n;i++){
if(n%i==){
vec.push_back(i);
if(i*i!=n) vec.push_back(n/i);
}
}
vec.push_back();vec.push_back(n);
vector <ll > ans ;
for(auto d:vec){
ll last = n-d+;
ans.push_back((last+)*((last-)/d+)/);
}
sort(ans.begin(),ans.end());
for(auto v:ans){
printf("%I64d ",v);
}
return ;
}
D. New Year and the Permutation Concatenation
题意:
按字典序给出1-n的所有全排列的序列，然后问有多少个长度为n的序列，他们的和为n*(n+1)/2。
题解：
首先分析，如果和为n*(n+1)/2，那么必然1-n中的每个数出现了一次。
然后给出两种思路：
第一种：注意分析条件，给出的序列是按字典序的，那么就有这么一个性质：
如果当前改变的最高位为i(从右开始数)，那么1~i-1的数字是不会有改变的（我们两段两段地分析，每段长度为n）。
之后我们考虑，对于第i位的数字，它会增大几次？显然答案为n-i次，也就是说，这一位作为最高位发生变化的情况有n-i次。
那么我们就可以求出每一位作为最高位而发生改变的总情况为 (n-i)*fac[n]/fac[n-i+1] 次，每次对答案会有i的贡献(1+i-1)，所以每一位的总贡献就是i*(n-i)*fac[n]/fac[n-i+1]。
PS：最后答案会加上一个1，因为我们这里算的是有变化而产生的情况，而对于最后一段不会有变化了，但它本身就是一种情况。
代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = ,N = 1e6+;
ll n;
ll fac[N];
ll qp(ll a,ll b){
ll ans = ;
while(b){
if(b&) ans=ans*a%MOD;
a=a*a%MOD;
b>>=;
}
return ans ;
}
int main(){
cin>>n;
ll ans = ;
fac[]=;
for(int i=;i<=1e6;i++) fac[i]=fac[i-]*i%MOD;
for(int i=n-;i>=;i--){
ll d = n-i;
ll now = fac[n]*qp(fac[n-i+],MOD-)%MOD;
ans=(ans+(ll)i*now%MOD*d%MOD)%MOD;//out
}
cout<<ans;
return ;
}
另外一种思路与第一种也有相似之处，还是利用序列按字典序排列后所拥有的性质。
我们首先知道一共有n*n!总情况，我们之前分析的是对答案有贡献的情况，现在从另一个角度来分析：对答案没有贡献的情况。
我们考虑长度为n的序列中，从第i位到第n位都为递减，即此时为1~i-1不变时的最大序列，那么下次会对i-1位进行改变，改变的操作就是从i-1位变为i，i变为i-1。注意此时i~n位递减，不包含i-1也递减的情况。
在这两段序列中，从1~i-1开始的长度为n的序列，依然满足条件，而i~n开始的，则不满足条件。
那么我们只需要把不满足条件的减去就好了。
假设序列后面k个单减，那么他们出现的总情况就为fac[n]/fac[k]，最后减去他们就行了。
当k=n时结果为1，但我们不用减去，这种情况对答案的贡献是1。跟刚才加上1类似。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = ,N = 1e6+;
ll fac[N],inv[N];
ll n;
ll qp(ll a,ll b){
ll ans =;
while(b){
if(b&) ans=a*ans%MOD;
a=a*a%MOD;
b>>=;
}
return ans ;
}
int main(){
cin>>n;
fac[]=inv[]=;
for(int i=;i<=n;i++) fac[i]=i*fac[i-]%MOD;
for(int i=;i<=n;i++) inv[i]=qp(fac[i],MOD-);
ll ans = n*fac[n]%MOD;
ll tmp = fac[n];
ll sum = ;
for(int i=;i<n;i++)
sum=(sum+inv[i])%MOD;
ans = ((ans-tmp*sum)%MOD+MOD)%MOD;
cout<<ans;
return ;
}