Codeforces Round 962 (Div. 3)
A.legs
题解: 简单的贪心，可以对n预处理，将n除以2，此时可将动物视为1，则动物便是1条或两条腿，此时若是奇数才需要鸡，否则全部是牛便是最优解
Show Code
#include< bits/stdc++.h >
#define ANS cout << ans << '\n'
using namespace std;
void solve()
{
int n,ans=0;
cin>>n;
n/=2;
if(n&1) ans++,n--;
n>>=1;
ans+=n;
ANS;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
cin >> T;
while(T--) solve();
return 0;
}
B.Scale
题解：简单的模拟
Show Code
#include < bits/stdc++.h >
#define FOR(i,j,n,k) for(int i = (j);i <= (n);i +=k )
using namespace std;
solve()
{
int n,k;
cin>>n>>k;
vector< string> s(n+5);
FOR(i,1,n,1) cin>>s[i];
FOR(i,1,n,k) {
FOR(j,0,n-1,k) cout<< s[i][j];
cout<< endl;
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
cin >> T;
while(T--) solve();
return 0;
}
C.Sort
题解：简单的前缀数据结构维护处理，遍历字符串，使用int cnt[N][26]记录前缀不同字符种类数量，由题意我们不考虑该[l,r]区间字母的顺序，只需要满足同类字符数量相同即可，因此对于每次询问，使用 cnt[r][j]-cnt[l-1][j]得出该种字符在这个区间的数量并让答案加上两个串在该字符的数量差，最后将答案除2输出(原始答案是重了一倍的情况)
Show Code
#include < bits/stdc++.h>
#define FOR(i,j,n,k) for(int i = (j);i <= (n);i +=k )
#define ANS cout << ans << '\n'
using namespace std;
const int N = 2e5 + 10;
int n,q;
string a,b;
int cnta[N][26],cntb[N][26];
void init()
{
a=" "+a,b=" "+b;
FOR(i,1,n,1){
FOR(j,0,25,1){
cnta[i][j]=cnta[i-1][j];
cntb[i][j]=cntb[i-1][j];
cnta[i][j]+=(a[i]-'a')==j?1:0;
cntb[i][j]+=(b[i]-'a')==j?1:0;
}
}
}
void solve()
{
cin>>n>>q;
cin>>a>>b;
init();
FOR(i,1,q,1){
int l,r,ans=0;
cin>>l>>r;
FOR(j,0,25,1){
int aa=cnta[r][j]-cnta[l-1][j];
int bb=cntb[r][j]-cntb[l-1][j];
ans+=abs(aa-bb);
}
ans/=2;
ANS;
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
cin >> T;
while(T --)
{
solve();
}
return 0;
}
D.Fun
题解：暴力枚举，枚举a,b,时间复杂度O(nlog(n))
\[当a=1时，b<= \frac{n}{1} , 当a=2时，b<= \frac{n}{2} ,当a=i时，b<=\frac{n}{i} \]显然此时出现调和数列，而调和数列的数列和约为 ln(n+1)+r 证明链接
Show Code
#include< bits/stdc++.h >
#define ANS cout << ans << '\n'
typedef long long ll;
using namespace std;
int n,k;
void solve()
{
cin>>n>>k;
ll ans=0;
for(int a=1;a<=n;a++){
for(int b=1;a*b<=n&&(a+b)< ;b++){
ans=ans+min((n-a*b)/(a+b),k-a-b);
}
}
ANS;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
cin >> T;
while(T--) solve();
return 0;
}
E.Decode
题解：大概题意：字符串中每个[l,r]区间中0，1数量相等的子串的数量和的总和字串的子串,正向思维，现找出每个子区间，再从子区间中找满足的子串，难以进行，不妨逆向来，从满足的子串出发，若子串满足，其l，r可知该串对答案的贡献值，即(l+1)*(n-r+1)，即包含该串的子区间数量，于是我们正向向右推进，以i为子串的右端点，用map记录左侧已扫过的点的贡献值，前缀和的方式记录，遇到1,temp++,否则temp--,每次走到这个右端点就找左侧与之相等的点， 易错细节即初始时mp[0]=1
Show Code
#include
using namespace std;
const int N=2e5+5;
typedef long long ll;
const int mod=1e9+7;
string s;
void solve()
{
cin>>s;
int n=s.size();
s=" "+s;
ll temp=0;
map< ll,ll> mp;
mp[0]=1;
ll ans=0;
for(int i=1;i<=s.size();i++){
if(s[i]=='1') temp++;
else temp--;
ans=ans+mp[temp]*(n-i+1)%mod;
mp[temp]+=i+1;
}
ans%=mod;
cout<< ans<< endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin>>T;
while(T--) solve();
return 0;
}