数学（八） (2-2)

void solve() {

int n, x;cin＞＞n＞＞x;

int ans = 0;

for (int a = 1; a ＜= n; a++) {

for (int b = 1; a * b ＜= n && a + b ＜= x; b++) {

ans += min((n - a * b) / (a + b), x - a - b);

}

}

cout＜＜ans＜＜"\n";

}

E - Decode

找所有包含小区间[x,y]内字符0的个数等于1的个数的大区间[L,R]的个数

对字符串求前缀和，字符0贡献为-1，字符1贡献为1，满足条件的区间就是这段区间和为0的个数，即pre[y]=pre[x-1]，对每一对[x,y]，显然贡献数量一共是所有左端点数量([1,x]共计x个)*所有右端点个数([y,n]共计n-y+1个)

我们枚举左端点x，找到满足条件的所有右端点并计算答案，map记录所有的pre[i]的可供选择的右端点数量总和

void solve() {

string s;cin＞＞s;

int n=s.length(),ans=0;

s=" "+s;

vector＜int＞pre(n+100);

map＜int,int＞mp;

for(int i=1;i＜=n;i++){

pre[i]=pre[i-1]+(s[i]=='0'?-1:1);

}

for (int i = n; i ＞=1; i--) {

ans = (ans + i * mp[pre[i-1]]) % mod;

mp[pre[i]] += n - i + 1;

}

cout＜＜ans＜＜endl;

}

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。