2.11 simulation summary

Preface

145（175？）pts
100+45+0（30？）
rnk11（8？）
There are brackets because T3 Inexplicably TLE 了 ？
After the exam, I handed in the same code again 30 I'll get the points …
It shouldn't be my problem , Today's exam machine is really a little strange , At first, the evaluation was messy qwq.

I feel there is no big mistake in the overall play .
But the ranking is not very good …
I don't think today's question is too simple qwq
Maybe only I think so
If an exam fails for too long , It seems almost difficult to get a good ranking …
Like this time , Last 10：45 There's nothing to do from about the beginning , Always checking the code …
And in the middle lyn The senior chatted back

title

Character transformation （character）

Because of the operation 1, As long as the number of letters is the same , You can transform each other at will , Belong to the same “ Equivalence class ”, The number of schemes can also be obtained by non rearrangement （__int128 The first day ！）
When n=30 when , The number of equivalence classes is 5500 about （ Later, the number of equivalent classes is called $w$）
Then the transformation of operation two given in the topic is to transfer between different equivalence classes , Violence plus complexity is $O(wm)$ Of , Acceptable .
Then run tarjan Shrinkage point , Run another simple path with the longest weight dp that will do .

This problem is really not too difficult , The overall thinking is relatively smooth .

Lattice dyeing （color）

Magic topic .
Get 45 Enough points .
The way to solve this problem is to observe sg Find rules in function table , Large spectrum .
especially k=1 Of sg, The rule is ：“ When n>=52 when , There is a size of 34 The cycle of ”.
What God man can see …
In fact, if you want to tell me something similar, I can't see it , But I really don't think it will be the law of this kind of ghost animal …
k=2 Of sg The derivation of properties can use something similar to mathematical induction （ However, it is still very easy to type a watch ）, In fact, this rule is much stronger than that ghost thing , But because of k=1 I don't even see the regularity , I didn't fight k=2 Table of , Big loss .

Cover a circle with lines （circle）

A wonderful shape dp.
Non discrete expectations feel like they can't be done at all …
The key is ： What a scheme really cares about is the absolute size of its integer part and the decimal part Relative size relationship .
So you can enumerate the size of the decimal part violently , Then it becomes something like $n\ast m$ Point on point pressure .
However, due to some mysterious problems , I just can't get through .

Last written n=2 spot 30 Divide the quilt ybt The machine ate ？？
Hand in the same code again after the game and you'll get it 30 branch …
I don't know .

Code

T1

#include<bits/stdc++.h>
using namespace std;
#define ll __int128
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
inline ll read(){
    
  ll x(0),f(1);char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;c=getchar();}
  while(isdigit(c)){
    x=(x<<1)+(x<<3)+c-'0';c=getchar();}
  return x*f;
}
void write(ll x){
    
  if(x>9) write(x/10);
  putchar('0'+x%10);
}
const int N=5500;

int n,m;

int num[N][5],tot;
ll jc[35],val[N<<1];

int id[31][31][31][31];
int x[5];
void print(int x){
    
  printf("(%d %d %d %d) ",num[x][1],num[x][2],num[x][3],num[x][4]);
}
void dfs(int k,int lft){
    
  if(k==4){
    
    x[k]=lft;
    ++tot;
    for(int i=1;i<=4;i++) num[tot][i]=x[i];
    val[tot]=jc[n]/jc[x[1]]/jc[x[2]]/jc[x[3]]/jc[x[4]];
    id[x[1]][x[2]][x[3]][x[4]]=tot;
    //printf("%d: ",tot);print(tot);puts("");
    return;
  }
  for(int i=0;i<=lft;i++){
    
    x[k]=i;dfs(k+1,lft-i);
  }
  return;
}
struct node{
    
