A 装备二选一（一）
题目大意：
手中武器增加a%的暴击率，伤害变为原来的b倍
新获取武器增加c%的暴击率，伤害变为原来的d倍
新武器是否可以替换老武器
赛时错误思路：
两件武器均没有提升面板属性，看暴击产生的额外伤害确定替换(平时玩游戏经常这么换),设普攻伤害为x
那么旧武器暴击产生的伤害为a% * b * x - x
新武器x+c% * d * x - x
所以如果c%*d > a% *b可换
正解
应该用概率求暴击和不暴击造成的伤害和大小
旧武器：不暴击(1-a)*x+暴击(a) *bx
新武器：不暴击(1-c)*x+暴击© *dx
化简得（d-1）* c >（b-1）* a 可换
Solved
if(c*(d-1)>a*(b-1)){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
D 四散而逃
题目大意：
给定一排n个格子，n个格子里有不同的人，每次可从 j 号格子中选择两个人分别逃到 i 号格子和 k 号格子，要求i<j<k ,且1<j<n，如果n个格子里所有人都可以逃到1或n号格子，那么输出奔逃次数，否则-1
赛时错误想法：
第一次写读错题目了，以为每次j只能逃到j-1和j+1，模拟时没有ac样例，
第二次看完题，还是看错题目了，以为只能偶数改，奇数不可以改，思路很绕，赛时一直在实现错误代码，但是很难实现，看完题解发现只要数量大于2即可奔逃
正解：
肯定2~n-1格子中至少保证有一个偶数才可全部逃到q或n，有一个偶数就可以确保其余奇数全部改成偶数，如果一个偶数都没有就是-1
其他情况的逃跑次数就是（奇数+1）/2次，偶数/2
Solved
if(i!=1&&i!=n){if(a[i]%2==0){flag=1;}ans+=(a[i]+1)/2;}
C 16进制世界
题目大意：
有n个月饼，月饼有饱食度和幸福度两个属性。Bob有m饱食度，吃的月饼的幸福度之和必须是16的倍数，醉倒吃几块月饼
赛时错误想法：
一看题目就可以知道是01背包问题
我的第一思路是如果在给幸福度开一维，依次枚举幸福度，肯定会超时，所以想将饱食度不是16的倍数的月饼合并到一起凑成一个16的倍数，简化成一个朴素01背包，但是我发现实现不了，因为组合成16的倍数有很多种组合方式
正解：
只需要最后幸福度为16的倍数，根据同余模定理，如果两个数a,b加起来是16的倍数，只需要a,b模16的余数加起来是16的倍数即可，因此可以在一维01背包的基础上再开一维记录幸福度%16的余数即可
f[][]初始化为0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
//在该步骤下吃不了东西但是会因为上一层0+1导致吃了，因此初始化不能为0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2正解：f[][]初始化为-1，f[0][0]=0
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Solved
memset(f,-1,sizeof(f)); f[0][0]=0;//枚举第几个月饼for(int i=1;i<=n;i++){cin>>v>>w;w%=mod;//枚举体积for(int j=m;j>=v;j--){//枚举幸福度余数for(int k=0;k<16;k++){f[j][k]=max(f[j][k],f[j-v][(k+w)%mod]+1);}}}int res=0;for(int i=1;i<=m;i++){res=max(res,f[i][0]);}cout<<res;
L koala的程序
题目大意：
优化3e5的约瑟夫环问题
思路：
可用树状数组构造前缀和模拟每个数字，删数就是将该树状数组位置上的数-1
通过二分树状数组求出对应数字
Solved：
int lowbit(int x)
{return x&-x;
}void add(int x,int k)
{for(int i=x;i<=n;i+=lowbit(i)){tr[i]+=k;}
}int ask(int x)
{int res=0;for(int i=x;i>=1;i-=lowbit(i)){res+=tr[i];}return res;
}void solve()
{cin>>n>>m;//建树状数组for(int i=1;i<=n;i++){add(i,1);}int nn=n,now=1;while(nn){now=(now-1+m-1)%nn+1;int l=1,r=n;//二分求数while(l<r){int mid=l+r>>1;if(ask(mid)>=now){r=mid;}else{l=mid+1;}}if(nn==1) break;cout<<l<<" ";add(l,-1);nn--;}
}
G 等公交车
题目大意：
一条路线上有n个站点，分别距离发车点ni
有m辆车，发车时间为mi
q次询问，t时刻有人来到了x站点，问最短等待时间，否则TNT
思路：
t时刻来到了站点，需要找到发车时间+到达该站点x的时间t之和小于该t时刻，
那么就可用该时间减去公交车从发车点到达x站点的时间tt，二分找到tt时间后第一辆发车的公家车即可
tip：给出的站点，发车时间升序
在一个从小到大排序数组中
lower_bound(begin,end,num) bengin到end-1位置二分查找第一个大于或者等于num的数字
找到返回数字下标，不存在返回end
upper_bound(begin,end,num) 大于num的数字
Solved：
cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];//车站}for(int i=1;i<=m;i++){cin>>b[i];//i车 发车时间}int q,t,x;cin>>q;for(int i=1;i<=q;i++){cin>>t>>x;t=t-a[x];auto tt=lower_bound(b+1,b+1+m,t);if(tt-b>m){cout<<"TNT"<<endl;}else{cout<< *tt-t<<endl;}}
I 正义从不打背身
题目大意：
m轮小游戏，第i轮：
-
序号为[1,i]的点位上的敌人位置改变。改变规则为: 从1,2,3,……，i 变为i，i−1,……,3,2,1(原来位于i号位置的敌人更换到1号位置，位于i-1号位置的敌人更换到2号位置……）
-
序号为[1,i]的点位上的敌人原地旋转180°。
给定每个人面对的方向，问m次游戏后，每个人面朝方向，正面为1，反面为0
思路：
单看题目来说的，看不出什么思路，但是可以把每轮游戏打表出来，可以看到明显规律
打表
signed main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){a[i]=i;}for(int i=1;i<=m;i++){for(int j=1;j<=i/2;j++){swap(a[j],a[i-j+1]);//a[i],a[m-i+1],第i个数和最后i个数}for(int j=1;j<=i;j++){//前i个数翻转 if(vis[a[j]]==1){vis[a[j]]=0;}else{vis[a[j]]=1;}}//打表 cout<<i<<":"<<endl; for(int j=1;j<=i;j++){cout<<a[j]<<" ";}cout<<endl;for(int j=1;j<=i;j++){cout<<vis[a[j]]<<" ";}cout<<endl<<endl;}return 0;
}
1:
1
12:
2 1
1 03:
3 1 2
1 1 04:
4 2 1 3
1 1 0 05:
5 3 1 2 4
1 1 1 0 06:
6 4 2 1 3 5
1 1 1 0 0 07:
7 5 3 1 2 4 6
1 1 1 1 0 0 08:
8 6 4 2 1 3 5 7
1 1 1 1 0 0 0 09:
9 7 5 3 1 2 4 6 8
1 1 1 1 1 0 0 0 010:
10 8 6 4 2 1 3 5 7 9
1 1 1 1 1 0 0 0 0 0
可以发现规律、
后m+1n没有参与操作，保持原样，1m翻转
前m个数是以m开头，2为公差递减到1或2的等差数列
后半段为以1，2中剩余的那个开头，以2为公差递增到m-1
前半段长度为（m+1）/2
后半段为m/2
Solved：
signed main()
{int n,m;cin>>n>>m;string s;cin>>s;s=" "+s;int k=1;for(int i=m;i>=1;i-=2){if(s[i]=='P'){vis[k++]=1;}else{vis[k++]=0; }}for(int i=(m%2)?2:1;i<=m;i+=2){if(s[i]=='P'){vis[k++]=1;}else{vis[k++]=0;}}for(int i=m+1;i<=n;i++){if(s[i]=='P'){vis[k++]=1;}else{vis[k++]=0;}}for(int i=1;i<=(m+1)/2;i++){if(vis[i]==1){vis[i]=0;}else{vis[i]=1;}}for(int i=1;i<=n;i++){cout<<vis[i]<<" ";}return 0;
}
H 24点
前置知识
next_permutation(begin(),end())全排列函数，可以得到序列的下一个字典序的全排列，
全排列模板
int num[3]={1,2,3}; do { cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl; }while(next_permutation(num,num+3));
将会输出
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
题目大意：
用给定的四张牌通过基本的数学运算（加、减、乘、除）得到24
思路：
枚举所有的情况，如果有值能够输出24，YES，否则NO
具体做法可以看代码实现
#include <bits/stdc++.h>
#define int long longusing namespace std;
const int N=1e3+10;map<string,int> mp={{"A",1},{"2",2},{"3",3},{"4",4},{"5",5},{"6",6},{"7",7},{"8",8},{"9",9},{"10",10},{"J",11},{"Q",12},{"K",13},
};int f(vector<double> a)
{//结束条件 //递归处理每个数，如果只剩1个数，比较一下与24的关系，但是除法有误差 if(a.size()==1) return abs(a[0]-24)<1e-6;for(int i=0;i<a.size();i++){//枚举第一个数字 for(int j=0;j<a.size();j++){if(i!=j){//当两者不为同一个数时，可进行操作vector<double> b;for(int k=0;k<a.size();k++){//将剩余数字存入b中 if(k!=i&&k!=j){b.push_back(a[k]); }}//枚举四种操作 for(int op=0;op<4;op++){//a+b==b+a和a*b==b*a,所以出现这两种情况，可以剪枝 if(op<2&&i>j) continue;switch(op){//加法，将枚举的两个数字相加并加入b中 case 0:b.push_back(a[i]+a[j]); break;//乘法 case 1:b.push_back(a[i]*a[j]); break;//减法 case 2:b.push_back(a[i]-a[j]); break;//除法 case 3:b.push_back(a[i]/a[j]); break;} //递归处理剩下的数字，直到只剩一个数字 if(f(b)) return 1;b.pop_back(); } }}}
}void solve()
{vector<double> a(4);for(int i=0;i<4;i++){string s;cin>>s;a[i]=mp[s];}sort(a.begin(),a.end());//全排列处理每种情况 do{if(f(a)){cout<<"YES"<<endl;return;}}while(next_permutation(a.begin(),a.end()));cout<<"NO"<<endl;
}signed main()
{int t;cin>>t;while(t--){solve();}return 0;
}
