zibenlun 的博客本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-10 15:22:48
根据题目要求，可以看出想要 $AC$ 的话需要一定少的步数，所以可以想到一种不太聪明的方法：
首先我们从左上到右下依次下红子，这时不太聪明的交互库就会开始从蓝色点防守。这四个子下完后，我们就直接绝杀，下黄色所在的两个子。
其实这个方法有点问题，所以想看正解还是去看其他大佬的吧。
#include<bits\/stdc++.h>
using namespace std;
int main(){
cout<<"500 500";
cout<<"501 501";
int x,y;
cin>>x>>y>>x>>y;
cout<<"502 502";
cout<<"503 503";
cin>>x>>y>>x>>y;
cout<<"502 501";
cout<<"501 502";
return 0;
}
代码仅提供思路，不要抄……
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-11 20:53:21
为什么没有人写题解呢？
挺简单的一题，题目大体意思就是求最少跳多远就能从第一条线段走到最后一条线段。
很容易想到二分，所以重点在于怎么判断当前长度是否合法，可以想到维护从一开始到现在所能跳到的范围。
时间复杂度 $O(nlogn)$
#include<bits\/stdc++.h>
using namespace std;
\/\/从来不用的快读快写
inline long long read() {
long long s=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') {
s=(s<<3)+(s<<1)+(ch^48);
ch=getchar();
}
return s;
}
inline void write(long long x) {
if(x<0) putchar('-'),x=-x;
if(x>9) write(x\/10);
putchar(x%10+'0');
}
int t,n;
struct nd{
long long l,r;
}a[1000005];\/\/存一下左右边界
bool check(int k){
long long l=0,r=0;
for(int i=1;i<=n;i++){
if(a[i].l>r){
if(a[i].l-r>k) return false;
r=min(a[i].r,r+k);
l=a[i].l;
}
else if(a[i].r<l){
if(l-a[i].r>k) return false;
l=max(l-k,a[i].l);
r=a[i].r;
}
else {
r=min(a[i].r,r+k);
l=max(a[i].l,l-k);
}
}
return true;
}
int main(){
\/\/ freopen(".in","r",stdin);
\/\/ freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].l>>a[i].r;
long long l=0,r=1e9+5,ans=0x3f3f3f3f3f3f;\/\/二分长度
while(l<r){
long long mid=(l+r)>>1;
if(check(mid)){
r=mid-1;
ans=min(ans,mid);\/\/记录答案
}
else {
l=mid+1;
}
}
for(int i=max(ans-10,1ll*0);i<=ans;i++){
if(check(i)) {
ans=i;
break;
}
}
\/\/本人的二分老是挂，所以写了个补丁……
cout<<ans<<"\n";
}
return 0;
}
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-11 21:07:24
这题乍一看感觉是括号匹配，但是细想其实是一个更加复杂的贪心。
例如这一组数据：
$abcdee$ 可以看到，当我们从左到右开始模拟的时候，发现最后剩下了 $ee$ 但是事实上，可以通过不按照原先的顺序从而消除所有的字符。
并且再通过观察，如果有一段连续的相同字符，那么它的两遍总是会有与它不同的字符，所以理论上是全部可以消除的。
但在常识上，如果在一个字符串中出现最多的字符出现次数占到了一半以上，那么肯定是消除不完的。
所以就有了以下代码：
#include<bits\/stdc++.h>
using namespace std;
inline long long read() {
long long s=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') {
s=(s<<3)+(s<<1)+(ch^48);
ch=getchar();
}
return s;
}
inline void write(long long x) {
if(x<0) putchar('-'),x=-x;
if(x>9) write(x\/10);
putchar(x%10+'0');
}
int t,n,cnt[30],maxx;
char s[1000005];
int main(){
\/\/ freopen(".in","r",stdin);
\/\/ freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--){
cin>>n>>(s+1);
memset(cnt,0,sizeof cnt),maxx=0;
for(int i=1;i<=n;i++){
cnt[s[i]-'a']++;
maxx=max(maxx,cnt[s[i]-'a']);
}
if(maxx>n\/2) cout<<maxx*2-n;
else cout<<(n&1);
cout<<"\n";
}
return 0;
}
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-03-12 21:01:28
题目的要求很简单，根据众数的定义我们可以知道，当有多个数一样时这几个数都是众数，所以我们要尽可能的去维护一个能让各个数中出现次数的最大值所包含的数最多例如： 当我们有1 2 3 3 4时 我们应该将它们排列为1 2 3 4 3 这样我们的众数和就是1 1+2 1+2+3 1+2+3+4 3即为最大解 而其余的排列方法均是小于它的（至于为什么，你们自己试试就知道了） 所以我们就把所有的数字最分散地排列就行了 下面就是代码：
#include<iostream>
\/\/头文件也可以用#include<bits\/stdc++.h>
using namespace std;
long long n,ans,a[1000005],sum[1000005],cnt;
int main(){
scanf("%lld",&n);\/\/平时用scanf的话这里记得用%lld
for(int i=1;i<=n;i++) {
scanf("%lld",&a[i]);
}
for(int i=n;i>=1;i--){
while(cnt<a[i]) sum[++cnt]+=i+sum[cnt-1];\/\/前缀和
ans+=sum[a[i]];
}
printf("%lld",ans);
return 0;
}
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-04-09 15:20:14
Bombs
题目描述
有一个 R 行 C 列的盘面，点 (i)(j) 表示第 i行第 j列的格子。上面有三种状态,”.”代表空地,”#” 代表一堵墙,1,2,3,4,5,6,7,8,9代表炸弹。上面的1-9代表炸弹的威力值。
下面，所有的炸弹同时爆炸，所有曼哈顿距离小于等于每个点上的威力值的墙将变成空地。
注意：如果该点在爆炸范围内，且该点是炸弹，则不会变成空地。爆炸后，该炸弹本身会变成空地。
你需要输出爆炸后的盘面
直接暴力，先遍历所有的点，找到炸弹，再从头遍历，把所有在范围内的“#”变成“.”
注意：引爆时，不能把周围的炸弹变成“.”```
#include<bits\/stdc++.h>
using namespace std;
int n,m;
char a[1005][1005];
int main() {
cin>>n>>m;
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin>>a[i][j];
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if(a[i][j]>='1'&&a[i][j]<='9') {
for(int x=1; x<=n; x++) {
for(int y=1; y<=m; y++) {
if(abs(i-x)+abs(j-y)<=a[i][j]-'0'&&a[x][y]=='#') {
a[x][y]='.';
}
}
}
}
}
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if(a[i][j]>='1'&&a[i][j]<='9') a[i][j]='.';
cout<<a[i][j];
}
cout<<endl;
}
return 0;
}
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-05-03 19:12:18
首先遍历左右端点，然后从两端向中间遍历，对两端的数值进行比较，并统计个数。 话不多说直接上代码
#include<bits\/stdc++.h>
using namespace std;
int sum;
string a;
int main(){
cin>>a;
for(int i=0;i<a.size();i++){
for(int j=i;j<a.size();j++){
if(a[j]<a[i]){
sum++;
}
else if(a[j]==a[i]&&i!=j){
for(int x=i,y=j;y>x;x++,y--){
if(a[y]<a[x]){
sum++;
break;
}
else if(a[y]>a[x]){
break;
}
}
}
}
}
printf("%d",sum);
return 0;
}
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-06 10:56:50
一定要通过啊！
看到题解里都是折半（或叫双端）搜索，那我就来发一个随便乱搞 模拟退火。
由于我们不知道选几个数，所以直接暴力出选择的长度，再来跑上几遍 SA。
#include<bits\/stdc++.h>
using namespace std;
int n,m;
long long a[1000005];
long long ans;
long long check(int len){
long long cnt=0;
for(int i=1;i<=len;i++){
cnt+=a[i];
}
if(cnt<=m) return cnt;
else return 0;
}
void SA(int len){
double t=rand()%6000,x=0.682755;
while(t>1e-15){
int l=rand()%(len)+1,r=min(rand()%(n-len+1)+len,n);
swap(a[l],a[r]);
long long sum=check(len);
if(sum>ans){
ans=sum;
}
else {
if(rand()*pow(x,100)>t) swap(a[l],a[r]);
}
t*=x;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=10000;j++) SA(i);
}
cout<<ans;
return 0;
}
没什么讲的必要，纯纯模版题，双端搜完再二分拼合就行了。
#include<bits\/stdc++.h>
using namespace std;
long long a[1100005],b[1100005],s[55],ans,m,cntt,cnt,n;
void dfs1(int x,long long sum){
if(sum>m) return;
if(x>n\/2){
a[++cnt]=sum;
return;
}
dfs1(x+1,sum+s[x]);
dfs1(x+1,sum);
}
void dfs2(int x,long long sum){
if(sum>m) return;
if(x>n){
b[++cntt]=sum;
return;
}
dfs2(x+1,sum+s[x]);
dfs2(x+1,sum);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>s[i];
dfs1(1,0);
dfs2(n\/2+1,0);
sort(a+1,a+cnt+1);
sort(b+1,b+cntt+1);
for(int i=1;i<=cnt;i++) ans=max(ans,b[upper_bound(b+1,b+cntt+1,m-a[i])-b-1]+a[i]);
cout<<ans;
return 0;
}
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-07 10:19:08
你有两个字符串 $s$ 和 $t$，它们初始都为 a，你会对字符串进行 $q$ 次操作两种类型的操作：
操作一：在 $s$ 末尾添加字符串 $k$ 恰好 $x$ 次
操作二：在 $t$ 末尾添加字符串 $k$ 恰好 $x$ 次
求每次操作之后，是否可以重新排列 s 和 t 的字符，使 s 字典序比 t 小，如果可以，则 cout<<"YES"; ，否则 cout<<"NO";。
字符串的字典序比较与正常的数字不同，它比较的主要是每一个字符的大小，只有当两个字符串较短部分完全相等时才会比较长度，而比较符号只会判断字符的大小，并不会比较长度所以长度需要单独判断。
首先我们知道 a 是小写字母中最小的字符，所以我们可以发现，只要去维护 $s$ 的开头为 a 就是最有机会成立的，同时我们也要维护 $t$ 的开头不为 a 就可以使 $s$ 的字典序比 $t$ 小。当两者不能通过开头比较时，在比较全文或长度。
之后你提交代码就会发现超时了，那就再考虑剪枝，我们可以发现其实只要 $t$ 的开头不是 a 并且比 $s$ 小时那么之后一定是成立的。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-10 09:01:17
给定两个字符串，通过相邻两位的异或和或运算，使一个字符串变成另一个。
本题的关键是或运算，因为或运算的结果都是 $1$,所以只要有了一个 $1$，那么所有的 $0$ 就都能够变成 $1$，所以我们可以得出结论，只要 $B$ 字符串中有 $1$，那么 $A$ 中必须也有一个 $1$，不然就不能变成 $B$ 串。
#include<bits\/stdc++.h>
using namespace std;
\/\/快读，快写
inline int read(){
int s=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9'){
s=(s<<3)+(s<<1)+(ch^48);
ch=getchar();
}
return s;
}
inline void write(long long x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x\/10);
putchar(x%10+'0');
}
int main(){
\/\/ freopen(".in","r",stdin);
\/\/ freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string a,b;
cin>>a>>b;
if(a.size()!=b.size()){
cout<<"NO";
return 0;
}
int flaga=0,flagb=0;
for(int i=0;i<a.size();i++){
if(a[i]=='1') flaga=1;
if(b[i]=='1') flagb=1;
}
if(flagb==1&&flaga==0 || flaga==1&&flagb==0) cout<<"NO";
else cout<<"YES";
return 0;
}
点个赞再走吧~
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-20 11:41:15
首先我们可以发现因为有了其中一边是 $2$ 的 $x$ 方，所以我们可以轻而易举的算出其中一条边，那么另一条边就可以通过这条边推出。此时分为两种情况，第一种是已经算出的为高，另一种就是已经算出的边为宽，最后取最大值输出就可以了。
要开 long long
#include<bits\/stdc++.h>
using namespace std;
inline long long read()
{
long long s=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') {
s=(s<<3)+(s<<1)+(ch^48);
ch=getchar();
}
return s;
}
inline void write(long long x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x\/10);
putchar(x%10+'0');
}
long long h,w,ans=1;
int main()
{
\/\/ freopen(".in","r",stdin);
\/\/ freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
h=read();
w=read();
while(ans<<1 <= min(h,w)) ans<<=1;
if(min(h, (long long)(ans*1.25))>=min(w, (long long)(ans*1.25))) {
write(min(h, (long long) (ans*1.25)));
putchar(' ');
write(ans);
} else {
write(ans);
putchar(' ');
write(min(w, (long long) (ans*1.25)));
}
return 0;
}
鲁ICP备2025150228号