当前位置:网站首页>2.11 simulation summary
2.11 simulation summary
2022-07-06 02:39:00 【wind__ whisper】
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 w w)
Then the transformation of operation two given in the topic is to transfer between different equivalence classes , Violence plus complexity is O ( w m ) O(wm) 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 ∗ m n*m n∗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 .
边栏推荐
- 【MySQL 15】Could not increase number of max_ open_ files to more than 10000 (request: 65535)
- Referenceerror: primordials is not defined error resolution
- RobotFramework入门(三)WebUI自动化之百度搜索
- [Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 23
- 729. My schedule I / offer II 106 Bipartite graph
- [untitled] a query SQL execution process in the database
- Patch NTP server at the beginning of DDoS counterattack
- 07 单件(Singleton)模式
- Paper notes: limit multi label learning galaxc (temporarily stored, not finished)
- Six stone management: why should leaders ignore product quality
猜你喜欢
Qt发布exe软件及修改exe应用程序图标
The third level of C language punch in
【MySQL 15】Could not increase number of max_open_files to more than 10000 (request: 65535)
构建库函数的雏形——参照野火的手册
Yyds dry inventory comparison of several database storage engines
剑指 Offer 30. 包含min函数的栈
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 16
Sword finger offer 29 Print matrix clockwise
主数据管理理论与实践
Easy to use js script
随机推荐
Large scale DDoS attacks take Myanmar offline
Microsoft speech synthesis assistant v1.3 text to speech tool, real speech AI generator
RobotFramework入门(一)简要介绍及使用
SSM assembly
ReferenceError: primordials is not defined错误解决
Redis skip table
[Digital IC manual tearing code] Verilog asynchronous reset synchronous release | topic | principle | design | simulation
从顶会论文看2022年推荐系统序列建模的趋势
一个复制也能玩出花来
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 8
inherited constructors
Template_ Quick sort_ Double pointer
剑指 Offer 29. 顺时针打印矩阵
550 permission denied occurs when FTP uploads files, which is not a user permission problem
Follow the mouse's angle and keyboard events
DDoS "fire drill" service urges companies to be prepared
怎么检查GBase 8c数据库中的锁信息?
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 9
Structural theme model (I) STM package workflow
A doctor's 22 years in Huawei