西安邮电大学第五届ACM-ICPC校赛（同步赛） 题解
一.总结
懵了，全都不会，应该都不是正解，全是黑科技操作。
二.题解
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;
}
哔哩哔哩公司氛围 89人发布