Solved：5/13
Penalty: 707
Rank：101
Rank（ucup）：200
A. The Fool
题意：给一个 \(n\times m\) 的字符串矩阵，有一个字符串和其他不同，求这个字符串的位置。
直接模拟即可。
#include<bits/stdc++.h>
using namespace std;
const int N=205;
string a[N];
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int n,m,k;
cin>>n>>m>>k;
for(int i=0;i<n;++i)cin>>a[i];
string t=a[0].substr(0,k);
int x,y,cnt=0;
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
if(a[i].substr(j*k,k)!=t)x=i,y=j,++cnt;
if(cnt>1)cout<<"1 1\n";
else cout<<x+1<<' '<<y+1<<'\n';
}
J. Temperance
题意：三维空间中有 \(n\) 个点，定义一个点的密度为与它某一维坐标相同的点数的最大值。现要删去一些点，使所有留下的点密度都至少为 \(k\)，对 \(k=0,1,\dots,n-1\) 求最少删去的点数。
一开始想复杂了，以为要维护一个 set 然后删点什么的。结果写一半发现复杂度不对。
然后发现暴力就是对的，因为每次删点都会把 \(k\) 最小的点都删掉（而且不会影响 \(k\) 更大的点），所以最多就删根号次。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N],b[N],c[N],s[N],ans[N];
int x[N],y[N],z[N];
bool vis[N];
void solve(){
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i]>>b[i]>>c[i],vis[i]=0;
++x[a[i]],++y[b[i]],++z[c[i]];
}
int k=0,cnt=0;
while(cnt<n){
for(int i=1;i<=n;++i)if(!vis[i])s[i]=max(max(x[a[i]],y[b[i]]),z[c[i]]);
int mn=n;
for(int i=1;i<=n;++i)if(!vis[i])mn=min(mn,s[i]);
while(k<=mn-1)ans[k]=cnt,++k;
for(int i=1;i<=n;++i)if(!vis[i]&&s[i]<=k)
vis[i]=1,--x[a[i]],--y[b[i]],--z[c[i]],++cnt;
}
while(k<=n-1)ans[k]=n,++k;
for(int i=0;i<=n-1;++i)cout<<ans[i]<<' ';
cout<<'\n';
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int T;
cin>>T;
while(T--)solve();
}
F. The Hermit
题意：对一个整数集 \(S\)，定义
\[f(S) = \max\{|T|: T\subset S, \min(T)\neq \gcd(T)\} \]，求
\[\sum\{f(S): S\subset \{1,2,\dots,n\}, |S| = m\} \]首先对一个确定的集合，我们一定会删掉最小的几个数，直到 \(\min\neq \gcd\) 为止。
假设删掉的最大数为 \(d\)，则集合中原有的比 \(d\) 小的数都是 \(d\) 的约数且后一个是前一个的倍数（不妨称为“倍数链”）；比 \(d\) 大的数都是 \(d\) 的倍数且满足 \(\gcd\neq \min\)。
对每个 \(d\)，dp 预处理 \(f(d,k)\) 表示 \(d\) 的“倍数链”的数量，暴力整除分块计算后半部分的方案即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,mod=998244353;
ll fac[N],inf[N];
ll f[N][18];
void init(int n){
fac[0]=1;
for(int i=1;i<=n;++i)fac[i]=fac[i-1]*i%mod;
inf[1]=1;
for(int i=2;i<=n;++i)inf[i]=inf[mod%i]*(mod-mod/i)%mod;
inf[0]=1;
for(int i=1;i<=n;++i)inf[i]=inf[i-1]*inf[i]%mod;
for(int i=1;i<=n;++i)f[i][1]=1;
for(int k=2;k<=17;++k)
for(int i=1;i<=n;++i)
for(int j=i*2;j<=n;j+=i)
f[j][k]=(f[j][k]+f[i][k-1])%mod;
}
ll C(int n,int m){
if(n<m||m<0)return 0;
return fac[n]*inf[m]%mod*inf[n-m]%mod;
}
ll calc(int n,int m){
if(!m)return 1;
if(n<=m)return 0;
ll res=C(n-1,m);
for(int i=2,j;i<=n;i=j+1){
j=n/(n/i);
res=(res-(j-i+1)*C(n/i-1,m-1))%mod;
}
return res;
}
int n,m;
int main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
init(n);
ll ans=C(n,m)*m%mod;
for(int i=1;i<=n;++i)
for(int j=1;j<=min(m,17);++j)if(f[i][j])
ans=((ans-j*f[i][j]%mod*calc(n/i,m-j))%mod+mod)%mod;
cout<<ans<<'\n';
}
B. The Magician
题意：你有 \(n\) 张初始手牌和一些换手牌的规则，要凑出尽可能多的同花。
暴搜就完了。那一坨规则全搜一遍也只有 \(20^4\times 4\times 16 = 10240000\) 种情况。
#include<bits/stdc++.h>
using namespace std;
int op(char c){
if(c=='D')return 0;
if(c=='C')return 1;
if(c=='H')return 2;
if(c=='S')return 3;
}
int n,c[5],t[6],ans;
string ss;
void dfs(int x){
if(x==6){
int d[5];
memcpy(d,c,sizeof(d));
int sum=0;
for(int i=0;i<4;++i)sum+=c[i]/5,c[i]%=5;
sort(c,c+4);
for(int i=3;i>=0;--i){
if(c[i]+c[4]>=5)c[4]-=5-c[i],++sum;
}
ans=max(ans,sum);
memcpy(c,d,sizeof(c));
return;
}
if(t[x]){
if(x<=3){
int id[3],d[5];
for(int i=0,j=0;i<4;++i)if(i!=x)id[j++]=i;
for(int i=0;i<=3&&i<=c[id[0]];++i)
for(int j=0;i+j<=3&&j<=c[id[1]];++j)
for(int k=0;i+j+k<=3&&k<=c[id[2]];++k){
memcpy(d,c,sizeof(d));
c[id[0]]-=i;
c[id[1]]-=j;
c[id[2]]-=k;
c[x]+=i+j+k;
dfs(x+1);
memcpy(c,d,sizeof(c));
}
}
else if(x==4){
for(int i=0;i<4;++i)if(c[i]){
--c[i],++c[4];
dfs(x+1);
++c[i],--c[4];
}
}
else{
for(int i=0;i<5;++i)if(c[i])
for(int j=0;j<4;++j)if(c[j]){
--c[j],++c[i];
dfs(x+1);
++c[j],--c[i];
}
}
}
dfs(x+1);
}
void solve(){
cin>>n;
for(int i=1;i<=n;++i)cin>>ss,++c[op(ss[1])];
ans=0;
int sum=0;
for(int i=0;i<4;++i)sum+=c[i]/5,c[i]%=5;
for(int i=0;i<6;++i)cin>>t[i];
dfs(0);
cout<<ans+sum<<'\n';
memset(c,0,sizeof(c));
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int T;
cin>>T;
while(T--)solve();
}
I. The Hanged Man
题意：给一棵树，加一些边使得每条边都恰好在一个环上，且不存在重边和子环。输出方案，无解输出 -1。
等价于将树拆分成若干条长度 \(\geq 2\) 的链。对每棵子树，如果有偶数个儿子，直接配对；如果有奇数个儿子，将最长的链传到根上。
选取一个偶度数的点作为根开始 dfs。如果所有点的度数都为奇数，则无解。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=3e5+5;
int n,x,y,d[N];
vector<int> e[N];
void adde(int x,int y){
e[x].push_back(y),++d[y];
}
int dep[N];
vector<pii> ans;
int dfs(int u,int f){
vector<int> b;
for(int v:e[u])if(v!=f){
dep[v]=dep[u]+1;
int t=dfs(v,u);
b.push_back(t);
}
int m=b.size();
if(m&1){
for(int i=0;i<m;++i)if(dep[b[i]]>dep[b[m-1]])swap(b[i],b[m-1]);
}
for(int i=0;i+1<m;i+=2)ans.emplace_back(b[i],b[i+1]);
if(m&1)return b[m-1];
else return u;
}
void solve(){
cin>>n;
for(int i=1;i<=n;++i)e[i].clear(),d[i]=0;
for(int i=1;i<n;++i){
cin>>x>>y;
adde(x,y),adde(y,x);
}
int rt=0;
for(int i=1;i<=n;++i)if(!(d[i]&1)){rt=i;break;}
if(!rt){cout<<"-1\n";return;}
int s=dfs(rt,0);
if(s!=rt)ans.emplace_back(s,rt);
cout<<ans.size()<<'\n';
for(auto [x,y]:ans)cout<<x<<' '<<y<<'\n';
ans.clear();
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int T;
cin>>T;
while(T--)solve();
}