A题：Aaronson
静下心来观察就会发现
1.如果m大于等于n的位数，那么n直接写成二进制形式就是最优解形式
2.如果m小于n的位数，那么贪心地使得高位尽可能地多消掉n的值，因为高位少写一个数
就意味着低位要写更多位来弥补抵消
3.在第二种情况下，枚举2^m也不会超int，因为（n<le9）最多有30位,且m小于n的位数
,m就不会很大
#include <bits/stdc++.h>
using namespace std;
const int Max=1e5+;
inline int cacu(int x)
{
int ans=;
while(x)
{
ans++;
x/=;
}
return ans;
}
int main()
{
int T;
for(scanf("%d",&T);T;T--)
{
int n,m;
scanf("%d%d",&n,&m);
m+=;
int c=cacu(n);
int sum;
if(m>=c)
{
sum=;
while(n)
{
if(n&) sum+=;
n>>=;
}
}
else
{
sum=;
int re;
while(n)
{
re=n/(<<(m-));
sum+=re;
n=n-re*(<<(m-));
m--;
}
}
cout<<sum<<endl;
}
return ;
}
B题：Bellovin
给出一个序列，求与这个序列LIS相同的最小字母序序列
观察可知，答案即为求每位LIS
以dp[x]代表长度为x的LIS,且dp[x]==LIS长度为x的末尾值
每次都往前取dp[x]中最小的一个,当然在保证x尽可能地大的情况下
因为dp[x]是递增的，所以可以二分,l=1,r=当前最长的LIS
求得当前以小于当前a[i]的最长LIS
#include <bits/stdc++.h>
using namespace std;
const int Max=1e5+;
int A[Max];
int dp[Max];
int LIS[Max];
void Get_lis(int n)
{
int i,j,l,r,mid,ans;
dp[]=A[];
int len=;
for(i=;i<=n;i++)
{
if(dp[len]<A[i]) j=++len;
else
{
l=;r=len;
ans=;
while(l<=r)
{
mid=(l+r)>>;
if(A[i]>dp[mid]&&A[i]<=dp[mid+])
{
ans=mid;break;
}
else if(A[i]>dp[mid]) l=mid+;
else r=mid-;
}
j=ans+;
}
dp[j]=A[i];
LIS[i]=j;
}
}
int main()
{
int T;
for(scanf("%d",&T);T;T--)
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&A[i]);
dp[i]=;
}
LIS[]=;
Get_lis(n);
for(int i=;i<=n;i++)
{
if(i!=) printf(" ");
printf("%d",LIS[i]);
}
puts("");
}
return ;
}
C题：Colmerauer
已知一个鞍点可覆盖范围是一个矩形,以这个鞍点作为原点
可以利用单调栈求出它的(u,l,d,r)
在枚举子矩阵的时候，会有多少次覆盖到这个鞍点的区域？
不如思考一下这个鞍点的区域可以分成多少个子矩阵
分类：
将鞍点看做原点0，那么原本的左右区间可以写成(-l,r);
鞍点在x轴上可以分为三部分:(-l,0,r)
那么左边的长度有l种,右边也有r种
分类法加分步法分析：
第一种：先选左边：那么左边l种区间的长度和为(l)(l+1)/2,因为此时右边可以任选,
，有r+1(包括原点)种方式，再乘以r+1
第二种：先选右边: 那么右边(r+1)(包括鞍点自身)种区间的长度和为(r+1)(r+2)/2,因为
此时左边可以任选，有l+1种方式，再乘以l+1
鞍点在y轴上的区分求法同上
注意此题求出的l,r,u,d比实际值高了一位
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD=(LL)(<<)*(LL)(<<);
const int Max=1e3+;
const int inf=0x3f3f3f3f;
int matrix[Max][Max],l[Max][Max],r[Max][Max],
u[Max][Max],d[Max][Max];
stack<int>st;
LL Cacu(int x,int y)
{
LL ans=(x*(x+)/*(y+)%MOD+(y+)*(y+)/*(x+)%MOD)%MOD;
return ans;
}
int main()
{
int T;
for(scanf("%d",&T); T; T--)
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=; i<=n; i++) for(int j=; j<=m; j++)
scanf("%d",&matrix[i][j]); //行中最小
for(int i=; i<=n; i++)
{
matrix[i][m+]=matrix[i][]=-inf;
while(!st.empty()) st.pop();
st.push();
for(int j=; j<=m; j++)
{
while(!st.empty()&&matrix[i][st.top()]>matrix[i][j]) st.pop();
l[i][j]=st.top();
st.push(j);
}
while(!st.empty()) st.pop();
st.push(m+); for(int j=m; j>=; j--)
{
while(!st.empty()&&matrix[i][st.top()]>matrix[i][j]) st.pop();
r[i][j]=st.top();
st.push(j);
}
} //列中最大
for(int j=; j<=m; j++)
{
matrix[][j]=matrix[n+][j]=inf;
//这里是为了保证u[1]=0和d[n]=n+1,因此要设到最大
while(!st.empty()) st.pop();
st.push();
for(int i=; i<=n; i++)
{
while(!st.empty()&&matrix[st.top()][j]<matrix[i][j]) st.pop();
u[i][j]=st.top();
st.push(i);
}
while(!st.empty()) st.pop();
st.push(n+);
for(int i=n; i>=; i--)
{
while(!st.empty()&&matrix[st.top()][j]<matrix[i][j]) st.pop();
d[i][j]=st.top();
st.push(i);
}
}
LL ans=;
int uy,dy,lx,rx;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
uy=i-u[i][j]-;lx=j-l[i][j]-;
dy=d[i][j]-i-;rx=r[i][j]-j-;
ans=(ans+(Cacu(uy,dy)*Cacu(lx,rx)%MOD*matrix[i][j]))%MOD;
}
}
printf("%I64d\n",ans);
}
return ;
}
D题：Dertouzos
求1到n-1中最大因数是d的数的个数
设m是1到n-1的任意一个数
设m=d*r,若d是m的最大因数,r必须满足:
1.r必然是m的最小因数,
2.r必然是素数,不然总可以拆成另外的几个数,导致存在比d大的因数
3.r必然小于等于d
可以看到,m最大是n-1,r最大是n-1/d
那么可以从最小素数2开始进行检查，看其是否能成为r
1到1e9的素数筛出来,过于艰难
通过观察可以发现：
当d很小时,由于r小于等于d,循环d次即可
当d很大时,由于r小于等于n-1/d,循环次数也不会很多
可以将d<=1e4时当作很小进行分析：
d<=1e4,r不会超过1e4
d>1e4,n最高等于1e9,n-1/d<=1e5,r不会超过1e5
因此我们只要筛出1到1e5的素数就好了
#include <bits/stdc++.h>
using namespace std;
const int Max=1e7+;
int prime[Max],is_prime[Max],top;
void Erato()
{
int m,n;
n=1e5+;
for(int i=; i<=n; i++) if(!is_prime[i])
{
prime[top++]=i;
for(int j=i*; j<=n; j+=i) is_prime[j]=;
}
}
int check(int n,int d)
{
int ans=;
for(int i=; i<top; i++)
{
if(d*prime[i]>=n) return ans;
if(d%prime[i]==) return ans+; //包括自身
ans++;
}
return ans;
}
int main()
{
Erato();
int T;
for(scanf("%d",&T); T; T--)
{
int n,d;
scanf("%d%d",&n,&d);
int ans=check(n,d);
printf("%d\n",ans);
}
return ;
}
E题：Eades
待续。。。。。。