當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

2.11模拟总结

發布時間：2023/12/3 编程问答 36 豆豆

生活随笔收集整理的這篇文章主要介紹了 2.11模拟总结小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

前言

145（175？）pts
100+45+0（30？）
rnk11（8？）
之所以有括號是因為T3莫名其妙的TLE了？
考后我一模一樣的碼再交一遍30分就到手了…
應該不是我的問題吧，今天考試的機子確實有些詭異，一開始評測亂七八糟的qwq。

感覺整體發揮沒有大的失誤。
但是排名就是不太好…
感覺今天題也不算太簡單阿qwq
可能只有我這么認為吧
如果一場考試擺爛的時間太長，似乎幾乎很難拿到太好的排名…
就像這次，最后10：45左右開始就沒啥事干了，一直在檢查代碼…
中間還和lyn學長聊了回天

題目解析

字符變換（character）

由于操作1，只要字母個數相同，就可以任意互相轉化，屬于同一個“等價類”，其方案數也可以用不可重排列求得（__int128 天下第一！）
當 n=30 時，等價類個數是 5500 左右（以后稱等價類個數為 $w$ ）
然后題目給出的操作二的轉化就是在不同的等價類之間轉移，暴力加邊復雜度是 $O (w m)$ 的，可以接受。
然后跑個tarjan縮點，再跑個帶權最長路徑的簡單 dp 即可。

這個題確實沒有太大的難度，思路整體是比較順的。

格子染色（color）

魔法題目。
拿到45分足矣。
本題的正解做法就是觀察sg函數表找規律，離大譜。
尤其 k=1 的sg，規律是：“當n>=52時，存在一個大小為 34 的周期”。
這個甚么神人能看出來啊…
其實你要告訴我是類似的東西也未見得看不出來，但是實在不會想到會是這種鬼畜的規律…
k=2的 sg 性質的推導可以使用類似于數學歸納法的東西（然而打表還是很好用），其實這個規律比那個鬼畜東西強多了，但是由于 k=1 我都沒看出來規律，就沒有打 k=2 的表，大損失。

以線覆圓（circle）

很妙的一個狀壓 dp。
非離散的期望感覺根本沒法做的樣子…
關鍵是：一個方案真正關心的只有其整數部分的絕對大小和小數部分的相對大小關系。
所以可以暴力枚舉小數部分的大小，然后就變成了類似于 $n ? m$ 個點上狀壓。
然鵝由于某些奧秘重重的問題，我就是過不去。

最后寫的n=2點30分被ybt機子吃了？？
賽后再交一遍一樣的碼就拿到了30分…
我諤諤。

代碼

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

調不出來了

總結

今天整體還不錯，沒有掛分。
ybt機子的鍋就不算了吧。

總結

以上是生活随笔為你收集整理的2.11模拟总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。