HZOJ
写在前面
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh T1几分钟出思路然后在写假的道路上越改越远,T2来不及了乱写,T3猜不到结论,只有T4是合理得分、、、
A. median
题意是给定5个长为\(n\) 的序列,求问这五个序列所有组合中的中位数和是多少。
赛时代码思路大概对,然后死在了容斥。然后正解做法就是将所有数以大小为第一关键字,所在序列为第二关键字排序,计算每个序列在总序列中的前后缀。然后对于每个位置,就是在除开其所在序列的其他序列选两个小于它,选两个大于它,规定这四个序列的大小关系,就能避免容斥。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10,mod=998244353;
int n;
struct node{int type,v;
}k[maxn*5];
inline bool cmp(node aa,node bb){if(aa.v!=bb.v) return aa.v<bb.v;return aa.type<bb.type;
}
int pre[6][maxn*5],suf[6][maxn*5];
int main(){
// freopen("ex_data2.in","r",stdin);freopen("median.in","r",stdin);freopen("median.out","w",stdout);ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++) cin>>k[i].v,k[i].type=1;for(int i=1;i<=n;i++) cin>>k[i+n].v,k[i+n].type=2;for(int i=1;i<=n;i++) cin>>k[i+2*n].v,k[i+2*n].type=3;for(int i=1;i<=n;i++) cin>>k[i+3*n].v,k[i+3*n].type=4;for(int i=1;i<=n;i++) cin>>k[i+4*n].v,k[i+4*n].type=5;sort(k+1,k+5*n+1,cmp);for(int i=1;i<=5*n;i++){for(int j=1;j<=5;j++) pre[j][i]=pre[j][i-1];pre[k[i].type][i]++;}for(int i=5*n;i>=1;i--){for(int j=1;j<=5;j++) suf[j][i]=suf[j][i+1];suf[k[i].type][i]++;}int ans=0;for(int i=1;i<=5*n;i++){for(int a=1;a<=5;a++){if(a==k[i].type) continue;for(int b=a+1;b<=5;b++){if(b==k[i].type||b==a) continue;for(int c=1;c<=5;c++){if(c==k[i].type||c==a||c==b) continue;for(int d=c+1;d<=5;d++){if(d==k[i].type||d==a||d==b||d==c) continue;ans=(ans+1ll*k[i].v*suf[a][i]%mod*suf[b][i]%mod*pre[c][i]%mod*pre[d][i]%mod)%mod;}}}} }cout<<ans;return 0;
}
B. travel
题意是给定一张不保证没有自环或重边的图,求问是否存在一对起点到终点,不存在一个阈值,使得经过超过这个阈值的步数从起点到终点的路径数相同。
赛时输出“YES”跳了,然而不仅给配了spj,所有测了的点还没一个对的。先考虑一些一定存在符合条件点对的条件:
1.拥有两个及以上自环的点:随着步数增大,方案数将趋近正无穷,因为每步都可以选择任意一个自环。
2.存在一对都有自环的点且这对点间存在路径:类似于1,就是步数增大时,可以选择任意一个自环走若干步。
3.存在一个多元环:如一个二元环。以起点为终点,则步数是2的倍数时方案数为1,反之则为0。
因为自环可以输入的时候判掉,然后这题剩下的情况就转化为了判2、3。可以直接拓扑排序,队里记录两个值,一个是是否经过了一个有自环的点,一个是点是否被访问过。若当前点有自环且当前路径已经经过了有自环的点,则符合2可以判掉。如果队列为空但是还有点没被遍历到,说明存在环,可以判掉3.剩下的情况就是存在阈值的情况了。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
int n,m,selfc[maxn],du[maxn],sum;
vector<int> e[maxn];
bool vis[maxn];
queue<pair<int,bool>> q;
int main(){
// freopen("ex_data3.in","r",stdin);freopen("travel.in","r",stdin);freopen("travel.out","w",stdout);ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1,u,v;i<=m;i++){cin>>u>>v;if(u==v){if(selfc[u]) cout<<"Yes",exit(0);selfc[u]++;}else e[u].emplace_back(v),++du[v];}for(int i=1;i<=n;i++)if(!du[i]) q.push({i,selfc[i]});if(q.empty()) cout<<"Yes",exit(0);while(q.size()){pair<int,bool> k=q.front();q.pop();++sum;for(auto y:e[k.first]){if(k.second&&selfc[y]) cout<<"Yes",exit(0);du[y]--;if(!du[y]) q.push({y,k.first||selfc[y]});}}if(sum!=n) cout<<"Yes";else cout<<"No";return 0;
}
C. game
结论题。。。题意是两个人玩游戏,规则是每次操作可以选择一堆石头,选择其数量范围内的至少1个石头拿走,选择其剩余范围内至少0个石头任意分配到其他堆里,第一个无法操作者败。求问给定初始石头状态是否存在先手必胜的情况。
我无语了。反正规律赛时是找不到的。首先可以显然知道当只有两堆时先手必败的石头分布情况:1 1。继续推广到a a。那我们的问题就转化为了初始状态能否转化为后手必败的情况。当只有1堆,先手必赢;当只有两堆且两堆数目不同,可以通过操作将两堆数量变为相同的,进而使得后手必败;当只有3堆时,可以操作减少一堆且使得剩下的两堆数量相等;当只有4堆时,如果所有堆数都能两两配对,则无论先手怎么操作,后手都能保证剩下的堆两两配对,直至剩下2堆相等的石头,但是如果不能两两配对,先手就可以操作将石头配对,使得后手必败。然后大概就能猜出结论:只有当堆数为偶数且数量能两两配对时先手才会输。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int n,a[maxn];
unordered_map<int,int> mp;
int main(){
// freopen("ex_data2.in","r",stdin);freopen("game.in","r",stdin);freopen("game.out","w",stdout);ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T;cin>>T;for(T=1;T<=10;++T){cin>>n;mp.clear();for(int i=1;i<=n;i++) cin>>a[i],++mp[a[i]]; if(n%2==0){bool yh=0;for(int i=1;i<=n;i++)if(mp[a[i]]&1){yh=1;break;}if(!yh){cout<<"No\n";continue;} }cout<<"Yes\n";}return 0;
}
D. counter
题意大概是给出两个数,一个起点一个终点。每个数可以到达其加减十进制下的各位的数的数,求问从起点出发能否到达终点,如果能,最小步数是多少。
赛时想着建张图进行些乱七八糟的操作,还好假性质推翻得及时老老实实写暴力去了。
每个数能到达的数没有必然的规律,从每个数出发经过的路径也不具有单调性,所以从起点到终点的最短路径在值域上可能会越过终点。但是不可能超出很远,所以可以设定一个阈值,在起点到终点的值域+-该阈值的范围内讨论。注意到十进制下最大数是9,那么对于一个长度为9的区间,从其左端的区间到其右端的区间必然会经过当前区间。题解做法是log的分治。但是我比较喜欢暴力数据结构(其实是不会分治),所以我选择用分块(?),虽然复杂度有差距,但是能过就行,而且其中的思想是相似的。经过计算,暴力bfs查找在数据范围内能承受的最大区间长度是3600,所以我们可以每隔3600的距离撒9个点,预处理数据范围内所有点到这些点的距离和这些点到所有点的距离。对于距离小于3600的点,我们暴力bfs。对于距离大于3600的点,我们可以枚举作为中转点的撒的点,经过一些调整理论可以\(O(1)\) 求。由于STl清空队列太慢,只能利用评测机波动AC,所以可以手写队列。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+300,B=3600,inf=0x3f3f3f3f;
int dis[2][27][9][maxn],bl[maxn];
int dist[maxn];
vector<int> e[maxn];
struct que{int q[maxn],ft,bk;inline void clear(){ft=1,bk=0; } inline void push(int x){q[++bk]=x;}inline bool empty(){return ft>bk;}inline int front(){return q[ft];}inline void pop(){++ft;}
}q;
int main(){
// freopen("ex_data2.in","r",stdin);freopen("counter.in","r",stdin);freopen("counter.out","w",stdout);ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);for(int i=1;i<1e5+200;i++){int v=i;while(v){if(v%10){if(i+v%10<1e5+200) e[i+v%10].emplace_back(i);if(i-v%10>=0) e[i-v%10].emplace_back(i);}v/=10;}}q.clear();for(int i=0;i<=26;i++){for(int j=0;j<=8;j++){q.clear();q.push((i+1)*3600+j+1);dis[0][i][j][q.front()]=1;while(!q.empty()){int u=q.front(),v=u;q.pop();while(v){if(u+v%10<1e5+200&&!dis[0][i][j][u+v%10]) dis[0][i][j][u+v%10]=dis[0][i][j][u]+1,q.push(u+v%10); if(u-v%10>=0&&!dis[0][i][j][u-v%10]) dis[0][i][j][u-v%10]=dis[0][i][j][u]+1,q.push(u-v%10); v/=10;}}q.clear();q.push((i+1)*3600+j+1);dis[1][i][j][q.front()]=1;while(!q.empty()){int u=q.front();q.pop();for(auto v:e[u])if(!dis[1][i][j][v]) dis[1][i][j][v]=dis[1][i][j][u]+1,q.push(v);}}}for(int i=0;i<1e5+200;i++) bl[i]=i/3600;int T,lans=0;cin>>T;while(T--){int x,y;cin>>x>>y;x^=lans+1,y^=lans+1;if(x==y){lans=0;cout<<0<<'\n';continue;}if(abs(x-y)>3600){int ans=inf;for(int i=max(min(bl[x],bl[y])-1,0);i<=min(26,max(bl[x],bl[y]+1));i++)for(int j=0;j<=8;j++) if(dis[1][i][j][x]&&dis[0][i][j][y]) ans=min(ans,dis[1][i][j][x]+dis[0][i][j][y]-2);lans=(ans==inf?-1:ans);cout<<lans<<'\n';continue;}q.clear();q.push(x);int up=min(100199,max(x,y)+200),dw=max(0,min(x,y)-200);for(int i=dw;i<=up;i++) dist[i]=inf;dist[x]=0;while(!q.empty()){int u=q.front(),v=u;q.pop();while(v){if(v%10){if(u+v%10<=up&&dist[u+v%10]==inf) dist[u+v%10]=dist[u]+1,q.push(u+v%10); if(u-v%10>=dw&&dist[u-v%10]==inf) dist[u-v%10]=dist[u]+1,q.push(u-v%10); }v/=10;}}lans=(dist[y]==inf?-1:dist[y]);cout<<lans<<'\n';}return 0;
}