Rect
算法分析：
方法一： 玄学做法（毫无正确性）（摘自hyj）
期望得分: 40
时间复杂度：n
1）读入；
2）转成数字，全部相乘后，除以a，除以2，输出;
Source:
#include#include#include#includeusing namespace std;
int main() {
//、freopen("rect.in","r",stdin);
// freopen("rect.out","w",stdout);
int a;
string s;
ios::sync_with_stdio(0);
cin.tie(0);
cin>>a;
cin>>s;
int num[4001],n=s.length();
for(register int i=1; i<=n; ++i)
num[i]=s[i-1]-'0';
int ans=1;
for(register int i=1; i<=n; ++i) {
ans*=num[i];
}
ans=(ans/a)/2;
cout<
方法二：正常做法(其实更加玄学) 期望得分：100
时间复杂度：n2 log2 n2 (n=4000讲道理我也不知道我怎么过的)
1）读入字符串，分离各位置，并求取前缀和；
2）求得每一个区间和
3）排序并且离散化，记录数字和次数
4）从第一位开始，每一位二分查找a/i，两者相乘，到sqrt(a);
注意：做除法的时候，一定要特判0，a为0进行分类讨论
Source：
#include#include#include#include#include#include using namespace std; int a,len,cnt,ans,scnt,top,temp; string s; int w[4010]; /*w:权值*/ int sum[4010]; /*sum:前缀和*/ int cut[16000010]; /*cut:区间和*/ int ct[16000010]; /*ct:该值的个数*/ int find(int l,int r,int num) /*二分查找a/cut[i]*/ { while(l<=r) { int mid=(l+r)>>1; if(cut[mid]>num) { r=mid-1; } if(cut[mid] sq) /*超出sqrt(a),不重复*/ break; int ret; ret=ct[i]*find(i,top,a/cut[i]); if(a/cut[i]==cut[i]) { temp=ct[i]; ans+=(ct[i]*(ct[i]-1)/2); continue ; } ans+=ret; } ans=(ans<<1); ans+=temp; cout< >a>>s; work(s); return 0; }
方法三：最正解方法 期望得分：100
时间复杂度：n2
1）读入字符串，分离各位置，并求取前缀和；
2）给每一个区间和进行计数（桶排思想）
3）从第一位开始，每一位乘以cnt[a/i];
注意：因为size<=4000 所以区间和不超过36000，可以进行桶排思想，然后注意求cnt[a/i]时，保证a/i<sum[len];
Source:
#include#include#include#include#include#include using namespace std; int a,len,ans,top; string s; int w[4010]; /*w:权值*/ int sum[4010]; /*sum:前缀和*/ int cnt[37000]; /*cnt:差的计数*/ void work(string s) { len=s.size(); for(int i=0;i top) /*大于最大值，过*/ continue; int ret=0; ret=cnt[i]*cnt[a/i]; ans+=ret; } cout< >a>>s; work(s); return 0; }
Summary:
本题是我唯一想到正解的题目·······但是写炸了，其实这道题是最简单的一道题，直接用数学方法进行证明，可以很轻松得到表达式，在随便捣鼓一下就可以了，表示之前完全没有找对方向······