涵盖知识点：思维、构造、单调栈/线段树分治。
比赛链接：
http://codeforces.com/contest/1313
A:Fast Food Restaurant
题意：三个物品各有a,b,c个，问最多可以形成多少组合。
题解：排序后从多的开始减，七种情况枚举一遍即可。
Accept Code：
1 #include <bits/stdc++.h> 2 typedef long long ll; 3 using namespace std; 4 int main(){ 5 int t; 6 scanf("%d", &t); 7 while (t--){ 8 int a,b,c,res=0; 9 cin>>a>>b>>c; 10 if(a)a--,res++; 11 if(b)b--,res++; 12 if(c)c--,res++; 13 if(a>b)swap(a,b); 14 if(a>c)swap(a,c); 15 if(b>c)swap(b,c); 16 if(b&&c)b--,c--,res++; 17 if(a&&c)a--,c--,res++; 18 if(a&&b)a--,b--,res++; 19 if(a&&b&&c)res++; 20 cout<<res<<" "; 21 } 22 }
B:Different Rules
题意：给第一场的排名x和第二场的排名y，问最多、最少几个人两场排名和小于等于你。
题解：
1.最多就是构造尽可能多的人排名等于x+y，所以答案为x+y-1和n之间的最小值。
2.最少分两种情况讨论：
1）x+y<=n：可以构造其他所有人都大于等于n。所以答案为1.
2）others：构造前t个人尽可能小。所以解不等式x-t+y-t<=n-t。解出t>=x+y-n。所以答案为x+y-n+1。
Accept Code：
1 #include <bits/stdc++.h> 2 typedef long long ll; 3 using namespace std; 4 int getmax(int n,int x,int y){ 5 return min(n,x+y-1); 6 } 7 int getmin(int n,int x,int y){ 8 if(x+y<=n)return 1; 9 return min(n,x+y-n+1); 10 } 11 int main(){ 12 int t; 13 cin>>t; 14 while (t--){ 15 int n,x,y; 16 cin>>n>>x>>y; 17 cout<<getmin(n,x,y)<<" "<<getmax(n,x,y)<<" "; 18 } 19 }
C:Skyscrapers
题意：构造一个单峰序列，每个位置有最大值限制。使得最后总和最大。
题解：利用单调栈维护出前缀和以及后缀和。遍历所有点得出最大值所在的峰值下标。最后向两边重新给数组赋值即可。另有分治得出最小值并使用线段树维护区间的方法。
复杂度：除去单调栈O(n)。线段树最好O(nlogn)。
Accept Code：
1 #include <bits/stdc++.h> 2 typedef long long ll; 3 using namespace std; 4 const int maxn=5e5+10; 5 ll a[maxn],pre[maxn],nxt[maxn],l[maxn],r[maxn]; 6 int main(){ 7 int n; 8 cin>>n; 9 a[0]=a[n+1]=0; 10 for(int i=1;i<=n;i++){ 11 cin>>a[i]; 12 } 13 stack<int> s; 14 s.push(0); 15 for(int i=1;i<=n;i++){ 16 while(a[s.top()]>a[i]) 17 s.pop(); 18 pre[i]=s.top(); 19 s.push(i); 20 l[i]=l[pre[i]]+a[i]*(i-pre[i]); 21 } 22 while(!s.empty()) 23 s.pop(); 24 s.push(n+1); 25 for(int i=n;i>=1;i--){ 26 while(a[s.top()]>a[i]) 27 s.pop(); 28 nxt[i]=s.top(); 29 s.push(i); 30 r[i]=r[nxt[i]]+a[i]*(nxt[i]-i); 31 } 32 int idx=0; 33 ll res=0; 34 for(int i=1;i<=n;i++){ 35 if(res<l[i]+r[i]-a[i]) 36 res=l[i]+r[i]-a[i],idx=i; 37 } 38 for(int i=idx-1;i>=1;i--){ 39 a[i]=min(a[i],a[i+1]); 40 } 41 for(int i=idx+1;i<=n;i++){ 42 a[i]=min(a[i],a[i-1]); 43 } 44 for(int i=1;i<=n;i++){ 45 cout<<a[i]<<" "; 46 } 47 cout<<" "; 48 }