西安邮电大学第五届ACM-ICPC校赛（同步赛）

A.拯救咕咕咕之史莱姆

Solution

按题意来，手算：

1. DAAAAAMN!
2. AOLIGEI!

   Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e6 + 5;

ll n;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin>>n&&n){
        if(n>75) cout<<"DAAAAAMN!\n";
        else cout<<"AOLIGEI!\n";
    }
    return 0;
}

B.烦人的依赖

Solution

sort+映射+优先队列拓扑排序
拓扑排序模板题。
和普通的拓扑排序不同的点在于，这里给出的string，且字典序小的具有优先级。
优先级？嗯哼想到了什么？我们的老朋友优先队列！

1. 这里需要预处理字符串的时候，先进字符串进行排序，再用unordered_map对其进行映射。
2. 利用映射之后的值（数字）对其进行拓扑排序，普通的拓扑序用queue即可，而这道题目有个字典序小的优先的要求，所以我们要用priority_queue（优先队列）去拓扑。
3. 若成环则"Impossible!"；
   输出拓扑序。

tips:多组数据注意初始化(补题WA了一发

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 3e4 + 5;

int n,m;
string s[N];
vector<int> G[N];
unordered_map<string,int> id;
int in[N],a[N],cnt;

void topsort(){
    priority_queue<int>q;
    for(int i=1;i<=n;i++) if(!in[i]) q.push(i);
    while(q.size()){
        int p=q.top();q.pop();
        a[++cnt]=p;
        for(auto c:G[p]) if(!--in[c]) q.push(c);
    }
}

void solve(int x){
    cin>>n>>m;
    id.clear();
    cnt=0;
    for(int i=1;i<=n;i++) G[i].clear(),in[i]=0;
    for(int i=1;i<=n;i++) cin>>s[i];
    sort(s+1,s+1+n,greater<string>());
    for(int i=1;i<=n;i++) id[s[i]]=i;
    for(int i=1;i<=m;i++){
        string u,v;
        cin>>u>>v;
        ++in[id[v]];
        G[id[u]].push_back(id[v]);
    }
    topsort();
    cout<<"Case #"<<x<<":"<<'\n';
    if(cnt!=n) cout<<"Impossible\n";
    else{
        for(int i=1;i<=n;i++) cout<<s[a[i]]<<'\n';
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    for(int i=1;i<=T;i++) solve(i);
    return 0;
}

C.异或生成树

Solution

树形DP
设表示以为根能否组成。

1. 用临时变量保存
2. 更新
3. 更新答案

   Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 2e2 + 5;

int n,a[N],ans;
bool f[N][N];
bool s[N];
vector<int> G[N];

void dfs(int x,int fa){
    f[x][a[x]]=true;
    for(auto c:G[x]){
        if(c==fa) continue;
        dfs(c,x);
        memset(s,false,sizeof(s));
        for(int i=0;i<=127;i++)
            for(int j=0;j<=127;j++)
                s[i^j]|=f[x][i]&&f[c][j];
        for(int i=0;i<=127;i++)
            f[x][i]|=s[i];
    }
    for(int i=1;i<=127;i++)
        if(f[x][i]) ans=max(ans,i);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    cout<<ans;
    return 0;
}

E.无敌阿姨

Solution

纯模拟

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e2 + 5;

int n,m,k,a[N];

void solve(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    int hp=m;
    int ans=1;
    for(int i=1;i<=n;){
        if(hp>a[i]){
            hp-=a[i];
            a[i]=0;
            if(hp<=k && i<n) hp=m,ans++;
            if(hp<m && hp>k && i<n) hp-=k;
            i++;
        }else if(hp<a[i]){
            a[i]-=hp;
            hp=m;
            ans++;
        }else{
            a[i]-=hp;
            hp=m;
            if(a[n]!=0) ans++;
            i++;
        }
        if(a[n]==0) break;
    }
    cout<<ans<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--) solve();
    return 0;
}

G.校车

Solution

利用set唯一性记录站点数量
利用差分纪录最大座位数量
由于我是直接遍历set，所以不需要离散化。

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e5 + 5;

int n;

void solve(){
    cin>>n;
    set<int>s;
    unordered_map<int,int> M;
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        M[x]++;M[y]--;
        s.insert(x);
        s.insert(y);
    }
    int ans=1;
    int tmp=0;
    for(auto c:s){
        M[c]+=tmp;
        ans=max(ans,M[c]);
        tmp=M[c];
    }
    cout<<s.size()<<" "<<ans<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

H.中位数

Solution

这道题就是先求出，再算个前缀和预处理，没次输出答案即可。
问题在于如何求出？

1. 的因子一定成对分布在的左右两侧
2. 的中位数因子，一定
3. 我们记录最大的的中位数因子在中，后续
4. 求前缀和记录答案

   Code

#include <iostream>
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e6 + 5;

ll pre[N],f[N];

void init(){
    ll cnt=0;
    for(int i=1;i<N;i++)
        for(int j=i;j<N;j+=i){
            if(1ll*i*i<=j) f[j]=i;
        }
    for(int i=1;i<N;i++) f[i]=(f[i]+i/f[i])/2;
    for(int i=1;i<N;i++) pre[i]=(pre[i-1]+f[i])%mod;
}

void solve(){
    ll x;
    cin>>x;
    cout<<pre[x]<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    init();
    while(T--) solve();
    return 0;
}

体验

感觉参赛体验挺差的，D题应该没那么简单，但是一开始却看大家n^2做法暴力随便过，我一直在思考nlogn的写法，也没思考出什么结果，后来重判都WA了。歪榜浪费了不少时间，然后G题很简单的差分题，然后第一遍就AC的，由于他数据错了，怎么改都是WA，又浪费了不少时间，这也是由于我自己经验不足吧，心态也有点崩，大家都过了E，然后我G也不知道WA到哪儿，然后写E的时候很菜的WA了7发才过，有一行代码上下顺序不对。
怎么说呢，这些杂七杂八的因素不应该成为对自己的干扰，还是要保持冷静、理智的头脑去解题吧。