Helvetic Coding Contest 2024 online mirror (teams allowed, unrated)（13/21）

心得

感觉这个b1-b3出的还是挺妙的一个构造，e3矩阵快速幂中规中矩吧

a3括号序列树也是不错的idea

题目

A1 - Balanced Shuffle (Easy)

按题意模拟

// Problem: A1. Balanced Shuffle (Easy)A1。平衡随机播放（简单）
// Contest: Codeforces - Helvetic Coding Contest 2024 online mirror (teams allowed, unrated)Helvetic 编码大赛 2024 在线镜像（允许团队，未评级）
// URL: https://codeforces.com/contest/1970/problem/A1
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Time: 2024-05-04 15:47:34#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define ll long long
using namespace std;
typedef vector<int> vint;
typedef pair<int,int> pii;int main() {ios::sync_with_stdio(false);cin.tie(0);string a; cin>>a;int n=a.size();vint pr(n),ind(n);iota(ind.begin(),ind.end(),0);pr[0]=0;for(int i=1;i<n;i++) {pr[i]=pr[i-1]+(a[i-1]=='('?1:-1);}sort(ind.begin(),ind.end(),[&](int i,int j) {if(pr[i]==pr[j]) return i>j;else return pr[i]<pr[j];});for(int i=0;i<n;i++) cout<<a[ind[i]];return 0;
}

A2 - Balanced Unshuffle (Medium)

A3 - Balanced Unshuffle (Hard)

参考一下队友的代码，大概是按栈的顺序逆序递归下去

#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define ll long long
using namespace std;
typedef vector<int> vint;
typedef pair<int,int> pii;int main() {ios::sync_with_stdio(false);cin.tie(0);string a; cin>>a;int n=a.size();vint pd(n,-1),id(n);int now=0,now1=0;for(int i=0;i<n;i++) {if(a[i]==')') now++;if(a[i]=='(') now1++;if(pd[now]==-1) pd[now]=i;id[i]=now1;}function<void(int)> solve=[&](int ind) {cout<<'(';int now=id[ind];int l=pd[now],r=pd[now+1];for(int i=r-1;i>l;i--) solve(i);cout<<')';return;};int beg=0;while(a[beg]=='(') beg++;for(int i=beg-1;i>=0;i--) solve(i);return 0;
}

B1 - Exact Neighbours (Easy)

注意到ai是偶数，n个数里必有两个数相同，

所以可以这两个互相参照，让其他的都参照这两个

