训练记录番外篇（3）：2019-2020 ICPC Southeastern European Regional Programming Contest (SEERC 2019)

2019-2020 ICPC Southeastern European Regional Programming Contest (SEERC 2019)


6题961罚时，按照国外444的牌数看来是打铁了。
最后1h其实已经把AE两题思路都出来了，但是队友最终都没有vp的时候写完，可惜了。

A. Max or Min

代码不在我手上，如果队友之后发我再补。
思路是把所有数考虑成-1，0，1，可以把答案转换成一个求环上所有交替的-1，1序列长度/2向上取整的方案数。考虑线段树维护单点修改和区间合并，分类讨论一下环上的情况即可。

B. Level Up

队友单切，一个看不懂的dp。

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e3 + 10, MOD = 1e9 + 7;
int dp[N][N];
struct node 
{
    int x,t,y,r;
    bool operator < (const node &b) const 
    {
        return x<b.x;
    }
}e[N];
inline void solve(){
    int n, s1, s2; cin >> n >> s1 >> s2;
    for(int i=1;i<=n;i++)
    {
        cin>>e[i].x>>e[i].t>>e[i].y>>e[i].r;
    }
    for(int i=0;i<=2000;i++)
    {
        for(int j=0;j<=2000;j++) dp[i][j]=1e18;
    }
    sort(e+1,e+1+n);
    dp[0][0]=0;
    int ans=1e18;
    for(int k=1;k<=n;k++)
    {
        int x=e[k].x, t=e[k].t, y=e[k].y, r=e[k].r;
        for(int i=s1+x-1;i>=0;i--)
        {
            for(int j=s2+y-1;j>=0;j--)
            {
                if(i>=x) dp[i][j]=min(dp[i][j],dp[i-x][j]+t);
                if(j>=y) dp[i][j]=min(dp[i][j],dp[i][j-y]+r);
                if(i>=s1 && i-s1+j>=s2) ans=min(dp[i][j],ans);
            }
        }
    }
    if(ans==1e18) cout<<"-1\n";
    else cout<<ans<<"\n";
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}

D. Cycle String?

分类讨论题。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e3 + 10;

int cnt[305];
#define yes cout << "YES\n"
#define no cout << "NO\n"
bool cmp(char x,char y){
    return cnt[x]>cnt[y]||cnt[x]==cnt[y]&&x<y;
}
inline void solve(){
    string s; cin >> s;
    int n = s.size() / 2;
    for(auto ch : s) cnt[ch]++;
    if(n==1){
        if(s[0]==s[1]){
            no;
        }
        else{
            yes;
            cout<<s;
        }
        return;
    }
    sort(s.begin(),s.end(),cmp);
    if(n==2){
        if(s[2]==s[0])no;
        else{
            yes;
            cout<<s;
        }
        return;
    }
    
    if(s.back()==s[0]||s[2*n-2]==s[0]||s[2*n-2]==s.back()&&cnt[s[0]]==2*n-2){//2n-1个
        no;return;
    }

    if(s[n-1]==s[0]){
        swap(s[n-1],s[2*n-1]);
    }
    yes;
    cout<<s;
}   

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}

E. Life Transfer

情况同A，考虑贪心，一开始假设所有人都骑车，枚举开车人数，每次开车的人和坐车的人是确定的。模拟即可。代码如果队友发我了再补。

F. Game on a Tree

一个博弈题，队友秒出。但是我一开始读错了以为结论错的。本来可以更早交的。

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;

vector<int> g[N];

int dp[N];

void dfs(int u, int fa) {
    for(auto v : g[u]) {
        if(v == fa) continue;
        dfs(v, u);
        dp[u] += dp[v];
    }
    if(!dp[u]) dp[u]++;
    else dp[u]--;
}

inline void solve(){
    int n = 0; cin >> n;
    for(int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    dfs(1, 0);
    if(dp[1]) cout << "Alice\n";
    else cout << "Bob\n";
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}

G. Projection

模拟题。

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;
int vis[105][105][105];
int n,m,h;
int vis1[105][105],vis2[105][105];
string s;
vector<int>ansx[105],ansy[105];
struct node{
    int x,y,z;
    bool operator<(const node &t)const {
        return x<t.x||x==t.x&&y<t.y||x==t.x&&y==t.y&&z<t.z;
    }
};
vector<node>ans;
inline void solve(){
    cin >> n >> m >> h;
    for(int i=0;i<n;i++){
        cin>>s;
        for(int j=0;j<m;j++){
            if(s[j]=='1'){
                vis1[i][j]=1;
                for(int k=0;k<h;k++){
                    vis[i][j][k]++;
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        cin>>s;
        for(int j=0;j<h;j++){
            if(s[j]=='1'){
                vis2[i][j]=1;
                for(int k=0;k<m;k++){
                    vis[i][k][j]++;
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(vis1[i][j]){
                int fg=0;
                for(int k=0;k<h;k++){
                    if(vis[i][j][k]==2){fg=1;break;}
                }
                if(!fg){
                    cout<<-1;
                    return;
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<h;j++){
            if(vis2[i][j]){
                int fg=0;
                for(int k=0;k<m;k++){
                    if(vis[i][k][j]==2){fg=1;break;}
                }
                if(!fg){
                    cout<<-1;
                    return;
                }
            }
        }
    }
    int ansmx=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            for(int k=0;k<h;k++){
                if(vis[i][j][k]==2)ansmx++;
            }
        }
    }
    cout<<ansmx<<endl;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            for(int k=0;k<h;k++){
                if(vis[i][j][k]==2){
                    cout<<i<<" "<<j<<" "<<k<<endl;
                }
            }
        }
    }
    int ansmn=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(vis1[i][j]){
                ansx[i].push_back(j);
            }
        }
        for(int j=0;j<h;j++){
            if(vis2[i][j]){
                ansy[i].push_back(j);
            }
        }
        while(ansx[i].size()<ansy[i].size()){
            ansx[i].push_back(*ansx[i].begin());
        }
        while(ansx[i].size()>ansy[i].size()){
            ansy[i].push_back(*ansy[i].begin());
        }
        sort(ansx[i].begin(),ansx[i].end());
        sort(ansy[i].begin(),ansy[i].end());
        for(int j=0;j<ansx[i].size();j++){
            ans.push_back({i,ansx[i][j],ansy[i][j]});
        }
        ansx[i].clear();
        ansy[i].clear();
    }
    cout<<ans.size()<<endl;
    for(auto [x,y,z]:ans){
        cout<<x<<" "<<y<<" "<<z<<endl;
    }
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}

I. Absolute Game

签到。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e3 + 10;
int a[N], b[N];

inline void solve(){
    int n = 0; cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int mn=1e18;
        for(int j=1;j<=n;j++)
        {
            mn=min(abs(a[i]-b[j]),mn);
        }
        ans=max(ans,mn);
    }
    cout<<ans<<"\n";
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}

J. Graph and Cycles

考虑每个点在回路中一定存在相同的出度和入度，所以贪心即可。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10;
int a[N], vis[N];
int n;
vector<int>p[2005];
inline void solve(){
    cin>>n;
    for(int i=1;i<=n*(n-1)/2;i++){
        int u,v,w;cin>>u>>v>>w;
        p[u].push_back(w);
        p[v].push_back(w);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        sort(p[i].begin(),p[i].end());
        for(int j=0;j<p[i].size();j+=2){
            ans+=p[i][j+1];
        }
    }
    cout<<ans;
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}