目录
A.会赢吗?
B.能做到的吧
C.会赢的!
D.好好好数
F.随机化游戏时间
A.会赢吗?
思路: 签到题,比大小
void solve()
{double a,b;cin>>a>>b;if(a>=b) cout<<"NO";else cout<<"YES";
}
B.能做到的吧
思路:只要能变大就行,那么我们就将字符串从大到小排序,如果最大字符串与原字符串相等,则不能变大了,输出NO,反之输出YES
void solve()
{int t;cin>>t;while(t--){string s;cin>>s;string temp=s;sort(s.rbegin(),s.rend());if(s==temp) pnelse py}
}
C.会赢的!
思路:思维+贪心,我们可以分以下几种情况讨论
(1)x<0||y<0,起始点为(0,0),每次只能向下或向右走,所以当终点在上方或左边时,两个人不可能到达,即结果一定为平局
(2)(x+y)%2==0,说明到达终点的最短步数为偶数步,而先手只能在奇数步移动棋子,所以到达终点的最后一步一定是后手,那先手现在只能尽可能让局面走向平局,那如何走呢?我们会发现平局的时候是终点在棋子上方或左边的时候,也就是棋子的横坐标>x或 棋子的纵坐标>y,那先手就要选择x,y中更小的那个方向走了,因为这样才能尽快的走向平局,如果先手超过了x,y中最小的那个值mind,若此时为mind+1<maxd,表明后手还没到达终点,且已经被先手移动到终点右边或下面了,输出PING,否则先手输
(3)(x+y)%2==1,与(2)同理,后手尽可能让局面走向平局,如果mind+1==maxd,由于先手先下,所以每次先手下棋的时候都是领先后手一步棋,设x为mind,y为maxd,当后手下在(mind,mind)位置时,先手接着就会下在(mind,mind+1)位置,所以后手走到mind+1==maxd时,先手已经走到了(mind,maxd)的位置,即先手赢,否则PING
void solve()
{int t;cin>>t;while(t--){int x,y;cin>>x>>y;int sum=x+y;if(x<0||y<0) cout<<"PING"<<endl;else {if(sum==1){pycontinue;}int maxd=max(x,y),mind=min(x,y);if(sum&1){int s=mind+1;if(s==maxd) pyelse if(s<maxd) cout<<"PING"<<endl;}else{int s=mind+1;if(x==y) pnelse if(s<maxd) cout<<"PING"<<endl;}}}
}
D.好好好数
思路: 因为k的好数为若干个不同的k的整数次幂之和的数字,也就是好数对应的k进制位只有0和1,如果一个数至少由两个好数组成,说明这两个好数中有重复的幂次,那么在转换成k进制时会累加重复的那个k进制位,比如12 3,12=9+3=(3^2)+3^1=(110)3,因为(110)中最大的数为1,说明只需一个好数,15=12+3=(110)3+(010)3=(120)3,最大为2,由两个好数组成。
void solve()
{int t;cin>>t;while(t--){int n,k;scanf("%lld %lld",&n,&k);if(k==1){printf("1\n");continue;}int maxd=0;while(n){maxd=max(maxd,n%k);n/=k;}printf("%lld\n",maxd);}}
F.随机化游戏时间
思路 :主席树的板子忘了,又把板子掏出来看了一眼🤣,一个区间中含有k个小于等于这个幸运数的数字,说明这个幸运数>=这个区间第k小的数,查询的时候还要分情况讨论下
(1)k==0,说明[l,r]这个区间的数都大于幸运数字,那么幸运数字的所在范围的右区间应<=[l,r]第1小的数字-1
(2)k==r-l+1,说明这个幸运数字大于等于这个区间的所有数字,幸运数字所在范围的左区间>=这个区间第k小的数字
(3)0<k<r-l+1,幸运数字左右区间都要更新。
constexpr int N=2e5+5,mod=1e9+7;int a[N],n,m,root[N],idx;
vector<int> num;struct node{int l,r,cnt;
}tr[N*20];int find(int x)
{return lower_bound(num.begin(),num.end(),x)-num.begin();
}int build(int l,int r)
{int p=++idx;if(l<r){int mid=(l+r)>>1;tr[p].l=build(l,mid);tr[p].r=build(mid+1,r);}tr[p].cnt=0;return p;
}int modify(int pre,int l,int r,int x)
{int p=++idx;tr[p]=tr[pre];tr[p].cnt++;if(l==r) return p;int mid=(l+r)>>1;if(x<=mid) tr[p].l=modify(tr[pre].l,l,mid,x);else tr[p].r=modify(tr[pre].r,mid+1,r,x);return p;
}int query(int p,int q,int l,int r,int k)
{if(l==r) return l;int sum=tr[tr[q].l].cnt-tr[tr[p].l].cnt;int mid=(l+r)>>1;if(k<=sum) return query(tr[p].l,tr[q].l,l,mid,k);else return query(tr[p].r,tr[q].r,mid+1,r,k-sum);
}int qmi(int a,int b)
{int res=1;while(b){if(b&1) res=res*a%mod;b>>=1;a=a*a%mod;}return res;
}void solve()
{idx=0;num.clear();mem(root,0)cin>>n>>m;for(int i=1;i<=n;i++) {cin>>a[i];num.pb(a[i]);}sort(num.begin(),num.end());num.erase(unique(num.begin(),num.end()),num.end());int Max=num.size()-1;int L=1,R=n;root[0]=build(0,Max);for(int i=1;i<=n;i++)root[i]=modify(root[i-1],0,Max,find(a[i]));while(m--){int l,r,k;cin>>l>>r>>k;if(!k){int q=num[query(root[l-1],root[r],0,Max,1)];R=min(R,q-1);}else if(k==r-l+1){int q=num[query(root[l-1],root[r],0,Max,k)];L=max(L,q);}else{int q=num[query(root[l-1],root[r],0,Max,k)];L=max(L,q);q=num[query(root[l-1],root[r],0,Max,k+1)];R=min(R,q-1);}}if(L==R) cout<<1<<' '<<L<<endl;else cout<<qmi(R-L+1,mod-2)<<endl;
}int32_t main()
{//__md//init();int t;cin>>t;//t=1;while(t--){solve();}}