#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<vector>
#include<map>
#include<unordered_map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10;
int n,m,a[N],ans[N],x[N],y[N],col[N],b[N],cnt[N];
vector<int>now;
int main(){sci(n);m=(n+1)/2;rep(i,1,n){if(i==m)continue;now.pb(i);}sort(now.begin(),now.end(),[&](int x,int y){return abs(x-m)>abs(y-m);});rep(i,1,n){sci(a[i]);cnt[a[i]]++;b[i]=i;}sort(b+1,b+n+1,[&](int x,int y){if(cnt[a[x]]!=cnt[a[y]])return cnt[a[x]]>cnt[a[y]];return a[x]<a[y];});rep(j,1,n){int i=b[j];//printf("j:%d i:%d\n",j,i);if(j==1)x[i]=m,y[i]=1,ans[i]=i,col[m]=i;else{int v=now.back();now.pop_back();x[i]=v;if(a[i]==0){y[i]=1;ans[i]=i;}else if(abs(v-m)>a[i]){if(v<m){y[i]=a[i]-1+y[col[v+1]];//printf("i:%d y:%d coln:%d\n",i,y[i],col[i+1]);if(y[i]>n)y[i]=y[col[v+1]]-(a[i]-1);ans[i]=col[v+1];}else{y[i]=a[i]-1+y[col[v-1]];//printf("i:%d y:%d\n",i,y[i]);if(y[i]>n)y[i]=y[col[v-1]]-(a[i]-1);ans[i]=col[v-1];} }else{y[i]=a[i]-abs(v-m)+1;ans[i]=b[1];}col[v]=i;}}if(a[b[1]])ans[b[1]]=b[2];//成对puts("YES");rep(i,1,n){printf("%d %d\n",x[i],y[i]);}rep(i,1,n){printf("%d%c",ans[i]," \n"[i==n]);}return 0;
}

B2 - Exact Neighbours (Medium)

注意到a1=0，所以可以把a1放到((n+1)/2,0)的位置，让自己参照自己

让其他的沿这条轴从近到远放，如果曼哈顿距离能达到a1这一列，就参照a1这个位置，

否则参照上一个放的相邻的位置，也就是分a[i]是否超过当前的x轴距离讨论

#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<vector>
#include<map>
#include<unordered_map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10;
int n,m,a[N],ans[N],x[N],y[N],col[N];
vector<int>now;
int main(){sci(n);m=(n+1)/2;rep(i,1,n){if(i==m)continue;now.pb(i);}sort(now.begin(),now.end(),[&](int x,int y){return abs(x-m)>abs(y-m);});rep(i,1,n){sci(a[i]);if(i==1)x[i]=m,y[i]=1,ans[i]=1,col[m]=i;else{int v=now.back();now.pop_back();x[i]=v;if(a[i]==0){y[i]=1;ans[i]=i;}else if(abs(v-m)>a[i]){if(v<m){y[i]=a[i]-1+y[col[v+1]];//printf("i:%d y:%d coln:%d\n",i,y[i],col[i+1]);if(y[i]>n)y[i]=y[col[v+1]]-(a[i]-1);ans[i]=col[v+1];}else{y[i]=a[i]-1+y[col[v-1]];//printf("i:%d y:%d\n",i,y[i]);if(y[i]>n)y[i]=y[col[v-1]]-(a[i]-1);ans[i]=col[v-1];} }else{y[i]=a[i]-abs(v-m)+1;ans[i]=1;}col[v]=i;}}puts("YES");rep(i,1,n){printf("%d %d\n",x[i],y[i]);}rep(i,1,n){printf("%d%c",ans[i]," \n"[i==n]);}return 0;
}

B3 - Exact Neighbours (Hard)

n个数，ai∈[0,n]，

1. 如果出现0，可以参考第二问

2. 如果出现两个相同的，可以参考第一问

否则，都不相同，说明ai从[1,n]里每个恰出现了一次

（1）对于n=2的情况，互相参照一个为1一个为2显然不行，为no

（2）对于n>=3的情况，可以令曼哈顿距离1、2、3的两两互相参照

具体来说，可以令1在（x,1），3在（x+1,1），2在（x-1，2），

这样可以1参照3，3参照2，2参照1

其他的仍然可以参考第二问的实现形式，要么参照1，要么参照相邻列

#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<vector>
#include<map>
#include<unordered_map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10;
int n,m,a[N],ans[N],x[N],y[N],col[N],b[N],cnt[N];
vector<int>now;
int main(){sci(n);m=(n+1)/2;rep(i,1,n){if(i==m)continue;now.pb(i);}sort(now.begin(),now.end(),[&](int x,int y){return abs(x-m)>abs(y-m);});rep(i,1,n){sci(a[i]);cnt[a[i]]++;b[i]=i;}sort(b+1,b+n+1,[&](int x,int y){if(cnt[a[x]]!=cnt[a[y]])return cnt[a[x]]>cnt[a[y]];return a[x]<a[y];});if(a[b[1]]==0 || cnt[a[b[1]]]>=2){rep(j,1,n){int i=b[j];//printf("j:%d i:%d\n",j,i);if(j==1)x[i]=m,y[i]=1,ans[i]=i,col[m]=i;else{int v=now.back();now.pop_back();x[i]=v;if(a[i]==0){y[i]=1;ans[i]=i;}else if(abs(v-m)>a[i]){if(v<m){y[i]=a[i]-1+y[col[v+1]];//printf("i:%d y:%d coln:%d\n",i,y[i],col[i+1]);if(y[i]>n)y[i]=y[col[v+1]]-(a[i]-1);ans[i]=col[v+1];}else{y[i]=a[i]-1+y[col[v-1]];//printf("i:%d y:%d\n",i,y[i]);if(y[i]>n)y[i]=y[col[v-1]]-(a[i]-1);ans[i]=col[v-1];} }else{y[i]=a[i]-abs(v-m)+1;ans[i]=b[1];}col[v]=i;}}if(a[b[1]])ans[b[1]]=b[2];//成对}else{if(n==2){puts("NO");return 0;}else{rep(j,1,3){int i=b[j];if(j==1)x[i]=m,y[i]=1,col[m]=i;else{if(j==2)x[i]=m-1,y[i]=2,col[m-1]=i;else if(j==3)x[i]=m+1,y[i]=1,col[m+1]=i;now.pop_back();}}ans[b[1]]=b[3];ans[b[3]]=b[2];ans[b[2]]=b[1];rep(j,4,n){int i=b[j];//printf("j:%d i:%d\n",j,i);if(j==1)x[i]=m,y[i]=1,ans[i]=i,col[m]=i;else{int v=now.back();now.pop_back();x[i]=v;if(a[i]==0){y[i]=1;ans[i]=i;}else if(abs(v-m)>a[i]){if(v<m){y[i]=a[i]-1+y[col[v+1]];//printf("i:%d y:%d coln:%d\n",i,y[i],col[i+1]);if(y[i]>n)y[i]=y[col[v+1]]-(a[i]-1);ans[i]=col[v+1];}else{y[i]=a[i]-1+y[col[v-1]];//printf("i:%d y:%d\n",i,y[i]);if(y[i]>n)y[i]=y[col[v-1]]-(a[i]-1);ans[i]=col[v-1];} }else{y[i]=a[i]-abs(v-m)+1;ans[i]=b[1];}col[v]=i;}}}}puts("YES");rep(i,1,n){printf("%d %d\n",x[i],y[i]);}rep(i,1,n){printf("%d%c",ans[i]," \n"[i==n]);}return 0;
}

C1 - Game on Tree (Easy)

C2 - Game on Tree (Medium)

C3 - Game on Tree (Hard)

三个题只是前两题有弱化条件的限制，直接上C3换根dp即可

#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<vector>
#include<map>
#include<unordered_map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10;
int t,n,u,v,a[N],q[N],dp[N],ans[N];
vector<int>e[N];
void dfs(int u,int fa){int c=0;for(auto &v:e[u]){if(v==fa)continue;dfs(v,u);c++;dp[u]+=(dp[v]==0);}if(!c)dp[u]=0;
}
void dfs2(int u,int fa){ans[u]=dp[u];for(auto &v:e[u]){if(v==fa)continue;dp[u]-=(dp[v]==0);dp[v]+=(dp[u]==0);dfs2(v,u);dp[v]-=(dp[u]==0);dp[u]+=(dp[v]==0);}
}
int main(){sci(n);sci(t);rep(i,2,n){sci(u),sci(v);e[u].pb(v);e[v].pb(u);}dfs(1,0);//ans[1]=dp[1];dfs2(1,0);rep(i,1,t){sci(q[i]);puts(ans[q[i]]?"Ron":"Hermione");}return 0;
}

E1 - Trails (Easy)

按题意模拟

#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define ll long long
using namespace std;
typedef vector<ll> vint;
typedef pair<int,int> pii;vector<vint> jzksm(vector<vint> a, ll k) {int n = a.size();vector<vint> ans(n, vint(n));for(int i=0;i<n;i++) ans[0][i]=1;ll mod = 1e9 + 7;function<vector<vint>(vector<vint>&, vector<vint>&)>tt = [&](vector<vint>& a, vector<vint>& b) {vector<vint> an(n, vint(n));for (int i = 0;i < n;i++) {for (int j = 0;j < n;j++) {for (int k = 0;k < n;k++) {an[i][j] += (a[i][k] * b[k][j]) % mod;an[i][j] %= mod;}}}return an;};while (k) {if (k & 1) {ans = tt(ans, a);}a = tt(a, a);k >>= 1;}return ans;
}ll mod=1e9+7;int main() {ios::sync_with_stdio(false);cin.tie(0);int m,n; cin>>m>>n;vint s(m),l(m);for(int i=0;i<m;i++) cin>>s[i];for(int i=0;i<m;i++) cin>>l[i];vint ans(m);ans[0]=1;auto sol=[&](ll t,ll i,ll j) {return t*((s[i]*s[j]+s[i]*l[j]+l[i]*s[j])%mod)%mod;};for(int i=0;i<n;i++) {vint nans(m);for(int j=0;j<m;j++) {for(int k=0;k<m;k++) {nans[j]+=sol(ans[k],k,j);nans[j]%=mod;}}ans=nans;}ll an=0;for(int i=0;i<m;i++) an=(an+ans[i])%mod;cout<<an<<endl;return 0;
}

E2 - Trails (Medium)

m<=500，n<=1e9，矩阵快速幂，记录一下最后一个的位置

#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define ll long long
using namespace std;
typedef vector<ll> vint;
typedef pair<int,int> pii;ll mod=1e9+7;vector<vint> tt (vector<vint>& a, vector<vint>& b) {int n=a.size();vector<vint> an(n, vint(n));for (int i = 0;i < n;i++) {for (int j = 0;j < n;j++) {for (int k = 0;k < n;k++) {an[i][j] += (a[i][k] * b[k][j]) % mod;an[i][j] %= mod;}}}return an;
};
vector<vint> jzksm(vector<vint>& a, ll k) {int n = a.size();vector<vint> ans(n, vint(n));for(int i=0;i<n;i++) ans[i][i]=1;ll mod = 1e9 + 7;while (k) {if (k & 1) {ans = tt(ans, a);}a = tt(a, a);k >>= 1;}return ans;
}int main() {ios::sync_with_stdio(false);cin.tie(0);int m,n; cin>>m>>n;vint s(m),l(m);for(int i=0;i<m;i++) cin>>s[i];for(int i=0;i<m;i++) cin>>l[i];vector<vint> cal(m,vint(m)),cal2(m,vint(m)),cal3(m,vint(m));auto sol=[&](ll i,ll j) {return ((s[i]*s[j]+s[i]*l[j]+l[i]*s[j])%mod)%mod;};for(int i=0;i<m;i++) {for(int j=0;j<m;j++) {cal[i][j]=sol(i,j);}}vector<vint> beg(m,vint(m));beg[0][0]=1;cal=jzksm(cal,n);beg=tt(beg,cal);ll an=0;for(int i=0;i<m;i++) {an=(an+beg[0][i])%mod;}cout<<an<<endl;return 0;
}

E3 - Trails (Hard)

把[0.5,1.5]天看成是完整的一天，[1.5,2.5]天看成是完整的一天

只有「长长」、「长短」、「短长」、「短短」四种情况，分别标号0、1、2、3

手玩一下判断一下哪种情况不能转移，然后矩阵快速幂，

最后，根据[0.5,1]和[n-1,n-0.5]天这两个半天是什么，

把[0,0.5]天和[n-0.5,n]天这两个半天拼接上即可，

如果另外半天已经出现短了，当前半天就都可以，否则当前半天只能出现短

复杂度O(m+4^3logn)

#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
using namespace std;
typedef long long ll;
const int N=1e5+10,mod=1e9+7;
struct mat {static const int MAXN=4;ll c[MAXN][MAXN];int m, n;mat(){memset(c, 0, sizeof(c));m=n=MAXN;}mat(int a, int b) : m(a), n(b) {memset(c, 0, sizeof(c));}void clear(){memset(c, 0, sizeof(c));}mat operator * (const mat& temp) {mat ans(m, temp.n);for (int i = 0; i < m; i ++)for (int j = 0; j < temp.n; j ++){for (int k = 0; k < n; k ++){ans.c[i][j] += c[i][k] * temp.c[k][j];ans.c[i][j]%=mod;}}return ans;}mat operator ^(ll n){mat M(*this),ans(M.m, M.m);for (int i = 0; i < M.m; i ++)ans.c[i][i] = 1;while (n > 0) {if (n & 1) ans = ans * M;M = M * M;n >>= 1;}return ans;}
}b;
int a[4],m,n,s[N],l[N],s1,l1;
int main(){sci(m),sci(n);rep(i,1,m){sci(s[i]);s1+=s[i];a[3]=(a[3]+1ll*s[i]*s[i]%mod)%mod;}rep(i,1,m){sci(l[i]);l1+=l[i];a[0]=(a[0]+1ll*l[i]*l[i]%mod)%mod;a[1]=(a[1]+1ll*l[i]*s[i]%mod)%mod;}a[2]=a[1];// rep(i,0,3){//     printf("i:%d a:%d\n",i,a[i]);// }b.c[0][2]=a[2];b.c[0][3]=a[3];b.c[1][0]=a[0];b.c[1][1]=a[1];b.c[1][2]=a[2];b.c[1][3]=a[3];b.c[2][2]=a[2];b.c[2][3]=a[3];b.c[3][0]=a[0];b.c[3][1]=a[1];b.c[3][2]=a[2];b.c[3][3]=a[3];if(n==1){printf("%lld\n",(1ll*s[1]*(s1+l1)+1ll*l[1]*s1)%mod);return 0;}b=b^(n-2);int ans=0;rep(i,0,3){rep(j,0,3){//printf("%d ",b.c[i][j]);int x=i&2,y=j&1,pre,suf;if(x==0)pre=s[1];else pre=(s[1]+l[1])%mod;if(y==0)suf=s1;else suf=(s1+l1)%mod;//if(b.c[i][j] && pre && suf)printf("i:%d j:%d c:%d pre:%d suf:%d\n",i,j,b.c[i][j],pre,suf);ans=(ans+1ll*pre*a[i]%mod*b.c[i][j]%mod*suf%mod)%mod;}//puts("");// ans=(ans+b.c[i][j])%mod;}pte(ans);return 0;
}

G1 - Min-Fund Prison (Easy)

按题意模拟

// Problem: G1. Min-Fund Prison (Easy)G1。敏基金监狱（简单）
// Contest: Codeforces - Helvetic Coding Contest 2024 online mirror (teams allowed, unrated)Helvetic 编码大赛 2024 在线镜像（允许团队，未评级）
// URL: https://codeforces.com/contest/1970/problem/G1
// Memory Limit: 256 MB
// Time Limit: 1500 ms
// Time: 2024-05-04 17:32:44#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define ll long long
using namespace std;
typedef vector<ll> vint;
typedef pair<int,int> pii;int main() {ios::sync_with_stdio(false);cin.tie(0);int times; cin>>times;while(times--) {ll n,m,c; cin>>n>>m>>c;vector<vint> tr(n);for(int i=0;i<m;i++) {int u,v; cin>>u>>v;tr[--u].push_back(--v);tr[v].push_back(u);}auto cal=[&](ll x) {return x*x;};vint deep(n);function<int(int,int)> dfs=[&](int now,int fa) {deep[now]=1;for(auto x:tr[now]) {if(fa!=x) deep[now]+=dfs(x,now);}return deep[now];};dfs(0,-1);ll ans=LONG_LONG_MAX;for(int i=0;i<n;i++) {if(deep[i]!=n) ans=min(ans,cal(deep[i])+cal(n-deep[i]));}cout<<ans<<endl;}return 0;
}