A. 小A的文化节
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N=1e5+10,mod=1e9+7;
int n,m,a[N];
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
int res=0;
for(int i=1;i<=m;i++)
{
int x;
cin>>x;
res+=a[x];
}
cout<<res;
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
int T=1;
// cin>>T;
while(T--)
{
solve();
}
return 0;
}
B. 小A的游戏
有胜有负才能拉开差距，每次差距为3，判断差值是否为3的倍数即可
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N=1e5+10,mod=1e9+7;
int x,y;
void solve()
{
cin>>x>>y;
if(abs(x-y)%3) cout<<"No\n";
else cout<<"Yes\n";
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
int T=1;
cin>>T;
while(T--)
{
solve();
}
return 0;
}
C. 小A的数字
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N=1e5+10,mod=1e9+7;
string s;
void solve()
{
cin>>s;
int n=s.size(),i,j;
for(i=0;i<n;i++)//找到第一个为0的位置，i
if(s[i]=='0')
break;
if(i==n)//直到末尾都没有出现0
{
if(s[n-1]=='1') cout<<2<<endl;//特判
else cout<<1<<endl;
return;
}
for(j=i;j<n;j++)//从第一个0开始，是0输出1，否则输出0
{
if(s[j]=='0') cout<<1;
else cout<<0;
}
cout<<endl;
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
int T=1;
cin>>T;
while(T--)
{
solve();
}
return 0;
}
D. 小A的线段（easy version）
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N=1e5+10,mod=998244353;
int n,m,a[N],st[N],ed[N],d[N],ans;
void dfs(int u,int f)//u：选第几个，f：0表示不选，1表示选
{
if(u==m)
{
for(int i=1;i<=n;i++)
{
d[i]=d[i-1]+a[i];//用另一个数组对差分数组前缀和
if(d[i]<2) return;//小于2，return
}
ans=(ans+1)%mod;// ++
return;
}
dfs(u+1,0);
a[st[u+1]]++,a[ed[u+1]+1]--;//差分
dfs(u+1,1);
a[st[u+1]]--,a[ed[u+1]+1]++;//回溯
}
void solve()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>st[i]>>ed[i];
}
dfs(0,0),dfs(0,1);
cout<<ans/2;//去重
//也可以直接二进制形式枚举2^m次方次，对每种情况分别判断
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
int T=1;
// cin>>T;
while(T--)
{
solve();
}
return 0;
}
E. 小A的任务
有k~n种选择，当i>=k时，每次花费为a类前i个+b类前i个中选k个
可以发现，一定是前i个中最小的k个
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N=1e5+10,mod=1e9+7;
int n,a[N],b[N],q,k;
void solve()
{
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
for(int i=1;i<=n;i++) a[i]+=a[i-1];//前缀和
while(q--)
{
cin>>k;
int res=0,mx=1e18;
priority_queue<int>q;//大根堆，里面元素从大到小排序
for(int i=1;i<=k;i++) q.push(b[i]),res+=b[i];//加入k个元素，k个元素和为res
for(int i=k;i<=n;i++)
{
mx=min(mx,res+a[i]);//计算min
res-=q.top();//将队列中固定k个元素，每次减去最大的
q.pop();//弹出最大的
q.push(b[i+1]);//加入下一个元素
res+=b[i+1];//更新k个元素之和
}
cout<<mx<<endl;//输出
}
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
int T=1;
// cin>>T;
while(T--)
{
solve();
}
return 0;
}
F. 小A的线段（hard version）
f [ l, r ]：
0~l，覆盖两次以上
l~r，覆盖一次
r~n，0次
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N=1e5+10,mod=998244353;
int n,m,a[N],st,ed;
void solve()
{
vector<pair<int,int>>v;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>st>>ed;
v.push_back({st,ed});
}
sort(v.begin(),v.end());//区间根据左端点排序
map<pair<int,int>,int>f;
f[{0,0}]=1;//定义0处覆盖两次以上
for(int i=0;i<m;i++)
{
auto [L,R]=v[i];//依次选取区间[L,R]
auto g=f;
for(auto [it,v]:f)//对于每个区间[l,r]，判断区间[L,R]
{
auto [l,r]=it;
if(L<=l+1)//L<=l和L==l+1两种情况的合并
{
if(R<=l)//[L,R]在(l,r]左边,增加左边覆盖次数，对右边(l,r]覆盖一次无影响
g[{l,r}]=(g[{l,r}]+v)%mod;
else if(R<=r)//L在(l,r]左边,R在(l,r]中,则l~R多覆盖一次->2,(R,r]一次
g[{R,r}]=(g[{R,r}]+v)%mod;
else//L在(l,r]左边,R在(l,r]右边,则(l,r]多覆盖一次至2,(r,R]为1,更新区间
g[{r,R}]=(g[{r,R}]+v)%mod;
}
}
f.swap(g);//交换map，f和g
}
cout<<f[{n,n}]<<endl;//[1,n]覆盖两次
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
int T=1;
// cin>>T;
while(T--)
{
solve();
}
return 0;
}