总体来说难度还行，不如昨天的 csp 恶心，还是要注意细节，因为两个字符挂了 70 分。
T1
容易发现这个东西如果最后胜者的出的东西确定了，那么整个序列其实就确定了，这个可以预处理出来，所以我们考虑使这个序列字典序最小。
我们可以考虑用归并排序之类的方法，复杂度是 (O(nlog n))，其中 (n) 是序列长度。
代码：
#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 70010
#define M number
using namespace std;
// #define fre
const int INF=0x3f3f3f3f;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int t,r,p,s,a[3][20][N],all,cnt[3][3];
vector<int> v;
string S[4];
inline void Init(){
v.clear();for(int j=0;j<=3;j++) S[j].clear();
read(r);read(p);read(s);all=r+p+s;
memset(cnt,0,sizeof(cnt));
}
inline void PreWork(){
a[0][0][1]=0;a[1][0][1]=1;a[2][0][1]=2;
for(int i=0;i<=14;i++){
for(int j=1;j<=(1<<i);j++){
for(int k=0;k<=2;k++){
if(a[k][i][j]==0){
a[k][i+1][(j<<1)-1]=0;
a[k][i+1][(j<<1)]=1;
}
else if(a[k][i][j]==1){
a[k][i+1][(j<<1)-1]=2;
a[k][i+1][(j<<1)]=1;
}
else if(a[k][i][j]==2){
a[k][i+1][(j<<1)-1]=0;
a[k][i+1][(j<<1)]=2;
}
}
}
}
}
inline void Solve(int k,int n,int id){
for(int i=1;i<=n;i++){
int len=(1<<i);
for(int j=1;j<=(1<<n);j+=len){
int p=len/2;bool op=1;
for(int q=1;q<=p;q++){
if(a[k][n][j+q-1]!=a[k][n][j+q-1+p]){
if(a[k][n][j+q-1]<a[k][n][j+q-1+p]) op=1;
else op=0;
break;
}
}
if(!op){
for(int q=1;q<=p;q++){
swap(a[k][n][j+q-1],a[k][n][j+q-1+p]);
}
}
}
}
for(int j=1;j<=(1<<n);j++){
if(a[k][n][j]==0) S[id]+=(string)"P";
else if(a[k][n][j]==1) S[id]+=(string)"R";
else if(a[k][n][j]==2) S[id]+=(string)"S";
}
}
int main(){
#ifdef fre
freopen("my.in","r",stdin);
freopen("my.out","w",stdout);
#endif
read(t);PreWork();
while(t--){
Init();int n=-1;while(all){n++;all>>=1;}
for(int j=1;j<=(1<<n);j++){
for(int k=0;k<=2;k++){
cnt[k][a[k][n][j]]++;
}
}
bool op=0;
for(int k=0;k<=2;k++){
if(r==cnt[k][1]&&p==cnt[k][0]&&s==cnt[k][2]){op=1;v.push_back(k);}
}
if(!op){printf("-1
");continue;}
for(int j=0;j<v.size();j++){
Solve(v[j],n,j);
}
string ans=S[0];
for(int j=0;j<v.size();j++) ans=min(ans,S[j]);
cout<<ans<<'
';
}
return 0;
}
永远不要相信自己的贪心策略，最好还是打表验证一下。
T2
考场上握手先想到的是 DP，但空间时间开销过大。容易发现我们可以构造图来帮助我们做题。其中每一个节点都是一个余数，我们通过往后增加可行的数，在节点之间连边。如果节点 (0) 与我们的起始节点有同路，说明有解。至于找字典序最小的解，我们只需要让 bfs 遍历的顺序优先选择字典序小的即可，这样先遍历到的就是字典序最小的。
注意因为余数可能不超过 (9)，所以在从总结点向初始结点连边的时候注意需要取模。
代码：
#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 1000100
#define M number
using namespace std;
// #define fre
const int INF=0x3f3f3f3f;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
struct edge{
int to,next,w;
inline void Intt(int to_,int ne_,int w_){
to=to_;next=ne_;w=w_;
}
};
edge li[N*9];
int head[N],tail;
inline void Add(int from,int to,int w){
li[++tail].Intt(to,head[from],w);
head[from]=tail;
}
int a,k,pre[N],epre[N],ans[N<<1],anstail;
bool wei[N],vis[N];
vector<int> v;
queue<int> q;
int main(){
#ifdef fre
freopen("my.in","r",stdin);
freopen("my.out","w",stdout);
#endif
read(a);read(k);
for(int i=1;i<=k;i++){
int x;read(x);wei[x]=1;
}
for(int i=0;i<=9;i++) if(!wei[i]) v.push_back(i);
for(int i=1;i<=a-1;i++){
for(int j=v.size()-1;j>=0;j--){
int now=(i*10+v[j])%a;
Add(i,now,v[j]);
}
}
for(int j=v.size()-1;j>=0;j--) if(v[j]!=0) Add(a,v[j]%a,v[j]);
q.push(a);
vis[a]=1;
while(q.size()){
int top=q.front();q.pop();
for(int x=head[top];x;x=li[x].next){
int to=li[x].to,w=li[x].w;
if(vis[to]) continue;
vis[to]=1;pre[to]=top;epre[to]=w;
q.push(to);
}
}
if(!vis[0]){printf("-1
");return 0;}
int now=0;
while(now!=a){
ans[++anstail]=epre[now];
now=pre[now];
}
for(int i=anstail;i>=1;i--) printf("%d",ans[i]);
return 0;
}
T3
其实有一个结论是最后的答案一定可以被分为若干连通块，其中每一个连通块一定都是一个二部图，即每一个节点向其所有相对的节点连边。我们首先考虑证明这个东西。
令 (n) 表示左部点右部点节点个数，当 (n) 为 (1,2) 的时候，很明显结论成立，现在我们假设 (n-1) 时结论成立，考虑 (n)。假设极端情况，目前第 (n) 个左部点我们设为 (l_n)，第 (n) 个右部点我们设为 (r_n)。因为其余 (n-1) 个左部点和右部点形成了一个二部图。所以点与点之间等价。我们不妨设 (l_n) 向 (r_1,r_2,...r_{n-2},) 都有连边，设 (r_n) 与 (l_1,l_2,...l_{n-2}) 都有连边。
-
第一种情况是 (l_n) 与 (r_n) 之间有边，而 (l_n,r_{n-1}) 以及 (l_{n-1},r_n) 之间没有边。
这个时候我们选 ((l_1,r_2),(l_2,r_3),...,(l_{n-2},r_{n-1}),(l_n,r_1))，这个时候你发现 (r_n) 匹配不上了。
-
第二种情况是 (l_n,r_{n-1})，(r_n,l_{n-1}) 之间有边，而 (l_n,r_n) 之间没边。
这个时候我们选 ((l_1,r_1),(l_2,r_2),...(l_{n-1},r_{n-1})) 就可以使 (l_n,r_n) 匹配不上。
剩下的所有情况都是上面这两种情况的子图，易知边越少越不可能匹配。
其实实战中画一下 (n=2,n=3)，知道可以用归纳法，这个结论就算证明完了。
或者压根不证明，自信相信自己的结论，卡不掉就是对的。
然后我们接下来的工作就是划分连通块，因为 (n) 的个数，所有原图上的连通块个数不会很多，我们把只有一个点的连通块拿出来，剩下的我们直接大力搜索合并连通块，在加上一些减枝，跑的不知道比谢老板的状压快多少。
代码：
#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 60
#define M number
using namespace std;
// #define fre
const int INF=0x3f3f3f3f;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
template<typename T> inline T Min(T a,T b){return a<b?a:b;}
template<typename T> inline T Max(T a,T b){return a<b?b:a;}
int sizel[N],sizer[N];
struct DSU{
int fa[N];
inline void Init(int n){for(int i=1;i<=n;i++) fa[i]=i;}
inline int Find(int x){return x==fa[x]?x:fa[x]=Find(fa[x]);}
inline void Merge(int a,int b){
int faa=Find(a),fab=Find(b);fa[faa]=fab;
if(faa==fab) return;
sizel[fab]+=sizel[faa];sizer[fab]+=sizer[faa];
}
}dsu;
int t,n,l,r,ans,edgecnt,sum,T;
char s[N];
bool vis[N];
typedef pair<int,int> P;
vector<P> v;
inline void Clear(){
v.clear();for(int i=0;i<=(n<<1);i++) vis[i]=0;
for(int i=1;i<=(n<<1);i++) sizel[i]=sizer[i]=0;
edgecnt=0;sum=0;l=r=0;
// l=r=0;ans=0;edgecnt=0;sum=0;memset(vis,0,sizeof(vis));
// n=0;v.clear();memset(sizel,0,sizeof(sizel));memset(sizer,0,sizeof(sizer));
// memset(dsu.fa,0,sizeof(dsu.fa));
}
bool op=0;
inline void Init(){
read(n);dsu.Init(n<<1);
for(int i=1;i<=(n<<1);i++){sizel[i]=(i<=n);sizer[i]=(i>n);}
for(int i=1;i<=n;i++){
scanf("%s",s);int len=strlen(s);
for(int j=0;j<=len-1;j++){
if(s[j]=='1'){dsu.Merge(i,j+1+n);edgecnt++;}
}
// if(op&&!t&&T==5&&n==8) cout<<s<<endl;
}
for(int i=1;i<=(n<<1);i++){
if(dsu.fa[i]!=i) continue;
if(sizel[i]==sizer[i]){sum+=sizel[i]*sizel[i];continue;}
if(sizer[i]==0) l++;
if(sizel[i]==0) r++;
if(sizel[i]&&sizer[i]) v.push_back(make_pair(sizel[i],sizer[i]));
}
ans=n*n;
}
inline void Solve(int k,int l,int r,int all,int delta,int last){
// if(k==v.size()+1){ans=Min(ans,sum+l);return;}
if(last<0){
if(k==v.size()+1){ans=Min(ans,sum+l);return;}
}
if(sum+Max(l,r)>=ans) return;
if(last>=0){
sum=sum+(all+Max(delta,0))*(all+Max(delta,0));
if(delta>=0&&delta<=l) Solve(k,l-delta,r,0,0,-1);
else if(delta<0&&delta+r>=0) Solve(k,l,r+delta,0,0,-1);
sum=sum-(all+Max(delta,0))*(all+Max(delta,0));
}
for(int i=last+1;i<=v.size()-1;i++){
if(vis[i]) continue;
vis[i]=1;
Solve(k+1,l,r,all+v[i].first,delta-v[i].first+v[i].second,i);
vis[i]=0;
}
}
int main(){
#ifdef fre
freopen("my.in","r",stdin);
freopen("my.out","w",stdout);
#endif
read(t);T=t;
while(t--){
Init();
Solve(1,l,r,0,0,-1);
printf("%d
",ans-edgecnt);
if(ans-edgecnt==10) op=1;
else op=0;
Clear();
}
}
T4
首先我们考虑如果只有一个这样双层的图，方案数很好计算，设 (g_{i,j}) 表示第一层剩下 (i) 个，第二层剩下 (j) 个的方案数是多少，然后转移方程就是 (g_{i,j}=g_{i-1,j}+g_{i,j-1})，当然 (i>j) 的状态是没有意义的，注意要弄成 (0)。
接下来我们回到原图上，时间复杂度要求 (n^2)，我们仍然考虑 dp，令 (f_{i,j}) 表示第一层选了 (i) 个，第二层选了 (j) 个的方案数。
如果当前 (i=j)，那么因为要保证状态的合法性，我们只能选上面的，在选了上面的之前，因为 (j) 控制着一组图的第一层，我们需要枚举这一组图的第一层选了多少个，然后我们选一个上面的，再然后这一组图就会完全独立，我们只需要考虑把他们的拓扑序，即这个长度为 (2n) 的序列放在哪里，这是一个组合数，然后我们在乘上这个序列拓扑序方案数。
否则，如果我们拿上层的一个，我们直接从 (f_{i,j}) 转移到 (f_{i+1,j}) 即可，如果我们拿下层的一个，如果 (j+1=i) ，那么我们依然还是直接拿即可。
如果 (j+1<i)，那么这个时候会有一组完全独立，我们还是直接把他们放入当前的拓扑序中，用方案数乘上一个组合数。
代码：
#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 3010
#define M number
using namespace std;
const int INF=0x3f3f3f3f;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int fac[N*N*2],inv[N*N*2],f[N][N],g[N][N],mod,n;
inline int C(int n,int m){
if(m>n) return 0;
return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
inline void PreWork(int n){
fac[1]=1;inv[1]=1;fac[0]=inv[0]=1;
for(int i=2;i<=n;i++){
fac[i]=1ll*fac[i-1]*i%mod;
inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
}
for(int i=2;i<=n;i++) inv[i]=1ll*inv[i]*inv[i-1]%mod;
}
int main(){
read(n);read(mod);PreWork(n*n*2);
for(int i=0;i<=n;i++) g[0][i]=1;
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++) g[i][j]=(g[i-1][j]+g[i][j-1])%mod;
f[1][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=i;j++){
if(j==i){
if(j==n) break;
for(int k=0;k<=n;k++){
int now=i+1+j+k+(i-1)*2*n;
f[i+1][j]=(f[i+1][j]+1ll*g[n-k][n]*C(2*n*n-now,2*n-k)%mod*f[i][j]%mod)%mod;
}continue;
}
if(i<n) (f[i+1][j]+=f[i][j])%=mod;
if(i==j+1) (f[i][j+1]+=f[i][j])%=mod;
else{
int now=i+j+1+j*2*n;
f[i][j+1]=(f[i][j+1]+1ll*g[n][n]*C(2*n*n-now,2*n)%mod*f[i][j]%mod)%mod;
}
}
printf("%d
",f[n][n]);
return 0;
}