数学（八）
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<char＞＞s(n+100,vector＜char＞(n+100));
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;
}
