2021-2022 ICPC, NERC, Northern Eurasia Onsite C,D,L题解

题目链接 https://codeforces.com/contest/1666

C Connect the Points

题意

给出三个点，找任意条平行x轴或y轴线段，使得线经过3个点，且线段长度和最小。

思路

手玩可以发现，线段和最长可以不超过3点x坐标最大差值加上3点y坐标最大差值，所以我们可以找到y坐标第二大的点，过它作一条从x最小值到x最大值的平行x轴线段，然后从另外两个点作到这个线段的垂线即可。

Accepted code

#include <bits/stdc++.h>
using namespace std;

struct node {
    int x, y;
} a[3];

bool cmp(node a, node b) { return a.y < b.y; }

int main() {
    int lx = 1000000000 + 7, rx = -1;
    for (int i = 0; i < 3; i++) {
        cin >> a[i].x >> a[i].y;
        lx = min(lx, a[i].x);
        rx = max(rx, a[i].x);
    }
    sort(a, a + 3, cmp);
    int num = 0;
    for (int i = 0, b = -1; i < 3; i++) {
        if (a[i].y != b) ++num;
        b = a[i].y;
    }
    cout << num << '\n';
    cout << lx << ' ' << a[1].y << ' ' << rx << ' ' << a[1].y << '\n';
    if (a[0].y != a[1].y)
        cout << a[0].x << ' ' << a[0].y << ' ' << a[0].x << ' ' << a[1].y
             << '\n';
    if (a[2].y != a[1].y)
        cout << a[2].x << ' ' << a[2].y << ' ' << a[2].x << ' ' << a[1].y
             << '\n';
    return 0;
}

D Deletive Editing

题意

给两个字符串s和t，可以进行多次以下操作：

• 选择一种字符，删除s串中这种字符（从左到右）第一次出现的那一个。

问s串是否可以变成t串。

思路

s串从右往左匹配t串，寻找最右匹配序列，然后从左往右模拟删除其余字符，能得到t串就YES，否则NO

Accepted code

#include <bits/stdc++.h>
using namespace std;

int n;
string s, t;
int vis[35];
map<char, int> mp;

int main() {
    cin >> n;
    for (int ii = 0; ii < n; ii++) {
        mp.clear();
        memset(vis, 0, sizeof(vis));
        cin >> s >> t;
        int flag = 1;
        for (int i = s.size() - 1, idx = t.size() - 1; i >= 0; i--) {
            if (idx < 0) break;
            if (s[i] == t[idx]) {
                vis[i] = 1;
                idx--;
            }
            if (i == 0) {
                if (idx >= 0) flag = 0;
            }
        }
        if (!flag) {
            cout << "NO\n";
            continue;
        }
        for (int i = 0; i < s.size(); i++) {
            if (vis[i]) {
                ++mp[s[i]];
            } else {
                if (mp[s[i]] > 0) {
                    flag = 0;
                    break;
                }
            }
        }
        if (flag) {
            cout << "YES\n";
        } else
            cout << "NO\n";
    }
    return 0;
}

L Labyrinth

题意

给出一个有向图，给定起点，要求找到一个终点，可以通过走两条完全不同的路径从起点走到终点（指除了起点和终点外，两条路径不能有相同的点），并求出两条路径。

思路

对于起点的不同出边所dfs到的点标上不同的vis标记，当一条出边dfs到令一条出边所搜到的节点，则该节点可以作为合法终点。

对于第一条路径，我们可以在回溯时就将路径上的节点push进栈中，令一条路径可以在vis标记与终点相同的节点中再一次搜索得到。

Accepted code

#include <bits/stdc++.h>
#include <algorithm>
using namespace std ;

#define endl '\n'
#pragma GCC optimize(2)
typedef long long ll ;
const int maxn = 2e5+100 ;
const int mod = 1e9+7 ;

int n , m , s,t = -1 ;
vector <int> edge[maxn] ;
int vis[maxn] ;
int vis1[maxn];
int cnt=0,flag=0;
stack<int>route;
void dfs(int x){
    //cout<<x<<' '<<cnt<<'\n';
    if(x==s) vis[x]=1;
    else vis[x]=cnt;
    for(auto v:edge[x]){
        if(x==s) ++cnt;
        if(flag)return;
        if(vis[v]){
            if(vis[v]==cnt||v==s) continue; // 同时特判环到起点的情况
            else {
                route.push(v);
                route.push(x);
                flag=1;
                t=v;
                return ;
            }
        }else{
            dfs(v);
            if(flag){
                route.push(x);
                return ;
            }
        }
    }
}
int route1[maxn],flag1=0,len;
void dfs1(int x,int idx){
    route1[idx]=x;
    if(x==t) {
        len=idx;
        flag1=1;
        return ;
    }
    vis1[x]=1;
    for(auto v:edge[x]){
        if(!vis1[v]&&vis[v]==vis[t]){
            dfs1(v,idx+1);
            if(flag1) return ;
        }
    }
}
void solve(){
    cin >> n >> m >> s ;
    while(m--){
        int u , v ;
        cin >> u >> v ;
        edge[u].push_back(v) ;
    }
    dfs(s);
    if(t==-1){
        cout<<"Impossible";
        return ;
    }
    cout<<"Possible\n";
    dfs1(s,0);
    cout<<len+1<<'\n';
    for(int i=0;i<=len;i++){
        cout<<route1[i]<<' ';
    }
    // printf("\n");
    cout<<'\n';
    cout<<route.size()<<'\n';
    while(!route.empty()){
        cout<<route.top()<<' ';
        route.pop();
    }
}
int main() {
    ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
    int t = 1 ;
    //cin >> t ;
    while(t--){
        solve();
    }
    return 0 ;
}