  int to,nxt;
}p[N*N];
int fi[N<<1],cnt;
inline void addline(int x,int y){
    
  p[++cnt]=(node){
    y,fi[x]};fi[x]=cnt;
}
int s[5],t[5];
int now[5];
char s1[N],s2[N];
int dfn[N<<1],low[N<<1],zhan[N<<1],col[N<<1],top,tim;
void tarjan(int x){
    
  dfn[x]=low[x]=++tim;
  zhan[++top]=x;
  for(int i=fi[x];~i;i=p[i].nxt){
    
    int to=p[i].to;
    if(!dfn[to]){
    
      tarjan(to);
      low[x]=min(low[x],low[to]);
    }
    else if(!col[to]) low[x]=min(low[x],dfn[to]);
  }
  if(low[x]==dfn[x]){
    
    col[x]=++tot;
    val[tot]=val[x];
    while(zhan[top]!=x){
    
      int now=zhan[top--];
      col[now]=tot;
      val[tot]+=val[now];
    }
    top--;
  }
}
ll dp[N<<1];
ll find(int x){
    
  if(dp[x]) return dp[x];
  dp[x]=val[x];
  for(int i=fi[x];~i;i=p[i].nxt){
    
    int to=p[i].to;
    dp[x]=max(dp[x],find(to)+val[x]);
  }
  return dp[x];
}

signed main(){
    
  freopen("character.in","r",stdin);
  freopen("character.out","w",stdout);
  //printf("%d\n",sizeof(p)/1024/1024);
  //printf("%d\n",sizeof(e)/1024/1024);
  //printf("%d\n",sizeof(id)/1024/1024);
  //printf("%d\n",sizeof(val)/1024/1024);
  
  memset(fi,-1,sizeof(fi));cnt=-1;

  n=read();m=read();ok;
  jc[0]=1;
  for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i;
  dfs(1,n);
  //printf("tot=%d\n",tot);
  for(int tim=1;tim<=m;tim++){
    
    memset(s,0,sizeof(s));
    memset(t,0,sizeof(t));
    scanf(" %s %s",s1+1,s2+1);
    int len=strlen(s1+1);
    if(len>n) continue;
    for(int i=1;i<=len;i++) s[s1[i]-'A'+1]++;
    for(int i=1;i<=len;i++) t[s2[i]-'A'+1]++;
    //printf("\ntim=%d\n",tim);
    //for(int i=1;i<=4;i++) printf("%d ",s[i]);puts("");
    //for(int i=1;i<=4;i++) printf("%d ",t[i]);puts("");
    for(int i=1;i<=tot;i++){
    
      int flag(0);
      for(int j=1;j<=4;j++){
    
	now[j]=num[i][j]-s[j];
	if(now[j]<0) flag=1;
      }
      if(flag) continue;
      for(int j=1;j<=4;j++) now[j]+=t[j];
      int to=id[now[1]][now[2]][now[3]][now[4]];
      addline(i,to);
      //printf("%d->%d\n",i,to);
    }
  }
  n=tot;
  for(int i=1;i<=n;i++){
    
    if(!dfn[i]) tarjan(i);
  }
  for(int i=1;i<=n;i++){
    
    for(int j=fi[i];~j;j=p[j].nxt){
    
      int to=p[j].to;
      if(col[i]==col[to]) continue;
      addline(col[i],col[to]);
    }
  }
  ll ans(0);
  for(int i=n+1;i<=tot;i++) ans=max(ans,find(i));
  write(ans);
  return 0;
}
/* */

T2

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
inline ll read(){
    
  ll x(0),f(1);char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;c=getchar();}
  while(isdigit(c)){
    x=(x<<1)+(x<<3)+c-'0';c=getchar();}
  return x*f;
}
const int N=1e5+100;

int n,m;
int a[N];

struct AA{
    
  int sg[N];
  int bac[N],clo;
  int find(int x){
    
  	if(x>54){
    
  		x-=54;
  		x%=34;
  		x+=54;
	}
    if(x<=2) return 0;
    if(sg[x]!=-1) return sg[x];
    for(int i=2;i<=x-1;i++){
    
      find(i-1);find(x-i);
    }
    ++clo;
    for(int i=2;i<=x-1;i++){
    
      bac[find(i-1)^find(x-i)]=clo;
    }
    sg[x]=0;
    while(bac[sg[x]]==clo) ++sg[x];
    return sg[x];
  }

  void work(){
    
    memset(sg,-1,sizeof(sg));
  	//for(int i=1;i<=1000;i++) printf("%d\n",find(i));
  	//exit(0);
    int now=1,ans(0);
    for(int i=1;i<=n;i++){
    
      if(a[i]){
    
	ans^=find(now);now=0;
      }
      else ++now;
    }
    ++now;
    ans^=find(now);
    if(ans) printf("YES\n");
    else printf("NO\n");
  }
}A;

struct BB{
    
