Preface
由于今天 HDU 多校是自己学校出的题，因此像我这种没出题的就可以白兰一天爽歪歪
然后和祁神找了场 Ucup 来 VP，这场傻逼题巨多，不那么傻逼的题后面发现被搬到去年暑假前集训了，然后直接 3h 10 题下班
后期徐神全力冲刺他最喜欢的造计算机题，反观某人已经在 Celeste 启动了，怎么回事呢
A. Simplified Genome Translation
傻逼题，把题目里的表格复制一下模拟即可
#include<cstdio>
#include<iostream>
#include<string>
#include<map>
#define RI register int
#define CI const int&
using namespace std;
int t; string s; map <string,string> trs;
int main()
{
trs["UUU"]=trs["UUC"]="F";
trs["UUA"]=trs["UUG"]=trs["CUU"]=trs["CUC"]=trs["CUA"]=trs["CUG"]="L";
trs["AUU"]=trs["AUC"]=trs["AUA"]="I";
trs["AUG"]="M";
trs["GUU"]=trs["GUC"]=trs["GUA"]=trs["GUG"]="V";
trs["UCU"]=trs["UCC"]=trs["UCA"]=trs["UCG"]=trs["AGU"]=trs["AGC"]="S";
trs["CCU"]=trs["CCC"]=trs["CCA"]=trs["CCG"]="P";
trs["ACU"]=trs["ACC"]=trs["ACA"]=trs["ACG"]="T";
trs["GCU"]=trs["GCC"]=trs["GCA"]=trs["GCG"]="A";
trs["UAU"]=trs["UAC"]="Y";
trs["CAU"]=trs["CAC"]="H";
trs["CAA"]=trs["CAG"]="Q";
trs["AAU"]=trs["AAC"]="N";
trs["AAA"]=trs["AAG"]="K";
trs["GAU"]=trs["GAC"]="D";
trs["GAA"]=trs["GAG"]="E";
trs["UGU"]=trs["UGC"]="C";
trs["UGG"]="W";
trs["CGU"]=trs["CGC"]=trs["CGA"]=trs["CGG"]=trs["AGA"]=trs["AGG"]="R";
trs["GGU"]=trs["GGC"]=trs["GGA"]=trs["GGG"]="G";
trs["UAA"]=trs["UAG"]=trs["UGA"]="|";
ios::sync_with_stdio(0); cin.tie(0);
for (cin>>t;t;--t)
{
cin>>s; string ans="";
for (RI i=0;i+2<s.size();i+=3)
{
string tmp=s.substr(i,3);
if (trs[tmp]!="|") ans+=trs[tmp]; else break;
}
cout<<ans<<'\n';
}
return 0;
}
B. Multi-Ladders
首先不难发现问题分为两个部分：
- 给 \(k\) 个点的环染色；
- 给 \(n\) 层的 Ladder 染色；
后者的方案数很好计算，我们按层来考虑，当给环染完色后每个 Ladder 的第一层就是确定的
手玩一下会发现后面的每一层方案数都是 \((\lambda-2)^2+(\lambda-1)\) 种，因此总方案数为 \([(\lambda-2)^2+(\lambda-1)]^{(n-1)\times k}\)
而环上的情况相对来说要麻烦一些，通过暴力打表手玩我们发现这个有递推关系
令 \(f(k)\) 表示 \(k\) 个点的环的染色方案，初始值：\(f(2)=\lambda(\lambda-1),f(3)=\lambda(\lambda-1)(\lambda-2)\)，转移有 \(f(k)=(\lambda-1)\times f(k-2)+(\lambda-2)\times f(k-1)\)，很容易用矩乘优化
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
using pii = pair<int, int>;
int powe(int x, int p){
int res=1;
while (p>0){if (p&1) res=res*x%MOD; x=x*x%MOD; p>>=1;}
return res;
}
struct Matrix
{
int n,m,a[2][2];
inline Matrix(const int& N=0,const int& M=0)
{
n=N; m=M; memset(a,0,sizeof(a));
}
inline int* operator [] (const int& x)
{
return a[x];
}
friend inline Matrix operator * (Matrix A,Matrix B)
{
Matrix C(A.n,B.m);
for (int i=0;i<C.n;++i) for (int j=0;j<C.m;++j)
for (int k=0;k<A.m;++k) (C[i][j]+=1LL*A[i][k]*B[k][j]%MOD)%=MOD;
return C;
}
friend inline Matrix operator ^ (Matrix A,int p)
{
Matrix T(A.n,A.m); for (int i=0;i<T.n;++i) T[i][i]=1;
for (;p;p>>=1,A=A*A) if (p&1) T=T*A; return T;
}
};
void solve(){
int n, k, c; cin >> n >> k >> c;
if (c<=1) cout << "0\n";
else if (2==c) cout << (k%2==0 ? 2 : 0) << '\n';
else{
Matrix A(2,1),D(2,2);
A[0][0]=1LL*c*(c-1)%MOD;
A[1][0]=1LL*A[0][0]*(c-2)%MOD;
D[0][0]=0; D[0][1]=1;
D[1][0]=c-1; D[1][1]=c-2;
A=(D^(k-3))*A;
int cy=A[1][0];
int ld = ((c-2)*(c-2)%MOD + (c-1))%MOD;
cy = cy*powe(ld, (n-1)*k%(MOD-1))%MOD;
cout << cy << '\n';
}
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t; while (t--) solve();
return 0;
}
C. Distance Calculator
每一步可以交换相邻的两个数，因此答案就是给出的排列的逆序对数
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=105;
int t,n,a[N];
int main()
{
for (scanf("%d",&t);t;--t)
{
scanf("%d",&n); int ans=0;
for (RI i=1;i<=n;++i) scanf("%d",&a[i]);
for (RI i=1;i<=n;++i) for (RI j=i+1;j<=n;++j) ans+=(a[i]>a[j]);
printf("%d\n",ans);
}
return 0;
}
D. Tangle: A DAG for storing transactions
逆天阅读理解题，读完发现随便写个 \(O(n^2)\) 的东西上去就行
#include<cstdio>
#include<iostream>
#include<bitset>
#define RI register int
#define CI const int&
using namespace std;
const int N=10005;
int n,lim,x,u[N],v[N],w[N]; bitset <N> G[N];
int main()
{
scanf("%d%d",&n,&lim);
for (RI i=1;i<=n;++i)
{
scanf("%d",&x); G[x].set(x);
scanf("%d%d%d",&u[x],&v[x],&w[x]);
}
for (RI i=n+1;i>=2;--i)
G[u[i]]|=G[i],G[v[i]]|=G[i];
int cnt=0;
for (RI i=2;i<=n;++i)
{
int ret=0;
for (RI j=2;j<=n+1;++j)
if (G[i].test(j)) ret+=w[j];
if (ret>=lim) printf("%d %d\n",i,ret),++cnt;
}
printf("%d\n",cnt);
return 0;
}
E. Printing Stickers
不可做题，弃疗
F. AA Country and King Dreamoon
注意到缺失的一定是一段连续的区间，同时我们知道欧拉序是可逆的，倒着看欧拉序其实就是把原树中每个边的边表 reverse 后得到的结果
因此先对前后一段已知信息建树并确定当前所在的节点，树上这两个点之间的路径都是必须要经过的
同时找出所有还未使用的点，现在就是要把这些点挂在路径上的点的子树内
根据字典序的性质可以贪心，每一步要么选择挂一个新点，要么选择回溯一步，选较小的一边即可
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=300005;
int t,n,a[N<<1],anc[N],vis[N],dep[N];
int main()
{
for (scanf("%d",&t);t;--t)
{
scanf("%d",&n);
for (RI i=1;i<=n;++i) vis[i]=0;
for (RI i=1;i<=2*n-1;++i) scanf("%d",&a[i]);
int ft=n+1;
for (RI i=1;i<=2*n-1;++i)
{
if (!a[i]) break;
if (!vis[a[i]]) dep[a[i]]=dep[ft]+1,anc[a[i]]=ft,ft=a[i],vis[a[i]]=1;
else ft=a[i];
}
int bk=n+1;
for (RI i=2*n-1;i>=1;--i)
{
if (!a[i]) break;
if (!vis[a[i]]) dep[a[i]]=dep[bk]+1,anc[a[i]]=bk,bk=a[i],vis[a[i]]=1;
else bk=a[i];
}
auto getLCA=[&](int x,int y)
{
while (x!=y)
{
if (dep[x]<dep[y]) swap(x,y);
x=anc[x];
}
return x;
};
int lca=getLCA(ft,bk);
vector <int> path;
while (ft!=lca) path.push_back(ft),ft=anc[ft];
vector <int> tmp;
while (bk!=lca) tmp.push_back(bk),bk=anc[bk];
reverse(tmp.begin(),tmp.end());
path.push_back(lca);
for (auto x:tmp) path.push_back(x);
vector <int> valid;
for (RI i=1;i<=n;++i) if (!vis[i]) valid.push_back(i);
sort(valid.begin(),valid.end(),greater <int>());
int beg=-1,end=-1;
for (RI i=1;i<=2*n-1;++i)
if (!a[i]) { beg=i; break; }
for (RI i=2*n-1;i>=1;--i)
if (!a[i]) { end=i; break; }
vector <int> stk;
if (beg!=-1)
{
for (RI i=beg,j=0;i<=end;++i)
{
if (!stk.empty())
{
int x=stk.size()>=2?stk[stk.size()-2]:path[j];
int y=valid.empty()?n+2:valid.back();
if (x<y)
{
a[i]=x; stk.pop_back();
} else a[i]=y,valid.pop_back(),stk.push_back(y);
} else
{
int x=j+1<path.size()?path[j+1]:n+2;
int y=valid.empty()?n+2:valid.back();
if (x<y) a[i]=x,++j;
else a[i]=y,valid.pop_back(),stk.push_back(y);
}
}
}
for (RI i=1;i<=2*n-1;++i) printf("%d%c",a[i]," \n"[i==2*n-1]);
}
return 0;
}
G. Repetitive Elements
签到 string 题，祁神开场写的我题目都没看
#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
void solve(){
map<string, vector<pii>> mp;
string str1;
cin >> str1;
int n = str1.length();
for (int i=0; i<n; ++i){
for (int j=1; i+j-1<n; ++j){
mp[str1.substr(i, j)].emplace_back(i, i+j-1);
}
}
pii seg{n, n};
for (auto [str, vec] : mp){
sort(vec.begin(), vec.end());
if (vec[0].second < vec.back().first){
int len = str.length();
int lenans = seg.second-seg.first+1;
if (len > lenans) seg=vec[0];
else if (len == lenans){
if (vec[0].first < seg.first) seg=vec[0];
}
}
}
cout << str1.substr(seg.first, seg.second-seg.first+1) << '\n';
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t; while (t--) solve();
return 0;
}
H. Meeting Places
去年暑假前集训几何专题的一个题，被祁神火眼金睛看出来秒了
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define LD long double
const LD eps = 1e-8;
const LD INF = 1e18;
const int MOD = ((1LL<<31)-1);
int sgn(LD x){return fabs(x)<=eps ? 0 : (x>eps ? 1 : -1);}
int getNext(int x){ return (x*233811181LL+1)%MOD;}
const int N = 2005;
struct Pt{
LD x, y;
Pt operator-(Pt b)const{return Pt{x-b.x, y-b.y};}
Pt operator+(Pt b)const{return Pt{x+b.x, y+b.y};}
Pt operator*(LD b)const{return Pt{x*b, y*b};}
LD crs(Pt b)const{return x*b.y-y*b.x;}
LD len2()const{return x*x+y*y;}
LD len()const{return sqrt(x*x+y*y);}
Pt rot90()const{return Pt{-y, x};}
}pt[N];
struct Cir{
Pt c; LD r;
bool cover(Pt p){return sgn(r - (p-c).len())>=0;}
};
Pt pt_l_l(Pt p1, Pt v1, Pt p2, Pt v2){
return p1 + v1*(1.0L*v2.crs(p1-p2)/v1.crs(v2));
}
Cir getCir(Pt a, Pt b, Pt c){
Pt o = pt_l_l((b+a)*0.5L, (b-a).rot90(), (c+a)*0.5L, (c-a).rot90());
LD r = (o-a).len();
return Cir{o, r};
}
int n, k, xx[N], yy[N];
LD cost[N][N], dp[N];
vector<int> vec[N];
signed main(){
scanf("%lld%lld%lld", &n, &k, &xx[1]);
yy[1] = getNext(xx[1]);
for (int i=2; i<=n; ++i) xx[i]=getNext(yy[i-1]), yy[i]=getNext(xx[i]);
for (int i=1; i<=n; ++i) pt[i]={1.0L*xx[i], 1.0L*yy[i]};
for (int r=1; r<=n; ++r){
Cir cir={pt[r], 0.0L};
cost[r][r]=0.0L;
for (int i=r-1; i>0; --i){
if (!cir.cover(pt[i])){
vec[r].push_back(i);
cir={pt[i], 0.0L};
for (int j=r; j>i; --j){
if (cir.cover(pt[j])) continue;
cir={(pt[i]+pt[j])*0.5L, (pt[i]-pt[j]).len()*0.5L};
for (int k=r; k>j; --k){
if (cir.cover(pt[k])) continue;
cir=getCir(pt[i], pt[j], pt[k]);
}
}
}
cost[i][r]=cir.r;
}
vec[r].push_back(0);
}
for (int j=1; j<=n; ++j) dp[j]=INF;
for (int i=1; i<=k; ++i){
for (int j=n; j>0; --j){
for (int x : vec[j]) dp[j] = min(dp[j], dp[x]+cost[x+1][j]);
}
}
printf("%.10Lf\n", dp[n]);
return 0;
}
I. Cell Nuclei Detection
由于矩形的边长很小因此暴力建图连出的边数不会很多，可以大力 Dinic 艹过
#include<bits/stdc++.h>
using namespace std;
#define RI int
using pii = pair<int, int>;
const int N = 2005;
int m, n;
vector<array<int, 3>> rect[N][N];
namespace Network_Flow
{
const int NN=100005,MM=1e7+5,INF=1e9;
struct edge
{
int to,nxt,v;
}e[MM<<1]; int cnt=1,head[NN],cur[NN],dep[NN],s,t;
inline void clear(void)
{
memset(head,0,(t+1)*sizeof(int)); cnt=1;
}
inline void addedge(int x,int y,int z)
{
e[++cnt]=(edge){y,head[x],z}; head[x]=cnt;
e[++cnt]=(edge){x,head[y],0}; head[y]=cnt;
}
#define to e[i].to
inline bool BFS(void)
{
memset(dep,0,(t+1)*sizeof(int)); dep[s]=1;
queue <int> q; q.push(s);
while (!q.empty())
{
int now=q.front(); q.pop();
for (RI i=head[now];i;i=e[i].nxt)
if (e[i].v&&!dep[to]) dep[to]=dep[now]+1,q.push(to);
}
return dep[t];
}
inline int DFS(int now,int tar,int dis)
{
if (now==tar) return dis; int ret=0;
for (RI& i=cur[now];i&&dis;i=e[i].nxt)
if (e[i].v&&dep[to]==dep[now]+1)
{
int dist=DFS(to,tar,min(dis,e[i].v));
if (!dist) dep[to]=0;
dis-=dist; ret+=dist;
e[i].v-=dist; e[i^1].v+=dist;
if (!dis) return ret;
}
if (!ret) dep[now]=0; return ret;
}
#undef to
inline int Dinic(int ret=0)
{
while (BFS()) memcpy(cur,head,(t+1)*sizeof(int)),ret+=DFS(s,t,INF); return ret;
}
}
using namespace Network_Flow;
void solve(){
for (int i=0; i<N; ++i) for (int j=0; j<N; ++j) rect[i][j].clear();
cin >> m >> n;
for (int i=1; i<=m; ++i){
int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
if (x1>x2) swap(x1, x2);
if (y1>y2) swap(y1, y2);
rect[x1][y1].push_back({x2, y2, i});
}
for (int v=1; v<=n; ++v){
int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
if (x1>x2) swap(x1, x2);
if (y1>y2) swap(y1, y2);
for (int i=max(0, x1-3); i<x2; ++i){
for (int j=max(0, y1-3); j<y2; ++j){
for (auto [xd2, yd2, id] : rect[i][j]){
int xl = max(x1, i), xr = min(x2, xd2);
int yl = max(y1, j), yr = min(y2, yd2);
if (xl>=xr || yl>=yr) continue;
int area1 = (xr-xl)*(yr-yl);
int area2 = (xd2-i)*(yd2-j);
if (area1*2 >= area2) addedge(id, v+m, 1);
}
}
}
}
s=n+m+1, t=n+m+2;
for (int i=1; i<=m; ++i) addedge(s, i, 1);
for (int i=m+1; i<=m+n; ++i) addedge(i, t, 1);
cout<<Dinic()<<'\n';
clear();
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t; while (t--) solve();
return 0;
}
J. Traveling in Jade City
去年 暑假前集训数据结构专题 的原题，直接 CV 过来魔改了下输入输出就过了
#include<cstdio>
#include<iostream>
#include<utility>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=1000005,INF=1e9;
int n,m,S,a[N],b[N],q,opt,x,y,ans; bool visA[N],visB[N];
class Tree_Array
{
private:
int lim,bit[N];
#define lowbit(x) (x&-x)
inline int get(RI x,int ret=0)
{
for (;x;x-=lowbit(x)) ret+=bit[x]; return ret;
}
public:
inline void init(CI n)
{
lim=n;
}
inline void add(RI x,CI y)
{
for (;x<=lim;x+=lowbit(x)) bit[x]+=y;
}
inline int query(CI l,CI r)
{
if (l>r) return 0; return get(r)-get(l-1);
}
#undef lowbit
}A,B;
inline int query(int x,int y)
{
if (x>y) swap(x,y); int ret=INF;
auto DisA1=[&](CI p)
{
return min(A.query(1,p-1),A.query(p,n));
};
auto DisAS=[&](CI p)
{
int u=p,v=S; if (u>v) swap(u,v);
return min(A.query(u,v-1),A.query(v,n)+A.query(1,u-1));
};
auto DisB1=[&](CI p)
{
return min(B.query(1,p),B.query(p+1,m+1)+A.query(1,S-1));
};
auto DisBS=[&](CI p)
{
return min(B.query(p+1,m+1),B.query(1,p)+A.query(1,S-1));
};
if (y<=n)
{
ret=min(ret,A.query(x,y-1));
ret=min(ret,A.query(y,n)+A.query(1,x-1));
ret=min(ret,DisA1(x)+DisAS(y)+B.query(1,m+1));
ret=min(ret,DisA1(y)+DisAS(x)+B.query(1,m+1));
} else if (x>n)
{
x-=n; y-=n; ret=min(ret,B.query(x+1,y));
ret=min(ret,B.query(y+1,m+1)+A.query(1,S-1)+B.query(1,x));
ret=min(ret,DisB1(x)+(A.query(1,n)-A.query(1,S-1))+DisBS(y));
ret=min(ret,DisB1(y)+(A.query(1,n)-A.query(1,S-1))+DisBS(x));
} else
{
y-=n; ret=min(ret,DisA1(x)+DisB1(y));
ret=min(ret,DisAS(x)+DisBS(y));
}
return ret;
}
signed main()
{
//freopen("J.in","r",stdin);
ios::sync_with_stdio(0); cin.tie(0);
RI i; cin>>n>>S>>m>>q; A.init(n); B.init(m+1);
for (i=1;i<=n;++i) cin>>a[i],A.add(i,a[i]);
for (i=1;i<=m+1;++i) cin>>b[i],B.add(i,b[i]);
for (i=1;i<=q;++i)
{
char opt; cin>>opt;
switch (opt)
{
case 'q':
cin>>x>>y; ans=query(x,y);
if (ans!=INF) cout<<ans<<'\n'; else cout<<"impossible\n"; break;
case 'c':
cin>>x; if (!visA[x]) A.add(x,INF); else A.add(x,-INF);
visA[x]^=1; break;
case 'x':
cin>>x; ++x; if (!visB[x]) B.add(x,INF); else B.add(x,-INF);
visB[x]^=1; break;
}
}
return 0;
}
K. Group Guests
看起来也是个不可做题，弃疗
L. Programmable Virus
徐神最爱的造计算机，现在徐神正在全力冲刺中
M. Connectivity Problem
签到题，我题目都没看
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, fa[N];
int gf(int x){return fa[x]==x ? x : fa[x]=gf(fa[x]);}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
for (int i=0; i<N; ++i) fa[i]=i;
for (int i=1; i<=n; ++i){
int u, v; cin >> u >> v;
if (gf(u)==gf(v)) cout << "Y\n";
else{
fa[gf(u)] = gf(v);
cout << "N\n";
}
}
return 0;
}
Postscript
感觉这场有点过于简单了，而且好多题目就是纯纯的阅读理解，怪不得这么多 downvote
标签：return,Pt,Contest,int,Regional,Programming,ret,const,trs From： https://www.cnblogs.com/cjjsb/p/18343887