先创建一个map,使m[队列元素]=队列编号,这样后面好查找元素的组别; 再创建一个队列q[301],q[i]表示队列编号为i的排队情况。q[0]表示小组的排序; 队列输入不用多说,只需要注意一个新小组的人入队要给新小组排上队; 队列输出时查看q[0]队头,看到小组编号后查该小组的队头,再输出,注意小组的人全部出队后要把空小组删掉。
题目717 [SDOI 2007] 小组队列
AAAAAAAAAA
1
评论
2024-12-19 21:29:19
|
|
考场一个小时切不出来T1于是暴力及时止损,看题解才想到的贪心,,
首先我们要知道,对任意数列进行有限次邻项交换后,必定能得到该数列的全排列。这样你就拿到了 $n\leq10$ 的20分。 如果你能想到在 $t_1$ 和 $t_2$ 中的由连续的1组成的连通块内,对应的 $s_1$ 与 $s_2$ 的部分可以任意排列,那你就拿到了 $t_1=t_2$ 的20分。 如果你能想到当 $s_1$ 全是0或1的时候不管 $s_2$ 如何排列答案都不会变,那你就拿到了性质A的20分。
(性质C太难了不讨论了)()()
暴力的60分该拿还是得拿的)
然后是正解 从前往后扫,如果这个位置 $s_1$ 和 $s_2$ 有一个不能能换,那就从对应连通块内挑一个数放上去配对就好了 如果都能换,同上,挑0挑1都一样 如果都不能换,直接算答案
感性地贪一下,如果这个位置不配对,那就是给后面的位置留了一个0或1,但这个数在后面至多也只有1的贡献,还不如拿到就马上配了(
换之前记得先看看这个块剩下的0和1数量还够不够 (其实用并查集维护会方便一点)
#include<bits/stdc++.h> #define ll long long #define lowbit(x) (x&(-x)) #define mem(a,b) memset(a,b,sizeof a) #define rev(x) reverse(x.begin(),x.end()) using namespace std; struct node{ int n0,n1; node operator+(const node&q)const{return (node){n0+q.n0,n1+q.n1};} }siz[100010][2]; int fa[100010][2]; inline int find(int x,int p){ if(x==fa[x][p]) return x; return fa[x][p]=find(fa[x][p],p); } inline void merge(int x,int y,int p){ x=find(x,p),y=find(y,p); if(x!=y) siz[y][p]=siz[y][p]+siz[x][p],fa[x][p]=y; } int main(){ int t;cin>>t; while(t--){ int n;cin>>n; string s1,s2,t1,t2;cin>>s1>>s2>>t1>>t2; for(int i=0;i<n;i++) fa[i][0]=fa[i][1]=i; for(int i=0;i<n;i++){ siz[i][0].n0=s1[i]=='0'; siz[i][0].n1=s1[i]=='1'; siz[i][1].n0=s2[i]=='0'; siz[i][1].n1=s2[i]=='1'; } for(int i=1;i<n;i++){ if(t1[i]=='1'&&t1[i-1]=='1') merge(i-1,i,0); if(t2[i]=='1'&&t2[i-1]=='1') merge(i-1,i,1); } int ans=0; for(int i=0;i<n;i++){ int p1=find(i,0); int p2=find(i,1); if(siz[p1][0].n0>0&&siz[p2][1].n0>0) siz[p1][0].n0--,siz[p2][1].n0--,ans++; else if(siz[p1][0].n1>0&&siz[p2][1].n1>0) siz[p1][0].n1--,siz[p2][1].n1--,ans++; } cout<<ans<<endl; } return 0; }
题目4089 [NOIP 2024]编辑字符串
评论
2024-12-07 19:38:07
|
|
Pro4088 仪式感 题解挺不错的题,原题是 CF 的某个题,但我找不到题号了,所以写个比较易懂的题解方便补,可能废话很多。 首先要有一点初步的观察,可以发现 $\max$ 的求解是很方便的,我们只需要找出所有 $k$ 的倍数,这样一定能让 $\gcd$ 尽可能为 $k$,并且使取的数的个数最多。 然后是最小值。这仍然需要一些观察和经验。我们想要每个取的数都不是 "无用" 的,也就是说,它必须能帮我们 "赶出去" 某些没有用的素因子。 下面是一些经验。假设一开始随便选了一个数 $x(k|x)$,再选一个数 $y(k|y)$,那么必然有 $\gcd(x, y)<x$,否则 $y$ 不如不选。那么有 $\frac{x}{\gcd(x, y)}\ge 2$,因为最小的素因子是 2。 于是我们知道,选数的最小个数其实是 $\mathcal O(\log \max(S_i))$ 级别的,在这道题里面也就 18 个左右。 面对最优化问题关于答案范围的极强约束,一般地,直接枚举答案,转化为 $\forall s\in [1, 18]$,对于 $1\sim n$ 的每个 $k$ 判断是否 "存在" 一种取出 $s$ 个数使得 $\gcd$ 为 $k$ 的方案。 然后是这道题非常巧妙的一个点,一般我们很少遇到判定比计数还困难的题目,这道题就是一个例子。 那怎么办?直接换成计数来做。意识到这一点需要有莫比乌斯反演的功底,这样才能在面对着一个和计数没有关系的题目时,通过诸如 $\gcd = k$ 这样的条件感受出做法。这也给我们启示,有时我们需要用这样的数学直观刺激直觉。 于是我们先枚举 $s$,计算 $F(k,s)$ 表示选 $s$ 个数使得 $\gcd$ 是 $k$ 的倍数,这是简单的,假设原序列有 $p$ 个数是 $k$ 的倍数,那么 $F(k,s)=\mathrm C_{p}^{s}$。$p$ 的计算可以使用狄利克雷后缀和解决,实质上就是高维前缀和的一种拓展。 接下来的操作很平凡,使用莫比乌斯反演,得 $G(k,s)$,即原本要求的方案数,为 $\sum\limits_{k|x}F(x,s)\times \mu(x/k)$。 时间复杂度 $\mathcal O(m\ln m\log m)$。题解好像写的有点魔怔,可能是文化课学多了导致思维也比较呆。
题目4088 仪式感
AAAAAAAAAA
2
评论
2024-11-30 18:12:49
|
|
#include<bits/stdc++.h> using namespace std; int f(int n,int k) { int s=1; for(int i=1;i<=k;i++) s*=10; <........................................................................ 该题解待审........................................................................(剩余 1025 个中英字符)
题目2869 [NOIP 2017PJ]图书管理员
2024-11-24 11:32:19
|
|
NOIp2017 时间复杂度 题解分析模拟,模拟,还是模拟。 给定了 $n$ 行 A++ 代码和一个小明算的时间复杂度,判断此复杂度是否正确($Yes$ 和 $No$)。 若代码存在语法问题($F$ 与 $E$ 未匹配或变量名重复定义),则输出 $ERR$。 思路循环可以嵌套,也可以并列,考虑用栈来模拟每一组循环。 使用两个栈,一个使用结构体维护循环信息 $st$,一个维护当前的时间复杂度信息 $opts$。 为了方便,开始之前先将 $opts$ 内压入一个 0。 (本题解时间复杂度表示中,$w$ 表示复杂度为 $O(n^w)$。)
接下来是模拟流程。 维护一个整数数组 $u$,$u_c$ 表示字符 $c$ 在此时被使用的次数。 如果读取到 $F$: - 将循环的参数 $i$、$x$ 和 $y$ 压入 $st$;为方便,将 $n$ 看做 101。 - 如果此前参数 $i$ 已经被使用,则将 $isERR$ 设为 1; - 将 $u_i$ 的值增加 1; - 将 0 压入 $opts$。
如果读取到 `E`: - 若此时栈空,即没有循环需要退出,$isERR$ 设为1; - 否则弹出当前 $st$ 顶的循环,使用 $opts$ 栈顶更新 $opts$ 次顶的时间复杂度。弹出栈顶。将 $u_i$ 的值减少 1。
当 $l$ 行代码运行完毕,若 $st$ 栈内仍有元素,则将 $isERR$ 设为 1。 最后,判定算得结果是否与小明的答案相同即可。 更新时间复杂度本题解将着重讲解一下时间复杂度的更新。 对于一层循环 ${i,x,y}$,其复杂度与内部的所有嵌套的子循环有关,且为所有嵌套的子循环中时间复杂度的最大值,再加上该循环自身的复杂度。 首先,若此循环中 $x>y$,即无法进入,则此循环及往下的复杂度一定为 $O(1)$,表示为 0; 若 $y=101$ 且 $x\neq 101$,则此循环的复杂度为 $O(n)$,表示为 1。 特别地,$x$ 与 $y$ 都为 101 时,此循环的复杂度仍记为 $O(1)$。 CODE
#include<bits/stdc++.h> #define ll long long #define rev(x) reverse(x.begin(),x.end()) #define lb(x) (x&(-x)) using namespace std; struct node{ char varName; int from,to; node(){ varName=' '; from=to=0; } bool ableToRun(){ return from<=to; } }; int varNameIsUsed[26]; stack<node> st; stack<int> opts; int main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); // freopen("2017complexity.in","r",stdin); // freopen("2017complexity.out","w",stdout); int t;cin>>t; while(t--){ while(!st.empty()) st.pop(); while(!opts.empty()) opts.pop(); opts.push(0); memset(varNameIsUsed,0,sizeof varNameIsUsed); bool isERR=false; int ls;cin>>ls; string ops;cin>>ops; for(int lne=1;lne<=ls;lne++){ char p;cin>>p; if(p=='F'){ node wp; cin>>wp.varName; string fm,tm;cin>>fm>>tm; if(fm=="n") wp.from=101; else{ int nw=0; for(int i=0;i<fm.length();i++) nw=nw*10+fm[i]-'0'; wp.from=nw; } if(tm=="n") wp.to=101; else{ int nw=0; for(int i=0;i<tm.length();i++) nw=nw*10+tm[i]-'0'; wp.to=nw; } if(varNameIsUsed[wp.varName-'a']) isERR=true; varNameIsUsed[wp.varName-'a']++; st.push(wp); opts.push(0); }else{ if(!st.empty()){ node tp=st.top(); st.pop(); varNameIsUsed[tp.varName-'a']--; int nwOpt=(opts.top()+(tp.to==101&&tp.from!=101?1:0))*tp.ableToRun(); opts.pop(); int kkk=opts.top(); opts.pop(); kkk=max(kkk,nwOpt); opts.push(kkk); }else{ isERR=true; } } } if(!st.empty()) isERR=true; int opsINT=0; if(ops=="O(1)") opsINT=0; else{ for(int i=4;i<ops.length()-1;i++) opsINT=opsINT*10+ops[i]-'0'; } if(isERR) cout<<"ERR"<<endl; else if(opsINT==opts.top()) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }
题目2865 [NOIP 2017]时间复杂度
1
评论
2024-11-09 02:58:47
|
|
×
提示!该题解未通过审核,建议分享者本着启发他人,照亮自己的初衷以图文并茂形式完善之,请勿粘贴代码。#include<bits/stdc++.h> using namespace std; int main() { freopen("poker.in","r",stdin);
freo 该题解等待再次审核........................................................................(剩余 821 个中英字符)
题目4049 [CSP 2024 J]扑克牌
2024-11-04 18:15:34
|