  int sg[N][3][3];
  int bac[N],clo;
  int find(int x,int l,int r){
    
  	if(!l&&!r) return x&1;
  	else if(!l||!r) return x;
  	else return l==r;
    if(x==0) return 0;
    if(sg[x][l][r]!=-1) return sg[x][l][r];
    for(int i=1;i<=x;i++){
    
      for(int j=1;j<=2;j++){
    
	if(i==1&&j==l) continue;
	if(i==x&&j==r) continue;
	find(i-1,l,j);find(x-i,j,r);
      }
    }
    ++clo;
    for(int i=1;i<=x;i++){
    
      for(int j=1;j<=2;j++){
    
	if(i==1&&j==l) continue;
	if(i==x&&j==r) continue;
	bac[find(i-1,l,j)^find(x-i,j,r)]=clo;
      }
    }
    sg[x][l][r]=0;
    while(bac[sg[x][l][r]]==clo) ++sg[x][l][r];
    //printf("x=%d (%d %d) sg=%d\n",x,l,r,sg[x][l][r]);
    return sg[x][l][r];
  }
  void work(){
    
    memset(sg,-1,sizeof(sg));
    int now=0,lst=0,ans=0;
    for(int i=1;i<=n+1;i++){
    
      if(a[i]||i>n){
    
	ans^=find(now,lst,a[i]);
	now=0;lst=a[i];
      }
      else ++now;
      //printf("i=%d now=%d lst=%d ans=%d\n",i,now,lst,ans);
    }
    ans^=find(now,lst,0);
    if(ans) puts("YES");
    else puts("NO");
  }
}B;

struct CC{
    
  void work(){
    
    int num(0);
    for(int i=1;i<=n;i++) num+=(a[i]==0);
    if(num&1) puts("YES");
    else puts("NO");
  }
}C;

signed main(){
    
  freopen("color.in","r",stdin);
  freopen("color.out","w",stdout);
  n=read();m=read();
  for(int i=1;i<=n;i++) a[i]=read();
  if(m==1) A.work();
  else if(m==2) B.work();
  else C.work();
  return 0;
}
/* */

T3

It can't be adjusted

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
inline ll read(){
    
  	ll x(0),f(1);char c=getchar();
	while(!isdigit(c)){
    if(c=='-')f=-1;c=getchar();}
  	while(isdigit(c)){
    x=(x<<1)+(x<<3)+c-'0';c=getchar();}
  	return x*f;
}
const int N=1e5+100;
const int mod=998244353;

int n,m;
ll f[350][150],mi[8],b;
int a[8],vis[8],pl[8],id[8];
double ans;
void calc(){
    
	for(int i=1;i<=n;i++) id[pl[i]]=i;
	memset(f,0,sizeof(f));
	f[a[1]*n+1][1]=1;
	for(int i=1;i<=n*m;i++){
    
		int k=(i-1)%n+1;
		for(int s=0;s<mi[n];s++){
    
			if(s&mi[k-1]) continue;
			for(int p=i;p<=n*m;p++){
    
				f[min(n*m+1,max(p,i+a[k]*n))][s|mi[k-1]]+=f[p][s];
			}
		}
	}
	ans+=1.0*f[n*m+1][mi[n]-1];
}
int clo;
void dfs(int k){
    
	if(k>n){
    
		calc();
		++clo;
		return;
	}
	for(int i=2;i<=n;i++){
    
		if(vis[i]) continue;
		pl[k]=i;
		vis[i]=1;
		dfs(k+1);
		vis[i]=0;
	}
	return;
}

signed main(){
    
	freopen("circle.in","r",stdin);
	freopen("circle.out","w",stdout);
	n=read();m=read();
	b=1;
	for(int i=1;i<n;i++) b*=m*i;
	for(int i=1;i<=n;i++) a[i]=read();
	sort(a+1,a+1+n);
	swap(a[1],a[n]);
	mi[0]=1;
	for(int i=1;i<=n;i++) mi[i]=mi[i-1]<<1;
	vis[1]=1;pl[1]=1;
	dfs(2);
	//for(int i=1;i<n;i++) ans/=i;
	ans/=b;
	//ans*=2;
	printf("%.12lf\n",ans);
	//printf("b=%lld clo=%d\n",b,clo);
	return 0;
}
/* 4 6 1 2 3 4 */

summary

Today's overall good , No marks .
ybt Forget the pot of the machine .