题解

luqyou · 2023-02-22 17:16:14 · 个人记录

一元一次方程

扫一遍字符串，然后处理出常数项与 x 的系数（其实就是合并同类项）相除即可。在处理时不要忘记移项变号和判断 x 系数为 1 的情况。

有个需要注意的点：%.1lf 占位符会把像 -0.01 的数保留成 -0.0，所以需要特判。

多测不清空，亲人两行泪。

#include<bits/stdc++.h>
using namespace std;
string s;
int sum1,sum2,len,z=1,num,t;
double ans;
bool f; 
int main(){
    cin>>t; 
    while(t--){
        cin>>s;
        len=s.size();
        s=" "+s;
        int k=s.find('=');
        for(;;z++){
            if(z==k) break;
            //cout<<sum1<<" "<<sum2<<" "<<num<<" "<<s[z]<<endl;;
            if(s[z]=='x'){
                f=1;
                if(!('0'<=s[z-1]&&s[z-1]<='9')){
                    num+=1;
                }
            }
            else if(s[z]=='+'){
                if(f){
                    sum1+=num;
                }
                else{
                    sum2-=num;
                }
                f=0;
                num=0;
            }
            else{
                num*=10;
                num+=(s[z]-'0');
            }
        }
        if(f){
            sum1+=num;
        }
        else{
            sum2-=num;
        }
        f=0;
        num=0;
        z++;
        for(;;z++){
            //cout<<z;
            if(z>len) break;
            //cout<<sum1<<" "<<sum2<<" "<<num<<" "<<s[z]<<endl;;
            if(s[z]=='x'){
                if(!('0'<=s[z-1]&&s[z-1]<='9')){
                    num+=1;
                }
                f=1;
            }
            else if(s[z]=='+'){
                if(f){
                    sum1-=num;
                }
                else{
                    sum2+=num;
                }
                f=0;
                num=0;
            }
            else{
                num*=10;
                num+=(s[z]-'0');
            }
        }
        if(f){
            sum1-=num;
        }
        else{
            sum2+=num;
        }
        f=0;
        num=0;
        ans=sum2*1.0/sum1*1.0;
        if((ans<0.1&&ans>=0)||(ans>-0.1&&ans<=0)) cout<<"0.0"<<endl;
        else printf("%.1lf\n",ans); 
        sum1=0;
        sum2=0;
        z=1;
    }
    return 0;
}

棋盘

手玩一下容易发现把所有偶数行全部反转就会让棋盘所有相同奇偶性的列变为同色（反转列同理）。

于是再反转一次颜色不同（即偶数）的列或行即可。

#include<bits/stdc++.h>
using namespace std;
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    printf("%d\n",n/2+m/2);
    for(int i=2;i<=n;i+=2){
        printf("%d %d %d %d\n",i,1,i,m);
    }
    for(int i=2;i<=m;i+=2){
        printf("%d %d %d %d\n",1,i,n,i);
    }
    return 0;
}

魔法楼

首先，我们可以一边 dfs 预处理出每个节点到根节点的异或路径（设为s）。

因为异或的性质，重复的部分会消掉（就是提示里面的 x \bigoplus x =0），所以每次询问时直接回答 s_x \bigoplus s_y 即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e6+10;
struct edge{
    int e,v;
};
int s[N],n,cnt,q;
vector<edge> vec[N];
void dfs(int x,int fa){
    for(int i=0;i<vec[x].size();i++){
        int nx=vec[x][i].e;
        if(nx!=fa){
            s[nx]=s[x]^vec[x][i].v;
            dfs(nx,x);
        }
    }
}
int main(){
    cin>>n>>q;
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        vec[u].push_back((edge){v,w});
        vec[v].push_back((edge){u,w});
    }dfs(1,-1);
    while(q--){
        int x,y;
        cin>>x>>y;
        cout<<(s[x]^s[y])<<endl;
    }
    return 0;
}

这里也给出 bfs 版本：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e6+10;
struct edge{
    int e,v;
};
struct node{
    int e,v,fa;
};
int s[N],n,cnt,Q;
vector<edge> vec[N];
queue<node> q;
void bfs(int x){
    q.push((node){x,0,-1});
    while(!q.empty()){
        int t1=q.front().e,t2=q.front().v,t3=q.front().fa;
        q.pop();
        for(int i=0;i<vec[t1].size();i++){
            int nxt=vec[t1][i].e,w=vec[t1][i].v;
            if(nxt!=t3){
                s[nxt]=t2^w;
                q.push((node){nxt,t2^w,t1});
            }
        }
    }
}
int main(){
    cin>>n>>Q;
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        vec[u].push_back((edge){v,w});
        vec[v].push_back((edge){u,w});
    }
    bfs(1);
    while(Q--){
        int x,y;
        cin>>x>>y;
        cout<<(s[x]^s[y])<<endl;
    }
    return 0;
}

果汁

首先，答案有两种可能：

• 答案不经过 1-n 的分界点。将序列从 1-n 的分界点切开，此时答案就是这个序列的最大子段和。

• 答案经过 1-n 的分界点。此时答案就是序列的和减去这个序列的最小子段和。假设如果可以再取一个数使得答案更优，那么从最小子段和中去掉这个数，和会更小，这个子段就不是最小子段和，与前面矛盾。

把这两种情况取 max 即可。