10.18 %你赛总结

news/2024/10/19 8:21:49

10.18 日模拟赛总结

T1 一维围棋

思路

由于本人太蒟了，不会 $O(n)$。求教。

简单题目。首先，看到数据范围 $|s| \le 100$，于是得到可以有 $O(n^4)$ 做法。先 $O(n)$ 枚举 $s_i$ 对于是 . 的位置变成 W。然后 $O(n^2)$ 枚举修改后的数组的每个子串，对于 $[l,r]$ 这个区间内的子串。当其满足 $s_l$ 与 $s_r$ 都为 W 且 $[l+1,r-1]$ 区间内全为 B 且从 $l-1$ 到 $1$ 与 $r+1$ 到 $n$ 的字符第一个不是 W 的字符不为 B 即可。因为 $[l,r]$ 需要暴力 check。故总时间复杂度为 $O(n^4)$。可以通过此题。

AC code

#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace WYL{int n,ans;string s,str;int main(){cin>>n;cin>>s;for(int i=0;i<s.size();i++){str=s;if(str[i]=='.'){str[i]='W';
//				cout<<str<<endl;for(int l=0;l<s.size();l++){for(int r=0;r<s.size();r++){if(r-l+1<3){continue;}int flag=0;if(str[l]=='W'&&str[r]=='W'){for(int j=l+1;j<=r-1;j++){if(str[j]!='B'){flag=1;break;}}}else{continue;}
//						cout<<flag<<" ";if(flag==1){continue;}for(int j=l;j>=0;j--){if(str[j]=='.'){flag=0;break;}if(str[j]=='B'){flag=1;break;}}if(flag==1){continue;}for(int j=r;j<=s.size()-1;j++){if(str[j]=='.'){flag=0;break;}if(str[j]=='B'){flag=1;break;}}if(flag==1){continue;}ans=max(ans,r-l-1);
//						cout<<l<<" "<<r<<endl;}}}}cout<<ans<<endl;return 0;}
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//	freopen("capture.in","r",stdin);
//	freopen("capture.out","w",stdout);WYL::main();return 0;
}

T2 斜二等轴测图

思路

其实跟一元二次方程难度差不多。这一提供两种思路。

第一。我们考虑把原图分成三个部分来看。我画个图，这就很明显了。

这个图是 $a=4,b=3,c=2$ 的。我们对于每一行每一列进行奇偶判断在直接输出一下就可以了。这里提醒 数组要开大一点，不然怎么挂的你都不知道。

第二种思路也很一眼。这是我亲爱的同机房大佬提出的。我们可以把原图分层，分开处理 /，+ 和 -。这样没有上面那种解法容易挂分。但是我考场写的上面那种思路。于是顺其自然只提供思路一的代码（乐。

AC code

#include<bits/stdc++.h>
using namespace std;
namespace WYL{int T,a,b,c,chang,kuan;char mp[200][200];void debug(){for(int i=1;i<=kuan;i++){for(int j=1;j<=chang;j++){cout<<mp[i][j];}cout<<endl;}}void shang(){for(int i=1;i<=b*2+1;i++){if(i%2==1){int shuliang=a*2+1;
//				cout<<shuliang<<endl;int qianmiankong=chang-shuliang-i+1;int sum=1;for(int j=qianmiankong+1;j<=qianmiankong+shuliang;j++){if(sum%2==1){mp[i][j]='+';}else{mp[i][j]='-';}sum++;}}else{int shuliang=a*2+1;int qianmiankong=chang-shuliang-i+1;int sum=1;for(int j=qianmiankong+1;j<=qianmiankong+shuliang;j++){if(sum%2==1){mp[i][j]='/';}else{mp[i][j]='.';}sum++;}}}return;}void qian(){int huangshu=c*2,sum=1;for(int i=kuan;i>=kuan-huangshu+1;i--){int shuliang=2*a+1;if(sum%2==1){int num=1;for(int j=1;j<=shuliang;j++){if(num%2==1){mp[i][j]='+';}else{mp[i][j]='-';}num++;}}else{int num=1;for(int j=1;j<=shuliang;j++){if(num%2==1){mp[i][j]='|';}else{mp[i][j]='.';}num++;}}sum++;}return;}void ce(){int lieshu=b*2,sum=1,kaishi=2;for(int i=chang;i>=chang-lieshu+1;i--){if(sum%2==1){int num=1;for(int j=1;j<=2*c;j++){if(num%2==1){mp[j+kaishi-1][i]='|';}else{mp[j+kaishi-1][i]='+';}num++;}}else{int num=1;for(int j=1;j<=2*c;j++){if(num%2==1){mp[j+kaishi-1][i]='.';}else{mp[j+kaishi-1][i]='/';}num++;}}sum++;kaishi++;}return;}int main(){cin>>T;while(T--){cin>>a>>b>>c;chang=(a+b)*2+1;kuan=(c+b)*2+1;
//			cout<<chang<<" "<<kuan<<endl;for(int i=1;i<=kuan;i++){for(int j=1;j<=chang;j++){mp[i][j]='.';}}shang();
//			debug();qian();
//			debug();ce();debug();}return 0;}
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//	freopen("draw.in","r",stdin);
//	freopen("draw.out","w",stdout);WYL::main();return 0;
}
/*1 4 3 221 1 16 2 4
*/