2024 暑假友谊赛 2

A.Tiling Challenge - CodeForces 1150B - Virtual Judge

 如果有两块相连的绿色地砖，这两个能组成同一个十字，那么这两个地砖不可能是十字的上面或者下面只能是中间，那么我们可以知道，每一个十字的上面那块都是确定的，我们从上到下枚举行，能补十字就补，一定是最优方案。最后检查有没有剩下的绿色地砖就可以。

#include<bits/stdc++.h>
#define endl '\n'
#define mk make_pair
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5+10;
int n,m,k;
char a[55][55];

void check(int x,int y){
    if(x+1>=n||x+2>=n||y-1<0||y+1>=n) return;
    if(a[x+1][y-1]=='.'&&a[x+1][y]=='.'&&a[x+1][y+1]=='.'&&a[x+2][y]=='.'){
        a[x+1][y-1]='#';a[x+1][y]='#';a[x+1][y+1]='#';a[x+2][y]='#';
        a[x][y]='#';
    }
}

void sovle(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>a[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(a[i][j]=='.'){
                check(i,j);
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            //cout<<a[i][j];
            if(a[i][j]=='.'){
                cout<<"NO"<<endl;
                return;
            }
        }//cout<<endl;
    }
    cout<<"YES"<<endl;
}

signed main()
{	
    ios::sync_with_stdio(false), cin.tie(0),cout.tie(0); 
    int t = 1;
    //cin>>t;
    while (t--){
        sovle();
    }

    return 0;
}

B.Walk on Matrix - CodeForces 1332D - Virtual Judge

 构造题，如果k是0答案很明显。

dp方法为什么会错？我们思考之后可以发现，dp只考虑到了走到当前位置的最大值，但是并不是走到最后一位的最大值，换句话说，因为是&运算，前面dp之后留下来的二进制位上的1最后一位很可能并没有。所以要得到最大的答案，应该走最后一位数上二进制位是1最多的路。知道这些之后，我们可以设计一条线路，最后一个数是k，在最后一步之前，dp值最大但是&k等于0，另一条线路&运算一直等于最后一个数，最后差值就是k。要设计dp线路，我们可以让dp等于比k大的2的某次方，这样&操作就是0.要设计正确线路，我们让这条线路上的数&都为k就行。矩阵的大小并不重要，重要的是满足这两条路线。具体看代码

#include<bits/stdc++.h>
#define endl '\n'
#define mk make_pair
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5+10;
int n,m,k;


void sovle(){
    cin>>n;
    int u=1;
    while(u<=n){
        u*=2;
    }
    int x=u+n;
    if(n==0){
        cout<<1<<' '<<1<<endl;
        cout<<1<<endl;return;
    }
    cout<<3<<' '<<3<<endl;
    cout<<x<<' '<<n<<' '<<0<<endl;
    cout<<u<<' '<<n<<' '<<0<<endl;
    cout<<x<<' '<<x<<' '<<n<<endl;
}

signed main()
{	
    ios::sync_with_stdio(false), cin.tie(0),cout.tie(0); 
    int t = 1;
    //cin>>t;
    while (t--){
        sovle();
    }

    return 0;
}

D.Reserve or Reverse - AtCoder arc134_b - Virtual Judge

 要使字典序最小，我们当然要让越小的字母越靠前。我们可以发现交换是在选中的字母中，分别交换第一位和最后一位，第二位和倒数第二位...... 那么每次交换之后右边字符后面的字符都不用考虑。要让最小的字母靠前，我们枚举a到z，对l-r(只有l-r是可行域)内，如果发现小字符在后就交换它和开头字符的顺序（保证开头字符大于小字符的前提，如果等于，那么交换无意义），这样我们就保证在交换规则下，有最小字典序的字符串。

#include<bits/stdc++.h>
#define endl '\n'
#define mk make_pair
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5+10;
int n,m,k;
map<char,int>v;

void sovle(){
    cin>>n;
    string s;cin>>s;
    int l=0,r=n-1;
    for(char i='a';i<='z'&&l<r;i++){
        while(s[l]==i) l++;
        for(int j=r;j>l;j--){
            if(s[j]==i){
                r=j-1;
                swap(s[j],s[l]);
                l++;
                while(s[l]==i) l++;
            }
        }
    }cout<<s<<endl;
}

signed main()
{	
    ios::sync_with_stdio(false), cin.tie(0),cout.tie(0); 
    int t = 1;
    //cin>>t;
    while (t--){
        sovle();
    }

    return 0;
}

E.All Assign Point Add - AtCoder abc278_d - Virtual Judge

 对于操作1，是对所有数都修改成同一个值。

对于操作2，是修改某一个数的值。

那么其实我们不需要遍历数组对所有数进行操作。我们开两个栈（后进的在顶）来存储操作1修改后的值和当前操作的时间，用一个pair数组存储操作2对单个数的修改和时间。

对每次查询，如果查询数的位置在pair数组修改的时间晚于栈顶的时间（上一次操作1），那么就是上次操作1加上pair数组修改的值。

#include<bits/stdc++.h>
#define endl '\n'
#define mk make_pair
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5+10;
int n,m,k;
int a[N];
pair<int,int> b[N];
stack<int>v,vv;

void sovle(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    cin>>k;
    int cnt=1;
    while(k--){
        cin>>m;
        if(m==1){
            int x;cin>>x;v.push(x);
            vv.push(cnt);
        }else if(m==2){
            int x,y;cin>>y>>x;
            if(!vv.size()||vv.size()&&b[y].second>vv.top()){
                b[y].first+=x;
            }else{
                b[y].first=x;
            }b[y].second=cnt;
        }else{
            int x;cin>>x;
            if(v.size()){
                if(b[x].second>vv.top()){
                    cout<<v.top()+b[x].first<<endl;
                }else{
                    cout<<v.top()<<endl;
                }
            }else{
                cout<<a[x]+b[x].first<<endl;
            }
        }
        cnt++;
    }
}

signed main()
{	
    ios::sync_with_stdio(false), cin.tie(0),cout.tie(0); 
    int t = 1;
    //cin>>t;
    while (t--){
        sovle();
    }

    return 0;
}

I.Earn to Advance - AtCoder abc344_f - Virtual Judge

 hard...