P1 三国杀
考点：if判断
题解：因为不知道小B的手牌是什么，但要确定小A必胜，考虑小B的m张手牌都是桃即可，所以就是问n张杀可以把一个生命值为m+k的人击败。
代码如下：
void solve(){
int n,m,k;
scanf("%d %d %d",&n,&m,&k);
if(n>=m+k){
puts("YES");
}else{
puts("NO");
}
}
P2 打地鼠
考点：循环计数
解题：分析题意，就是循环时遇到5就不处理，除了5的数字，5计数加一，其他数字计数加一。
代码如下：
void solve(){
int n,x;
int cnt[20]={0};
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&x);
if(x==5) continue; //若是5，原地击球，不会移动
cnt[x]++; //经过x的位置，路过x的次数加一
cnt[5]++; //回到5的位置，经过加一
}
for(int i=1;i<=9;i++){
printf("%d ",cnt[i]);
}
}
P3 进入校园
考点：分类讨论，ifelse。
做法：分析题目，有个重要细节就是，m<=n;
所以分三类;
第一类是：n等于m，那么所有人都可以一次进入学校，输出1；
第二类是：n不等于m，但m等于1，由于至少需要一个人把卡，带出来，这是一个无解的情况，输出-1；
第三类就是剩余情况：n个人，m张卡，假设最后一次，一定是m个人一起进入校园（这里是一次），那么现在就是n-m个人，每次进入m-1个人，问需要多少次，每次乘以2(因为来回），所以就是（n-m）除（m-1）上取整，
这里提一下，计算机语言中，整型只有整除，所以对于a除b上取整就是(a+b-1)/b。那么到这里，问题就解决了。
代码如下：
void solve(){
int n,m;
scanf("%d %d",&n,&m);
if(n==m){ //n个人有m张卡，直接
printf("1n");
}else if(m==1){
printf("-1n");
}else{
n-=m; //假设最后一次进去m个人；
m--; //然后考虑每次进入m-1个人，提前减1，方便后面书写
int cnt=1;
//cnt+=(n/m)*2; 另一中写法
//if(n%m!=0) cnt+=2;
cnt+=(n+m-1)/m*2; //n个人，每次进入m个，然后保证上取整
printf("%dn",cnt);
}
}
int main(){
int T;
scanf("%d",&T);
while(T--)solve();
return 0;
}
P4 BUFF
考点:差分，前缀和，枚举
题解：如果是在暴力的情况，直接枚举每个区间，然后进行涂色，最后暴力枚举，计算符合要求的数量即可，但是由于次数过多，导致会超时，所以要用到算法（差分）。然后这里有一个技巧，就是一步处理这种区间加的方法，就是差分,分享一个介绍差分与前缀和的博客链接添加链接描述。
代码如下：
void solve(){
int n,m;
scanf("%d %d",&n,&m);
int w[200010][2]={0}; //这里数组必须得开200000，不然m+ai，若数组开小了，可能会越界
for(int i=1;i<=n;i++){
int op,x;
scanf("%d %d",&op,&x);
if(op==1){
w[x][0]++,w[x+m][0]--;
}else{
w[x][1]++,w[x+m][1]--;
}
}
int t0=0,t1=0,res=0;
for(int i=1;i
P5 过五关斩六将
考点：爆搜，二进制枚举，贪心
题解：首先，不妨假设没有这个升级的限制，那么要如何重新组合一个数组，使前面元素累积的和能更多的大于目标数组呢，比较感性的去分析，就是吧这个数组按降序排序，那么为什么呢 假设一个降序数组为 5 4 3 2 1，他能达到的分数数组(前缀和数组)就是5 9 12 14 15，如果任意交换两个数字，变成5 2 3 4 1 ， 他能达到的分数数组(前缀和数组)就是5 7 10 14 15，通过这样的操作会发现一个结论：如果交换两个降序的数字，他们之前的和之后的显然是不会变换5 x x 14 15 但是中间的数会变小。
其次：由于n很小，只有15，所以可以考虑爆搜枚举所有状态，2的15次共计32768中情况，然后每次贪心的复杂度是nlogn大概100左右，所以复杂度大概在3e6，完全可以通过此题（关于复杂度添加链接描述）。何为2进制枚举，考虑有3个数字，2次升级机会，如何解释呢，3位的二进制数有000 001 010 011 100 101 110 111（有三位，第一个就是第一个数升级不升级，第二位就是第二个数升级不升级，第三位同理，1就是升级，0就是），共八个数字，我们考虑1代表升级，0代表不升级，那么，我们只需要对000 001 010 011 100 101 110 这些状态进行枚举，然后吧相应的值弄出来，用排序的方法，或者优先队列操作一下即可。
#include
using namespace std;
typedef long long LL;
const int N=50,mod=1e9+7;
int n,m,k;
int w[N][2],target[N];
void solve(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&target[i]); //读入每一轮之后的目标分数
for(int i=0;i>j&1) cnt++;
if(cnt<=m){ //若选择难度提升的小于m个，就判断一次
priority_queue q; //优先队列，可以让之后取出每个最大值
//这一步也可以选择吧所有数字从大到小降序排序
for(int j=0;j>j&1) q.push(w[j][1]);//这一位为1，则选择困难模式，反之选择简单模式
else q.push(w[j][0]);
}
int sum=0,sumcnt=0; //sum记录前面局数的和，sumcnt代表
for(int i=1;i<=n;i++){
sum+=q.top();q.pop();
if(sum>=target[i]) sumcnt++;
}
res=max(res,sumcnt);
}
}
printf("%dn",res);
}
int main(){
solve();
return 0;
}
P6 组队
考点：并查集，离线操作；
做法：考虑到同时出里友好关系和矛盾关系，其实并不好处理，所以用并查集先把所有友好关系，把他们分到不同的集合内，存下所有矛盾关系，在后面处理，再判断所有矛盾关系：两个人是否在一个集合内，若在一个集合内，则无法组队，若所有矛盾关系的两个人都不在一个集合内，则可以组队。
#include
using namespace std;
const int N=200010,mod=1e9+7;
struct node{
int x,y;
}e[N];
int fa[N]; //每个节点的父亲节点
int find(int x){ //并查集查找父亲节点的函数
if(x!=fa[x]) fa[x]=find(fa[x]); //路径压缩过程
return fa[x];
}
int main(){
int n,a,b,c,k=0; //k记录有矛盾的边
scanf("%d",&n);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1,a,b,c;i<=n;i++){
scanf("%d %d %d",&a,&b,&c);
if(c==1){
a=find(a),b=find(b); //查找格子的父亲节点
if(a!=b) fa[a]=b; //若父亲节点不相同，就合并成一个集合
}else e[k++]={a,b}; //矛盾关系存起来
}
bool f=true;
for(int i=0;i
P7 BOSS
考点：二分+前缀和
题解：首先发现，ai的值是没有意义的，有意义的只有两两之间的差值，然后对BOSS造成的伤害，就是每个差值减去蓄力时间（若小于0就无法造成伤害，忽略即可），然后对差值进行排序，可以发现只有大于k的值才会对答案造成贡献，就是找到第一个大于等于k的值，然后后面每个值减k，然后计算伤害，由于暴力枚举会超时，所以考虑 二分找到第一个大于k的位置，然后用前缀和来计算大于k那一段的和，再减去大于k的值得数量乘上k，即可算出目标伤害d
。时间复杂度是nlogn。
也有离线（就是把所有询问一次读入，一起计算，一起输出）的算法，就是把所有的差值按照降序排序，所有询问，按照蓄力时间降序排序，然后在查询每个询问时，若蓄力时间为k，边把所有差值大于等于k的依次累加，sum为放入的差值和，cnt为数目，那么计算每个询问的结果就是sum-k*cnt，即对boss造成的伤害，这样就能解决没个询问了，由于两个都是降序，两个数组都只会遍历一边，时间复杂度是on的，但sort的时间复杂度是nlogn，所以时间复杂度依然是nlogn。
#include
using namespace std;
typedef long long LL;
const int N=200010,mod=1e9+7;
int n,m,k;
int a[N];
LL b[N],s[N];
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;iy) r=mid;
else l=mid+1;
}
if(b[l]=x) puts("YES");
else puts("NO");
}
return 0;
}
P8 解密
考点：01背包计数，猜结论
题解：经过模拟和猜测，发现数组根满足结合律，即把每个数先加起来再做数字根，和先加起来，再做数字根的效果是相同的，所以读入每个数先做数字根，然后用经典01背包记录方案数的转移即可。
f[i][j] 代表前i个数，能组成数字根为j的方案数的数量。
转移过程就是当前数是i-1,数字根为j，加上的数的数字根为x，那么f[i-1][j]是能转移到f[i][(j+x)数字根的结果]，所以枚举0~9，进行转移计数即可。
#include
using namespace std;
typedef long long LL;
const int N=200010,mod=998244353;
int n,m;
int f[N][15];
int change(int x){
if(x<10) return x;
int res=0;
while(x){
res+= x%10;
x/=10;
}
return change(res);
}
int main(){
scanf("%d",&n);
f[0][0]=1;
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
x=change(x);
for(int j=0;j<=9;j++) f[i][j]=f[i-1][j];
for(int j=0;j<=9;j++){
int y=change(j+x);
f[i][y]=(f[i][y]+f[i-1][j])%mod;
}
}
for(int i=1;i<=9;i++) printf("%d ",f[n][i]);
return 0;
}
P9 是男人就下一百层
考点：离散化，树状数组，推公式
难度：压轴
题解：直接放原题题解题解，不过这题行列转换了一下，如果有人会前置知识，且想学的，私信我即可。
#include
using namespace std;
typedef long long LL;
const int N=500010,mod=1e9+7;
int n,m;
LL tr[N];
LL s1[N],s2[N],s3[N];
vector alls;
inline int lowbit(int x) {
return x&(-x);
}
void add(int x){
for(int i=x;i<=n;i+=lowbit(i)) tr[i]++;
}
int sum(int x){
int ans=0;
for(int i=x;i>0;i-=lowbit(i)) ans+=tr[i];
return ans;
}
int find(LL x){
return lower_bound(alls.begin(),alls.end(),x)-alls.begin()+1;
}
int main(){
scanf("%d",&m);
for(int i=1;i<=m;i++) scanf("%lld %lld %lld",&s1[i],&s2[i],&s3[i]);
for(int i=1;i<=m;i++) s1[i]+=s1[i-1];
for(int i=1;i<=m;i++) s2[i]+=s2[i-1];
for(int i=1;i<=m;i++) s3[i]+=s3[i-1];
for(int l=1;l<=m;l++){
alls.push_back(s2[l]+s3[m]-s3[l-1]);
alls.push_back(s2[l-1]-s1[l]);
}
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
n=alls.size();
LL ans=0;
for(int l=m;l>=1;l--){
int x=find(s2[l]+s3[m]-s3[l-1]),y=find(s2[l-1]-s1[l]);
add(x);
int cnts=sum(n)-sum(y-1);
ans=(ans+cnts)%mod;
}
cout<
