一.总结

懵了,全都不会,应该都不是正解,全是黑科技操作。

二.题解

A.拯救咕咕咕之史莱姆

正解的话应该是根据题目模拟计算第 6 天的 hp。
我的话直接观察样例,发现 73 可以但是 77不可以
故说明答案的分界线就在 74~76之间,最多 wa 3次就可以A,故从76开始,没想到一发就A了。

代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;
const int N=2e3+5;
const int mod=1e9+7;

int main(){
    ll p; 
    while(cin>>p&&p){
        if(p>76) cout<<"DAAAAAMN!"<<endl;
        else cout<<"AOLIGEI!"<<endl;
    }
    return 0;
}

B.烦人的依赖

明显拓扑排序模板题?
只不过需要先处理一下字符串,用个 map 来把字符串映射成数字
然后排序和用优先队列来保证字典序最小
中间用个 cnt 来记录进入队列的点数,如果小于 n 则说明有环存在,输出不可能

代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define mod 1e9+7
#define mo 998244353
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=3e4+5;
const int N=8e3+5;

map<string,ll>s1;
ll d[manx];
string s[manx];
vector<ll>ans,g[manx];
priority_queue<ll,vector<ll>,greater<ll>>q;

int main(){
    ios::sync_with_stdio(false);
    ll p; cin>>p;
    ll sb=0;  
    while(p--){
        cout<<"Case #"<<++sb<<":"<<endl;
        ll n,m; cin>>n>>m;
        for(int i=1;i<=n;i++) g[i].clear(),d[i]=0;  s1.clear(); ans.clear();
        for(int i=1;i<=n;i++) cin>>s[i];
        sort(s+1,s+1+n);
        for(int i=1;i<=n;i++) s1[s[i]]=i;//,cout<<s[i]<<endl;
        for(int i=1;i<=m;i++){
            string u,v; cin>>u>>v;
            d[s1[v]]++;
            g[s1[u]].pb(s1[v]);
        }
        while(q.size()) q.pop();
        ll cnt=0;
        for(int i=1;i<=n;i++){
            if(d[i]==0) q.push(i),++cnt;
        }
        while(q.size()){
            ll u=q.top(); ans.pb(u); q.pop();
            for(auto v: g[u]){
                d[v]--;
                if(d[v]==0) q.push(v),++cnt;
            }
        }
        if(n>cnt){
            cout<<"Impossible"<<endl;
            continue;
        }
        for(auto x:ans){
            cout<<s[x]<<endl;
        }
    }
    return 0;
}

C.异或生成树

树形Dp,没做出来还是有点不开心。
考虑 维护以 i 为根的子树能否组成 j 。
DFS 的时候,考虑 u 为当前结点 , v 为子结点,则有:

dp[ u ][ i ^ j ] = dp[ u ][ i ] && dp[ v ][ j ]

这里的 i 和 j 是可能取到的值,所以需要枚举 1 ~ 127 。

代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define mod 1e9+7
#define mo 998244353
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;
const int N=8e3+5;

bool dp[300][300],a[300];
ll col[300];
vector<ll>g[300];


void dfs(ll u,ll pre){
    dp[u][col[u]]=1;
    for(auto v: g[u]){
        if(v==pre) continue;
        dfs(v,u);
        for(int i=0;i<=127;i++) a[i]=dp[u][i];
        for(int i=0;i<=127;i++)
            for(int j=0;j<=127;j++)
                if(a[i]&&dp[v][j])
                    dp[u][i^j]=1;
    }
}

int main(){
    ll n; cin>>n;
    for(int i=1;i<=n;i++) cin>>col[i];
    for(int i=1;i<n;i++){
        ll u,v; cin>>u>>v;
        g[u].pb(v); g[v].pb(u);
    }
    dfs(1,0);
    ll ans=0;
    for(int i=1;i<=n;i++)
        for(ll j=1;j<=127;j++)
            if(dp[i][j]) ans=max(ans,j);
    cout<<ans<<endl;
    return 0;
}

E.无敌阿姨

根据题意模拟,注意减去被单后还要注意体力是否大于 k 。

代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define mod 1e9+7
#define mo 998244353
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=3e4+5;
const int N=8e3+5;

vector<ll>g[manx];
ll a[manx];

int main(){
    ios::sync_with_stdio(false);
    ll p;  cin>>p;
    while(p--){
        ll n,m,i=1,k,ans=0; cin>>n>>m>>k;
        for(int i=1;i<=n;i++) cin>>a[i];
        while(i<=n){
            ans++;
            ll x=m;
            while(x){
                if(x<a[i]) a[i]-=x,x=0;
                else {
                    x-=a[i];
                    if(x>k) x-=k,i++;
                    else x=0,i++;
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

G.校车

很明显离散化。
离散化后剩余的站点就是答案。
然后差分,差分累加的过程取 max ,就是第二个答案。

代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define mod 1e9+7
#define mo 998244353
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;
const int N=8e3+5;


ll l[manx],r[manx],h[manx],s[manx];

int main(){
    ll p; cin>>p;
    while(p--){
        ll n,k=0; cin>>n;
        for(int i=1;i<=n;i++) cin>>l[i]>>r[i],h[++k]=l[i],h[++k]=r[i];
        sort(h+1,h+1+k);
        ll sb=unique(h+1,h+1+k)-h-1;
        k=sb;
        for(int i=1;i<=n;i++)
            l[i]=lower_bound(h+1,h+1+k,l[i])-h,
            r[i]=lower_bound(h+1,h+1+k,r[i])-h;
        for(int i=1;i<=k;i++) s[i]=0;
        for(int i=1;i<=n;i++)
            s[l[i]]++,s[r[i]]--;
        ll ans=0;
        for(int i=1;i<=k;i++){
            s[i]+=s[i-1];
            ans=max(ans,s[i]);
         //   cout<<i<<" "<<s[i]<<" "<<ans<<endl;
        }
        cout<<k<<" "<<ans<<endl;
    }
    return 0;
}

H.中位因数

太菜了。
第一次知道筛法的复杂度为 O(nlogn)。
知道筛法就可以很快做出来了。
用数组 a 来标记 每个数的因子个数。
第二次用数组 b 来标记 每个数的因子个数,当 i 为 j 的整除因子的中位数时就存入 dp 数组。
最后累加取模即可。

代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define mod 1000000007
#define mo 998244353
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;
const int N=8e3+5;


ll a[manx],b[manx],dp[manx];

int main(){
    for(int i=1;i<=1e6;i++)
        for(int j=i;j<=1e6;j+=i)
            a[j]++;
    for(int i=1;i<=1e6;i++)
        for(int j=i;j<=1e6;j+=i){
            b[j]++;
            if((a[j]+1)/2==b[j]) dp[j]=(i+j/i)/2;
        }
    for(int i=1;i<=1e6;i++) dp[i]+=dp[i-1],dp[i]%=mod;
    ll p; cin>>p;
    while(p--){
        ll n; cin>>n; cout<<dp[n]<<endl;
    }
    return 0;
}