abc305解题报告

· · 个人记录

A

solution

枚举0,5,10,...,100即可

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;cin>>n;
    int ans=0;
    for(int i=0;i<=100;i+=5){
        if(abs(n-i)<abs(n-ans)) ans=i;
    }
    cout<<ans<<endl;
    return 0;
}

B

solution

用常量数组将字符转化为数字

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[]={0,3,4,8,9,14,23};
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    char x,y;cin>>x>>y;
    cout<<abs(a[x-'A']-a[y-'A'])<<endl;
    return 0;
}

C

solution

找出唯一的全#矩形中被挖掉的那个
可以先算出这个矩形的四个边界

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=505;
char a[N][N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int l=1e18,r=-1e18,u=1e18,d=-1e18;
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]=='#'){
                l=min(l,j);
                r=max(r,j);
                u=min(u,i);
                d=max(d,i);
            }
        }
    }
    for(int i=u;i<=d;i++){
        for(int j=l;j<=r;j++){
            if(a[i][j]=='.'){
                cout<<i<<' '<<j<<endl;
                return 0;
            }
        }
    }
    return 0;
}

D

solution

整个时间可以分成n-1段，我们设l在第x段，r在第y段
则答案分三段计算：
1、x+1到y-1，这个可以用稍加讨论的前缀和
2、l到x
3、y到r

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int a[N],sum[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=2;i<=n;i++){
        if(i%2==0) sum[i]=sum[i-1];
        else sum[i]=sum[i-1]+a[i]-a[i-1];
    }
    int q;cin>>q;
    while(q--){
        int l,r;cin>>l>>r;
        int x=lower_bound(a+1,a+n+1,l)-a;
        int y=lower_bound(a+1,a+n+1,r)-a;
        if(l>a[x]) x++;
        if(r<a[y]) y--;
        int ans=sum[y]-sum[x];
        if(x%2==1) ans+=a[x]-l;
        if(y%2==0) ans+=r-a[y];
        cout<<ans<<endl;
        //cout<<x<<' '<<y<<endl;
    }
    return 0;
}

E

solution

我们会先扩展剩余次数多的节点，因此，我们使用优先队列bfs

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+5;
vector<int> G[N];
void addedge(int u,int v){
    G[u].push_back(v);
}
struct node{
    int u,d;
    bool operator<(const node& o)const{
        return d<o.d;
    }
};
priority_queue<node> pq;
int vis[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n,m,k;cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        addedge(u,v);
        addedge(v,u);
    }
    for(int i=1;i<=k;i++){
        int p,h;cin>>p>>h;
        pq.push((node){p,h});
    }
    while(!pq.empty()){
        node t=pq.top();
        pq.pop();
        int u=t.u,d=t.d;
        vis[u]=1;
        if(d==0) continue;
        for(int v:G[u]){
            if(vis[v]) continue;
            vis[v]=1;
            pq.push((node){v,d-1});
        }
    }
    int tot=0;
    for(int i=1;i<=n;i++) if(vis[i]) tot++;
    cout<<tot<<endl;
    for(int i=1;i<=n;i++) if(vis[i]) cout<<i<<' ';
    cout<<endl;
    return 0;
}

F

solution

直接dfs即可，考虑最坏情况，每个点被遍历到两次，次数为2n，满足题意

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,k,pos,path[105];
vector<int> v[105];
bool on[105];
void explore(int x){
    cout<<x<<endl;
    if(x==n) exit(0);
}
void read(int x){
    cin>>k;
    on[x]=1,v[x].resize(k);
    for(int i=0;i<v[x].size();i++) cin>>v[x][i];
    for(int i:v[x]) if(!on[i]){
        path[i]=x;pos=i;
        return;
    }
    pos=path[x];
}
signed main(){
    cin>>n>>m;
    pos=1;
    while(1) read(pos),explore(pos);
    return 0;
}

G

我不会矩阵加速，看以后会不会写

H

这玩意就是fyc都不会做吧