组队赛，做出来了两道，很水啊。。。下来看了一下解题报告，记录一下：
http://acm.hdu.edu.cn/vcontest/vtl/problemlist/showproblemlist/vtlid/4905
Partition
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1170 Accepted Submission(s): 294
Total Submission(s): 1170 Accepted Submission(s): 294
Problem Description
Define f(n) as the number of ways to perform n in format of the sum of some positive integers. For instance, when n=4, we have
4=1+1+1+1
4=1+1+2
4=1+2+1
4=2+1+1
4=1+3
4=2+2
4=3+1
4=4
totally 8 ways. Actually, we will have f(n)=2(n-1) after observations.
Given a pair of integers n and k, your task is to figure out how many times that the integer k occurs in such 2(n-1) ways. In the example above, number 1 occurs for 12 times, while number 4 only occurs once.
4=1+1+1+1
4=1+1+2
4=1+2+1
4=2+1+1
4=1+3
4=2+2
4=3+1
4=4
totally 8 ways. Actually, we will have f(n)=2(n-1) after observations.
Given a pair of integers n and k, your task is to figure out how many times that the integer k occurs in such 2(n-1) ways. In the example above, number 1 occurs for 12 times, while number 4 only occurs once.
Input
The first line contains a single integer T(1≤T≤10000), indicating the number of test cases.
Each test case contains two integers n and k(1≤n,k≤109).
Each test case contains two integers n and k(1≤n,k≤109).
Output
Output the required answer modulo 109+7 for each test case, one per line.
SampleInput
2 4 2 5 5
SampleOutput
5 1
//题意其实就是的出一个公式f（a-b）=2^(a-b)+(a-b-1)*2^(a-b-2);要用次方幂求模算法
#include <stdio.h>
const long long Max =1000000007;
long long fun(long long x,long long y)
{
long long res=1;
while(y>0)
{
if(y%2==1)
{
res=(res*x)%Max;
}
x=(x*x)%Max;
y/=2;
}
return res%Max;
}
int main()
{
//printf("%d\n",fun(2,4));
__int64 T,a,b;
scanf("%I64d",&T);
while(T--)
{
scanf("%I64d%I64d",&a,&b);
__int64 x,y;
if(a<b)
{
printf("0\n");continue;
}
if(a==b)
{printf("1\n");continue;}
x=fun(2,a-b)%Max;
y=(x%Max+((a-b-1)*fun(2,(a-b-2)))%Max)%Max;
printf("%I64d\n",y);
}
}
Deque
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 616 Accepted Submission(s): 126
Total Submission(s): 616 Accepted Submission(s): 126
Problem Description
Today, the teacher gave Alice extra homework for the girl weren't attentive in his class. It's hard, and Alice is going to turn to you for help.
The teacher gave Alice a sequence of number(named A) and a deque. The sequence exactly contains N integers. A deque is such a queue, that one is able to push or pop the element at its front end or rear end. Alice was asked to take out the elements from the
sequence in order(from A_1 to A_N), and decide to push it to the front or rear of the deque, or drop it directly. At any moment, Alice is allowed to pop the elements on the both ends of the deque. The only limit is, that the elements in the deque should be
non-decreasing.
Alice's task is to find a way to push as many elements as possible into the deque. You, the greatest programmer, are required to reclaim the little girl from despair.
The teacher gave Alice a sequence of number(named A) and a deque. The sequence exactly contains N integers. A deque is such a queue, that one is able to push or pop the element at its front end or rear end. Alice was asked to take out the elements from the
sequence in order(from A_1 to A_N), and decide to push it to the front or rear of the deque, or drop it directly. At any moment, Alice is allowed to pop the elements on the both ends of the deque. The only limit is, that the elements in the deque should be
non-decreasing.
Alice's task is to find a way to push as many elements as possible into the deque. You, the greatest programmer, are required to reclaim the little girl from despair.
Input
The first line is an integer T(1≤T≤10) indicating the number of test cases.
For each case, the first line is the length of sequence N(1≤N≤100000).
The following line contains N integers A1,A2,…,AN.
For each case, the first line is the length of sequence N(1≤N≤100000).
The following line contains N integers A1,A2,…,AN.
Output
For each test case, output one integer indicating the maximum length of the deque.
SampleInput
3 7 1 2 3 4 5 6 7 5 4 3 2 1 5 5 5 4 1 2 3
SampleOutput
7 5 3
//这是大牛写的，从一组数中运用替换找到每个点的递增长度，递减长度和其中重复的数，然后求出最大的即可。
#include<cstdio>
#include<algorithm>
#define MAXN 100010
#define oo 123456789
using namespace std;
int arr[MAXN]; ///输入的数组
int up[MAXN], down[MAXN], cnt[MAXN]; //其中递增序列 递减序列 及重复出现的值
int st[MAXN], top;
void LIS(int n, int dp[]) {
int i;
int pos;
top = -1;
for (i = 0; i < n; i++) {
if (top < 0 || st[top] <= arr[i]) {
st[++top] = arr[i];
dp[i] = top + 1;
}
else {
pos = upper_bound(st, st + top + 1, arr[i]) - st; ///返回一个有序数组下标，相同值插后面
st[pos] = arr[i];
dp[i] = pos + 1;
}
cnt[i] = min(cnt[i],
upper_bound(st, st + top + 1, arr[i])
- lower_bound(st, st + top + 1, arr[i])); ///返回一个有序数组下标，相同值插前面
}
}
int main() {
int T;
int n;
int i;
int ans;
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
cnt[i] = oo;
}
reverse(arr, arr + n);
LIS(n, up);
for (i = 0; i < n; i++) {
arr[i] = -arr[i];
}
LIS(n, down);
ans = 0;
for (i = 0; i < n; i++) {
ans = max(ans, up[i] + down[i] - cnt[i]);
}
/*for(int i=0;i<n;i++)
{
printf("%d ",up[i]);
}
printf("\n");
for(int i=0;i<n;i++)
{
printf("%d ",down[i]);
}
printf("\n");
for(int i=0;i<n;i++)
{
printf("%d ",cnt[i]);
}
printf("\n");*/
printf("%d\n", ans);
}
return 0;
}