2024 暑假友谊赛 2
B. Tiling Challenge
1.我的方法是按顺序遍历，遇到' . '时就检查一下它的上下左右是不是都是点，如果都是点的话，标记这个点，把这个点和他上下左右都标记为‘？’，但是要加一个条件，如果‘.’的个数不是5的倍数就不符合题意，不加这个会wa37，我也不知道为什么
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
char c[55][55];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
bool st[55][55];
int n;
bool check(int i,int j)
{
for(int k=0;k<4;k++){
int a=i+dx[k],b=j+dy[k];
if(a>=0&&a<n&&b>=0&&b<n&&(c[a][b]=='#'||c[a][b]=='?')) return 0;
}
return 1;
}
void mark(int i,int j)
{
for(int k=0;k<4;k++){
int a=i+dx[k],b=j+dy[k];
if(a>=0&&a<n&&b>=0&&b<n&&c[a][b]!='?') c[a][b]='?';
}
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
int fla=0,cnt=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++) {
cin>>c[i][j];
if(c[i][j]=='.') fla=1,cnt++;
}
if(!fla||cnt%5!=0){
cout<<"NO";
return 0;
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(c[i][j]=='.'){
if(check(i,j)) mark(i,j),c[i][j]='?';
}
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
if(c[i][j]=='.'){
cout<<"NO";
return 0;
}
}
cout<<"YES";
return 0;
}
D - All Assign Point Add
1.主要是要优化操作一，不然就会tle，那怎么优化呢？因为1操作是让数组里的每个数都变成这个值，我不去整体改变这个数组，在1操作以后的第一次操作2后把这个操作2要改变的对应数组元素改为操作1给的数。
2.我的策略是开一个add数组，然后当操作1出现过后，把当前值放进数组里，当每个数第一次被操作2改变的时候，把这个数改为add【对应】，然后处理即可
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
char c[55][55];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
bool st[55][55];
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int n; cin>>n;
int a[n+1];
for(int i=1;i<=n;i++) cin>>a[i];
int m; cin>>m;
int add[200005];
map<int,int>mp;
int p=0;
for(int i=0;i<m;i++)
{
int x; cin>>x;
if(x==3) {
int id ;cin>>id;
if(p!=0)//这个条件
{
if(mp[id]==0){//和这个条件可以实现让这个对应的数改为1要求的数
a[id]=add[p];
mp[id]=1;
}
}
cout<<a[id]<<endl;
}
if(x==2){
int id,z; cin>>id>>z;
if(p!=0)
{
if(mp[id]==0){
a[id]=add[p];
mp[id]=1;
}
}
a[id]+=z;
}
if(x==1) {
int z;cin>>z;
add[++p]=z;//放进对应数组里
mp.clear();//记得清理标记
}
}
return 0;
}
B - Reserve or Reverse
1.使用双指针，每次检查一下s【l】，是不是l-r这个区间的最小字母，如果不是就用一个离r最近并且最小的字母来替换，也就是要不断维护区间的最小字母，使用multiset来维护最小，当s【r】不是最小的时候，就更新r，删掉set里面这个字母，相当于更新了区间。
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,int>pci;
#define x first
#define y second
#define all(v) v.begin(),v.end()
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int n; cin>>n;
string s; cin>>s;
multiset<char>se;
for(int i=0;i<n;i++) se.insert(s[i]);
int l=0,r=n-1;
while(l<r)
{
//先检查一下s【l】是不是l-r这段区间的最小字母
//如果不是，找一个离r最近的并且最小的字母与之交换
if(s[l]!=*se.begin())
{
while(s[r]!=*se.begin()){//如果不是就从set里删掉，维护区间最小字母
se.erase(se.find(s[r]));//每一次移动都要记得更新区间，达到维护区间最小的目的
r--;
}
swap(s[l],s[r]);
se.erase(se.find(s[l]));
l++;
se.erase(se.find(s[r]));
r--;
}else{
se.erase(se.find(s[l]));
l++;
}
}
cout<<s<<endl;
return 0;
}
D. Walk on Matrix
1.位与运算并不是数越大，结果越大的。我们构造一个矩阵，如果按照图片中的意思来走，结果得到为0，而正确的结果是k即可
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
char c[55][55];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
bool st[55][55];
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int k; cin>>k;
int num=0;
int p=k;
while(p)
{
num++;
p>>=1;
}
int a[3][2];
cout<<3<<" "<<2<<endl;
a[0][0]=(1<<(num+1))-1;//具有num+1位个1的二进制数
a[0][1]=k;
a[1][0]=(1<<num);
a[1][1]=(1<<(num+1))-1;
a[2][0]=0;
a[2][1]=(1<<num)-1;
for(int i=0;i<3;i++)
{for(int j=0;j<2;j++)cout<<a[i][j]<<" ";
cout<<endl;
}
return 0;
}