数学（八）

void solve() {

int n;cin＞＞n;

int k=n/4;

n-=k*4;

cout＜＜k+n/2＜＜endl;

}

B - Scale

void solve() {

int n,k;cin＞＞n＞＞k;

vector＜vector

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

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

cin＞＞s[i][j];

}

}

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

for(int j=1;j＜=n;j+=k){

cout＜＜s[i][j];

}

cout＜＜endl;

}

}

C - Sort

思路转化一下，求区间[l,r]内的不同字母个数其实就是分别求从a到z字母在区间[l,r]内的不同出现次数

dp,dp1[i][j]表示在区间1-i内，第一个字符串中，字母j的出现次数，两个dp分别对所有字符求差就可得出有多少个不同位置的二倍，因为每个不同位置都会被算两次‬

void solve() {

int n,q;cin＞＞n＞＞q;

string a,b;cin＞＞a＞＞b;

a=" "+a;b=" "+b;

vector dp1(n+1,vector＜int＞(27));

vector dp2(n+1,vector＜int＞(27));

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

dp1[i]=dp1[i-1];dp2[i]=dp2[i-1];

dp1[i][a[i]-'a']++;dp2[i][b[i]-'a']++;

}

while(q--){

int l,r;cin＞＞l＞＞r;

int ans1=0,ans2=0,ans=0;

for(int i=0;i＜26;i++){

ans+=abs((dp1[r][i]-dp1[l-1][i])-(dp2[r][i]-dp2[l-1][i]));

}

cout＜＜ans/2＜＜endl;

}

}

D - Fun

枚举a。由于ab+ac+bc≤n，所以至少ab≤n。两边同时除以a得到b≤n/a。当a=1时，b有n种选择；当a=2时，b有n²种选择。因此，总共b有n+n²+n³+...+n^n种选择。这是调和级数，所以在所有可能的a中，b大约有nlogn种选择。所以可以枚举a与b

计算c的合法最大数，从1到c的所有数字都是合法的方案

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://www.bjxsw.cc），接着再看更方便。